Achieving convergence-free routing using failure-carrying packets

Karthik Lakshminarayanan, Matthew Caesar, Murali Rangan, Tom Anderson, Scott Shenker, Ion Stoica

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Current distributed routing paradigms (such as link-state, distance-vector, and path-vector) involve a convergence process consisting of an iterative exploration of intermediate routes triggered by certain events such as link failures. The convergence process increases router load, introduces outages and transient loops, and slows reaction to failures. We propose a new routing paradigm where the goal is not to reduce the convergence times but rather to eliminate the convergence process completely. To this end, we propose a technique called Failure-Carrying Packets (FCP) that allows data packets to autonomously discover a working path without requiring completely up-to-date state in routers. Our simulations, performed using real-world failure traces and Rocketfuel topologies, show that: (a) the overhead of FCP is very low, (b) unlike traditional link-state routing (such as OSPF), FCP can provide both low loss-rate as well as low control overhead, (c) compared to prior work in backup path pre-computations, FCP provides better routing guarantees under failures despite maintaining lesser state at the routers.

Original languageEnglish (US)
Title of host publicationACM SIGCOMM 2007
Subtitle of host publicationConference on Computer Communications
Pages241-252
Number of pages12
DOIs
StatePublished - 2007
Externally publishedYes
EventACM SIGCOMM 2007: Conference on Computer Communications - Kyoto, Japan
Duration: Aug 27 2007Aug 30 2007

Publication series

NameACM SIGCOMM 2007: Conference on Computer Communications

Other

OtherACM SIGCOMM 2007: Conference on Computer Communications
Country/TerritoryJapan
CityKyoto
Period8/27/078/30/07

Keywords

  • Convergence
  • Internet routing
  • Protocols

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Fingerprint

Dive into the research topics of 'Achieving convergence-free routing using failure-carrying packets'. Together they form a unique fingerprint.

Cite this