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.
Title
Towards a Structured Underlay for Network Routing
Published
1905-06-26
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-04-1321
Type
Text
Extent
12 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
