TY - GEN
T1 - Achieving convergence-free routing using failure-carrying packets
AU - Lakshminarayanan, Karthik
AU - Caesar, Matthew
AU - Rangan, Murali
AU - Anderson, Tom
AU - Shenker, Scott
AU - Stoica, Ion
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Convergence
KW - Internet routing
KW - Protocols
UR - http://www.scopus.com/inward/record.url?scp=36949006050&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=36949006050&partnerID=8YFLogxK
U2 - 10.1145/1282380.1282408
DO - 10.1145/1282380.1282408
M3 - Conference contribution
AN - SCOPUS:36949006050
SN - 1595937137
SN - 9781595937131
T3 - ACM SIGCOMM 2007: Conference on Computer Communications
SP - 241
EP - 252
BT - ACM SIGCOMM 2007
T2 - ACM SIGCOMM 2007: Conference on Computer Communications
Y2 - 27 August 2007 through 30 August 2007
ER -