基于重构SPT的单链路故障路由保护方法

为了减少故障对网络运行带来的影响,提出了一种基于重构SPT的单链路故障路由保护算法SLFRPRSPT。该算法在最短路径树SPT的基础上实现,通过制定一系列定义和规则,对SPT进行重构,搜索节点关系发生改变的节点,为每个节点计算最佳备份下一跳节点,从而达到提高路由可用性的目的。经过实验验证,其在网络拓扑中故障保护率可以达到1,并且具有较低的路径拉伸度,可以有效避免单链路故障带来的影响。该方案支持增量部署和逐跳转发,便于实现。     

一种不需记录后继的扩展SPT动态更新算法

动态SPT算法是在图的拓扑改变时,以原有SPT为基础作局部更新;SPT动态更新需要解决寻找因为该改变而需要修正最短路径的相关节点的问题。对于传统的SPT定义先扩展,使节点记录距离相等的一条或多条最短路径,称之为ESPT。提出了一种不需记录后继的ESPT动态更新算法并加以证明,通过证明还说明在ESPT定义下该算法找到的所有节点都是动态更新所必要且充分的。给出算例,列出操作过程,对不同复杂度的图进行计算实验,将其结果与经典静态算法进行了对比。     

基于路由最短路径树的动态多节点删除算法

提出一种基于路由最短路径树的多节点删除动态算法。算法建立一个最短路径树更新队列,将所有将被删除节点的子孙节点保存到该队列;从原最短路径树中删除需要被删除的节点和其所有子孙节点;从队列中选取与根节点距离最短的节点进行更新,已更新节点不再被插入队列,从而减少节点更新次数。实验结果表明,该算法能有效减少节点的更新冗余。     

适用于无向网络的动态Dijkstra算法优化

网络拓扑发生变化时,利用静态Dijkstra算法重新计算最短路径树(SPT)会造成冗余计算。动态Dijkstra算法解决了这个问题,但目前动态算法一般是基于有向网络模型进行的研究。在已有的动态Dijkstra算法基础上,提出适用于无向网络的动态Dijkstra算法。算法主要解决了在无向网络中如何确定待更新节点的问题,对网络中的一条边权值增大、减小的处理方法进行了详细描述,并对已有的算法的筛选机制进行了优化。为了验证算法的正确性,用仿真实验实现了该算法并与静态算法进行性能比较。实验结果表明,新算法更能提高节点更新的时间效率。     

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

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

路径节点驱动的低代价最短路径树算法

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.     

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

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

基于节点多样性的域内路由保护算法

已有的路由保护方案都没有考虑网络中节点的重要程度,然而在实际网络中不同节点在网络中的重要程度是不相同的。针对该问题,提出一种基于节点多样性的域内路由保护算法（intra-domain routing protection algorithm based on node diversity,RPBND）。计算节点构造以目的为根的最短路径树（shortest path tree,SPT）,从而保证RPBND算法和目前互联网部署的路由算法的兼容性;在该最短路径树的基础上构造特定结构的有向无环图（directed acyclic graph,DAG）,从而最大化路由可用性。实验结果表明,RPBND极大地提高了路由可用性,降低了故障造成的网络中断时间,为ISP部署域内路由保护方案提供了充分的依据。     

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

计算动态环境下最短路径树是一个典型的组合优化问题。Ba11-and-String模型是一种高效的动态更新算法,但仍存在不少冗余计算。针对Ba11-and-String算法中边的处理进行了优化,从而提高了动态更新的效率,同时实现了对节点的删除和增加,以适应最短路径树的拓扑变化。实验结果表明新算法效率更高。     

一种Ad hoc网络中动态自适应的路由更新算法

目前Ad hoc网络中基于簇的路由算法都采用了混合路由策略,其路由信息的更新范围局限在局部网络中（或簇内）.提出了一种改进的路由更新算法-基于分簇机制的动态自适应路由更新算法.该算法使用簇头节点来进行簇内路由信息更新,使用簇头和网关节点来进行簇间路由信息更新,同时根据网络拓扑结构变化的快慢,动态地调整路由信息传播的范围.模拟结果显示该算法在使节点获得了较为准确的路由信息的前提下,有效地减少了路由信息更新所带来的控制开销.     

基于球绳模型的SPT完全动态算法

