Abstract
IP fast reroute is a mechanism that is used to reroute packets around a failed link as soon as the link fails. Most of the IP fast reroute mechanisms, that have been proposed so far, focus on single or dual link failures but can not handle Shared Risk Link Group (SRLG) failures when several links fail at the same time because of some common underlying component failure. Furthermore, most of current work is based on the assumption that each node in the network has access to some global topology information of the network. In this paper, we present the first IP fast reroute mechanism for SRLG failures that is not based on the assumption that the nodes in the network have global topology information of the network. In our mechanism, nodes in the network use “relay bits” to identify themselves as “relay nodes” for a reroute link in a fully distributed mannner. Through simulation, we show that our mechanism succeeds in rerouting around SRLG failures alomst 100% of the time, with average length of a reroute path about 1.5 times the re-converged shortest path.
Chapter PDF
Similar content being viewed by others
References
BRITE: Boston univeristy Representative Internet Topology gEnerator, http://www.cs.bu.edu/BRITE/
Enhanced interior gateway routing protocol, http://www.cisco.com/en/US/tech/tk365/technologies_white_paper09186a0080094cb7.shtml
Atlas, A.: U-turn alternates for IP/LDP fast-reroute (February 2006), Internet Draft http://draft-atlas-ip-local-protect-uturn-03.txt
Atlas, A., Zinin, A.: Basic specification for IP fast reroute: Loop-free alternates. In: RFC 5286 (September 2008)
Boutremans, C., Iannaccone, G., Diot, C.: Impact of link failures on VoIP performance. In: NOSSDAV’02 (May 2002)
Bryant, S., Filsfils, C., Previdi, S., Shand, M.: IP fast reroute using tunnels (November 2007), Internet Draft, draft-bryant-ipfrr-tunnels-03
Bryant, S., Shand, M.: A framework for loop-free convergence (October 2008), Internet Draft, draft-ietf-rtgwg-lf-conv-frmwk-03
Enyedi, G., Szilágyi, P., Rétvári, G., Császár, A.: IP fast reroute: Lightweight not-via without additional addresses. In: IEEE infocom mini-conference (2009)
Francois, P., Bonaventure, O.: Avoiding transient loops during IGP convergence in IP networks. In: IEEE Infocom (2005)
Francois, P., Bonaventure, O.: An evaluations of IP-based fast reroute techniques. In: CoNext (2005)
Francois, P., Bonaventure, O., Shand, M., Bryant, S., Previdi, S.: Loop-free convergence using oFIB (February 2008), Internet draft, draft-ietf-rtgwg-ordered-fib-02
Francois, P., Filsfils, C., Evans, J., Bonaventure, O.: Achieving subsecond IGP convergence in large IP networks. In: ACM Sigcomm (2005)
Gjoka, M., Ram, V., Yang, X.: Evaluations of IP fast reroute proposals. In: IEEE Comsware (2007)
Kini, S., Ramasubramanian, S., Kvalbein, A., Hansen, A.: Fast recovery from dual link failures in IP networks. In: IEEE Infocom (2009)
Kushman, N., Kandula, S., Katabi, D., Maggs, B.: R-BGP: Staying connected in a connected world. In: Usenix NSDI (2007)
Kvalbein, A., Hansen, A.F., Cicic, T., Gjessing, S., Lysne, O.: Fast IP network recovery using multiple routing configurations. In: IEEE Infocom (2006)
Lakshminarayanan, K., Caesar, M., Rangan, M., Anderson, T., Shenker, S., Stoica, I.: Achieving convergence-free routing using failure-carrying packets. In: ACM Sigcomm (2007)
Li, A., Francois, P., Yang, X.: On improving the efficiency and manageability of NotVia. In: CoNext (2007)
Li, Y., Gouda, M.G.: IP fast reroute in networks with shared risk links. UTCS Technical Report TR-09-38, The University of Texas at Austin (2009)
Li, Y., Gouda, M.G.: IP fast reroute without global topology information. UTCS Technical Report TR-09-34, The University of Texas at Austin (2009)
Malkin, G.: RFC 2453 - RIP Version 2 (November 1998)
Markopoulou, A., Iannaccone, G., Bhattacharyya, S., Chuah, C.-N., Dio, C.: Characterization of failures in an IP backbone. In: IEEE Infocom’04 (2004)
Motiwala, M., Elmore, M., Feamster, N., Vempala, S.: Path splicing. In: ACM Sigcomm (2008)
Nelakuditi, S., Lee, S., Yu, Y., Zhang, Z.-L., Chuah, C.-N.: Fast local rerouting for handling transient link failures. IEEE/ACM Transaction on Networking 15(2) (April 2007)
Olivier Bonaventure, C.F., Francois, P.: Achieving sub-50 milliseconds recovery upon BGP peering link failures. IEEE/ACM Transaction on Networking 15(5) (October 2007)
Shand, M., Bryant, S.: IP fast reroute framework (October 2009), Internet Draft, draft-ietf-rtgwg-ipfrr-framework-13.txt
Shand, M., Bryant, S., Previdi, S.: IP fast reroute using Not-via addresses (October 2008), draft-ietf-rtgwg-ipfrr-notvia-addresses-03
Wang, F., Gao, L.: A backup route aware routing protocol - fast recovery from transient routing failures. In: IEEE Infocom mini-conference (2008)
Wang, F., Gao, L.: Path diversity aware interdomain routing. In: IEEE Infocom (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, Y., Gouda, M.G. (2010). IP Fast Reroute in Networks with Shared Risk Links. In: Crovella, M., Feeney, L.M., Rubenstein, D., Raghavan, S.V. (eds) NETWORKING 2010. NETWORKING 2010. Lecture Notes in Computer Science, vol 6091. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12963-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-12963-6_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12962-9
Online ISBN: 978-3-642-12963-6
eBook Packages: Computer ScienceComputer Science (R0)