基于最短路径搜索序列编码的多下一跳路由

多下一跳路由较之单下一跳路由有许多天然的优势,通过分析现有多下一跳路由实现机制下的路由算法,提出了基于最短路径搜索序列编码的多下一跳路由.针对SPT(shortest path tree)路由实现机制无法利用等距离邻居节点之间链路的问题,提出了采用Dijkstra算法对网络节点编码赋值的思想.该方法可以对节点进行严格有序的赋值,规范了链路传输方向,有效地避免了环路,提高了网络资源利用率.仿真分析结果表明了该算法的可行性和有效性.     

LFA算法的一种高效实现方法

研究表明,网络中的故障不可避免而且频繁出现.当故障发生时,目前互联网部署的域内路由协议需要经历收敛过程.在此过程中,路由信息可能不一致,从而导致报文丢失,降低了路由可用性.因此,业界提出了利用LFA（loop free alternates）应对网络中发生的单故障情形,从而提高路由可用性.然而,已有的LFA实现方式算法时间复杂度大,需要消耗大量的路由器CPU资源.针对该问题严格证明了当网络中出现单故障时,只需要为特定的节点计算备份下一跳,其余受该故障影响节点的备份下一跳和该特定节点的备份下一跳是相同的.基于上述性质,分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法.实验结果表明：与LFA相比较,该算法的执行时间降低了90%以上,路径拉伸度降低了15%以上,并且与LFA具有同样的故障保护率.     

一种高效的最短路径完全动态更新算法

在通信网络中,节点间最短路径的计算是链路状态路由协议计算路由的基础。通过对现有动态最短路径算法的深入研究,提出了一种处理网络拓扑变化的完全动态最短路径算法DSPT-ID。该算法利用已有SPT的信息,建立一个最短路径树的更新队列,当网络拓扑发生变化时,算法针对边的权值增大和减小,分别进行更新,并将更新节点局限在受拓扑变化影响的节点中,从而达到SPT的增量更新。算法复杂度分析和仿真结果显示,DSPT-ID算法具有更少的节点更新次数和更高的时间效率。     

面向IP快速路径切换的OSPF冗余路径算法

在IP网络中,当某链路或者节点发生故障时,通过路由协议的收敛来绕开故障的链路或节点.对OSPF路由协议,这个时间至少为5秒,期间经过故障节点或链路的流量将会被丢弃,绝大多数的应用可以承受这种程度的延迟.但是,对延迟敏感的应用如VoIP而言,这种量级的延迟是很难为用户所接受的.基于现有的OSPF路由协议的最短路径树(SPT)算法,提出一种支持IP快速重路由的多冗余路径树计算算法.算法计算除最短路径外至少一条不相交无环备份路径,保证在最短路径的链路或节点故障时,通过快速切换到备份路径,以提高IP网络的故障收敛时间.     

一种SRIO网络负载均衡最短路径路由算法

在串行RapidIO传输过程中,路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出(SRIO)网络深度优先搜索分配路径非最优问题,提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓扑信息,以路由跳数定义路由的成本,根据改进Floyd-WarShall算法计算并保存交换节点间的K最短路径。给出预期负载的概念和链路上的路由路径数量来定义链路的负载,采用负载均衡算法从K最短路径中进行选路,建立SRIO网络最短路径约束的负载均衡路由。实验结果表明,与深度遍历路由算法、最小跳数算法相比,该算法在网络传输平均跳数、链路平均负载和链路负载均衡方面有更好的表现,能够有效提升SRIO路由网络的稳定性。     

三维水声传感器网络中多径容错路由协议研究

针对三维水声传感器网络中因节点或链路故障导致的路由性能低下问题,提出一种多径容错路由协议。该协议通过为每个节点设计一种称为后备箱的数据结构,并利用节点的路由表和后备箱构造主后备链路和辅后备链路,以便在节点或链路发生故障的情况下修复路由路径,确保数据的正常传输。仿真结果表明,多径容错路由协议可以减小节点或链路故障对数据传输率和网络吞吐量的影响。     

