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 (log N ) diameter DHT scheme with (1+ o (1))-congestion. FissionE shows that the DHT scheme with constant degree and constant congestion can achieve O (log N ) 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 2 N , and the average routing path length is about log 2 N , . The average path length of FissionE is shorter than CAN or Koorde with the same degree when the P2P network is large scale.