A novel constant degree and constant congestion DHT scheme for peer-to-peer networks

摘要

Degree, diameter and congestion are important measures of distributed hash table (DHT) schemes for peer-to-peer networks. Many proposed DHT schemes are based on some traditional interconnection topologies and the Kautz graph is a topology with good properties such as optimal network diameter. In this paper, FissionE, a novel DHT scheme based on the Kautz graph, is proposed. FissionE is the first constant degree and O(logN) diameter DHT scheme with (1+o(1))-congestion. FissionE shows that the DHT scheme with constant degree and constant congestion can achieve O(logN) diameter, which is better than the lower bound Ω(N~(1/d)) conjectured before. The average degree of FissionE is 4 and the diameter is 2*log_2N, and the average routing path length is about log_2N. The average path length of FissionE is shorter than CAN or Koorde with the same degree when the P2P network is large scale.