基于移动agent的能量平衡环形路由算法

由于无线传感器网络(WSNs)自身的特点,将移动agent(MA)用于WSNs可以解决诸多网络问题.提出一种基于MA的能量平衡环形路由算法(EBRRMA),网络首先建立节点到sink节点的最小跳数链路,形成环状跳数梯度,为MA提供路由和工作空间;然后MA在梯度环内以记录迁移路径方式和最小延时策略完成环内巡游,融合节点数据并找到环内能量最多的节点;最后MA通过此节点与sink节点通信链路将融合信息回传并且休眠和等待下一次工作.该算法引入MA技术来降低网络能耗和时延,利用梯度环中能量最多的节点提供MA所需能量以及数据回传路径,以达到网络能量平衡.仿真表明,此路由算法可以有效地平衡网络能量,延长网络寿命.与DD路由相比,该路由算法节能效果显著.     

一种分级的无线传感器网络路由算法设计

提出了一种分级的路由算法,分为路由建立、路由维护和周期性链路评估三个部分。该算法根据节点到汇聚节点的跳数将节点分级,根据级数建立和维护路由。还提出了基于路径最小节点能量信息的路由选择策略,该策略应用在路由建立、路由维护和周期性链路评估三个模块中,理论上延长了传感器网络的寿命。     

基于改进MAODV协议的WMN的组播路由算法

以基于树的组播路由协议MAODV为参考标准,结合WMN的特点及其对路由的影响,提出了WMN网络中基于链路稳定性的路由选择和基于链路可持续时间预测的组播路由改进算法MAODV-PPS,并进行了相应的数学理论分析和算法流程设计。该算法是在选择路径时比较反映各路径局部拓扑稳定性的路径稳定因子,选取相对稳定的路径转发数据;并在路径维护阶段,通过对路径上相邻节点间的能量变化率来预测链路可持续连接时间,当该时间小于链路断链阈值时,主动激活路由修复。仿真表明：该算法不仅稳定性好,路由跳数少,而且具有较好的网络扩展性和负载适应性,与已有的路径稳定性选择和链路预测算法相比,计算简单更符合实际应用。     

基于邻居表的ZigBee网络树路由改进算法

针对ZigBee网络树路由算法路由跳数多、数据传输延时长等问题,提出一种基于邻居表的ZigBee网络树路由改进算法。借助一跳邻居节点地址信息,建立邻居节点选择策略,在节点的一跳邻居节点中,选择到达目的节点树路由跳数最少的邻居节点作为下一跳转发节点。在树路由跳数相同时,选取LQI值大的节点为下一跳转发节点。理论分析结果表明,该算法路由路径优于树路由算法和ITRA算法路由路径;实验结果表明,该算法能很好地减少转发节点个数,提高了网络数据传输的可靠性,达到网络性能提高的目的。     

Fast reroute from single link and single node failures for IP multicast

The rise in multicast implementations has seen with it an increased support for fast failure recovery from link and node failures. Most recovery mechanisms augment additional services to existing protocols causing excessive overhead, and these modifications are predominantly protocol-specific. In this paper, we develop a multicast failure recovery mechanism that constructs protocol independent fast reroute paths to recover from single link and single node failures. We observe that single link failure recovery in multicast networks is similar to recovering unicast traffic, and we use existing unicast recovery mechanisms for multicast traffic. We construct multicast protection trees that provide instantaneous failure recovery from single node failures. For a given node x, the multicast protection tree spans all its neighbors and does not include itself. Thus, when the node fails, the neighbors of the node are connected through the multicast protection tree instead of node x, and forward the traffic over the multicast protection tree for the duration of failure recovery. The multicast protection trees are constructed a priori, without the knowledge of the multicast traffic in the network. Based on simulations on three realistic network topologies, we observe that the multicast protection trees increase the routing table size only by 38% on average and the path length between any source–destination pair by 13% on average.     

