More Web Proxy on the site http://driver.im/

research-article

Fast Rerouting Against Multi-Link Failures Without Topology Constraint

Authors:

Qi LiAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 26, Issue 1

Pages 384 - 397

https://doi.org/10.1109/TNET.2017.2780852

Published: 01 February 2018 Publication History

Abstract

Multi-link failures may incur heavy packet loss and degrade the network performance. Fast rerouting has been proposed to address this issue by enabling routing protections. However, the effectiveness and efficiency issues of fast rerouting are not well addressed. In particular, the protection performance of existing approaches is not satisfactory even if the overhead is high, and topology constraints need to be met for the approaches to achieve a complete protection. To optimize the efficiency, we first answer the question that whether label-free routing can provide a complete protection against arbitrary multi-link failures in any networks. We propose a model for interface-specific-routing which can be seen as a general label-free routing. We analyze the conditions under which a multi-link failure will induce routing loops. And then, we present that there exist some networks in which no interface-specific-routing ISR can be constructed to protect the routing against any $k$ -link failures $k \geq 2$ . Then, we propose a tunneling on demand TOD approach, which covers most failures with ISR, and activate tunneling only when failures cannot be detoured around by ISR. We develop algorithms to compute ISR properly so as to minimize the number of activated tunnels, and compute the protection tunnels if necessary. We prove that TOD can protect routing against any single-link failures and dual-link failures. We evaluate TOD by simulations with real-world topologies. The results show that TOD can achieve a near 100% protection ratio with small tunneling overhead for multi-link failures, making a better tradeoff than the state-of-the-art label-based approaches.

References

[1]

A. Markopoulou et al., "Characterization of failures in an operational IP backbone network," IEEE/ACM Trans. Netw., vol. 16, no. 4, pp. 749-762, Aug. 2008.

[2]

K. Lakshminarayanan et al., "Achieving convergence-free routing using failure-carrying packets," in Proc. ACM SIGCOMM, 2007, pp. 241-252.

[3]

S. Kini, S. Ramasubramanian, A. Kvalbein, and A. F. Hansen, "Fast recovery from dual-link or single-node failures in IP networks using tunneling," IEEE/ACM Trans. Netw., vol. 18, no. 6, pp. 1988-1999, Dec. 2010.

[4]

G. Robertson and S. Nelakuditi, "Handling multiple failures in IP networks through localized on-demand link state routing," IEEE Trans. Netw. Service Manage., vol. 9, no. 3, pp. 293-305, Sep. 2012.

[5]

B. Yang, J. Liu, S. Shenker, J. Li, and K. Zheng, "Keep forwarding: Towards K-link failure resilient routing," in Proc. IEEE INFOCOM, Apr./May 2014, pp. 1617-1625.

[6]

T. Elhourani, A. Gopalan, and S. Ramasubramanian, "IP fast rerouting for multi-link failures," in Proc. IEEE INFOCOM, Apr./May 2014, pp. 2148-2156.

[7]

T. Elhourani, A. Gopalan, and S. Ramasubramanian, "IP fast rerouting for multi-link failures," IEEE/ACM Trans. Netw., vol. 24, no. 5, pp. 3014-3025, Oct. 2016.

[8]

A. Gopalan and S. Ramasubramanian, "Multipath routing and dual link failure recovery in IP networks using three link-independent trees," in Proc. IEEE ANTS, Bengaluru, India, Dec. 2011, pp. 1-6.

[9]

S. S. Lor, R. Landa, R. Ali, and M. Rio, "Handling transient link failures using alternate next hop counters," in Proc. IFIP Netw., 2010, pp. 186-197.

[10]

J. Liu et al., "Ensuring connectivity via data plane mechanisms," in Proc. 10th USENIX Symp. Netw. Syst. Design Implement. (NSDI), 2013, pp. 113-126.

[11]

E. Gafni and D. Bertsekas, "Distributed algorithms for generating loop-free routes in networks with frequently changing topology," IEEE Trans. Commun., vol. COM-29, no. 1, pp. 11-18, Jan. 1981.

[12]

B. Stephens, A. L. Cox, and S. Rixner, "Plinko: Building provably resilient forwarding tables," in Proc. ACM HotNets, 2013, Art. no. 26.

[13]

G. T. Nguyen et al., "Slick packets," in Proc. ACM SIGMETRICS, 2011, pp. 245-256.

[14]

M. Motiwala, M. Elmore, N. Feamster, and S. Vempala, "Path splicing," in Proc. ACM SIGCOMM, 2008, pp. 27-38.

[15]

S. S. Lor, R. Landa, and M. Rio, "Packet re-cycling: Eliminating packet losses due to network failures," in Proc. ACM HotNets, 2010, Art. no. 2.

