基于超立方体容错路由算法分析*

基于超立方体的优良的拓扑性质,提出了一个应用于超立方体网络的容错路由算法.该容错路由算法是基于局部信息的,因为路由算法在路由过程中,只需要知道其邻节点的信息,而无须知道其他节点的出错情况.对于给定的源节点和目的节点,路由算法均能够找到一条最优容错路径,并且可以预防死锁.模拟实验结果表明,路由算法所构造的路由路径长度接近于两个节点之间的最优路径长度.     

基于拓扑关键点的多路径路由算法

提出了一种结合源路由和中间路由的多路径路由机制以满足可扩展性和路径节点不相交,并且发现了在网络中某些节点会作为拓扑关键点存在,这些节点形成了传输的热点并且是拥塞主要发生的地方,结合多路径路由分析,这些节点同时也会导致多路径路由的分离路径性能低下,这些节点称为拓扑关键点TN.设计了一种基于TN并包含了TN检测和避免的多路径路由算法,实验结果表明了该方法可以优化多路径路由的分离路径性能,提高网络的可靠性.     

一种界标辅助定位的WSN虚拟地理路由

基于地理信息的路由算法由于其高效、计算出的传输路径接近最优和良好的可扩展性等特点,在无线传感器网络中得到广泛的应用.但此类路由算法中,地理信息的获知必须借助GPS接收器或定位算法的辅助,成本和开销比较大.提出一种界标辅助定位的虚拟地理路由算法(Landmark-based Virtual Geographic Routing Algorithm,简称LVGR),无须知道节点自身的真实地理位置,利用局部链路连通及节点间的相对位置信息进行拓扑发现,在拓扑发现的基础上即能成功进行局部坐标路由.仿真实验表明LVGR能产生和实际地理路由相似的路由结果,并且能实现路由的负载均衡,具有低成本、低路由开销和高性能的优点.     

基于能量水平的多Sink节点传感器网络路由算法

单Sink节点传感器网络存在着部分关键路径上节点能量消耗过快、路由选择算法单一以及Sink节点失效等问题.首先提出了多Sink节点传感器网络数据收集的系统框架;给出了拓扑发现和维护策略;然后提出了基于最小能量消耗路由算法.在分析了该算法的不足后提出了基于能量水平的路由算法,按照计算得到的能量水平选择最优的路径进行数据传送.实验证明,基于能量水平的路由算法比基于最小能量消耗路由算法能更有效提高传感器网络的使用寿命.     

基于K-shell位置和两阶邻居的复杂网络节点重要性评估方法

K-shell分解法能快速识别复杂网络中的关键节点,但是无法辨别同壳层内节点重要性的差异,并且低估了处于网络边缘位置的高度值节点的重要性。针对这两个问题,提出一种基于K-shell位置和两阶邻居的节点重要性评估方法。该方法根据K-shell分解过程中节点移除的顺序细化节点的全局位置信息,然后综合考虑节点的局部拓扑结构信息和全局位置信息,利用两步长内邻居节点的K-shell位置信息度量节点的重要性。在八个真实网络上用传染病模型进行仿真实验,结果表明,所提方法与其他五种相关方法相比能更准确有效地评估并区分节点的重要性。     

无线传感器网络中基于数据融合的移动代理曲线动态路由算法研究

和传统的C/S模型相比,移动代理模型在数据融合方面更适合无线传感器网络.在基于移动代理的数据融合算法中,移动代理访问传感节点的顺序以及总数对算法的效率、网络寿命等有着重大影响.为此提出了一种基于数据融合的移动代理曲线动态路由算法设计方案.通过构造特定数据结构的数据报文和数据表,给出了目标节点基本信息收集算法获取目标节点到处理节点的最优路径;将移动代理路由归结为一个优化问题,由静态路由算法求出移动代理迁移的静态最优路由节点序列,进而获得了移动代理基于曲线的动态路由算法.理论分析和模拟实验表明,随着传感器网络规模的增大和传感数据量的增加,和其它算法相比,该算法有更小的网络耗能和延时.     

大规模网络上基于图嵌入的可扩展路由方法

大规模网络上理想的路由方法必须同时具有较小的路由表和较短的路径.传统的最短路径路由算法只考虑优化路径,但是路由表需要维护到所有节点的路由信息,故路由表项数至少随网络规模线性增长,因此呈现较差的扩展性.针对基于图嵌入的可扩展路由进行了研究,提出将网络嵌入到由它的支撑图(spanner)导出的度量空间.利用真实网络普遍存在的小世界和无标度拓扑特征,提出了一种嵌入和路由方法--GEROUTE,它用源于高度节点的树形支撑图来构造嵌入,对节点分配较短的标记,使得节点在支撑图上的距离能够由标记推算出来,在节点标记定义的度量空间中使用贪心路由,而节点的路由表只需要存放邻居的标记.分析和仿真表明该路由方法在像Internet的这类图上能够取得比较理想的路由性能,与其他同类方法相比表现更好.     

