| Publication Title: |
EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management |
| Publication Author: |
Leong, Ben |
| Additional Authors: |
Barbara Liskov, Erik D. Demaine |
| LCS Document Number: |
MIT-LCS-TR-963 |
| Publication Date: |
8-13-2004 |
| LCS Group: |
Programming Methodology |
| Additional URL: |
|
| Abstract: |
| EpiChord is a DHT lookup algorithm that demonstrates that we can
remove the O(log n)-state-per-node restriction on existing DHT
topologies to achieve significantly better lookup performance and
resilience using a novel reactive routing state maintenance strategy
that amortizes network maintenance costs into existing lookups and by
issuing parallel queries. Our technique allows us to design a new
class of unlimited-state-per-node DHTs that is able to adapt naturally
to a wide range of lookup workloads. EpiChord is able to achieve
O(1)-hop lookup performance under lookup-intensive workloads, and at
least O(log n)-hop lookup performance under churn-intensive
workloads even in the worst case (though it is expected to perform
better on average).
Our reactive routing state maintenance strategy allows us to maintain
large amounts of routing state with only a modest amount of bandwidth,
while parallel queries serve to reduce lookup latency and allow us to
avoid costly lookup timeouts. In general, EpiChord exploits the
information gleaned from observing lookup traffic to improve lookup
performance, and only sends network probes when necessary. Nodes
populate their caches mainly from observing network traffic, and
cache entries are flushed from the cache after a fixed lifetime.
Our simulations show that with our approach can reduce both lookup
latencies and pathlengths by a factor of 3 by issuing only 3 queries
asynchronously in parallel per lookup. Furthermore, we show that we
are able to achieve this result with minimal additional communication
overhead and the number of messages generated per lookup is no more
than that for the corresponding sequential Chord lookup algorithm over
a range of lookup workloads. We also present a novel token-passing
stabilization scheme that automatically detects and repairs global
routing inconsistencies. |
| To obtain this publication: |
|
|
|
To purchase a printed copy of this publication please contact
MIT
Document Services.
|