Xl: An efficient network routing algorithm

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

Research output: Contribution to journalConference article

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.

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

    Fingerprint

Keywords

  • Link-state
  • Routing protocol

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this