[16]

L. Ying and L. Yanpei, "A Characterization of embeddability of graphs on surfaces," Appl. Math.-J. Chin. Univ., vol. 13, no. 2, pp. 159-164, 1998.

[17]

K. Xi and H. J. Chao, "IP fast reroute for double-link failure recovery," in Proc. IEEE GLOBECOM, Nov./Dec. 2009, pp. 1-8.

[18]

B. Stephens, A. L. Cox, and S. Rixner, "Scalable multi-failure fast failover via forwarding table compression," in Proc. ACM Symp. SDN Res., 2016, Art. no. 9.

[19]

M. Shand and S. Bryant, IP Fast Reroute Framework, document RFC5714, IETF, Fremont, CA, USA, Jan. 2010.

[20]

A. Atlas and A. Zinin, Basic Specification for IP Fast Reroute: Loop-Free Alternates, document RFC5286, IETF, Fremont, CA, USA, Sep. 2008.

[21]

S. Nelakuditi, S. Lee, Y. Yu, and Z.-L. Zhang, "Failure insensitive routing for ensuring service availability," in Proc. IWQoS, 2003, pp. 287-304.

[22]

S. Nelakuditi, S. Lee, Y. Yu, Z. L. Zhang, and C. N. Chuah, "Fast local rerouting for handling transient link failures," IEEE/ACM Trans. Netw., vol. 15, no. 2, pp. 359-372, Apr. 2007.

[23]

B. Zhang, J. Bi, and J. Wu, "RPFP: IP fast ReRoute with providing complete protection and without using tunnels," in Proc. IEEE IWQoS, Jun. 2013, pp. 1-10.

[24]

P. Narvaez, K.-Y. Siu, and H.-Y. Tzeng, "New dynamic SPT algorithm based on a ball-and-string model," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 706-718, Dec. 2001.

[25]

P. Francois, C. Filsfils, J. Evans, and O. Bonaventure, "Achieving sub-second IGP convergence in large IP networks," ACM SIGCOMM Comput. Commun. Rev., vol. 35, no. 3, pp. 33-44, 2005.

[26]

P. Narvaez, "Routing reconfiguration in IP networks," Ph.D. dissertation, MIT, Cambridge, MA, USA, 2000.

[27]

J. He and J. Rexford, "Toward Internet-wide multipath routing," IEEE Netw., vol. 22, no. 2, pp. 16-21, Mar./Apr. 2008.

[28]

S. Ramasubramanian, H. Krishnamoorthy, and M. Krunz, "Disjoint multipath routing using colored trees," Comput. Netw., vol. 51, no. 8, pp. 2163-2180, 2007.

[29]

G. Jayavelu, S. Ramasubramanian, and O. Younis, "Maintaining colored trees for disjoint multipath routing under node failures," IEEE/ACM Trans. Netw., vol. 17, no. 1, pp. 346-359, Feb. 2009.

[30]

P. Mérindol, P. Francois, O. Bonaventure, S. Cateloin, and J.-J. Pansiot, "An efficient algorithm to enable path diversity in link state routing networks," Comput. Netw., vol. 55, no. 5, pp. 1132-1149, 2011.

[31]

H. Geng, X. Shi, X. Yin, and Z. Wang, "Dynamic distributed algorithm for computing multiple next-hops on a tree," in Proc. IEEE ICNP, Oct. 2013, pp. 1-10.

[32]

K.-W. Kwong, L. Gao, R. Guerin, and Z.-L. Zhang, "On the feasibility and efficacy of protection routing in IP networks," in Proc. IEEE INFOCOM, Mar. 2010, pp. 1235-1243.

[33]

D. Katz and D. Ward, Bidirectional Forwarding Detection (BFD) for IPv4 and IPv6 (Single Hop), document RFC 5881, IETF, Fremont, CA, USA, Jun. 2010.

[34]

P. Pan, G. Swallow, and A. Atlas, Fast Reroute Extensions to RSVPTE for LSP Tunnels, document RFC 4090, IETF, Fremont, CA, USA, May 2005.

[35]

P. Francois, "Improving the convergence of IP routing protocols," Ph.D. dissertation, Univ. Catholique de Louvain, Ottignies-Louvain-la-Neuve, Belgium, 2007.

[36]

P. Francois and O. Bonaventure, "An evaluation of IP-based fast reroute techniques," in Proc. ACM CoNEXT, 2005, pp. 244-245.

[37]

M. Gjoka, V. Ram, and X. Yang, "Evaluation of IP fast reroute proposals," in Proc. IEEE COMSWARE, Jan. 2007, pp. 1-8.

[38]

A. Li, P. Francois, and X. Yang, "On improving the efficiency and manageability of NotVia," in Proc. ACM CoNEXT, 2007, Art. no. 26,.

