Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2018, Vol. 58 Issue (8): 710-714    DOI: 10.16511/j.cnki.qhdxxb.2018.22.040
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
基于段路由的单节点故障路由保护算法
耿海军1, 刘洁琦1, 尹霞2
1. 山西大学 软件学院, 太原 030006;
2. 清华大学 计算机科学与技术系, 北京 100084
Single node failure routing protection algorithm based on segment routing
GENG Haijun1, LIU Jieqi1, YIN Xia2
1. School of Software Engineering, Shanxi University, Taiyuan 030006, China;
2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
全文: PDF(1785 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 针对已有的路由保护方案没有很好权衡路由保护算法的故障保护率和路径拉伸度之间的关系,该文提出了一种基于段路由(SR)体系结构的快速重路由算法IPFRRBSR。IPFRRBSR为每个源-目的对计算两条路径,其中一条是最短路径,另外一条是利用段标签构造的备份路径。当网络没有故障时利用最短路径转发报文,当网络出现故障时利用备份路径转发报文。最短路径和备份路径(除去源和目的)没有公共节点,因此二者几乎不会同时发生故障。实验结果表明:该算法不仅可以应对网络中任意的单节点故障情形,并且具有较小的路径拉伸度。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
耿海军
刘洁琦
尹霞
关键词 计算机网络网络故障路由保护段路由段标签    
Abstract:Existing routing protection schemes do not accurately consider the relationships between the failure protection ratio and the path stretch. A simple IP fast reroute based on the segment routing (IPFRRBSR) algorithm is given here to consider these relationships. IPFRRBSR calculates two paths between each source-destination pair with one being the shortest path and the other being a backup path constructed using segment labels. The packets are forwarded along the shortest path when the network is in the normal state, but are forwarded along the backup path when a network failure occurs. Since the shortest path and the backup path (except for the source and destination nodes) do not have any common nodes, the probability of them failing simultaneously is very low. Tests show that IPFRRBSR can deal with single node failures in the network and has a small path stretch.
Key wordscomputer network    network failure    routing protection    segment routing    segment label
收稿日期: 2018-01-02      出版日期: 2018-08-15
基金资助:国家“八六三”高技术项目(2015AA016105);国家自然科学基金资助项目(61702315)
引用本文:   
耿海军, 刘洁琦, 尹霞. 基于段路由的单节点故障路由保护算法[J]. 清华大学学报(自然科学版), 2018, 58(8): 710-714.
GENG Haijun, LIU Jieqi, YIN Xia. Single node failure routing protection algorithm based on segment routing. Journal of Tsinghua University(Science and Technology), 2018, 58(8): 710-714.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2018.22.040  或          http://jst.tsinghuajournals.com/CN/Y2018/V58/I8/710
  图1 算法IPFRRBSR 的执行过程
  图2 函数SRLABEL的执行过程
  表1 故障保护率
  表2 平均路径拉伸度
  图3 (网络版彩图)不同算法在 NJLATA的路径拉伸度
  图4 (网络版彩图)不同算法在 TORONTO 的路径拉伸度
  表3 段标签平均个数
  图5 (网络版彩图)段标签个数累积概率分布
[1] GENG H J, SHI X G, YIN X, et al. Algebra and algorithms for multipath QoS routing in link state networks[J]. Journal of Communications and Networks, 2017, 19(2):189-200.
[2] GENG H J, SHI X G, WANG Z L, et al. A hop-by-hop dynamic distributed multipath routing mechanism for link state network[J]. Computer Communications, 2018, 116:225-239.
[3] ZHENG J Q, XU H, ZHU X J, et al. We've got you covered:Failure recovery with backup tunnels in traffic engineering[C]//Proceedings of the 24th IEEE International Conference on Network Protocols (ICNP). Singapore, 2016:1-10.
[4] ELHOURANI T, GOPALAN A, RAMASUBRAMANIAN S, et al. IP fast rerouting for multi-link failures[J]. IEEE/ACM Transactions on Networking, 2016, 24(5):3014-3025.
[5] YANG Y, XU M W, LI Q. Tunneling on demand:A lightweight approach for IP fast rerouting against multi-link failures[C]//Proceedings of the 24th IEEE International Symposium on Quality of Service (IWQoS). Beijing, 2016:1-6.
[6] ANTONAKOPOULOS S, BEJERANO Y, KOPPOL P. Full protection made easy:The DisPath IP fast reroute scheme[J]. IEEE/ACM Transactions on Networking, 2016, 23(4):1229-1242.
[7] GOPALAN A, RAMASUBRAMANIAN S. IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees[J]. IEEE/ACM Transactions on Networking, 2016, 24(3):1336-1349.
[8] ATLAS A, ZININ A. Basic specification for IP fast reroute:Loop-free alternates:RFC 5286[S]. Reston, USA:Internet Society (ISOC), 2008.
[9] LEE S, YU Y Z, NELAKUDITI S, et al. Proactive vs reactive approaches to failure resilient routing[C]//Proceedings of the Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Hong Kong, China, 2004:1-9.
[10] ENYEDI G, SZILAGYI P, RÉTVÁRI G, et al. IP fast reroute:Lightweight Not-Via without additional addresses[C]//Proceedings of the 8th International IFIP-TC6 Networking Conference NETWORKING:International Conference on Research in Networking (INFOCOM). Rio de Janeiro, Brazil, 2009:2771-2775.
[11] SOMMERS J, BARFORD P, ERIKSSON B. On the prevalence and characteristics of MPLS deployments in the open Internet[C]//Proceedings of 2011 ACM SIGCOMM Conference on Internet Measurement Conference. Berlin, Germany, 2011:445-462.
[12] HAO F, KODIALAM M, LAKSHMAN T V. Optimizing restoration with segment routing[C]//Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). San Francisco, USA, 2016:1-9.
[13] CIANFRANI A, LISTANTI M, POLVERINI M. Incremental deployment of segment routing into an ISP network:A traffic engineering perspective[J]. IEEE/ACM Transactions on Networking, 2017, 25(5):3146-3160.
[14] HARTERT R, VISSICCHIO S, SCHAUS P. A declarative and expressive approach to control forwarding paths in carrier-grade networks[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(5):15-28.
[15] MORENO E, BEGHELLI A, CUGINI F. Traffic engineering in segment routing networks[J]. Computer Networks, 2017, 114:23-31.
[1] 刘武, 王永科, 孙东红, 任萍, 刘柯. 开源智能终端认证漏洞挖掘及登录认证改进[J]. 清华大学学报(自然科学版), 2017, 57(9): 897-902.
[2] 陈宇, 王娜, 王晋东. 利用三角模糊数的语言变量项集减项算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 892-896.
[3] 开毅,卢建元,刘斌. 基于分组处理能力共享的低功耗路由器体系结构[J]. 清华大学学报(自然科学版), 2014, 54(4): 485-489.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn