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

如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。由于动态路由协议在应对网络中的故障时，在协议动态收敛的过程中将会有大量的报文被丢弃。因此，目前路由器厂商普遍采用路由保护方法来克服网络故障，在众多的路由保护方法中，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规则的计算开销。

Efficient routing protection method with linear time complexity

How to deal with network faults efficiently and quickly is the basic requirement and main task of designing routing protocol. When dynamic routing protocols deal with network faults, a large number of packets are discarded during dynamic convergence. Therefore, at present, router manufacturers generally use routing protection methods to overcome network failures. Among many route protection methods, the DC(downstream criterion) rules is a generally recognized method. However, the time complexity of the existing DC rules algorithms is generally high, and the complexity increases rapidly with the increase of the average degree of network nodes. In order to deal with the above problems, this paper proposed a linear time complexity university routing protection scheme ERPLR(efficient routing protection method with linear time complexity). The method first proposed the backup next hop calculation rule, and then calculated the backup next hop for all source-destination node pairs based on the existing shortest path tree according to the backup next hop calculation rule. In the process of calculating the backup next hop, accessing each node and its neighbors at most once, so the time complexity of ERPLR is O(V+E) . The experimental results show that, compared with the existing rules for implementing DC rules, ERPLR has similar results in four metrics: failure protection ratio and path stretch. Compared with DC rules, ERPLR reduces the computational overhead by about 74.93% and 78.91% in real topology and generated topology, respectively, this method can greatly reduce the calculation cost of DC rules.