EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management

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 chum-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 path lengths by a factor of 3 by issuing only three 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 work-loads. We also present a novel token-passing stabilization scheme that automatically detects and repairs global routing inconsistencies. (C) 2005 Published by Elsevier B.V.