Segment Routing体系结构中的域内路由保护方案

学术界和工业界提出利用路由保护方案来提高域内路由协议应对故障的能力，从而加速网络故障恢复，降低由于网络故障引起的网络中断时间。目前互联网普遍采用的路由保护方案包括LFA和U-turn，由于它们的简单和高效，受到了互联网服务提供商的支持，但是这两种方案的单链路故障保护率较低。因此，段路由（Segment Routing，SR）被提出解决上述两种方案存在的问题，已有的针对SR的研究主要集中在其体系结构和应用场景。研究如何在SR中计算segments，将该问题表述为一个整数线性规划问题，提出一种两阶段的启发式算法（Two Phase Heuristic Algorithm，TPHA）求解该问题，将算法在不同网络拓扑中进行了模拟。模拟结果表明，TPHA的单链路故障保护率远远高于LFA和U-turn的单链路故障保护率。     

Joint coverage and link utilization for fast IP local protection

To mitigate the impact of failures, many IP Fast Local Recovery (IPFLR) schemes have been proposed to reroute traffic in the events of failures. However, the existing IPFLR schemes either aimed to find the alternate backup routes to protect failures, or focused on balancing the traffic load routed on the backup routes. Furthermore, in Internet, flows are often managed by shortest path routing, and therefore purely determining the backup routing paths is not sufficient in protecting the error-prone networks. In this paper, we propose a Simulated Annealing based Load balancing and Protection (SALP) scheme to determine link weights for balancing link utilization in the non-failure state and simultaneously construct backup routing tables for protecting any single link failure in IP networks. In our proposed scheme, the two most significant issues, (1) load balancing and (2) coverage, are jointly considered to recover the network operation from single link failures. In the proposed scheme, upon a failure, only the nodes adjacent to a failure are activated to divert affected traffic to backup paths without disturbing regular traffic. Numerical results delineate that the proposed scheme achieves high coverage rate and load balancing at the expense of slightly increasing the entries of backup routing table.     

基于关键网络状态的域内路由可用性研究

业界通常采用路由保护方案来提高域内路由可用性.然而已有的路由保护方案存在下面两个方面的问题:a)没有考虑网络中链路的失效概率,同等对待网络中所有的链路,事实上在互联网中,不同链路的失效概率是不同的,因此应该在路由保护方案中考虑链路的失效概率;b)将保护链路的数量作为设计目标,事实上方面某些链路出错的概率非常低,保护这些链路反而会增加开销,而另一方面某些链路出错的概率非常高,需要重点保护这些链路.因此应该将路由可用性作为路由保护方案的设计目标.针对上述两个问题,提出了一种基于关键网络状态的域内路由保护方案(RPBCNS),该算法首先通过链路失效概率计算出所有的关键网络状态,然后在每种关键网络状态下计算节点对之间相应的路径,保证节点对之间路径的多样性,从而使得尽可能多的节点对满足路由可用性需求.仿真实验将RPBCNS算法与主流算法ECMP、DC、path splicing分别在三个真实网络中进行对比,在网络可用性和节点对可用性满足率上RPBCNS的性能明显优于其他三种算法.仿真结果表明,RP-BCNS不仅具有较高的网络可用性,并且能够使得尽可能多的节点对满足路由可用性目标,更符合实时应用的实际需求.     

基于逐跳转发方式的单故障路由保护方法

业界提出利用LFA(loop free alternates)方案来应对网络中频繁出现的故障,然而LFA并不能保护网络中所有可能出现的单故障情形。针对上述问题,提出了一种基于逐跳转发方式的单故障路由保护算法SFRPA(single failure routing protection algorithm based on hop by hop forwarding)。SFRPA首先提出了三个无环路备份下一跳选取规则,然后制定了优先级队列的操作规则,最后利用优先级队列和无环路备份下一跳选取规则为所有源目的节点对计算出一个最优的备份下一跳。该算法具有支持逐跳转发、支持增量部署、保护网络中所有可能的单故障情形三个特征。实验结果表明,与经典的路由保护方案LFA、DMPA、TBFH和IAC相比较,SFRPA不仅可以应对网络中所有可能的单故障情形,并且具有较小的路径拉伸度。     