球绳模型SPT动态算法是已知的动态算法中最优的，但其仅局限于权值更新。因此，借鉴球绳模型的相关思想，提出了一种在图的拓扑发生变化后对SPT进行动态更新的解决方案，并结合球绳模型SPT动态算法，完成了一种基于球绳模型的SPT完全动态算法。该算法结构简洁，具有较强的应用价值。     

无线传感器网络数据融合路由算法的改进

无线传感器网络能量有限,数据融合能通过合并冗余数据减少传输数据量,但其本身的代价不可忽略。针对该问题,研究数据融合代价和数据传输代价对数据融合路由的影响,在基于决策数据融合技术AFST中,对直传数据采用动态最短路径(DSPT)算法,动态识别网络环境和数据特征变化,以最小的代价调整路由。实验与分析结果表明,当网络结构发生变化时,DSPT算法比SPT算法效率更高、更节能。     

AntNet算法在Ad Hoc网络QoS组播路由中的研究

由于网络拓扑结构变化频繁和节点能量有限的原因, Ad Hoc网络中的QoS组播路由算法必须能够尽快地感知网络中路径的能量状态并且自适应地改变组播路由。 AntNet 算法中的蚂蚁代理能够感知网络中各个子路径的能量状态和更新信息素,从而使组播路由能够衡量整个网络的能量变化情况,最后就找到了考虑到路径能量状态的QoS组播路由。仿真实验表明,该算法能够均衡节点能量从而提高网络性能。     

Dynamic SPT update for multiple link state decrements in network routing

Previous approaches to the dynamic updating of Shortest Path Trees (SPTs) have in the main focused on just one link state change. Not much work has been done on the problem of deriving a new SPT from an existing SPT for multiple link state decrements in a network that applies link-state routing protocols such as OSPF and IS-IS. This problem is complex because in the process of updating an SPT there are, firstly, no simple forms of node set to presumable contain all nodes to be updated and, secondly, multiple decrements can be accumulated to make the updating much harder. If we adopt the updating mechanisms engaged in one link state change for the case of multiple link state decrements, the result is node update redundancy, as a node changes several times before it reaches its final state in the new SPT. This paper proposes two dynamic algorithms (MaxR, MinD) for obviating unnecessary node updates by having part nodes updated in a branch on the SPT only after selecting a particular node from a built node list. The algorithm complexity analysis and simulation results show that MaxR and MinD require fewer node updates during dynamic update procedures than do other algorithms for updating SPT of multiple link state decrements.

Topology Dissemination for Reliable One-Hop Distributed Hash Tables

Many distributed hash tables (DHTs) resolve lookups in O(log n) hops, where n is the number of nodes. One-hop DHTs give lower lookup latencies and lower lookup failure rates. However, it is hard to maintain large, wide-area one-hop topologies. We contribute aecast, a new topology dissemination algorithm for one-hop DHTs. It avoids expensive repair mechanisms and critical points of failure in existing one-hop DHTs. When a node discovers by anti-entropy that it has missed a topology update, it initiates "controlled flooding,rdquo sending the update to nodes in the multicast tree that also missed the update. We compare aecast with a widely cited epidemic multicasting algorithm, pbcast, by analysis and simulation. Aecast gives at least fivefold fewer out-of-date nodes on average within one round of a topology update. We support it with a fault-tolerant topology agreement protocol, so that only legitimate topology changes propagate throughout the overlay. Consequently, we argue that one-hop DHTs deserve greater attention for Internet applications in which reasonably reliable nodes carry high lookup loads.     

稳定的最短路径树及其构造算法

构建最短路径树是动态网络研究的重要问题之一。在动态网络中,当边状态发生变化时会引发最短路径树动态的重新构建,反复地计算不仅消耗大量时间,也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法,使得构造的路径树在动态网络上更稳定,即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中,从而能够高效地减少边变化带来的操作。实验结果表明,与传统的动态最短路径树算法相比,该算法可以得到更稳定的最短路径树,并且更新时间减少了57.24%,结点更新次数降低了43.6%。     

多链路权值增大的动态最短路径算法

动态网络最短路径是交通、通信等系统中的重要问题。在处理多链路权值变大时,多链路权值增大的动态最短路径算法可有效地减少单链路权值增大动态最短路径算法的冗余计算。目前,多链路权值增大的动态最短路径算法的研究较少,尚未存在有效的多链路变大的动态最短路径算法。通过对现有动态最短路径算法的深入研究,提出了一种多链路权值增大的动态最短路径算法(DSPT-MLI)。算法复杂度分析和仿真结果显示,DSPT-MLI算法具有更少的节点更新次数和更高的时间效率。