Matthew Caesar, Miguel Castro and Antony Rowstron

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1321
2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1321.pdf

Structured peer-to-peer overlays have recently been developed with low stretch and overheads that increase with the logarithm of the number of nodes in the system. In this paper we develop a new network-layer routing protocol that leverages the design of these overlays to achieve their desirable scaling and robustness properties. The key difficulty in this approach is that these overlays typically assume an underlying network layer transport such as IP to provide connectivity between overlay nodes. We solve this problem with a layered approach: the overlay layer constructs and maintain overlay routes, and the underlay layer constructs paths between the overlay nodes. This technique maintains the desirable scaling properties of a structured overlay without reliance on IP transport. In particular, our results indicate that (i) overhead and stretch increase with the logarithm of the number of nodes in the system (ii) these performance metrics remain stable and the system maintains consistency under churn.

BibTeX citation:

@techreport{Caesar:CSD-04-1321,
    Author = {Caesar, Matthew and Castro, Miguel and Rowstron, Antony},
    Title = {Towards a Structured Underlay for Network Routing},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/6500.html},
    Number = {UCB/CSD-04-1321},
    Abstract = {Structured peer-to-peer overlays have recently been developed with low stretch and overheads that increase with the logarithm of the number of nodes in the system. In this paper we develop a new network-layer routing protocol that leverages the design of these overlays to achieve their desirable scaling and robustness properties. The key difficulty in this approach is that these overlays typically assume an underlying network layer transport such as IP to provide connectivity between overlay nodes. We solve this problem with a layered approach: the overlay layer constructs and maintain overlay routes, and the underlay layer constructs paths between the overlay nodes. This technique maintains the desirable scaling properties of a structured overlay without reliance on IP transport. In particular, our results indicate that (i) overhead and stretch increase with the logarithm of the number of nodes in the system (ii) these performance metrics remain stable and the system maintains consistency under churn.}
}

EndNote citation:

%0 Report
%A Caesar, Matthew
%A Castro, Miguel
%A Rowstron, Antony
%T Towards a Structured Underlay for Network Routing
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1321
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/6500.html
%F Caesar:CSD-04-1321