Achieving convergence-free routing using failure-carrying packets

ABSTRACT

Current distributed routing paradigms (such as link-state, distance-vector, and path-vector) involve a convergence process consisting of an iterative exploration of intermediate routes triggered by certain events such as link failures. The convergence process increases router load, introduces outages and transient loops, and slows reaction to failures. We propose a new routing paradigm where the goal is not to reduce the convergence times but rather to eliminate the convergence process completely. To this end, we propose a technique called Failure-Carrying Packets (FCP) that allows data packets to autonomously discover a working path without requiring completely up-to-date state in routers. Our simulations, performed using real-world failure traces and Rocketfuel topologies, show that: (a) the overhead of FCP is very low, (b) unlike traditional link-state routing (such as OSPF), FCP can provide both low loss-rate as well as low control overhead, (c) compared to prior work in backup path pre-computations, FCP provides better routing guarantees under failures despite maintaining lesser state at the routers.

REFERENCES

• 1: Abilene observatory data collections. 2006. http://abilene.internet2.edu/observatory/.
• 2: Anonymized OC48 traces, CAIDA. 2006.http://data.caida.org/.
• 3: C. Alaettinoglu, V. Jacobson, and H. Yu. Towards Millisecond IGP Convergence. IETF Draft, 2000.
• 4: A. Atlas. U-turn Alternates for IP/LDP Fast-Reroute. Internet Draft draft-atlas-ip-local-protect-uturn-03.txt, February 2006.
• 5: Jochen Behrens , J. J. Garcia-Luna-Aceves, Distributed, scalable routing based on link-state vectors, Proceedings of the conference on Communications architectures, protocols and applications, p.136-147, August 31-September 02, 1994, London, United Kingdom
• 6: S. Bryant, C. Filsls, S. Previdi, and M. Shand. IP Fast Reroute using Tunnels. Internet draft draft-bryant-ipfrr-tunnels-01.txt, Oct 2004.
• 7: S. Bryant and M. Shand. A Framework for Loop-free Convergence. Internet Draft draft-bryant-shand-lf-conv-frmwk-03, October 2006.
• 8: S. Bryant, M. Shand, and S. Previdi. IP Fast Reroute Using Not-via Addresses. Internet Draft draft-bryant-shand-ipfrr-notvia-addresses-03, 2006.
• 9: Matthew Caesar , Donald Caldwell , Nick Feamster , Jennifer Rexford , Aman Shaikh , Jacobus van der Merwe, Design and implementation of a routing control platform, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.15-28, May 02-04, 2005
• 10: G. Choudhury. Prioritized Treatment of Specific OSPF Version 2 Packets and Congestion Avoidance. RFC 4222, October 2005.
• 11: G. Choudhury, A. Atlas, R. Torvi, C. Martin, B. Imhoff, and D. Fedyk. Basic Specification for IP Fast-Reroute: Loop-free Alternates. IETF draft, 2005.
• 12: Bruce Davie , Yakov Rekhter, MPLS: technology and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 13: Paolo Giulio Franciosa , Daniele Frigioni , Roberto Giaccio, Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.33-46, February 27-March 01, 1997
• 14: Pierre Francois , Olivier Bonaventure, An evaluation of IP-based fast reroute techniques, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, October 24-27, 2005, Toulouse, France [doi>10.1145/1095921.1095962]
• 15: P. Francois and O. Bonaventure. Avoiding transient loops during IGP convergence in IP networks. In Proc. INFOCOM, 2005.
• 16: J. J. Garcia-Lunes-Aceves, Loop-free routing using diffusing computations, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.130-141, Feb. 1993 [doi>10.1109/90.222913]
• 17: Yih-Chun Hu , Adrian Perrig , Marvin Sirbu, SPV: secure path vector routing for securing BGP, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 18: G. Iannaccone, C. Chuah, S. Bhattacharyya, and C. Diot. Feasibility of IP Restoration in a Tier-1 Backbone. IEEE Networks, Special Issue, March 2004.
• 19: Juniper-Networks. Configure alternate backup paths using fate-sharing. 2005. http://www.juniper.net/techpubs/software/junos/junos53/swconfig53mpls-apps/html/mpls-signaled-config37.html.
• 20: N. Kushman, S. Kandula, D. Katabi, and B. Maggs. R-BGP: Staying Connected in a Connected World. In Proc. NSDI, 2007.
• 21: Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 22: J. Moy, OSPF Database Overflow, RFC Editor, 1995
• 23: J. T. Moy. OSPF Version 2. RFC 2328, April 1998.
• 24: J. T. Moy. OSPF complete implementation. In Addison-Wesley, New York, 2001.
• 25: Paolo Narváez , Kai-Yeung Siu , Hong-Yi Tzeng, New dynamic algorithms for shortest path tree computation, IEEE/ACM Transactions on Networking (TON), v.8 n.6, p.734-746, Dec. 2000 [doi>10.1109/90.893870]
• 26: S. Nelakuditi, S. Lee, Y. Yu, J. Wang, Z. Zhong, G. -H. Lu, and Z. -L. Zhang. Blacklist-Aided Forwarding in Static Multihop Wireless Networks. In Proc. of SECON, 2005.
• 27: Srihari Nelakuditi , Sanghwan Lee , Yinzhe Yu , Zhi-Li Zhang , Chen-Nee Chuah, Fast local rerouting for handling transient link failures, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.359-372, April 2007 [doi>10.1109/TNET.2007.892851]
• 28: P. Pan, G. Swallow, and A. Atlas. Fast Reroute Extensions to RSVP-TE for LSP Tunnels. RFC 4090, May 2005.
• 29: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 30: Ion Stoica , Hui Zhang, Stateless core: a scalable approach for quality of service in the internet, Carnegie Mellon University, Pittsburgh, PA, 2000
• 31: Lakshminarayanan Subramanian , Randy H. Katz , Volker Roth , Scott Shenker , Ion Stoica, Reliable broadcast in unknown fixed-identity networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073880]
• 32: R. Teixeira, N. Duffield, J. Rexford, and M. Roughan. Traffic Matrix Reloaded: Impact of Routing Changes. In Proc. of PAM, 2005.
• 33: Renata Teixeira , Aman Shaikh , Tim Griffin , Geoffrey M. Voelker, Network sensitivity to hot-potato disruptions, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 34: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 35: Feng Wang , Lixin Gao, On inferring and characterizing internet routing policies, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948208]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

General Terms:
Algorithms, Design, Performance

Keywords:
convergence, internet routing, protocols