research-article

Free access

Xl: an efficient network routing algorithm

Authors:

Kirill Levchenko,

Geoffrey M. Voelker,

Ramamohan Paturi,

Stefan SavageAuthors Info & Claims

SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 conference on Data communication

Pages 15 - 26

https://doi.org/10.1145/1402958.1402962

Published: 17 August 2008 Publication History

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]

D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris. Resilient overlay networks. In Proceedings of the 18th Symposium on Operating Systems Principles, pages 131--145, 2001.

Digital Library

[3]

J. Behrens and J. J. Garcia-Lunes-Aceves. Distributed, scalable routing based on link-state vectors. In Proceedings of the ACM SIGCOMM Conference, pages 136--147, 1994.

Digital Library

[4]

C. Cheng, R. Riley, S. P. R. Kumar, and J. J. Garcia-Lunes-Aceves. A loop-free extended Bellman-Ford routing protocol without bouncing effect. ACM SIGCOMM Computer Communication Review, 19(4):224--236, September 1989.

Digital Library

[5]

Cisco Systems. Introduction to EIGRP. Document ID 13669.

[6]

Cisco Systems. OSPF Design Guide. Document ID 7039.

[7]

T. H. Clausen and P. Jacquet. RFC 3626: Optimized Link State Routing protocol (OLSR), October 2003.

Digital Library

