Xl: an efficient network routing algorithm

ABSTRACT

In this paper, we present a new link-state routing algorithm called Approximate Link state (XL) aimed at increasing routing efficiency by suppressing updates from parts of the network. We prove that three simple criteria for update propagation are sufficient to guarantee soundness, completeness and bounded optimality for any such algorithm. We show, via simulation, that XL significantly outperforms standard link-state and distance vector algorithms - in some cases reducing overhead by more than an order of magnitude - while having negligible impact on path length. Finally, we argue that existing link-state protocols, such as OSPF, can incorporate XL routing in a backwards compatible and incrementally deployable fashion.

REFERENCES

• 1: Abilene interior-routing metrics. http://noc.net.internet2.edu, March 2006.
• 2: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: 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
• 4: C. Cheng , R. Riley , S. P. R. Kumar , J. J. Garcia-Luna-Aceves, A loop-free extended Bellman-Ford routing protocol without bouncing effect, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.224-236, Sep. 1989
• 5: Cisco Systems. Introduction to EIGRP. Document ID 13669.
• 6: Cisco Systems. OSPF Design Guide. Document ID 7039.
• 7: T. Clausen , P. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC Editor, 2003
• 8: V. Fayet, D. A. Khotimsky, and T. Przygienda. Hop-by-hop routing with node-dependent topology information. In Proceedings of The Eighteenth INFOCOM Conference, pages 79--87, 1999.
• 9: D. Fedyk and P. Bottorff. Provider link state bridging (PLSB). IEEE Draft, 2007.
• 10: 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]
• 11: F. E. Heart, A. McKenzie, J. M. McQuillan, and D. C. Walden. ARPANET completion report. Technical Report 4799, Bolt, Baranek and Newman, 1978.
• 12: P. A. Humblet. Another adaptive distributed shortest path algorithm. IEEE Transactions on Communications, 39(6):995--1003, June 1991.
• 13: Gianluca Iannaccone , Chen-nee Chuah , Richard Mortier , Supratik Bhattacharyya , Christophe Diot, Analysis of link failures in an IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637238]
• 14: IEEE 802.11s draft standard, 2007.
• 15: K. Ishiguro, V. Manral, A. Davey, and A. Lindem. Traffic engineering extensions to OSPF version 3. IETF Draft, 2007.
• 16: A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen. Scalable routing strategies for ad hoc wireless networks. IEEE Journal on Selected Areas in Communication, 17(8):1369--1379, August 1999.
• 17: J. M. Jaffe and F. H. Moss. A responsive distributed routing algorithm for computer networks. IEEE Transactions on Communications, COM-30(7):1758--1762, July 1982.
• 18: Priya Mahadevan , Calvin Hubble , Dmitri Krioukov , Bradley Huffaker , Amin Vahdat, Orbis: rescaling degree correlations to generate annotated internet topologies, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 19: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 20: G. Malkin. RFC 2453: RIP version 2, 1998.
• 21: J. M. McQuillan, G. Falk, and I. Richer. A review of the development and performance of the ARPANET routing algorithm. IEEE Transactions on Communications, COM-26(12):1802--1811, Dec 1978.
• 22: J. M. McQuillan, I. Richer, and E. C. Rosen. The new routing algorithm for the ARPANET. IEEE Transactions on Communications, 28(5):711--719, May 1980.
• 23: P. M. Merlin and A. Segall. A failsafe distributed routing protocol. IEEE Transactions on Communications, COM-27(9):1280--1287, September 1979.
• 24: J. Moy. RFC 2328: OSPF version 2, 1998.
• 25: Yasuhiro Ohara , Manav Bhatia , Nakamura Osamu , Jun Murai, Route Flapping Effects on OSPF, Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), p.232, January 27-31, 2003
• 26: A Performance Comparison of the Temporally-Ordered Routing Algorithm and Ideal Link-State Routing, Proceedings of the Third IEEE Symposium on Computers & Communications, p.592, June 30-July 02, 1998
• 27: P. Pillay-Esnault. OSPF Refresh and Flooding Reduction in Stable Topologies. RFC 4136, 2005.
• 28: B. Rajagopalan , M. Fairman, A new responsive distributed shortest-path rounting algorithm, Symposium proceedings on Communications architectures & protocols, p.237-246, September 25-27, 1989, Austin, Texas, United States
• 29: S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269--287, September 1983.
• 30: Aman Shaikh , Chris Isett , Albert Greenberg , Matthew Roughan , Joel Gottlieb, A case study of OSPF behavior in a large enterprise network, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637236]
• 31: M. Thorup. OSPF Areas Considered Harmful. Private paper, Apr 2003.
• 32: A. Zinin and M. Shand. Flooding Optimizations in Link-state Routing Protocols. IETF Draft, 2000.

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
link-state, routing protocol