基于优化链路权值的域内路由保护方案

目前,互联网部署的域内链路状态路由协议,如开放最短路径优先(Open Shortest Path First,OSPF)和中间系统到中间系统(Intermediate System-to-Intermediate System,IS-IS),采用被动恢复方案应对网络故障。随着网络的发展,大量的实时应用部署在互联网上,OSPF的收敛时间无法满足这些实时应用对收敛时间的需求。因此,学术界和工业界提出采用路由保护方案来应对网路中出现的故障。然而,已有的路由保护方案存在两个方面的问题:1)默认路径和备份路径的交叉度较高,如LFA；2)为了计算两条交叉度低的路径,对默认路径加以限制,即默认路径不采用最短路径,如Color Tree。为了解决上述两个问题,首先将上述问题归结为整数规划模型,接着利用启发式方法计算近似最优解,最后在实际网络和模拟网络中对所提算法进行了大量实验。实验结果表明,所提算法可以降低默认路径和备份路径的交叉度,极大地提高网络的可用性。     

An efficient critical protection scheme for intra-domain routing using link characteristics

In recent years, there are substantial demands to reduce packet loss on the Internet. Among the proposed schemes, finding backup paths in advance is considered to be an effective method to reduce the reaction time. Very commonly, a backup path is chosen to be the most disjoint path from the primary path, or on the network level, a backup path is computed for each link (e.g., IPFRR). The validity of this straightforward choice is based on two things. The first thing is all the links may have the equal likelihood to fail; the second thing is, facing the high protection requirement today, it just looks weird to have links not protected or to share links between the primary and backup paths. Nevertheless, many studies have confirmed that the individual vulnerability of the links on the Internet is far from being equal. In addition, we have observed that full protection schemes (In this paper, full protection schemes means schemes (1) in which backup path is a most disjoint path from the primary path; or (2) which compute backup path for each link.) may introduce high cost (e.g., computation).In this paper, we argue that such approaches may not be cost-efficient and therefore propose a novel critical protection scheme based on link failure characteristics. Firstly, we analyze the link failure characteristics based on real world traces of CERNET2 (China Education and Research NETwork 2). The analysis results clearly show that the failure probabilities of the links in CERNET2 backbone are heavy-tailed, i.e., a small set of links causing most of the failures. Based on this observation, we find out two key parameters which strongly impact link criticality and propose a critical protection scheme for both single link failure situation and multi-link failure situation. We carefully analyze the implementation details and overhead for backup path schemes of the Internet today; the problem is formulated as an optimization problem to guarantee the routing performance and minimize the backup cost. This cost is special as it involves computational overhead. Based on this, we propose a novel Critical Protection Algorithm which is fast itself for both the single link failure and the multi-link failure versions. A comprehensive set of evaluations with randomly generated topologies, real world topologies and the real traces from CERNET2, shows that our scheme gains significant achievement over full protection in both single link failure situation and multi-link failure situation. It costs only about 30–60% of the full protection cost when the network relative availability increment is 90% of the full protection scheme.     

A new approach for designing fault-tolerant WDM networks

In recent years, path protection has emerged as a widely accepted technique for designing survivable WDM networks. This approach is attractive, since it is able to provide bandwidth guarantees in the presence of link failures. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new approach for designing fault-tolerant WDM networks, based on the concept of survivable routing. Survivable routing of a logical topology ensures that the lightpaths are routed in such a way that a single link failure does not disconnect the network. When a topology is generated using our approach, it is guaranteed to have a survivable routing. We further ensure that the logical topology is able to handle the entire traffic demand after any single link failure. We first present an ILP that optimally designs a survivable logical topology, and then propose a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection.