Computer Science ›› 2019, Vol. 46 ›› Issue (1): 143-147.doi: 10.11896/j.issn.1002-137X.2019.01.022

• Network & Communication • Previous Articles     Next Articles

Intra-domain Routing Protection Scheme by Optimizing Link Weight

GENG Hai-jun   

  1. (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: 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

CLC Number: 

  • TP309.7
[1]CLARK D.The design philosophy of the DARPA internet protocols[J].Acm Sigcomm Computer Communication Review,1988,18(4):106-114.<br /> [2]BLACK U.Voice over IP[M].Prentice-Hall,Inc.,1999.<br /> [3]DREW P,GALLON C.Next-generation voip network architecture:MSF Technical Report:MSF-TR-ARCH-001-FINALIRI[R].Multiservice Switching Forum,2003.<br /> [4]GOODE B.Voice over internet protocol (voip)[J].Proceedings of the IEEE,2002,90(9):1495-1517.<br /> [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.<br /> [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.<br /> [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.<br /> [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.<br /> [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.<br /> [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.<br /> [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.<br /> [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.<br /> [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.<br /> [14]YANG X,WETHERALL D.Source selectable path diversity via routing deflections[J].ACM SIGCOMM Computer Communication Review,2006,36(4):159-170.<br /> [15]ATLAS A,ZININ A.Basic specification for ip fast reroute: Loop-free alternates:RFC 5286 .New York,NY,USA:A.Atlas,Ed.,2008.<br /> FRANCOIS P,BONAVENTURE O.An evaluation of IP-based fast reroute techniques//ACM Conference on Emerging Network Experiment and Technology.ACM,2005:244-245.<br /> HARTMANN M,HOCK D,MENTH M.Routing optimization for IP networks with loop-free alternates.Computer Networks,2016,95:35-50.<br /> 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.<br /> [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.<br /> [20]KINI S,RAMASUBRAMANIAN S,KVALBEIN A,et al.Fast recovery from dual link failures in IP networks[C]//Proc.INFOCOM.IEEE,2009.<br /> [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.<br /> [22]SUURBALLE J W.A quick method for finding shortest pairs of disjoint paths[J].Networks,2006,14(2):325-336.<br /> [23]NETWORK A B.Advanced networking for research and education[OL].http://abilene.internet2.edu.<br /> [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.<br /> [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.<br /> [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.
[1] GENG Hai-jun, YIN Xia. Efficient Intra-domain Routing Protection Algorithm Based on i-SPF [J]. Computer Science, 2019, 46(8): 116-120.
[2] GENG Hai-jun,ZHANG Shuang,YIN Xia. Overview of Routing Availability in Intra-domain Routing Networks [J]. Computer Science, 2019, 46(7): 1-6.
[3] LI Peng-fei, CHEN Ming, DENG Li, QIAN Hong-yan. NFV Based Detection Method Against Double LSAs Attack on OSPF Protocol [J]. Computer Science, 2019, 46(6A): 343-347.
[4] YUAN Pei-yan, ZHANG Hao. Energy Efficient Routing Algorithm in Mobile Opportunistic Networks [J]. Computer Science, 2019, 46(11A): 387-392.
[5] ZHOU Chang-jian, XING Jin-ge and LIU Hai-bo. Research on Network-layer Topology Discovery Algorithm Based on Multi-protocol [J]. Computer Science, 2017, 44(Z6): 361-365.
[6] LI Yan-gang, DENG Wen-ping, WANG Hong and LIU Ya-ping. Research and Analysis on Differences of Domain Routing Protocol OSPF and IS-IS [J]. Computer Science, 2015, 42(Z6): 256-259.
[7] DONG Gao-xiu,LING Shan and CHEN Wei-dong. Quasi-human Algorithm for Finding Non-interfering Disjoint Paths in Wireless Networks [J]. Computer Science, 2014, 41(8): 70-74.
[8] GUO Xian,FENG Tao,YUAN Zhan-ting. Multiple Node-disjoint Paths Distance Vector Routing for Ad hoc Networks [J]. Computer Science, 2011, 38(2): 86-90.
[9] . [J]. Computer Science, 2008, 35(1): 56-59.
[10] . [J]. Computer Science, 2007, 34(9): 35-38.
[11] LI Hua ,ZHANG Tao, YE Xin-Ming, GUO Yi-Jing, LI Yuan-Ping ,BAI Rui-Feng (College of Computer Science, Neimongol University, Hohhot 010021). [J]. Computer Science, 2007, 34(4): 59-62.
[12] ZHANG Jing ,RAN Xiao-Min, HU Han-Ying (Information Engineering University,Zhengzhou 450002). [J]. Computer Science, 2006, 33(7): 47-51.
[13] . [J]. Computer Science, 2005, 32(11): 16-19.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!