Achieving convergence-free routing using failure-carrying packets

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

Research output: Contribution to journalArticlepeer-review


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 lossrate as well as low control overhead, (c) compared to prior work in backup path precomputations, FCP provides better routing guarantees under failures despite maintaining lesser state at the routers.

Original languageEnglish (US)
Pages (from-to)241-252
Number of pages12
JournalComputer Communication Review
Issue number4
StatePublished - Oct 2007
Externally publishedYes


  • Convergence
  • Internet routing
  • Protocols

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


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

Cite this