Access Restriction

Author Lakshminarayanan, Karthik ♦ Rangan, Murali ♦ Anderson, Tom ♦ Caesar, Matthew ♦ Shenker, Scott ♦ Stoica, Ion
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Protocols ♦ Internet routing ♦ Convergence
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.
Description Affiliation: University of California at Berkeley, Berkeley, CA (Lakshminarayanan, Karthik; Caesar, Matthew; Rangan, Murali; Shenker, Scott; Stoica, Ion) || University of Washington, Seattle, WA (Anderson, Tom)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1993-07-01
Publisher Place New York
Journal ACM SIGCOMM Computer Communication Review (CCRV)
Volume Number 37
Issue Number 4
Page Count 12
Starting Page 241
Ending Page 252

Open content in new tab

   Open content in new tab
Source: ACM Digital Library