微信服务号

微信订阅号

2025-4-16- 7
Home > Archive>Volume 31, Issue 5, 2020 >1536-1548. DOI:10.13328/j.cnki.jos.005675
PDF HTML XML Export Cite reminder
Intra-domain Routing Protection Scheme Based on Minimum Intersection Paths
Author:
Affiliation:

Clc Number:

TP393

Fund Project:

National Natural Science Foundation of China (61702315, 61872226); Scientific and Technological Innovation Programs of Higher Education Institutions in Shanxi Province (201802013); National Key Research and Development Program of China (2018YFB1800401); Natural Science Foundation of Shanxi Province (201701D121052); Key Research and Development Program of Shanxi Province (International Science and Technology Cooperation Project) (201903D421003)

  • Article
    • | |
  • Metrics
    • |
  • Reference [34]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    The existing routing protection schemes are facing the following two problems: (1) the default path and the backup path contain a large number of common edges, such as ECMP and LFA; (2) in order to calculate two paths which have a small number of common edges, the shortest path cannot be used in the network, such as red-green tree method. To solve the above two problems, this study first describes the problem of computing backup paths and default paths as an integer programming model, and then a heuristic method is proposed to solve the problem. Next, the forwarding algorithm is introduced. Finally, the proposed algorithm is tested by simulation experiment and real experiment. Experiments show that the proposed algorithm not only has lower computational complexity, but also reduces the number of common edges contained in the default paths and the shortest paths, and greatly improve the network availability.

    Reference
    [1] Clark, D. The design philosophy of the DARPA Internet protocols. ACM Sigcomm Computer Communication Review, 1988,18(4): 106-114.
    [2] Varshney U, Snow A, Mcgivern M, et al. Voice over IP. Communications of the ACM, 2002,45(1):89-96.
    [3] Geng H, Shi X, Wang Z, et al. A hop-by-hop dynamic distributed multipath routing mechanism for link state network. Computer Communications, 2018,116:225-239.
    [4] Goode B. Voice over internet protocol (VoIP). Proc. of the IEEE, 2002,90(9):1495-1517.
    [5] Krist P. Scalable and efficient multipath routing: Complexity and algorithms. In: Proc. of the Int’l Conf. 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. In: Proc. of the Int’l Conf. on Network Protocols (ICNP). IEEE, 2016. 1-10.
    [7] Hartert R, Vissicchio S, Schaus P, et al. A declarative and expressive approach to control forwarding paths in carrier-grade networks. ACM Sigcomm Computer Communication Review, 2015,45(5):15-28.
    [8] Moy J. RFC 2328: OSPF Version 2, 1998. http://www.rfc-editor.org/info/rfc1583
    [9] Basu A, Riecke J. Stability issues in OSPF routing. ACM Sigcomm Computer Communication Review, 2001,31(4):225-236.
    [10] Markopoulou A, Iannaccone G, Bhattacharyya S, et al. Characterization of failures in an operational IP backbone network. IEEE/ ACM Trans. on Networking, 2008,16(4):749-762.
    [11] Hou M, Wang D, Xu M, et al. Selective protection: A cost-efficient backup scheme for link state routing. In: Proc. of the IEEE Int’l Conf. on Distributed Computing Systems (ICDCS). IEEE, 2009. 68-75.
    [12] Geng HJ, Shi XG, Yin X, Wang ZL, Yin SP. Algebra and algorithms for multipath QoS routing in link state networks. Journal of Communications and Networks, 2017,19(2):189-200.
    [13] Yallouz J, Rottenstreich O, Babarczi P, et al. Optimal link-disjoint node-“somewhat disjoint” paths. In: Proc. of the Int’l Conf. on Network Protocols (ICNP). IEEE, 2016. 1-10.
    [14] Kwong KW, Gao L, Zhang ZL. On the feasibility and efficacy of protection routing in IP networks. IEEE/ACM Trans. on Networking, 2011,19(5):1543-1556.
    [15] Gopalan A, Ramasubramanian S. IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees. IEEE/ ACM Trans. on Networking, 2016,24(3):1336-1349.
    [16] Antonakopoulos S, Bejerano Y, Koppol P. Full protection made easy: The DisPath IP fast reroute scheme. IEEE/ACM Trans. on Networking, 2015,23(4):1229-1242.
    [17] Xu A, Bi J, Zhang B. Failure inference for shortening traffic detours. In: Proc. of the Int’l Symp. on Quality of Service. IEEE, 2016. 1-10.
    [18] Sommers J, Barford P, Eriksson B. On the prevalence and characteristics of MPLS deployments in the open Internet. In: Proc. of the 2011 ACM SIGCOMM Conf. on Internet Measurement Conf. ACM, 2011. 445-462.
    [19] Yang Y, Xu M, Li Q. Fast rerouting against multi-link failures without topology constraint. IEEE/ACM Trans. on Networking, 2018,26(1):384-397.
    [20] Sridharan A, Guerin R, Diot C. Achieving near-optimal traffic engineering solutions for current ospf/is-is networks. IEEE/ACM Trans. on Networking, 2005,13(2):234-247.
    [21] Atlas A, Zinin A. Basic specification for IP fast reroute: Loop-free alternates. RFC5286, 2008. http://www.rfc-editor.org/info/rfc 5286
    [22] Yang X, Wetherall D. Source selectable path diversity via routing deflections. In: Proc. of the ACM Special Interest Group on Data Communication (SIGCOMM). 2006. 159-170.
    [23] Kvalbein A, Hansen AF, Čičić T, et al. Fast IP network recovery using multiple routing configurations. In: Proc. of the Int’l Conf. on Computer Communications (INFOCOM). IEEE, 2006. 1-11.
    [24] Lakshminarayanan K, Caesar M, Rangan M, et al. Achieving convergence-free routing using failure-carrying packets. In: Proc. of the ACM Special Interest Group on Data Communication (SIGCOMM). 2007. 241-252.
    [25] Enyedi G, Rétvári G, Szilágyi P, Császár A. IP fast ReRoute: Lightweight not-via without additional addresses. In: Proc. of the INFOCOM. 2009. 2771-2775.
    [26] Jayavelu G, Ramasubramanian S, Younis O. Maintaining colored trees for disjoint multipath routing under node failures. IEEE/ ACM Trans. on Networking, 2009,17(1):346-359.
    [27] Kini S, Ramasubramanian S, Kvalbein A, Hansen AF. Fast recovery from dual link failures in IP networks. In: Proc. of the Int’l Conf. on Computer Communications (INFOCOM). IEEE, 2009. 1368-1376.
    [28] Medard M, Finn S, Barry R, Gallagher R. Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs. IEEE/ACM Trans. on Networking, 1999,7(5):641-652.
    [29] Lee YO, Narasimha Reddy AL. Constructing disjoint paths for failure recovery and multipath routing. Computer Networks, 2012, 56(2):719-730.
    [30] Network AB. Advanced networking for research and education. 2003. http://abilene.internet2.edu
    [31] Spring N, Mahajan R, Wetherall D, et al. Measuring ISP topologies with rocketfuel. IEEE/ACM Trans. on Networking, 2004,12(1): 2-16.
    [32] http://www.cs.bu.edu/brite/
    [33] Heckmann O, Piringer M, Schmitt J, et al. Generating realistic ISP-level network topologies. Communications Letters IEEE, 2003, 7(7):335-336.
    [34] Gjoka M, Ram V, Yang X. Evaluation of IP fast reroute proposals. In: Proc. of the Communication Systems Software and Middleware. 2007. 1-8.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

耿海军,施新刚,王之梁,尹霞,胡治国.基于最小路径交叉度的域内路由保护方案.软件学报,2020,31(5):1536-1548

Copy
Share
Article Metrics
  • Abstract:1766
  • PDF: 3126
  • HTML: 1513
  • Cited by: 0
History
  • Received:October 30,2017
  • Revised:August 09,2018
  • Online: May 18,2020
  • Published: May 06,2020
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2035254Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063