A performance vs. cost framework for evaluating DHT design tradeoffs under churn
A performance vs. cost framework for evaluating DHT design tradeoffs under churn
复制标题
DOI：
10.1109/infcom.2005.1497894
复制
发表时间：
2005-03
期刊：
影响因子：
--
通讯作者：
Li;Jeremy;R. Morris;Kaashoek;Thomer;Gil
中科院分区：
文献类型：
--
作者：
Li;Jeremy;R. Morris;Kaashoek;Thomer;Gil
分布式哈希表（DHT）协议包含了一些功能，可以在面临成员流失和持续变化的情况下实现查找请求的低延迟。这些协议特征可以包括有向标识符空间、并行查找、成员关系改变的主动泛洪以及用于维持准确路由的稳定化协议。此外，DHT协议的参数，可以调整，以实现不同的权衡之间的查找延迟和通信成本，由于维护流量。的功能和参数的相对重要性还没有得到很好的理解，因为大多数以前的工作评估静态网络上的协议。本文提出了一个性能与成本框架（PVC），允许设计人员比较不同的协议功能和参数值的影响。PVC将协议视为消耗一定量的网络带宽以实现一定的查找延迟，并有助于揭示协议使用额外网络资源来改善延迟的效率。为了证明PVC的价值，本文模拟了Chord，Kademlia，Kelips，OneHop和Tapestry在不同工作负载下的情况，并使用PVC来了解哪些功能在流失下更重要。PVC分析表明，有效地使用额外的带宽的关键是一个协议，以调整其路由表的大小。它还表明，路由表稳定是浪费，可以通过正常的查找流量的机会学习取代。这些见解结合起来表明，PVC是DHT设计师的宝贵工具。
Protocols for distributed hash tables (DHTs) incorporate features to achieve low latency for lookup requests in the face of churn, continuous changes in membership. These protocol features can include a directed identifier space, parallel lookups, pro-active flooding of membership changes, and stabilization protocols for maintaining accurate routing. In addition, DHT protocols have parameters that can be tuned to achieve different tradeoffs between lookup latency and communication cost due to maintenance traffic. The relative importance of the features and parameters is not well understood, because most previous work evaluates protocols on static networks. This paper presents a performance versus cost framework (PVC) that allows designers to compare the effects of different protocol features and parameter values. PVC views a protocol as consuming a certain amount of network bandwidth in order to achieve a certain lookup latency, and helps reveal the efficiency with which protocols use additional network resources to improve latency. To demonstrate the value of PVC, this paper simulates Chord, Kademlia, Kelips, OneHop, and Tapestry under different workloads and uses PVC to understand which features are more important under churn. PVC analysis shows that the key to efficiently using additional bandwidth is for a protocol to adjust its routing table size. It also shows that routing table stabilization is wasteful and can be replaced with opportunistic learning through normal lookup traffic. These insights combined demonstrate that PVC is a valuable tool for DHT designers.