|
NSDI '04 — Abstract
Pp. 113–126 of the Proceedings
Efficient Routing for Peer-to-Peer Overlays
Anjali Gupta, Barbara Liskov, and Rodrigo Rodrigues, MIT Computer Science and Artificial Intelligence Laboratory
Abstract
Most current peer-to-peer lookup schemes keep
a small amount of routing state per node, typically
logarithmic in the number of overlay nodes. This design assumes that routing information at each member node must be kept small, so that the bookkeeping required to respond to system membership
changes is also small, given that aggressive membership dynamics are expected. As a consequence,
lookups have high latency as each lookup requires
contacting several nodes in sequence.
In this paper, we question these assumptions by
presenting two peer-to-peer routing algorithms with
small lookup paths. First, we present a one-hop
routing scheme. We show how to disseminate information about membership changes quickly enough
so that nodes maintain accurate routing tables with
complete membership information. We also deduce
analytic bandwidth requirements for our scheme that
demonstrate its feasibility.
We also propose a two-hop routing scheme for
large scale systems of more than a few million nodes,
where the bandwidth requirements of one-hop routing can become too large. This scheme keeps a xed
fraction of the total routing state on each node, chosen such that the rst hop has low latency, and thus
the additional delay is small.
We validate our analytic model using simulation
results that show that our algorithms can maintain
routing information su ciently up-to-date such that
a large fraction (e.g., 99%) of the queries will succeed without being re-routed.
- View the full text of this paper in HTML and PDF.
The Proceedings are published as a collective work, © 2004 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.
