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