EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management

Download: pdf, ps .

“EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management” by Ben Leong, Barbara Liskov, and Erik D. Demaine. MIT Technical Report MIT-LCS-TR-963, (Cambridge, MA), Aug. 2004.

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 traff{}ic 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 in general 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.

Download: pdf, ps .

BibTeX entry:

@techreport{leong04epichord-techreport,
   author = {Ben Leong and Barbara Liskov and Erik D. Demaine},
   title = {EpiChord: Parallelizing the Chord Lookup Algorithm with
	Reactive Routing State Management},
   institution = {MIT},
   type = {Technical Report},
   number = {MIT-LCS-TR-963},
   address = {Cambridge, MA},
   month = aug,
   year = {2004}
}