微信服务号

微信订阅号

2025-5-15- 15
Home > Archive>Volume 24, Issue 3, 2013 >575-592. DOI:10.3724/SP.J.1001.2013.04250
PDF HTML XML Export Cite reminder
Centralized Intra-Domain Protection Routing Mechanism for Low-Connectivity Topology
Author:
Affiliation:

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

    In centralized routing, routing tables are computed by a control platform, but routers do not make decisions anymore. It is necessary to build backup paths for each router so that packets can be forwarded after failure. Existing protecting routing schemes cannot work well in low-connectivity topology. To solve this problem, a method for building centralized protection routing is proposed in this paper. In this method, packets can be pushed back to the upstream nodes and sent by the backup paths of upstream nodes if current node has no valid paths after failure. The problem of building optimal protection routing for a given topology is proved to be NP-hard and a heuristic algorithm is proposed. The algorithm is verified in various topologies and the experimental results show that it is better than existing schemes.

    Reference
    [1] Fortz B, Thorup M. Internet traffic engineering by optimizing OSPF weights. In: Proc. of the IEEE INFOCOM 2000. Israel: IEEE Press, 2000. 519-528. [doi: 10.1109/INFCOM.2000.832225]
    [2] Greenberg A, Hjalmtysson G, Maltz DA, Myers A, Rexford J, Xie G, Yan H, Zhan J, Zhan H. A clean slate 4D approach to network control and management. ACM SIGCOMM Computer Communication Review, 2005,35(5):41-54. [doi: 10.1145/1096536. 1096541]
    [3] Kwong KW, Gao L, Guerin R, Zhang ZL. On the feasibility and efficacy of protection routing in IP networks. IEEE/ACM Trans. on Networking, 2011,19(5):1543-1556. [doi: 10.1109/TNET.2011.2123916]
    [4] Caesar M, Caldwell D, Feamster N, Rexford J. Design and implementation of a routing control platform. In: Proc. of the 2nd Symp. on Networked Systems Design & Implementation (NSDI 2005). Boston: ACM Press, 2005. 15-28.
    [5] Ohara Y, Imahori S, Meter RV. MARA: Maximum alternative routing algorithm. In: Proc. of the IEEE INFOCOM 2009. Brazil: IEEE Press, 2009. 298-306. [doi: 10.1109/INFCOM.2009.5061933]
    [6] Shand M, Bryant S. IP fast reroute framework. Internet Draft, 2009. http://tools.ietf.org/html/draft-ietf-rtgwg-ipfrr-framework-13
    [7] Moy J. OSPF version 2. IETF, RFC 2328, 1998.
    [8] Atlas A, Zinin A. Basic specification for IP fast reroute: Loop-Free alternates. IETF RFC 5286, 2008.
    [9] Ray S, Gúerin R, Kwong KW, Sofia R. Always acyclic distributed path computation. IEEE/ACM Trans. on Networking, 2010, 18(1):307-319. [doi: 10.1109/TNET.2009.2025374]
    [10] Schollmeier G, Charzinski J, Kirst-dter A, Reichert C, Schrodi K, Glickman Y, Winkler C. Improving the resilience in IP networks. In: Proc. of the IEEE Workshop on High Performance Swithching and Routing. Torino: IEEE Press, 2003. 91-96. [doi: 10.1109/ HPSR.2003.1226686]
    [11] Nelakuditi S, Lee S, Yu Y, Zhang ZL, Chuah CN. Fast local rerouting for handling transient link failures. IEEE/ACM Trans. on Networking, 2007,15(2):359-372. [doi: 10.1109/TNET.2007.892851]
    [12] Kvalbein A, Hansen AF, C-c-c T, Gjessing S, Lysne O. Multiple routing configurations for fast IP network recovery. IEEE/ACM Trans. on Networking, 2009,17(2):473-486. [doi: 10.1109/TNET.2008.926507]
    [13] SEnyedi G, Szilagyi P, Retvari G, Csaszar A. IP fast reroute: Lightweight not-via without additional addresses. In: Proc. of the IEEE INFOCOM 2009. Brazil: IEEE Press, 2009. 2771-2775.
    [14] Lakshminarayanan K, Caesar M, Rangan M, Anderson T, Shenker S, Stoica I. Achieving convergence-free routing using failurecarrying packets. In: Proc. of the SIGCOMM. Kyoto: ACM Press, 2007. 241-252.
    [15] Kushman N, Kandula S, Katabi D, Maggs B. R-BGP: Staying connected in a connected world. In: Proc. of the 4th Symp. on Networked Systems Design and Implementation (NSDI 2007). Berkeley: USENIX Association, 2007. 341-354. [doi: 10.1145/ 1282380.1282408]
    [16] Kullmann O. New methods for 3-SAT decision and worst-case analysis. TCS, 1999,223(1-2):1-72. [doi: 10.1016/S0304-3975(98) 00017-6]
    [17] Diestel R. Graph Theory. 3rd ed., Springer-Verlag, 2005.
    [18] Fujishige S. A maximum flow algorithm using MA ordering. Operations Research Letters, 2003,31(3):176-178. [doi: 10.1016/ S0167-6377(02)00237-7]
    [19] Spring N, Mahajan R, Wetherall D, Anderson T. Measuring ISP topologies with rocketfuel. IEEE/ACM Trans. on Networking, 2004,12(1):2-16. [doi: 10.1109/TNET.2003.822655]
    [20] Medina A, Lakhina A, Matta I, Byers J. BRITE: An approach to universal topology generation. In: Proc. of the 9th Int'l Symp. in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2001). Washington: IEEE Press, 2001. 346-353. [doi: 10.1109/MASCOT.2001.948886]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

谭晶,罗军舟,李伟.一种适合低连接度拓扑的集中式保护路由机制.软件学报,2013,24(3):575-592

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 30,2011
  • Revised:April 09,2012
  • Online: March 01,2013
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044671Visitors
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