Title :
Moore: An Extendable Peer-to-Peer Network Based on Incomplete Kautz Digraph with Constant Degree
Author :
Guo, Deke ; Wu, Jie ; Chen, Honghui ; Luo, Xueshan
Author_Institution :
Nat. Univ. of Defense Technol., Changsha
Abstract :
The topological properties of peer-to-peer overlay networks are critical factors that dominate the performance of these systems. Several non-constant and constant degree interconnection networks have been used as topologies of many peer-to-peer networks. One of these has many desirable properties: the Kautz digraph. Unlike interconnection networks, peer-to-peer networks need a topology with an arbitrary size and degree, but the complete Kautz digraph does not possess these properties. In this paper, we propose Moore: the first effective and practical peer-to-peer network based on the incomplete Kautz digraph with O(log d N) diameter and constant degree under a dynamic environment. The diameter and average routing path length are [log d (N) - log d (1 + 1/d)] and log d N, respectively, and are shorter than that of CAN, butterfly, and cube-connected-cycle. They are close to that of complete de Bruijn and Kautz digraphs. The message cost of node joining and departing operations are at most 2.5 d log d N and (2.5 d + 1) log d N, and only d and 2d nodes need to update their routing tables. Moore can achieve optimal diameter, high performance, good connectivity and low congestion evaluated by formal proofs and simulations.
Keywords :
directed graphs; peer-to-peer computing; telecommunication network routing; telecommunication network topology; Kautz digraph; Moore network; interconnection network; network topology; peer-to-peer overlay network; routing table; Communications Society; Costs; Educational institutions; Hypercubes; Laboratories; Management information systems; Multiprocessor interconnection networks; Network topology; Peer to peer computing; Routing;
Conference_Titel :
INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE
Conference_Location :
Anchorage, AK
Print_ISBN :
1-4244-1047-9
DOI :
10.1109/INFCOM.2007.101