基于优化链路权值的域内路由保护方案

doi:10.11896／j.issn.1002-137X.2019.01.022

计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 143-147.doi: 10.11896／j.issn.1002-137X.2019.01.022

基于优化链路权值的域内路由保护方案

耿海军

(山西大学软件学院太原030006)
(网络与交换技术国家重点实验室北京100876)

收稿日期:2017-07-06 出版日期:2019-01-15 发布日期:2019-02-25
作者简介:耿海军(1983－),男,博士,讲师,主要研究方向为网络体系结构和路由算法等,E-mail:ghj123025449@163.com(通信作者)。
基金资助:
国家自然科学基金(61702315),网络与交换技术国家重点实验室(北京邮电大学)开放课题资助项目(SKLNST-2018-1-19)资助

Intra-domain Routing Protection Scheme by Optimizing Link Weight

GENG Hai-jun

(School of Software Engineering,Shanxi University,Taiyuan 030006,China)
(State Key Laboratory of Networking and Switching Technology,Beijing 100876,China)

Received:2017-07-06 Online:2019-01-15 Published:2019-02-25

摘要/Abstract

摘要： 目前,互联网部署的域内链路状态路由协议,如开放最短路径优先(Open Shortest Path First,OSPF)和中间系统到中间系统(Intermediate System-to-Intermediate System,IS-IS),采用被动恢复方案应对网络故障。随着网络的发展,大量的实时应用部署在互联网上,OSPF的收敛时间无法满足这些实时应用对收敛时间的需求。因此,学术界和工业界提出采用路由保护方案来应对网路中出现的故障。然而,已有的路由保护方案存在两个方面的问题:1)默认路径和备份路径的交叉度较高,如LFA;2)为了计算两条交叉度低的路径,对默认路径加以限制,即默认路径不采用最短路径,如Color Tree。为了解决上述两个问题,首先将上述问题归结为整数规划模型,接着利用启发式方法计算近似最优解,最后在实际网络和模拟网络中对所提算法进行了大量实验。实验结果表明,所提算法可以降低默认路径和备份路径的交叉度,极大地提高网络的可用性。

关键词: 备份路径, 不相交性, 开放最短路径优先, 路由保护方案, 网络故障

Abstract: The current deployed intra-domain link state routing protocols on the Internet,such as Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS),generally adopt proactive recovery schemes to cope with network failures.In addition,with the emergence of real-time and mission-critical applications,stringent reliability and high availability are required.However,the deployed intra-domain link-state routing protocols need a global link-state advertisement and need to recalculate routing tables when link failures occur,inevitably causing network outage.As a result,academics and industry proposed to employ reactive routing protection solutions to deal with network failures in the network.The proactive schemes compute backup paths in advance,so that packets can be forwarded over those precomputing paths after the detection of network failures.However,the existing routing protection algorithms are facing two problems:1)the disjointness of the default path with respect to the backup path is very low,i.e.,ECMP and LFA,2)in order to compute two paths which have high disjointness,some restrictions must be impressed on default path,i.e.,the default path is not the shortest path.This paper first introduced the problem of constructing disjoint paths into integer programming problems,and then proposed to use the heuristic algorithm to calculate the approximate optimal solution.Finally,the algorithms were carried out in the real,measured and generated networks.The experimental results show that the proposed algorithms can greatly enhance the disjointness of the shortest path and the backup path,and improve the network availability.

Key words: Backup path, Disjoint, Network failure, OSPF, Routing protection scheme

中图分类号:

TP309.7

耿海军. 基于优化链路权值的域内路由保护方案[J]. 计算机科学, 2019, 46(1): 143-147. https://doi.org/10.11896／j.issn.1002-137X.2019.01.022

GENG Hai-jun. Intra-domain Routing Protection Scheme by Optimizing Link Weight[J]. Computer Science, 2019, 46(1): 143-147. https://doi.org/10.11896／j.issn.1002-137X.2019.01.022

参考文献

