EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management
EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management
复制标题
DOI：
10.1016/j.comcom.2005.10.002
复制
发表时间：
2006-05-31
影响因子：
6
通讯作者：
Demaine, Erik D.
中科院分区：
文献类型：
--
作者：
Leong, Ben;Liskov, Barbara;Demaine, Erik D.
EpiChord是一种分布式哈希表查找算法，它证明了我们可以消除现有分布式哈希表拓扑上每节点O(Logn)状态的限制，从而使用一种新的反应式路由状态维护策略来实现显著更好的查找性能和弹性，该策略将网络维护成本分摊到现有的查找中，并通过发出并行查询来实现。我们的技术允许我们设计一类新的无限状态的每节点分布式哈希表，它能够自然地适应广泛的查找工作负载。EpiChord能够在查找密集型负载下获得O(1)跳的查找性能，即使在最坏的情况下也能达到至少O(Logn)跳的查找性能(尽管预计它的平均性能会更好)。我们的反应式路由状态维护策略使我们能够用适度的带宽来维护大量的路由状态，而并行查询则用于减少查找延迟并允许我们避免代价高昂的查找超时。通常，EpiChord利用通过观察查找流量收集的信息来提高查找性能，并且仅在必要时发送网络探测。节点主要通过观察网络流量来填充缓存，缓存条目在固定的生命周期后被刷新。我们的模拟表明，通过每次查找只发出三个异步并行查询，我们的方法可以将查找延迟和路径长度减少3倍。此外，我们证明了我们能够以最小的额外通信开销获得这一结果，并且在一定的查找工作量范围内，每次查找产生的消息数量不超过相应的顺序Chord查找算法的消息数量。我们还提出了一种新的令牌传递稳定方案，该方案可以自动检测和修复全局路由不一致。(C)2005年，爱思唯尔出版。
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.