Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Exploiting Routing Redundancy Using a Wide-area Overlay

Ben Y. Zhao, Ling Huang, Anthony D. Joseph and John D. Kubiatowicz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-02-1215
November 2002

http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/CSD-02-1215.pdf

As new and interesting peer-to-peer applications combine with advancements in networking technology, they are reaching millions of users across the globe. Numerous studies have shown, however, that loss of connectivity is common on the wide-area network, due to hardware and software failures, and network misconfigurations. Despite the natural redundancy present in underlying network links, the current IP layer fails to recognize and recover from these frequent failures in a timely fashion. This paper presents fault-tolerant routing on the Tapestry overlay network, which exploits existing network redundancy by dynamically switching traffic onto precomputed alternate routes. Furthermore, messages in our system can be duplicated and multicast "around" network congestion and failure hotspots with rapid reconvergence to drop duplicates. Our simulations show fault-tolerant Tapestry to be highly effective at circumventing link and node failures, with reasonable cost in terms of additional routing latency and bandwidth cost.


BibTeX citation:

@techreport{Zhao:CSD-02-1215,
    Author = {Zhao, Ben Y. and Huang, Ling and Joseph, Anthony D. and Kubiatowicz, John D.},
    Title = {Exploiting Routing Redundancy Using a Wide-area Overlay},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2002},
    Month = {Nov},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/5692.html},
    Number = {UCB/CSD-02-1215},
    Abstract = {As new and interesting peer-to-peer applications combine with advancements in networking technology, they are reaching millions of users across the globe. Numerous studies have shown, however, that loss of connectivity is common on the wide-area network, due to hardware and software failures, and network misconfigurations. Despite the natural redundancy present in underlying network links, the current IP layer fails to recognize and recover from these frequent failures in a timely fashion. This paper presents fault-tolerant routing on the Tapestry overlay network, which exploits existing network redundancy by dynamically switching traffic onto precomputed alternate routes. Furthermore, messages in our system can be duplicated and multicast "around" network congestion and failure hotspots with rapid reconvergence to drop duplicates. Our simulations show fault-tolerant Tapestry to be highly effective at circumventing link and node failures, with reasonable cost in terms of additional routing latency and bandwidth cost.}
}

EndNote citation:

%0 Report
%A Zhao, Ben Y.
%A Huang, Ling
%A Joseph, Anthony D.
%A Kubiatowicz, John D.
%T Exploiting Routing Redundancy Using a Wide-area Overlay
%I EECS Department, University of California, Berkeley
%D 2002
%@ UCB/CSD-02-1215
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/5692.html
%F Zhao:CSD-02-1215