DC规则的高效实现方法  

Efficient implementation method for DC

作　　者：张伟[1] 李卓 耿海军 尹霞[3] Zhang Wei;Li Zhuo;Geng Haijun;Yin Xia(Institute for Network Sciences&Cyberspace,Tsinghua University,Beijing 100048,China;School of Software Engineering,Shanxi University,Taiyuan 030006,China;Dept.of Computer Science&Technology,Tsinghua University,Beijing 100084,China)

机构地区：[1]中国劳动关系学院计算机应用,北京100048 [2]山西大学软件学院,太原030006 [3]清华大学计算机科学与技术,北京100084

出　　处：《计算机应用研究》2020年第10期3112-3115,3130,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61702315);中国劳动关系学院2020年校级科研项目(20XYJS002)。

摘　　要：被动恢复方法应对网络故障的恢复时间较长,无法满足实时应用对网络时延和丢包率的要求。因此,路由器厂商普遍采用DC规则来处理网络中的故障。然而,已有的实现DC规则算法的时间复杂度普遍较高,并且随着网络节点平均度的增加而增加。因此,研究了如何降低实现DC规则的复杂度,提出了一种高效的DC实现方法(efficient DC implementation scheme,EDCS)。首先对DC规则进行了扩展,然后在构造最短路径树的过程中实现扩展DC规则,最后从理论上分析了算法的时间复杂度。实验结果表明,EDCS不仅具有较小的计算开销,并且可以计算出所有符合DC规则的备份下一跳。The reactive recovery methods have a long recovery time to deal with the network failures,which cannot meet the requirements of real-time applications for network delay and packet loss rate.Therefore,router vendors generally use DC rules to handle failures in the network.However,the complexity of existing algorithms to implement DC rules is generally high,and increases with the increase of network node degree.Therefore,this paper studied how to reduce the complexity of implementing DC rules,and proposed an efficient DC implementation method.This paper first extended the DC rule,then implemented the extended DC rule in the process of constructing the shortest path tree,and finally analyzed the time complexity of the algorithm theoretically.The experimental results show that EDCS not only has less computational overhead,but also can compute all the backup next hops that conform to DC rule.

关 键 词：网络故障 被动恢复方案 路由保护方案 DC规则 扩展DC规则 计算开销 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]