[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. Transactions on Networking, 1(1):130--141, Feb 1993.

Digital Library

[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]

G. Iannaccone, C. Chuah, R. Mortier, S. Bhattacharyya, and C. Diot. Analysis of link failures in an IP backbone. In Proceedings of the Second Internet Measurement Workshop, pages 237--242, 2002.

Digital Library

[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.

Digital Library

[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]

P. Mahadevan, C. Hubble, D. Krioukov, B. Huffaker, and A. Vahdat. Orbis: Rescaling degree correlations to generate annotated Internet topologies. In Proc. of the 2007 ACM SIGCOMM Conference, pages 325--336, 2007.

Digital Library

[19]

R. Mahajan, N. Spring, D. Wetherall, and T. Anderston. Inferring link weights using end-to-end measurements. In Proceedings of 2nd Internet Measurement Workshop, pages 231--236, 2002.

Digital Library

[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]

Y. Ohara, M. Bhatia, N. Osamu, and J. Murai. Route Flapping Effects on OSPF. In Proceedings of the 2003 Symposium on Applications and the Internet Workshops, 2003.

Digital Library

[26]

V. D. Park and M. S. Corson. A performance comparison of the temporally-ordered routing algorithm and ideal link-state routing. In Proceedings of the 3rd IEEE Symposium on Computers and Communications, pages 592--598, 1998.

Digital Library

[27]

P. Pillay-Esnault. OSPF Refresh and Flooding Reduction in Stable Topologies. RFC 4136, 2005.

[28]

B. Rajagopalan and M. Faiman. A new responsive distributed shortest-path routing algorithm. In Proceedings of the ACM SIGCOMM Conference, pages 237--246, 1989.

Digital Library

[29]

S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269--287, September 1983.

[30]

A. Shaikh, C. Isett, A. Greenberg, M. Roughan, and J. Gottlieb. A case study of OSPF behavior in a large enterprise network. In Proceedings of the 2nd Workshop on Internet Measurement, pages 217--230, 2002.

Digital Library

[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.

Cited By

Garg PGupta A(2016)Restoration Technique to Optimize Recovery Time for Efficient OSPF NetworkResearch Advances in the Integration of Big Data and Smart Computing10.4018/978-1-4666-8737-0.ch004(64-88)Online publication date: 2016
https://doi.org/10.4018/978-1-4666-8737-0.ch004
Raju VRao K(2016)Dynamic search technique used for improving passive source routing protocol in MANET2016 International Conference on Communication and Electronics Systems (ICCES)10.1109/CESYS.2016.7889968(1-6)Online publication date: Oct-2016
https://doi.org/10.1109/CESYS.2016.7889968
KIRIHA YNISHIHARA M(2013)Survey on Data Center Networking TechnologiesIEICE Transactions on Communications10.1587/transcom.E96.B.713E96.B:3(713-721)Online publication date: 2013
https://doi.org/10.1587/transcom.E96.B.713
Show More Cited By

Index Terms

Xl: an efficient network routing algorithm
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

Xl: an efficient network routing algorithm

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 ...
The Security Analysis and Attacks Detection of OSPF Routing Protocol
ICICTA '14: Proceedings of the 2014 7th International Conference on Intelligent Computation Technology and Automation

The widespread use of the Internet proposes great challenges for information security. Routing protocols are used to distribute network topology information among routers. Routers find the best route according to the topology information, and realize ...
Xl: a communication-efficient routing algorithm

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 conference on Data communication

August 2008

452 pages

ISBN:9781605581750

DOI:10.1145/1402958

General Chairs:
Victor Bahl
Microsoft Research
,
David Wetherall
Intel Research & University of Washington
,
Program Chairs:
Stefan Savage
University of California, San Diego
,
Ion Stoica
University of California, Berkeley

ACM SIGCOMM Computer Communication Review Volume 38, Issue 4
October 2008
436 pages
ISSN:0146-4833
DOI:10.1145/1402946
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM '08

Sponsor:

SIGCOMM '08: ACM SIGCOMM 2008 Conference

August 17 - 22, 2008

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
1,032
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Garg PGupta A(2016)Restoration Technique to Optimize Recovery Time for Efficient OSPF NetworkResearch Advances in the Integration of Big Data and Smart Computing10.4018/978-1-4666-8737-0.ch004(64-88)Online publication date: 2016
https://doi.org/10.4018/978-1-4666-8737-0.ch004
Raju VRao K(2016)Dynamic search technique used for improving passive source routing protocol in MANET2016 International Conference on Communication and Electronics Systems (ICCES)10.1109/CESYS.2016.7889968(1-6)Online publication date: Oct-2016
https://doi.org/10.1109/CESYS.2016.7889968
KIRIHA YNISHIHARA M(2013)Survey on Data Center Networking TechnologiesIEICE Transactions on Communications10.1587/transcom.E96.B.713E96.B:3(713-721)Online publication date: 2013
https://doi.org/10.1587/transcom.E96.B.713
Walraed-Sullivan MVahdat AMarzullo KAlmeroth KMathy LPapagiannaki KMisra V(2013)Aspen treesProceedings of the ninth ACM conference on Emerging networking experiments and technologies10.1145/2535372.2535383(85-96)Online publication date: 9-Dec-2013
https://dl.acm.org/doi/10.1145/2535372.2535383
Xu MHou MWang DYang J(2013)An efficient critical protection scheme for intra-domain routing using link characteristicsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2012.09.00657:1(117-133)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.comnet.2012.09.006
Zhao DWu CHu XLiu H(2013)LSC2: An extended link state protocol with centralized controlPeer-to-Peer Networking and Applications10.1007/s12083-013-0226-28:4(651-663)Online publication date: 30-Aug-2013
https://doi.org/10.1007/s12083-013-0226-2
Zhao DLiu HHu XWu C(2012)Towards network convergence and traffic engineering optimization2012 IEEE 31st International Performance Computing and Communications Conference (IPCCC)10.1109/PCCC.2012.6407656(448-455)Online publication date: Dec-2012
https://doi.org/10.1109/PCCC.2012.6407656
Muthuswamy PKar KGupta AKaraoglu HYuksel M(2012)ISPs as nodes or sets of links?2012 IEEE International Conference on Communications (ICC)10.1109/ICC.2012.6364492(2796-2800)Online publication date: Jun-2012
https://doi.org/10.1109/ICC.2012.6364492
Tang MZhang GSun YLiu JYang JLin T(2012)Integrating local and partial network view for routing on scale-free networksScience China Information Sciences10.1007/s11432-012-4655-y56:10(1-10)Online publication date: 17-Aug-2012
https://doi.org/10.1007/s11432-012-4655-y
Tarkoma S(2012)Distributed Publish/SubscribePublish/Subscribe Systems10.1002/9781118354261.ch7(145-175)Online publication date: 17-Jun-2012
https://doi.org/10.1002/9781118354261.ch7
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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 Publication

Media

Figures

Other

Tables

View Table of Contents