针对无标度网络的紧凑路由方法

衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.     

针对无标度网络的紧凑路由方法

衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.     

一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.     

因特网AS级拓扑的健壮性测度与健壮性演化

以自治系统(autonomous system,AS)为基本组成单元的域间路由系统是因特网(Internet)的核心组成部分,研究Internet AS级拓扑的健壮性对于整个Internet的健壮性设计具有重要意义.2003年的北美停电事故与2006年、2010年的台湾地震表明,当今Internet的健壮性仍亟待增强.本文结合基本的拓扑理论与实际的路由策略约束,利用Internet AS级拓扑的层次特性,从"单个AS"和"全局拓扑"两个不同的层面研究AS级拓扑的健壮性测度与健壮性演化:1)提出了对单个AS的健壮性测度的方法;2)对全局AS级拓扑的健壮性测度提出了k容错模型---任意k个AS级的节点/链路故障不影响任何其他两个AS之间的连通性;3)基于健壮性测度方法和k容错模型,提出了健壮性演化的机制与方法.对当今Internet AS级拓扑的统计分析表明:1)25.8%的AS节点还不能承受1个AS级的链路故障,26.4%的AS节点还不能承受1个AS节点故障;2)将现有的AS级拓扑演化为k容错拓扑不仅能保证任意节点对之间可达性的k容错,在故障数超过k的情况下,k容错拓扑的健壮性也显著优于原拓扑.     

互联网AS拓扑的结构与连通性研究

基于BGP协议的域间路由系统是Internet的核心基础设施。研究域间路由系统在自治系统AS级的拓扑结构,深入理解并揭示AS拓扑的结构及连通性方面的特性,对于提高互联网路由系统的安全性、健壮性以及性能都具有重要的指导意义。AS之间的商业关系模型是互联网域间路由系统的基本模型之一,是AS拓扑研究的基础。受商业关系的约束,AS拓扑的结构与连通性呈现出了与普通无向图或有向图所不具备的特性:层次结构特性与AS路径的无谷底约束。本文提出了针对AS拓扑的层次划分算法,对AS拓扑的连通性做了深入研究,分析并验证了顶级AS的全互联结构,并进一步阐述了从宏观上对单个AS的连通性的评估方法。     

一种自治系统分类方法

提出了一种使用BGP路由表对自治系统进行分类的方法。按照自治系统在Internet中所起的作用，将Internet层次模型分为5层。利用多个BGP路由表生成自治系统拓扑图，根据BGP路由表中自治系统路径的结构特点和传输自治系统的拓扑特点，结合随机扰动方法，对自治系统进行层次分类。与同类算法对比表明，该算法简洁有效。     

Two-Type Information Fusion Based IP-to-AS Mapping Table Refining

The Internet topology at the autonomous system (AS) level is of great importance, and traceroute has been known to be a potential tool to obtain a complete AS topology. The original IP-to-AS mapping table maps the IP addresses in traceroute paths to their origin ASes, which may cause false AS links. The existing methods refine the original mapping table based on traceroute-BGP path pairs or alias resolution data. However, the information extracted from either of them is inaccurate and incomplete. In this paper, we present a two-type information fusion based method to refine the original mapping table. We extract four kinds of information from path pair and alias resolution data. Based on these information, we build a candidate AS set for each router. Then we choose the AS that is consistent with the existing information to be the owner AS of each router and map all of the IP addresses on the router to it. We validate the result with the ground truth from PeeringDB and Looking Glass severs. Compared with the existing methods, our method produces a more accurate mapping table. In addition, we discuss the coverage of our method and show that our method is convergent and more robust against the reduction of information or the increase of incorrect information.     

An economic analysis of routing conflict and its resolution

Thousands of competing autonomous systems (ASes) must cooperate with each other to provide global Internet connectivity. Each AS has independent economic objectives and retains autonomy in setting their routing policies independently to maximize its profit. However, such autonomy enables ASes to produce conflicting routing polices and thus raises route oscillations between them (i.e., routing divergence). This paper studies the basic problem of routing divergence by investigating real ISP pricing data. We first demonstrate that routing divergences occur under economic dependency cycles, i.e., provider–customer cycles, of different ASes which are raised by economic conflicts between themselves. We then propose a provable cycle-breaking routing mechanism to detect and solve economic conflicts and route divergence. We show that every cycle-breaking strategy allows ASes to maximize their own profits to converge to a Nash equilibrium with a profit-sharing mechanism derived from the coalition game concept of Shapley value. At the Nash equilibrium point, the cycle-breaking strategies maximize ASes’ profits and encourage ASes so as to ensure divergence-free routing.     

