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 Kaut...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 ? (N1/d) conjectured before. The average degree of FissionE is 4 and the diameter is 2*log2N, and the average routing path length is about log2N. The average path length of FissionE is shorter than CAN or Koorde with the same degree when the P2P network is large scale.展开更多
Many proposed P2P networks are based on traditional interconnection topologies. Given a static topology, the maintenance mechanism for node join/departure is critical to designing an efficient P2P network. Kautz graph...Many proposed P2P networks are based on traditional interconnection topologies. Given a static topology, the maintenance mechanism for node join/departure is critical to designing an efficient P2P network. Kautz graphs have many good properties such as constant degree, low congestion and optimal diameter. Due to the complexity in topology maintenance, however, to date there have been no effective P2P networks that are proposed based on Kautz graphs with base ~ 2. To address this problem, this paper presents the ＂distributed Kautz （D-Kautz） graphs＂, which adapt Kautz graphs to the characteristics of P2P networks. Using the D-Kautz graphs we further propose SKY, the first effective P2P network based on Kautz graphs with arbitrary base. The effectiveness of SKY is demonstrated through analysis and simulations.展开更多
基金the National Natural Science Foundation of China(Grant Nos.90412011,90104001) the National Basic Research Program ofChina(Grant No.2005CB321801)
文摘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 ? (N1/d) conjectured before. The average degree of FissionE is 4 and the diameter is 2*log2N, and the average routing path length is about log2N. The average path length of FissionE is shorter than CAN or Koorde with the same degree when the P2P network is large scale.
基金Supported partially by the National Natural Science Foundation of China (Grant Nos. 60673167 and 60703072)the Hunan Provincial Natural Science Foundation of China (Grant No. 08JJ3125)the National Basic Research Program of China (973) (Grant No. 2005CB321801)
文摘Many proposed P2P networks are based on traditional interconnection topologies. Given a static topology, the maintenance mechanism for node join/departure is critical to designing an efficient P2P network. Kautz graphs have many good properties such as constant degree, low congestion and optimal diameter. Due to the complexity in topology maintenance, however, to date there have been no effective P2P networks that are proposed based on Kautz graphs with base ~ 2. To address this problem, this paper presents the ＂distributed Kautz （D-Kautz） graphs＂, which adapt Kautz graphs to the characteristics of P2P networks. Using the D-Kautz graphs we further propose SKY, the first effective P2P network based on Kautz graphs with arbitrary base. The effectiveness of SKY is demonstrated through analysis and simulations.
