Xl: An efficient network routing algorithm

Kirill Levchenko, Geoffrey M. Voelker, Ramamohan Paturi, Stefan Savage

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)15-26
Number of pages12
JournalComputer Communication Review
Issue number4
StatePublished - 2008
Externally publishedYes
EventACM SIGCOMM 2008 Conference on Data Communication, SIGCOMM'08 - Seattle, WA, United States
Duration: Aug 17 2008Aug 22 2008


  • Link-state
  • Routing protocol

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Xl: An efficient network routing algorithm'. Together they form a unique fingerprint.

Cite this