《计算机应用研究》|Application Research of Computers

DC规则的一种高效实现方法

Efficient implementation method for DC

免费全文下载 (已被下载 次)  
获取PDF全文
作者 张伟,李卓,耿海军,尹霞
机构 中国劳动关系学院 计算机应用教研室;山西大学 软件学院;清华大学 计算机科学与技术
统计 摘要被查看 次,已被下载
摘要 研究证实,网络中的故障无法避免,并且频繁发生。目前互联网部署的域内路由协议通过被动恢复方法来应对网络中频繁发生的故障。但是被动恢复方法应对网络故障的恢复时间较长,无法满足实时应用对网络时延和丢包率的要求。因此,路由器厂商普遍采用DC(downstream criterion)规则来处理网络中的故障。然而,已有的实现DC规则算法的时间复杂度普遍较高,并且随着网络节点平均度的增加而增加。因此,文章研究如何降低实现DC规则的复杂度,提出了一种高效的DC实现方法(an efficient dc implementation scheme,EDCS)。文章首先对DC规则进行了扩展,然后在构造最短路径树的过程中实现扩展DC规则,最后从理论上分析了算法的时间复杂度。实验结果表明,EDCS不仅具有较小的计算开销,并且可以计算出所有符合DC规则的备份下一跳。
关键词 网络故障;被动恢复方案;路由保护方案;DC规则;扩展DC规则;计算开销
基金项目 国家自然科学基金资助项目(61702315)
本文URL http://www.arocmag.com/article/02-2020-10-049.html
收稿日期
修回日期
页码 -
中图分类号 TP309.7
文献标志码