Title :
Quasi-Kautz Digraphs for Peer-to-Peer Networks
Author :
Guo, Deke ; Wu, Jie ; Liu, Yunhao ; Jin, Hai ; Chen, Hanhua ; Chen, Tao
Author_Institution :
Sch. of Comput. Sci. & Technol., Huazhong Univ. of Sci. & Technol., Wuhan, China
fDate :
6/1/2011 12:00:00 AM
Abstract :
The topological properties of peer-to-peer overlay networks are critical factors that dominate the performance of these systems. Several nonconstant and constant degree interconnection networks have been used as topologies of many peer-to-peer networks. The Kautz digraph is one of these topologies that have many desirable properties. Unlike interconnection networks, peer-to-peer networks need a topology with an arbitrary order and degree, but the 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 quasi-Kautz digraph with O(logd n) diameter and constant degree under a dynamic environment. The diameter and average routing path length, respectively, are shorter than that of CAN, butterfly, and cube-connected cycle, and are close to that of the de Bruijn and Kautz digraphs. The message cost of node joining and departing operations are at most 2.5dlogd n and (2.5d+1)logd 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; multiprocessor interconnection networks; peer-to-peer computing; telecommunication congestion control; telecommunication network routing; MOORE peer-to-peer network; average routing path length; constant degree interconnection network; de Bruijn digraph; departing operation; low congestion; message cost; node joining; peer-to-peer overlay network; quasiKautz digraph; topological property; Construction industry; Heuristic algorithms; Multiprocessor interconnection; Network topology; Peer to peer computing; Routing; Topology; Consensus; collision detection.; multiple access channel; mutual exclusion;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
DOI :
10.1109/TPDS.2010.161