SKY:Efficient peer-to-peer networks based on distributed Kautz graphs  

作　　者：ZHANG YiMing LU XiCheng LI DongSheng 

机构地区：[1]National Laboratory for Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China

出　　处：《Science in China(Series F)》2009年第4期588-601,共14页中国科学（F辑英文版）

基　　金：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.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.

关 键 词：peer-to-peer network Kautz graph constant degree topology maintenance D-Kautz graph 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O157.5[自动化与计算机技术—计算机科学与技术]