Abstract
Up to not so long ago, loop-free alternates (LFA) was the only viable option for providing fast protection in pure IP and MultiProtocol Label Switching–Label Distribution Protocol networks. Unfortunately, LFA cannot provide protection for all possible failure cases in general. Recently, the Internet Engineering Task Force has initiated the remote loop-free alternates (rLFA) technique as a simple extension to LFA, to boost the fraction of failure cases covered by fast protection. Before further standardization and deployment, however, it is crucial to determine to what extent rLFA can improve the level of protection against single link or node failures in a general IP network, as well as to find optimization methods to tweak a network for 100 % rLFA coverage. In this paper, we take the first steps towards this goal by solving these problems in the special, but practically relevant, case when each network link is of unit cost. We also provide preliminary numerical evaluations conducted on real IP network topologies, which suggest that rLFA significantly improves the level of protection, and most networks need only 2–3 new links to be added to attain 100 % failure case coverage irrespectively of whether link or node protection is considered.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
In IP routing, the next router along the shortest path to a destination is called next-hop.
In computer networking, the maximum transmission unit (MTU) is the size of the largest protocol data unit that the layer can pass onwards.
The triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. It is one of the defining properties of the distance function, which is used in shortest path routing.
See the remote-lfa maximum-cost option on [11].
References
Ahn, G., Jang, J., & Chun, W. (2002). An efficient rerouting scheme for mpls-based recovery and its performance evaluation. Telecommunication Systems, 19(3–4), 481–495. doi:10.1023/A:1013806925464.
Amund, K., Fosselie, H. A., Čičic, Tarik, Stein, G., & Olav, L. (2009). Multiple routing configurations for fast IP network recovery. IEEE/ACM Transactions on Netwworking, 17(2), 473–486. doi:10.1109/TNET.2008.926507.
Andersson, L., Minei, I., & Thomas, B. (2007). Ldp specifiaction. RFC 5036.
Antonakopoulos, S., Bejerano, Y., & Koppol, P. (2012). A simple ip fast reroute scheme for full coverage. In 2012 IEEE 13th International Conference on, High Performance Switching and Routing (HPSR) (pp. 15–22). doi:10.1109/HPSR.2012.6260822.
Atlas, A., & Zinin, A. (2008). Basic specification for IP fast reroute: Loop-Free Alternates. RFC 5286.
Bryant, S., Filfils, C., Previdi, S., & Shand, M. (2007). IP fast reroute using tunnels. IETF DRAFT.
Bryant, S., Filfils, C., Shand, M., & So, N. (2012). Remote LFA FRR. IETF DRAFT.
Bryant, S., Shand, M., & Previdi, S. (2010). IP fast reroute using Not-via addresses. Internet Draft.
Čičic, T. (2006). An upper bound on the state requirements of link-fault tolerant multi-topology routing. IEEE ICC, 3, 1026–1031.
Cisco Systems: Cisco ios release 12.0 and network protocols configuration guide (2011).
Cisco Systems: Ip routing: Ospf configuration guide, cisco ios release 15.2s—ospf ipv4 remote loop-free alternate ip fast reroute (downloaded: Apr. 2012).
Császár, A., Enyedi, G., & Kini, S. (March 2011). Ip fast re-route with fast notification. Internet Draft.
Csikor, L., Nagy, M., & Rétvári, G. (2011). Network optimization techniques for improving fast ip-level resilience with loop-free alternates. Infocommunications Journal, 3(4), 2–10.
Csikor, L., & Rétvári, G. (2012). IP fast reroute with remote loop-free alternates: The unit link cost case. In Proceedings of the RNDM (pp. 16–22).
Csikor, L., Rétvári, G., & Tapolcai, J. (2012). Optimizing igp link costs for improving ip-level resilience with loop-free alternates. Computer Communications. doi:10.1016/j.comcom.2012.09.004.
Enyedi, G., Rétvári, G., & Cinkler, T. (2007). A novel loop-free IP fast reroute algorithm. In EUNICE.
Enyedi, G., Szilágyi, P., Rétvári, G., & Császár, A. (2009). IP Fast ReRoute: Lightweight Not-Via without additional addresses. In INFOCOM Mini-conf.
Golumbic, M. C. (2004). Algorithmic Graph Theory and Perfect Graphs (2nd ed.). Amsterdam: Elsevier Science.
Gomes, T., oes, C.S., & Fernandes, L. (2011). Resilient routing in optical networks using srlg-disjoint path pairs of min-sum cost. Springer Telecommunication Systems Journal.
Hock, D., Hartmann, M., Menth, M., Pioro, M., Tomaszewski, A., & Zukowski, C. (2011). Comparison of ip-based and explicit paths for one-to-one fastreroute in mpls networks. Springer Telecommunication Systems Journal, 1–12. doi:10.1007/s11235-011-9603-4.
Hokelek, I., Fecko, M., Gurung, P., Samtani, S., Cevher, S., & Sucec, J. (Feb 2008). Loop-free ip fast reroute using local and remote lfaps. Internet Draft.
Iannaccone, G., Chuah, C.N., Mortier, R., Bhattacharyya, S., & Diot, C. (2002) Analysis of link failures in an ip backbone. In ACM SIGCOMM Internet Measurement Workshop (pp. 237–242).
ISO: Intermediate ststem-to-intermediate system (is-is) routing protocol. ISO/IEC 10589 (2002).
Iyer, S., Bhattacharyya, S., Taft, N., & Diot, C. (2003). An approach to alleviate link overload as observed on an IP backbone. In INFOCOM.
Jarry, A. (2013). Fast reroute paths algorithms. Telecommunication Systems, 52(2), 881–888. doi:10.1007/s11235-011-9582-5.
Juniper Networks: Junos 9.6 routing protocols configuration guide (2009).
Knight, S., Nguyen, H.X., Falkner, N., Bowden, R., & Roughan, M. The internet topology zoo. http://www.topology-zoo.org (downloaded: Apr. 2012)
Kwong, K.W., Gao, L., Guerin, R., & Zhang, Z.L. (2010). On the feasibility and efficacy of protection routing in ip networks. In INFOCOM, long version is available in Tech. Rep. 2009. University of Pennsylvania.
Labovitz, C., Malan, G. R., & Jahanian, F. (1998). Internet routing instability. IEEE/ACM Transactions on Networking, 6(5), 515–528.
Lakshminarayanan, K., Caesar, M., Rangan, M., Anderson, T., Shenker, S., & Stoica, I. (2007). Achieving convergence-free routing using failure-carrying packets. In Proceedings of the SIGCOMM.
Lee, S., Yu, Y., Nelakuditi, S., Zhang, Z.L., & Chuah, C.N. (2004). Proactive vs reactive approaches to failure resilient routing. In INFOCOM.
Mahajan, R., Spring, N., Wetherall, D., & Anderson, T. (2002). Inferring link weights using end-to-end measurements. In ACM IMC (pp. 231–236).
Markopoulou, A., Iannacone, G., Bhattacharyya, S., Chuah, C.N., & Diot, C. (Mar. 2004). Characterization of failures in an ip backbone. In Proceedings of the IEEE Infocom.
Médard, M., Barry, R. A., Finn, S. G., & Galler, R. G. (1999). Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs. IEEE/ACM Transactions on Networking, 7(5), 641–652.
Menth, M., Hartmann, M., Martin, R., Čičic, T., & Kvalbein, A. (2010). Loop-free alternates and not-via addresses: A proper combination for ip fast reroute? Computer Networks, 54(8), 41300–41315. doi:10.1016/j.comnet.2009.10.020.
Merindol, P., Pansiot, J.J., & Cateloin, S. (2008). Providing protection and restoration with distributed multipath routing. In International symposium on, performance evaluation of computer and telecommunication systems, 2008. SPECTS 2008 (pp. 456–463).
Moy, J. (1998). Ospf version 2. RFC 2328.
Nagy, M., Tapolcai, J., & Rétvári, G. (2012). Optimization methods for improving ip-level fast protection for local shared risk groups with loop-free alternates. Springer Telecommunication Systems Journal.
Pan, P., Swallow, G., & Atlas, A. (2005). Fast reroute extensions to RSVP-TE for LSP tunnels. RFC 4090.
Rétvári, G., Csikor, L., Tapolcai, J., Enyedi, G., & Császár, A. (Oct. 2011). Optimizing igp link costs for improving IP-level resilience. In Proceedings of the DRCN (pp. 62–69).
Rétvári, G., Tapolcai, J., Enyedi, G., & Császár, A. (2011). IP fast ReRoute: Loop free alternates revisited. In INFOCOM (pp. 2948–2956).
Schollmeier, G., Charzinski, J., Kirstädter, A., Reichert, C., Schrodi, K., Glickman, Y., & Winkler, C. (2003). Improving the resilience in ip networks. In Proceedings of the HPSR.
Shand, M., & Bryant, S. (2010). IP Fast Reroute framework. RFC 5714.
SNDLib: Survivable fixed telecommunication network design library. http://sndlib.zib.de (downloaded: Apr. 2012).
Sterbenz, J., Cetinkaya, E.K., Hameed, M.A., Jabbar, A., Qian, S., & Rohrer, J.P. (2011). Evaluation of network resilience, survivability, and disruption tolerance: Analysis, topology generation, simulation and experimentation. Springer Telecommunication Systems Journal, 1–32. doi:10.1007/s11235-011-9573-6.
Vulimiri, A., Michel, O., Godfrey, P.B., & Shenker, S. (2012). More is less: reducing latency via redundancy. In Hotnets.
Zhong, Z., Nelakuditi, S., Yu, Y., Lee, S., Wang, J., & Chuah, C.N. (2005). Failure inferencing based fast rerouting for handling transient link and node failures. In INFOCOM.
Acknowledgments
The authors thank the support of High Speed Networks Laboratory at BME. This project was supported by TÁMOP 4.2.2.B-10/1-2010-0009 and OTKA-PD 104939 grants. Levente Csikor was supported by the hungarian Sándor Csibi Research Grant.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Csikor, L., Rétvári, G. On providing fast protection with remote loop-free alternates. Telecommun Syst 60, 485–502 (2015). https://doi.org/10.1007/s11235-015-0006-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11235-015-0006-9