A network accountability based verification mechanism for detecting inter-domain routing path inconsistency

Border Gateway Protocol (BGP) has no mechanism to guarantee the consistency between actual routing path and announced routing path in the inter-domain routing. Due to incentives of gaining more economic benefits, malicious Autonomous Systems (AS) could announce inconsistent path and misroute data packets. In this case, routing policies are meaningless, rational ASes are cheated and stability of Internet is destroyed seriously. Existing methods are devoted to securing announce routing path only or discovering path inconsistency with lots of overhead. Based on network accountability, a routing path verification mechanism is proposed to detect path inconsistency. The mechanism enables ASes in the path to generate routing evidence. Routing evidence is produced by analyzing packets in a time slot and is encrypted with the key of AS. With routing evidence, source AS checks every subpath connecting adjacent ASes until it confirms the existence of path inconsistency. The factors that influence the mechanism and the deployment in the real network are also discussed. The experiment results show that it has a good performance from aspects of effectiveness, overhead and scalability.     

在BGP／MPLS VPNs中用BGP实现域间流量工程

在BGP／MPLS VPNs中，用MPLS实现的流量工程主要被限止在单个管理域内。然而，随着企业规模的不断扩大，VPN跨越越来越多的管理域，急需管理域间流量的有效方法。以BGP属性、BGP策略和AS关系为基础的，一方面通过配置LOCAL-PREF属性值，运用输入策略，控制AS的出界流量；另一方面，保证客户AS不在提供者间或对等体间过渡流量，或允许客户AS向它的部分提供者通告路由，或人为增长AS-PATH，控制AS的入界流量。仿真表明此方法能有效地在BGP／MPLS VPNs中用BGP实现域间流量工程。     

区分自治系统关系的域间路由体系研究

BGP-4是Internet采用的惟一域间路由协议，但它并不能确保路由收敛，复杂的网络结构加剧了路由潜在振荡的危险性．为此，提出了一种自约束的域间选路机制，在不违反传统流量工程原则和自治系统间结算原则的前提下，通过抑制违背自治系统间关系的路由通告和路由选择，达到维护全系统路由稳定的目的；对昕提方案的技术可行性进行论证，给出了新的选路机制原型系统的定义和关键算法的实现．区分自治系统关系的域间路由体系有效回避了路由策略一致性全局检测这一NP-complete问题．     

BGP-XM: BGP eXtended Multipath for transit Autonomous Systems

Multipath interdomain routing has been proposed to enable flexible traffic engineering for transit Autonomos Systems (ASes). Yet, there is a lack of solutions providing maximal path diversity and backwards compatibility at the same time. The BGP-XM (Border Gateway Protocol-eXtended Multipath) extension presented in this paper is a complete and flexible approach to solve many of the limitations of previous BGP multipath solutions. ASes can benefit from multipath capabilities starting with a single upgraded router, and without any coordination with other ASes. BGP-XM defines an algorithm to merge into regular BGP updates information from paths which may even traverse different ASes. This algorithm can be combined with different multipath selection algorithms, such as the K-BESTRO (K-Best Route Optimizer) tunable selection algorithm proposed in this paper. A stability analysis and stable policy guidelines are provided. The performance evaluation of BGP-XM, running over an Internet-like topology, shows that high path diversity can be achieved even for limited deployments of the multipath mechanism. Further results for large-scale deployments reveal that the extension is suitable for large deployment since it shows a low impact in the AS path length and in the routing table size.     

域间路由协同监测中的信息共享机制

路由协同监测通过在自治系统之间共享路由监测信息来形成更为完整的全局监测视图,从而克服域间路由系统自治性的制约,提高单个自治系统的路由监测能力.针对路由协同监测的核心问题——监测信息共享,基于自组织思想设计了信息共享机制CoISM.该机制利用BGP路由策略引起的信息局部性对路由监测信息的传播范围进行裁减和控制,在被动查询的基础上增加了信息"反射"行为,利用路由监测信息之间的相关性实现信息的主动推送,将自治系统的利益建立在主动信息共享这一利他行为的基础上.CoISM能够引导自治系统实现路由监测信息的自组织聚合与按需共享,具有激励性,能够促进自治系统之间的协同.该机制采用分布式体系结构,具有良好的扩展性和较低的通信开销,不需要修改BGP协议,支持可渐进部署,适用于域间路由协同监测、路由故障协同分析、协同入侵检测等多种跨域协同管理应用.