Karthik Kalambur Lakshminarayanan and Matthew Chapman Caesar and Murali Rangan and Thomas Anderson and Scott Shenker and Ion Stoica

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-28

February 22, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-28.pdf

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.

---

BibTeX citation:

@techreport{Lakshminarayanan:EECS-2007-28,
    Author= {Lakshminarayanan, Karthik Kalambur and Caesar, Matthew Chapman and Rangan, Murali and Anderson, Thomas and Shenker, Scott and Stoica, Ion},
    Title= {Achieving Convergence-Free Routing using Failure-Carrying Packets},
    Year= {2007},
    Month= {Feb},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-28.html},
    Number= {UCB/EECS-2007-28},
    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.},
}

EndNote citation:

%0 Report
%A Lakshminarayanan, Karthik Kalambur 
%A Caesar, Matthew Chapman 
%A Rangan, Murali 
%A Anderson, Thomas 
%A Shenker, Scott 
%A Stoica, Ion 
%T Achieving Convergence-Free Routing using Failure-Carrying Packets
%I EECS Department, University of California, Berkeley
%D 2007
%8 February 22
%@ UCB/EECS-2007-28
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-28.html
%F Lakshminarayanan:EECS-2007-28