Graph-Theoretic Analysis of Kautz Topology and DHT Schemes
Graph-Theoretic Analysis of Kautz Topology and DHT Schemes
复制标题
Kautz 拓扑和 DHT 方案的图论分析
DOI：
10.1007/978-3-540-30141-7_45
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Jinshu Su
中科院分区：
文献类型：
--
作者：
Dongsheng Li;Xicheng Lu;Jinshu Su
许多针对点对点网络的分布式哈希表（DHT）方案都是基于一些传统的并行互连拓扑结构。本文证明了Kautz图是构造DHT格式的一个很好的静态拓扑结构。我们证明了Kautz图的最优直径和最优容错特性，并证明了在使用长路径路由算法时，Kautz图是（1+o(1)）)无拥塞的。然后，我们提出了一种新的基于Kautz图的DHT方案FissionE。FissionE是一个常数度，O（logN）直径和(1+ O(1))-无拥塞。FissionE表明，恒度、恒拥塞的DHT方案可以达到eo （logN）直径，优于之前推测的下限Ω（N1/d）。
Many proposed distributed hash table (DHT) schemes for peer-to-peer network are based on some traditional parallel interconnection topologies. In this paper, we show that the Kautz graph is a very good static topology to construct DHT schemes. We demonstrate the optimal diameter and optimal fault tolerance properties of the Kautz graph and prove that the Kautz graph is (1+o(1))-congestion-free when using the long path routing algorithm. Then we propose FissionE, a novel DHT scheme based on Kautz graph. FissionE is a constant degree,O(logN) diameter and (1+o(1))-congestion-free. FissionE shows that the DHT scheme with constant degree and constant congestion can achieveO(logN) diameter, which is better than the lower bound Ω(N1/d) conjectured before.