基于增量最短路径优先算法的高效LFA实现方法

针对已有LFA实现方式计算开销大和部署难度高的问题,提出了一种基于增量最短路径优先算法的LFA实现方法（LFA implementation method based on incremental shortest path first algorithm,ERPISPF）。首先将快速实现LFA的问题转换为如何在以计算节点为根的最短路径树上高效地计算其所有邻居节点到网络其余所有节点的最小代价问题;然后提出了计算该代价的定理并且证明了它的正确性,最后从理论上分析了算法的时间复杂度。仿真结果表明,ERPISPF不仅计算开销小,并且与LFC的故障保护率是相同的。     

一种线性时间复杂度的高效路由保护方法

如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。由于动态路由协议在应对网络中的故障时,在协议动态收敛的过程中将会有大量的报文被丢弃。因此,目前路由器厂商普遍采用路由保护方法来克服网络故障,在众多的路由保护方法中,DC（downstream criterion）规则是一种被普遍认可的方法。然而,已有的实现 DC规则算法的时间复杂度普遍较高,并且复杂度随着网络节点平均度的增加而迅速增加。为了应对上述问题,提出一种线性时间复杂度的高效路由保护方案ERPLR（an efficient routing protection method with linear time complexity）,该方法首先提出了备份下一跳计算规则,然后在已有最短路径树的基础上,根据备份下一跳计算规则为所有的源目的节点对计算备份下一跳。在计算备份下一跳的过程中,每个节点和其邻居最多被访问一次,因此ERPLR的时间复杂度为O（V+E）。实验结果表明,与已有的实现DC规则相比较,ERPLR在故障保护率和路径拉伸度两个度量指标结果相似的情况下,在真实网络拓扑和模拟拓扑中,ERPLR分别降低了大约74.93%和78.91%的计算开销,该方法可以极大地降低DC规则的计算开销。     

DC规则的高效实现方法

被动恢复方法应对网络故障的恢复时间较长,无法满足实时应用对网络时延和丢包率的要求。因此,路由器厂商普遍采用DC规则来处理网络中的故障。然而,已有的实现DC规则算法的时间复杂度普遍较高,并且随着网络节点平均度的增加而增加。因此,研究了如何降低实现DC规则的复杂度,提出了一种高效的DC实现方法（efficient DC implementation scheme,EDCS）。首先对DC规则进行了扩展,然后在构造最短路径树的过程中实现扩展DC规则,最后从理论上分析了算法的时间复杂度。实验结果表明,EDCS不仅具有较小的计算开销,并且可以计算出所有符合DC规则的备份下一跳。     

基于软件定义网络的高故障保护率的路由保护方案

软件定义网络(Software Defined Network, SDN)以其强大的可编程性和集中控制的优势得到了学术界的广泛关注。现有的SDN设备在执行报文转发时仍然使用最短路径协议，当最短路径中的结点发生故障时，网络仍然需要重新收敛，在此期间报文可能会被丢弃，进而无法传递至目的结点，给实时性应用的流畅性造成了冲击，影响用户体验。学术界普遍采用路由保护的方案来应对网络故障，现有的路由保护方案存在以下两个方面的问题：(1)故障保护率低；(2)当网络出现故障时，备份路径可能会出现路由环路。为了解决上述两个问题，首先提出了备份下一跳计算规则；然后基于此规则设计了一种软件定义网络下的高故障保护率的路由保护算法(Routing Protection Algorithm with High Failure Protection Ratio, RPAHFPR),该算法融合了路径生成算法(Path Generation Algorithm, PGA)、旁支优先算法(Side Branch First Algorithm, SBF)和环路规避算法(Loop Avoidance Algorithm, L...     

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

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

交通道路网中任意两点之间最短路径的快速算法

寻找交通道路网中任意两点之间最短路径的算法已有许多 ,其中Dijkstra算法是最有效的算法之一 ,其时间复杂性为O(n2 )。本文提出的算法与Dijkstra算法不同 ,其主要思想是依据从始点至终点的直线段方向选择边产生二叉树 ,并采取有效方法降低二叉树的规模及缩短路径长度 ,然后由二叉树节点的标记计算出近似最短路径及其长度。反复执行常数次该算法可以求得最短路径及其长度。     

基于EPA的工业无线的工业无线网络网络网络实时可靠路由算法实时可靠路由算法实时可靠路由算法

针对工业无线网络数据通信的可靠性、确定性和实时性要求,提出一种基于EPA标准的实时可靠路由算法。该算法在短地址分配的基础上,利用周期发送的同步组网报文,结合邻居链表实现多径不相交路由。综合考虑链路质量和剩余转发时间,给出基于最短路径扩散机制的实时路由选择方法,降低链路故障对数据传输的影响,同时通过链路故障处理,以及基于转发记录表与黑名单机制的网络回路检测,保证通信可靠性。性能测试结果表明,该算法将周期数据正确接收率保持在99%左右,平均路径传输延时降低了30%,从而保证网络传输数据的可靠性和实时性。     

基于最低开销模型的传感网络通信优化仿真

当传感网络中某条链路发生变化时,需要重新计算最短路径树,一旦传感网络规模较大,传统的算法采用抑制链路改变的方法提高传感网络通信容量,但这大幅抑制通信节点周期内路径选择灵活性,通信延迟明显.提出一种改进的A-OSPF算法并应用到传感网络通信优化中,该算法在原始的OSPF基础上融人了最低开销节点机制,增强了传感网络中节点构建的概率,考虑了节点移动性,将更加平稳的链路当成节点,按照链路代价原理得到源节点到目标节点的最佳路径,确保数据包可在链路质量最高的路径上进行传递,降低传感网络数据传送的平均端到端延时.仿真结果表明改进算法在传感网络生存周期以及平均端到端延时方法优于原始的OSPF算法,实现了延长传感网络生存周期以及能量均衡的目标.     

基于优先队列的时变网络最短路径算法

提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。     

基于Dijkstra算法的范围规划问题

Dijkstra(迪杰斯特拉)算法是典型的最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。该算法能得出最短路径的最优解,在实际选择路径方案中起重要作用。本文是Dijkstra算法在范围规划问题中的应用。