[1]CLARK D.The design philosophy of the DARPA internet protocols[J].Acm Sigcomm Computer Communication Review,1988,18(4):106-114. [2]BLACK U.Voice over IP[M].Prentice-Hall,Inc.,1999. [3]DREW P,GALLON C.Next-generation voip network architecture:MSF Technical Report:MSF-TR-ARCH-001-FINALIRI[R].Multiservice Switching Forum,2003. [4]GOODE B.Voice over internet protocol (voip)[J].Proceedings of the IEEE,2002,90(9):1495-1517. [5]KRIST P.Scalable and Efficient Multipath Routing:Complexity and Algorithms[C]//2015 IEEE 23rd International Conference on Network Protocols (ICNP).IEEE,2015:376-385. [6]ZHENG J,XU H,ZHU X,et al.We’ve Got You Covered:Failure Recovery with Backup Tunnels in Traffic Engineering[C]//2016 IEEE 24rd International Conference on Network Protocols (ICNP).IEEE,2016. [7]HARTERT R,VISSICCHIO S,SCHAUS P,et al.A Declarative and Expressive Approach to Control Forwarding Paths in Car-rier-Grade Networks [J].Acm Sigcomm Computer Communication Review,2015,45(5):15-28. [8]MARKOPOULOU A,IANNACCONE G,BHATTACHARYYA S,et al.Characterization of failures in an operational ip backbone network[J].IEEE/ACM Transactions on Networking,2008,16(4):749-762. [9]HOU M,WANG D,XU M,et al.Selective protection:a cost-efficient backup scheme for link state routing[C]//29th IEEE International Conference onDistributed Computing Systems.IEEE,2009:68-75. [10]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. [11]YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal Link-Disjoint Node-“Somewhat Disjoint” Paths[C]//2016 IEEE 24rd International Conference on Network Protocols (ICNP).IEEE,2016:1-10. [12]KWONG K W,GAO L,ZHANG Z L.On the feasibility and efficacy of protection routing in IP networks [J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556. [13]SRIDHARAN A,GUERIN R,DIOTC.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks [J].IEEE/ACM Transactions on Networking,2005,13(2):234-247. [14]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[J].ACM SIGCOMM Computer Communication Review,2006,36(4):159-170. [15]ATLAS A,ZININ A.Basic specification for ip fast reroute: Loop-free alternates:RFC 5286 .New York,NY,USA:A.Atlas,Ed.,2008. FRANCOIS P,BONAVENTURE O.An evaluation of IP-based fast reroute techniques//ACM Conference on Emerging Network Experiment and Technology.ACM,2005:244-245. HARTMANN M,HOCK D,MENTH M.Routing optimization for IP networks with loop-free alternates.Computer Networks,2016,95:35-50. LI A,FRANCOIS P,YANG X.On improving the efficiency and manageability of NotVia//ACM Conference on Emerging Network Experiment and Technology (CONEXT).ACM,2007:1-12. [19]JAYAVELU G,RAMASUBRAMANIAN S,YOUNIS O.Maintaining colored trees for disjoint multipath routing under node failures[J].IEEE/ACM Transactions on Networking,2009,17(1):346-359. [20]KINI S,RAMASUBRAMANIAN S,KVALBEIN A,et al.Fast recovery from dual link failures in IP networks[C]//Proc.INFOCOM.IEEE,2009. [21]MEDARD M,FINN S,BARRY R,et al.Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs[J].IEEE/ACM Transactions on Networking,1999,7(5):641-652. [22]SUURBALLE J W.A quick method for finding shortest pairs of disjoint paths[J].Networks,2006,14(2):325-336. [23]NETWORK A B.Advanced networking for research and education[OL].http://abilene.internet2.edu. [24]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring isp topologies with rocketfuel [J].IEEE/ACM Transactions on Networking,2004,12(1):2-16. [25]MEDINA A,LAKHINA A,MATTA I,et al.Brite:An approach to universal topology generation[C]//IEEE InternationalWorkshop on Modeling,Analysis,and Simulation of Computer and Telecommunication Systems.IEEE,2001:346-353. [26]GJOKA M,RAM V,YANG X.Evaluation of ip fast reroute proposals[C]//International Conference on Communication Systems Software and Middleware.IEEE,2007:1-8.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于优化链路权值的域内路由保护方案

Intra-domain Routing Protection Scheme by Optimizing Link Weight

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 0

[1]	耿海军, 尹霞. 基于增量最短路径优先的域内高效路由保护算法 Efficient Intra-domain Routing Protection Algorithm Based on i-SPF 计算机科学, 2019, 46(8): 116-120. https://doi.org/10.11896/j.issn.1002-137X.2019.08.019
[2]	耿海军,张爽,尹霞. 互联网域内路由可用性综述 Overview of Routing Availability in Intra-domain Routing Networks 计算机科学, 2019, 46(7): 1-6. https://doi.org/10.11896/j.issn.1002-137X.2019.07.001
[3]	周帆帆. 校园网络故障用户自助排查技术的探讨 Study on Campus Network Faults for Investigation Technology of User Self-service 计算机科学, 2014, 41(Z11): 461-462.