[39]

M. Menth, M. Hartmann, R. Martin, T. Čičic, and A. Kvalbein, "Loopfree alternates and not-via addresses: A proper combination for IP fast reroute?" Comput. Netw., vol. 54, no. 8, pp. 1300-1315, 2010.

[40]

G. Rétvári, J. Tapolcai, G. Enyedi, and A. Császár, "IP fast ReRoute: Loop free alternates revisited," in Proc. IEEE INFOCOM, Apr. 2011, pp. 2948-2956.

[41]

M. Xu, Y. Yang, and Q. Li, "Selecting shorter alternate paths for tunnel-based IP fast ReRoute in linear time," Comput. Netw., vol. 56, no. 2, pp. 845-857, 2012.

[42]

M. Chiesa et al., "On the resiliency of static forwarding tables," IEEE/ACM Trans. Netw., vol. 25, no. 2, pp. 1133-1146, Apr. 2016.

[43]

G. Enyedi, G. Rétvári, and T. Cinkler, "A novel loop-free IP fast reroute algorithm," in Proc. EUNICE, vol. 4606. 2007, pp. 111-119.

[44]

J. Feigenbaum et al., "Brief announcement: On the resilience of routing tables," in Proc. ACM PODC, 2012, pp. 237-238.

[45]

J. Edmonds, "Optimum branchings," J. Res. Nat. Bureau Standards, vol. 71B, no. 4, pp. 233-240, 1967.

[46]

N. Spring, R. Mahajan, D. Wetherall, and T. Anderson, "Measuring ISP topologies with Rocketfuel," IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 2-16, Feb. 2004.

[47]

C. Guo et al., "BCube: A high performance, server-centric network architecture for modular data centers," ACM SIGCOMM Comput. Commun. Rev., vol. 39, no. 4, pp. 63-74, 2009.

[48]

OpenFlow Switch Specification Version 1.5.1. Accessed: Mar. 26, 2015. [Online]. Available: https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-switchv1.5.1.pdf

Cited By

Giarrè FHadjadj-Aoul Y(2024)Exploring the effectiveness of service migration strategies for virtual network embeddingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110553250:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110553
Godinho NSilva HCurado MPaquete L(2022)A reconfigurable resource management framework for fog environmentsFuture Generation Computer Systems10.1016/j.future.2022.03.015133:C(124-140)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.future.2022.03.015
Yi BWang XHuang MHe Q(2022)A QoS Based Reliable Routing Mechanism for Service CustomizationJournal of Computer Science and Technology10.1007/s11390-021-0686-437:6(1492-1508)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11390-021-0686-4

Fast Rerouting Against Multi-Link Failures Without Topology Constraint
1. Networks
  1. Network protocols
    1. Network layer protocols

Recommendations

Fast local rerouting for handling transient link failures

Link failures are part of the day-to-day operation of a network due to many causes such as maintenance, faulty interfaces, and accidental fiber cuts. Commonly deployed link state routing protocols such as OSPF react to link failures through global link ...
OSPF-based fast reroute for BGP link failures
GLOBECOM'09: Proceedings of the 28th IEEE conference on Global telecommunications

The Border Gateway Protocol (BGP) is one of the key components of today's Internet infrastructure. Many ISPs rely on BGP for convergence of inter-domain routes upon BGP link failures. However, the convergence of BGP requires several seconds of downtime, ...
IP Fast Rerouting for Multi-Link Failures

IP fast reroute methods are used to recover packets in the data plane upon link failures. Previous work provided methods that guarantee failure recovery from at most two-link failures. We develop an IP fast reroute method that employs rooted arc-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 26, Issue 1

February 2018

644 pages

ISSN:1063-6692

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 01 February 2018

Published in TON Volume 26, Issue 1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
83
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Giarrè FHadjadj-Aoul Y(2024)Exploring the effectiveness of service migration strategies for virtual network embeddingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110553250:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110553
Godinho NSilva HCurado MPaquete L(2022)A reconfigurable resource management framework for fog environmentsFuture Generation Computer Systems10.1016/j.future.2022.03.015133:C(124-140)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.future.2022.03.015
Yi BWang XHuang MHe Q(2022)A QoS Based Reliable Routing Mechanism for Service CustomizationJournal of Computer Science and Technology10.1007/s11390-021-0686-437:6(1492-1508)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11390-021-0686-4
Liu BYu PXue-song QShi L(2020)Survivability-aware routing restoration mechanism for smart grid communication network in large-scale failuresEURASIP Journal on Wireless Communications and Networking10.1186/s13638-020-1653-42020:1Online publication date: 19-May-2020
https://dl.acm.org/doi/10.1186/s13638-020-1653-4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents