Xl: An efficient network routing algorithm

Kirill Igorevich 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

Network routing
Routing algorithms

Keywords

  • Link-state
  • Routing protocol

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

Xl : An efficient network routing algorithm. / Levchenko, Kirill Igorevich; Voelker, Geoffrey M.; Paturi, Ramamohan; Savage, Stefan.

In: Computer Communication Review, Vol. 38, No. 4, 01.12.2008, p. 15-26.

Research output: Contribution to journalConference article

Levchenko, Kirill Igorevich ; Voelker, Geoffrey M. ; Paturi, Ramamohan ; Savage, Stefan. / Xl : An efficient network routing algorithm. In: Computer Communication Review. 2008 ; Vol. 38, No. 4. pp. 15-26.
@article{3f2bed18f0e14715807ffc53c76a8ecb,
title = "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.",
keywords = "Link-state, Routing protocol",
author = "Levchenko, {Kirill Igorevich} and Voelker, {Geoffrey M.} and Ramamohan Paturi and Stefan Savage",
year = "2008",
month = "12",
day = "1",
doi = "10.1145/1402946.1402962",
language = "English (US)",
volume = "38",
pages = "15--26",
journal = "Computer Communication Review",
issn = "0146-4833",
publisher = "Association for Computing Machinery (ACM)",
number = "4",

}

TY - JOUR

T1 - Xl

T2 - An efficient network routing algorithm

AU - Levchenko, Kirill Igorevich

AU - Voelker, Geoffrey M.

AU - Paturi, Ramamohan

AU - Savage, Stefan

PY - 2008/12/1

Y1 - 2008/12/1

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

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

KW - Link-state

KW - Routing protocol

UR - http://www.scopus.com/inward/record.url?scp=65249120689&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65249120689&partnerID=8YFLogxK

U2 - 10.1145/1402946.1402962

DO - 10.1145/1402946.1402962

M3 - Conference article

AN - SCOPUS:65249120689

VL - 38

SP - 15

EP - 26

JO - Computer Communication Review

JF - Computer Communication Review

SN - 0146-4833

IS - 4

ER -