基于Petersen图和Cayley图的P2P覆盖网络设计与分析
|
摘要
对等网络(Peer-to-Peer network,简称P2P网络)是在当前Internet环境下,采用对等计算模式工作的计算机网络,P2P网络本质上是一个分布式系统。目前,P2P网络系统的广泛应用推动了P2P技术的快速发展。P2P网络中的每个节点在网络中是平等的,它打破了传统的客户／服务器模式,不再有客户／服务器之分,网络中的任何节点既可以充当服务器,又可以充当客户机,它们之间都能够直接共享文件和传递信息。这样的网络连接充分利用了网络带宽,具有较高的可扩展性、容错性、自治性和自组织性,所有的这些使得P2P技术迅速发展成为计算机领域内的一项重要技术,在网络研究领域也越来越得到专家和学者的广泛重视。
P2P覆盖网络从拓扑结构的角度来说,主要分为两大类：结构化P2P覆盖网络和非结构化P2P覆盖网络。结构化P2P覆盖网络是在应用层基于特定静态拓扑图来构建的覆盖网络,它是依靠分布式哈希表(DHT)来准确定位信息和数据对象,网络中的每个节点维护一个包含邻居节点标识符和IP地址的路由表,查询请求和消息路由沿着覆盖网络中的路径路由到网络中的节点上；而非结构化P2P覆盖网络没有严格控制的拓扑结构,信息的定位和数据对象的定位是随意的,非结构化P2P覆盖网络使用洪泛、随机走、扩展环TTL搜索机制等随机地来查询网络节点上存储的内容信息,但这种随意性也符合一定的数学规律。本论文着重研究结构化P2P覆盖网络。
对结构化P2P覆盖网络的网络拓扑研究发现,基于特定的静态拓扑图所构造的P2P覆盖网络的性能,在很大程度上与该P2P覆盖网络应用层所依据的静态图的性质有很大关系。结构化P2P系统在选择静态拓扑图时,倾向于选择具有常数度和最优直径的静态图,像D2B和Koorde是依赖于常数度De Brujin图的；Viceroy是基于蝴蝶结构的常数度图；FissonE和Moore是建立在静态的常数度Kautz图上的等。可见,从图论的角度来研究常数度图的性质,是研究结构化P2P覆盖网络拓扑的一种方法。这些现有的结构化P2P系统所采用的静态拓扑图是常数度的图,在这些图中,图所构造的系统节点的度是常数的,节点的加入与离开过程都遵循一定的规则,而基于这些图所构造的系统节点,节点的负载均衡、动态性、容错性和路由效率不是很高,针对这些问题,本论文又设计了两个效率较高、负载均衡性较好的系统。
本论文在全面分析和讨论了现有的结构化P2P系统的静态拓扑的基础上,从图论的角度,把图的性质和P2P系统的性能联系起来,提出了更加有效的结构化P2P系统。其主要工作有：
(1)从现有P2P系统的研究入手,对目前的P2P系统进行了总结,并从图论的角度来研究静态拓扑图的性质,从而提出了一种新的基于改进的Petersen图的P2P覆盖网络——GPSG,并在此覆盖网络中引入了超节点机制。该系统融合了Petersen图、超节点和环的性质,使GPSG系统具有较高的动态性和容错性,并对所构造的GPSG覆盖网络进行了理论分析和实验仿真。我们从仿真实验中可以得到,基于双环的GPSG系统的负载均衡性略高于基于单环的Chord系统；GPSG系统中节点的加入时间较短,节点加入或离开GPSG系统时所消耗的消息代价要略小于Chord系统；且GPSG系统比Chord系统的路由效率要高。
(2)从研究另一类高对称图——Cayley图的性质入手,基于群的任意生成集来构造Cayley图,并提出了另一种高对称的结构化的P2P覆盖网络——CLG系统,这样所构造的系统具有高对称性、灵活性、模糊查询和负载均衡性,符合动态网络的变化特征,并从实验仿真的角度对基于Cayley图构建的CLG系统和基于常数度的deBrujin图(非Cayley化图)构建的D2B系统进行了比较。我们从仿真实验中可以看到,CLG系统比D2B系统负载均衡性要好；CLG系统比D2B系统具有更高的查找效率；且CLG系统中新节点的加入时间较短,从而证明了CLG系统具有较高的实用性。
最后,总结本论文的主要内容,并提出了下一步要研究的主要问题。
Peer-to-Peer network (P2P network) is work by adopting to the computing model of peer-to-peer in the current Internet environment, P2P overlay networks are distributed systems in nature. At present, the widely using of P2P network system is promoting the rapid development of P2P technology. Each node of the P2P network are equal in the network, they have broken the traditional client/server model, without the difference of the client and server. Any node in the network, which not only act as a server, but also act as a client, they are able to share files and transmit information between them. These network connections make full use of network bandwidth, and have very high scalability, good fault tolerance, autonomy and self-organization, all of which makes the rapid development of P2P technology to become an important technology of computer, and also become widely attention by more and more experts and scholars.
From the view of the network topology, the research of the P2P overlay network mainly divided into two classes:the structured P2P overlay network and unstructured P2P overlay network. The structured P2P overlay network is static based on the specific static topology graph to build overlay network on the application layer, which relying on a distributed hash table (DHT) to accurately locate data information and data objects, each peer maintains a small routing table consisting of its neighboring peers'NodeIDs and IP address. Lookup queries or message routing are forwarded across overlay paths to peers in a progressive manner; But the unstructured P2P overlay network topology is not strictly controlled, locating data information and data objects is arbitrary, the overlay networks organize peers using flooding or random walks or expanding-ring Time-To-Live (TTL) search, etc to query content stored by overlay peers, but this arbitrariness is also conform to certain mathematical laws. This paper is based on a structured P2P overlay network.
From the research on the network topology of Structured P2P overlay network, we found that the P2P overlay network basing on a specific static topology, to a large extent, whose performance is related to the properties of the static graph. When choosing the static topology graph of Structured P2P system, we are tend to choose the static graph with constant degree and optimal diameter, Such as the D2B system and Koorde system are dependent on constant-degree de Brujin graph; The Viceroy system is based on a butterfly structure constant-degree graph; The Moore system is based on a constant-degree Kautz graph and so on. So from the perspective of graph theory to study the properties of static graph, which is a method to research the network topology of the structured P2P overlay network. The static topology graph which used by these existing structured P2P systems is a constant degree graph. In these graphs, the degree of nodes is constant and the process of nodes' join and leave follows certain rules, but the nodes of system based on these constant static graphs, whose load balance, dynamic properties, fault tolerance and routing efficiency are not very high. Because of these problems, we designed two P2P systems, which have high efficiency and good load balance.
This paper comprehensively analyzes and discusses the existing structured P2P system which based on a static topology graph. From the perspective of graph theory, we combined the properties of graph with the performance of P2P systems, and proposed more effectively structured P2P system. Its main work includes:
First, we study the current P2P systems, and summarize the technology of the current P2P systems. And from the perspective of graph theory to study the properties of graph, and proposed a new P2P overlay network-GPSG, which based on improved Petersen graph. In GPSG system, we introduce the super node mechanism in this overlay network. This system combines the Petersen graph, super-nodes and the properties of the ring, so the GPSG system has a high dynamic and fault tolerance, in the last, we carried out theoretical analysis and experimental simulation of the GPSG system. From the results, we conclude that the GPSG system which based on double loops has higher load balance than the Chord system, which based on the single ring; the nodes of GPSG join the system shorter than the node of Chord, and the nodes join or leave the GPSG system consume less than the nodes of Chord system; and the routing efficiency of the GPSG system is higher than the Chord system.
Secondly, from studying the properties of another type of graph-Cayley graph, from the respective of constructing Cayley graph based on an arbitrary generating set of groups, we put forward an alternative high-symmetrical structure of the P2P overlay network-CLG, which have high symmetry, flexibility and load balance, which conform to the dynamic characteristics of the network. From the perspective of experimental simulation, we compared the CLG system that based on Cayley graph with the D2B system that based on de Brujin graph of constant degree. We can conclude from the simulation experiments that the CLG system has better load balance than the D2B system; CLG system has more search efficiency than the D2B system; and the new nodes of CLG system consume less time when they join the system, all that prove CLG system has higher availability.
At last, we summarized the main contents of this paper and present the following problems for future research.
P2P覆盖网络从拓扑结构的角度来说,主要分为两大类：结构化P2P覆盖网络和非结构化P2P覆盖网络。结构化P2P覆盖网络是在应用层基于特定静态拓扑图来构建的覆盖网络,它是依靠分布式哈希表(DHT)来准确定位信息和数据对象,网络中的每个节点维护一个包含邻居节点标识符和IP地址的路由表,查询请求和消息路由沿着覆盖网络中的路径路由到网络中的节点上；而非结构化P2P覆盖网络没有严格控制的拓扑结构,信息的定位和数据对象的定位是随意的,非结构化P2P覆盖网络使用洪泛、随机走、扩展环TTL搜索机制等随机地来查询网络节点上存储的内容信息,但这种随意性也符合一定的数学规律。本论文着重研究结构化P2P覆盖网络。
对结构化P2P覆盖网络的网络拓扑研究发现,基于特定的静态拓扑图所构造的P2P覆盖网络的性能,在很大程度上与该P2P覆盖网络应用层所依据的静态图的性质有很大关系。结构化P2P系统在选择静态拓扑图时,倾向于选择具有常数度和最优直径的静态图,像D2B和Koorde是依赖于常数度De Brujin图的；Viceroy是基于蝴蝶结构的常数度图；FissonE和Moore是建立在静态的常数度Kautz图上的等。可见,从图论的角度来研究常数度图的性质,是研究结构化P2P覆盖网络拓扑的一种方法。这些现有的结构化P2P系统所采用的静态拓扑图是常数度的图,在这些图中,图所构造的系统节点的度是常数的,节点的加入与离开过程都遵循一定的规则,而基于这些图所构造的系统节点,节点的负载均衡、动态性、容错性和路由效率不是很高,针对这些问题,本论文又设计了两个效率较高、负载均衡性较好的系统。
本论文在全面分析和讨论了现有的结构化P2P系统的静态拓扑的基础上,从图论的角度,把图的性质和P2P系统的性能联系起来,提出了更加有效的结构化P2P系统。其主要工作有：
(1)从现有P2P系统的研究入手,对目前的P2P系统进行了总结,并从图论的角度来研究静态拓扑图的性质,从而提出了一种新的基于改进的Petersen图的P2P覆盖网络——GPSG,并在此覆盖网络中引入了超节点机制。该系统融合了Petersen图、超节点和环的性质,使GPSG系统具有较高的动态性和容错性,并对所构造的GPSG覆盖网络进行了理论分析和实验仿真。我们从仿真实验中可以得到,基于双环的GPSG系统的负载均衡性略高于基于单环的Chord系统；GPSG系统中节点的加入时间较短,节点加入或离开GPSG系统时所消耗的消息代价要略小于Chord系统；且GPSG系统比Chord系统的路由效率要高。
(2)从研究另一类高对称图——Cayley图的性质入手,基于群的任意生成集来构造Cayley图,并提出了另一种高对称的结构化的P2P覆盖网络——CLG系统,这样所构造的系统具有高对称性、灵活性、模糊查询和负载均衡性,符合动态网络的变化特征,并从实验仿真的角度对基于Cayley图构建的CLG系统和基于常数度的deBrujin图(非Cayley化图)构建的D2B系统进行了比较。我们从仿真实验中可以看到,CLG系统比D2B系统负载均衡性要好；CLG系统比D2B系统具有更高的查找效率；且CLG系统中新节点的加入时间较短,从而证明了CLG系统具有较高的实用性。
最后,总结本论文的主要内容,并提出了下一步要研究的主要问题。
Peer-to-Peer network (P2P network) is work by adopting to the computing model of peer-to-peer in the current Internet environment, P2P overlay networks are distributed systems in nature. At present, the widely using of P2P network system is promoting the rapid development of P2P technology. Each node of the P2P network are equal in the network, they have broken the traditional client/server model, without the difference of the client and server. Any node in the network, which not only act as a server, but also act as a client, they are able to share files and transmit information between them. These network connections make full use of network bandwidth, and have very high scalability, good fault tolerance, autonomy and self-organization, all of which makes the rapid development of P2P technology to become an important technology of computer, and also become widely attention by more and more experts and scholars.
From the view of the network topology, the research of the P2P overlay network mainly divided into two classes:the structured P2P overlay network and unstructured P2P overlay network. The structured P2P overlay network is static based on the specific static topology graph to build overlay network on the application layer, which relying on a distributed hash table (DHT) to accurately locate data information and data objects, each peer maintains a small routing table consisting of its neighboring peers'NodeIDs and IP address. Lookup queries or message routing are forwarded across overlay paths to peers in a progressive manner; But the unstructured P2P overlay network topology is not strictly controlled, locating data information and data objects is arbitrary, the overlay networks organize peers using flooding or random walks or expanding-ring Time-To-Live (TTL) search, etc to query content stored by overlay peers, but this arbitrariness is also conform to certain mathematical laws. This paper is based on a structured P2P overlay network.
From the research on the network topology of Structured P2P overlay network, we found that the P2P overlay network basing on a specific static topology, to a large extent, whose performance is related to the properties of the static graph. When choosing the static topology graph of Structured P2P system, we are tend to choose the static graph with constant degree and optimal diameter, Such as the D2B system and Koorde system are dependent on constant-degree de Brujin graph; The Viceroy system is based on a butterfly structure constant-degree graph; The Moore system is based on a constant-degree Kautz graph and so on. So from the perspective of graph theory to study the properties of static graph, which is a method to research the network topology of the structured P2P overlay network. The static topology graph which used by these existing structured P2P systems is a constant degree graph. In these graphs, the degree of nodes is constant and the process of nodes' join and leave follows certain rules, but the nodes of system based on these constant static graphs, whose load balance, dynamic properties, fault tolerance and routing efficiency are not very high. Because of these problems, we designed two P2P systems, which have high efficiency and good load balance.
This paper comprehensively analyzes and discusses the existing structured P2P system which based on a static topology graph. From the perspective of graph theory, we combined the properties of graph with the performance of P2P systems, and proposed more effectively structured P2P system. Its main work includes:
First, we study the current P2P systems, and summarize the technology of the current P2P systems. And from the perspective of graph theory to study the properties of graph, and proposed a new P2P overlay network-GPSG, which based on improved Petersen graph. In GPSG system, we introduce the super node mechanism in this overlay network. This system combines the Petersen graph, super-nodes and the properties of the ring, so the GPSG system has a high dynamic and fault tolerance, in the last, we carried out theoretical analysis and experimental simulation of the GPSG system. From the results, we conclude that the GPSG system which based on double loops has higher load balance than the Chord system, which based on the single ring; the nodes of GPSG join the system shorter than the node of Chord, and the nodes join or leave the GPSG system consume less than the nodes of Chord system; and the routing efficiency of the GPSG system is higher than the Chord system.
Secondly, from studying the properties of another type of graph-Cayley graph, from the respective of constructing Cayley graph based on an arbitrary generating set of groups, we put forward an alternative high-symmetrical structure of the P2P overlay network-CLG, which have high symmetry, flexibility and load balance, which conform to the dynamic characteristics of the network. From the perspective of experimental simulation, we compared the CLG system that based on Cayley graph with the D2B system that based on de Brujin graph of constant degree. We can conclude from the simulation experiments that the CLG system has better load balance than the D2B system; CLG system has more search efficiency than the D2B system; and the new nodes of CLG system consume less time when they join the system, all that prove CLG system has higher availability.
At last, we summarized the main contents of this paper and present the following problems for future research.
引文
[1]Napster.http://www.napster.com.
[2]Gnutella.http://www.gnutella.com.
[3]KaZaA. http://kazaa.com.
[4]Clarke, O.Sandberg, B. Wiley, T. W. Hong. Freenet:A Distributed Anonymous Information Storage and Retrieval System [A]. Proceedings of the 2000 International Workshop on Desgin Issues in Anonymity and Unobservability (DIAU'00), Spinger-Verlag 2009,46-66.
[5]BitTorrent. http://bitconjurer.org/BitTorrent/.
[6]M. Harren, J. M. Hellerstein, R. Huebsch, B. T. Loo, S. Shenker, I. Stoica. Complex Queries in DHT-based Peer-to-Peer Networks [R]. IPTPS,2002.
[7]S.Ratnasamy, P.Franeis, M.Handley, R.Karp, S.Shenker, A scalable content addressable network, in:Proceedings of ACM SIGCOMM,2001,329-350.
[8]F.Kaashoek and D.Karger. Koorde:a simple degree-optimal distributed hash table[C]. In Proc 2nd International Workshop on Peer-to-Peer Systems, IPTPS,2003.
[9]P. Fraigniaud and P. Gauron. D2B:a de bruijn based content-addressable network [J]. Theoretical Computer Science,2006,355(1):65-79.
[10]Stoica, R. Morris, D. Karger, M. Kaashoek, Chord:a scalable peer-to-peer lookup service for internet applications, ACM SIGCOMM,2001.
[11]B.zhao, J.Kubiatowicz, A.Joseph, Tapestry:an infrastructure for fault-tolerant wide- area location and routing, Computer Science Division, UC Berkeley,2001,41-53.
[12]A. Rowstron, P. Druschel, Pastry:Scalable, centralized object location and routing for large-scale peer-to-peer systems, Proceedings of the 18th IFIF/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany,2001,329-350.
[13]Dahlia Malkhi, Moni Naor, David Ratajczak.Viceroy:A Scalable and Dynamic Emulation of the Butterfly. In:ACM PODC'02,183-192.
[14]N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, A.Wolman. SkipNet: A Scalable Overlay Network with Practical Locality Properties [R]. USITS'03,2003.
[15]M.Miller and J.Siran. Moore graphs and beyond:A survey of the degree/diameter problem [J]. In Proc. Electronic Journal of Combinatorics, December 2005.
[16]孙林林.广义Petersen图和循环图的连通支配研究[D].计算机软件学报,2008.
[17]王雷,林亚平,陈治平.基于Petersen图互连的超立方体网络及其路由算法[J].系统仿真学报2007(06).
[18]徐明曜,徐尚进.交错群A5的小度数Cayley图的对称性.中国科学A辑[J],200434(1).
[19]叶和平,肖文俊,朱小平.Cayley图连通圈的一个代数性质研究.工程数学学报[J].2008,25(12).
[20]Rita H. Wouhaybiand Adnrew T. Campbell. Building resilient low-diameter peer-to-peer topologies. Computer Networks, Volume 52, April,2008,1019-1039.
[21]A. L. Barabasi and R. Albert. Emergence of scaling in random networks [J]. Science,1999,509-512.
[22]Xueyan Tang, Jianliang Xu, Wang-Chien Lee. Analysis of TTL-Based Consistency in Unstructured Peer-to-Peer Networks. IEEE International Conference on Communications, vol.30, June,2009.
[23]John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski. OceanStore:architecture for global-scale persistent storage. Cambridge, MA, USA, November 2000.
[24]William J. Bolosky, John R. Douceur, and Jon Howell, The farsite project:a retrospective, in ACM SIGOPS Operating Systems Review 41 (2), Association for Computing Machinery, Inc., April,2007.
[25]Xi Tong, Dalu Zhang, Zhe Yang, Efficient Content Location Based On Interest-Cluster in Peer-to-Peer System[C]. IEEE international Conference on e-Business Engineering, Oct.,2005,324-331.
[26]Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim. A Survey and Comparison of Peer-to-Peer Overlay Networks Schemes. IEEE Communications Survey and Tutorial,2008, 72-93.
[27]H. Balakrishnan, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica. Looking up data in p2p systems [J]. Communications of the ACM,2003,46(2):43-48.
[28]H. Shen, C. Xu, and G. Chen. Cycloid:A constant degree and lookup-efficient p2p overlay network [C]. In International Parallel and Distributed Processing Symposium (IPDPS2004), Santa Fe, New Mexico, Apr.,2004.
[29]Thara Angskun, Graham Fagg, George Bosilca. Self-healing network for scalable fault-tolerant runtime. Future Generation Computer Systems, Volume 26, March,2009.
[30]Q. B. Zhang, W. Peng, X. C. Lu. ERSN:An efficient and Robust Super-Peer P2P Network [J]. Journal of Computer Research and Development, vol.43,2002.
[31]W. H. Kautz. The design of optimum interconnection networks for multiprocessors [C]. Architecture and Design of Digital Computer. Nato advanced Institute (1969),249-272.
[32]Denis Caromel, Alexandre di Costanzo and Christian Delbe. Peer-to-Peer and Fault-tolerance Towards Deployment-based technical services. Future Generation,Computer Systems, August,2009.
[33]P. Maymounkov, D. Mazires. Kademlia:A peer-to-peer information system based on the xor metric [C]. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPIPS'02), Gambridge, 2002,53-65.
[34]Jun Xu, Abhishek Kumar, Xingxing Yu. On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks [M]. IEEE Journal on Selected'Areas in Communications (JSAC),2004,22(1):151-163.
[35]徐俊明.组合网络理论[M].北京：科学出版社,2007.
[36]D. Loguinov, A. Kumar, V. Rai, and S. Ganesh. Graph-theoretic analysis of structured peer-to-peer systems:routing distances and fault resilience [A]. In ACM Annual Conference on Data Communication, Karlsruhe, Germany, Aug.2008.
[37]侯新民：王天明等.广义Petersen图的宽直径[J].数学研究与评论,2004,12(24).
[38]黄煦艳,李乔等.Petersen图的一致最优可靠性[J].上海交通大学学报,2001,5(15).
[39]徐俊明.图论及其应用[M].安徽：中国科学技术大学出版社,1998.
[40]Yang, Neo, Gene Eu Jan, Shao-Wei Leu, In-Jen Lin:A study of the generalized Peterson Graph and a Novel Graph Y. Algorithms and Computational Molecular Biology,2008,898-909.
[41]Ljubljana, Slovenia. The Remarkable Generalized Petersen Graph, Preprint series, Vol.35,1997.
[42]陈贵海,李振华.对等网络：结构、应用与设计[M].北京：清华大学出版社,2007.
[43]L. Lamport. Using time instead of timeout for fault-tolerant distributed systems [J]. ACM Transactions on Programming Languages and Systems,1984,6(02):254-280.
[44]Changtao Qu, Wolfgang N. Cayley DHTs-A Group-Theoretic Framework for Analyzing DHTs Based on Cayley Graphs [C]. In Proc. of ISPA, Oct.29,2004.
[45]Chao Xie, Guihai Chen, Art Vandenberg, Yi Pan:Analysis of hybrid overlay network topology [J]. Computer Communications,2008,190-200.
[46]Y. Saad, M. H. Shultz. Topological properties of hypercubes [J]. IEEE Trans. on Computers,1998, 37(7):867-872.
[47]J. A. Bondy and U. S. R. Murty. Graph Theory With Applications [C]. The MACMILLAN Press LTD,1976.
[48]D. Malkhi, M. Naor, D. Ratajczak. Viceroy:A Scalable and Dynamic Emulation of the Butterfly [C]. PODC,2002.
[49]M. T. Schlosser, M. Sintek, S. Decker, W. Nejdl. Hypercup-hypercubes, ontologies, and efficient search on peer-to-peer networks [C]. Agents and Peer-to-Peer Computing (AP2PC'02),2002.
[50]Ding-Zhu Du, D. Frank Hsu. Combinatorial Network Theory [M]. Printed in the Netherlands, Kluwer Academic Publishers,1996,65-105.
[51]Rudolf Bayer. Symmetric Binary B-trees:Data Structure and Maintainance Algorithms [J]. Acta Informatica,1972,290-306.
[52]Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim. A Survey and Comparison of Peer-to-Peer Overlay Networks Schiemes. IEEE Communications Survey and Tutorial, Match,2004,72-93.
[53]C. Gkantsidis, M. Mihai, A. Saberi. Hybrid search schemes for unstructured peer-to-peer Networks[C]. Proc. of IEEE INFOCOM,2005.
[54]D. S. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins, Z. Xu. Peer-to-peer computing [R]. Technical Report:HP L-2002-57. Hewlett Packard Laboratories, March 8th,2002.
[55]H. Zhuge, L. Ding, X. Li. Networking scientific resources in the Knowledge Grid environment [J]. Concurrency and Computation:Practice and Experience,2007,7(19):1087-1113.
[56]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci. Wireless Sensor Network:A Survey [J], Computer Networks, vol.38,2008,393-341.
[57]M. Ali, Z. A. Uzmi. CSN:A network protocol for serving dynamic queries in large-scale wireless sensor networks[C]. In Proc. Of CNSR'04, Canada, May 2004.
[2]Gnutella.http://www.gnutella.com.
[3]KaZaA. http://kazaa.com.
[4]Clarke, O.Sandberg, B. Wiley, T. W. Hong. Freenet:A Distributed Anonymous Information Storage and Retrieval System [A]. Proceedings of the 2000 International Workshop on Desgin Issues in Anonymity and Unobservability (DIAU'00), Spinger-Verlag 2009,46-66.
[5]BitTorrent. http://bitconjurer.org/BitTorrent/.
[6]M. Harren, J. M. Hellerstein, R. Huebsch, B. T. Loo, S. Shenker, I. Stoica. Complex Queries in DHT-based Peer-to-Peer Networks [R]. IPTPS,2002.
[7]S.Ratnasamy, P.Franeis, M.Handley, R.Karp, S.Shenker, A scalable content addressable network, in:Proceedings of ACM SIGCOMM,2001,329-350.
[8]F.Kaashoek and D.Karger. Koorde:a simple degree-optimal distributed hash table[C]. In Proc 2nd International Workshop on Peer-to-Peer Systems, IPTPS,2003.
[9]P. Fraigniaud and P. Gauron. D2B:a de bruijn based content-addressable network [J]. Theoretical Computer Science,2006,355(1):65-79.
[10]Stoica, R. Morris, D. Karger, M. Kaashoek, Chord:a scalable peer-to-peer lookup service for internet applications, ACM SIGCOMM,2001.
[11]B.zhao, J.Kubiatowicz, A.Joseph, Tapestry:an infrastructure for fault-tolerant wide- area location and routing, Computer Science Division, UC Berkeley,2001,41-53.
[12]A. Rowstron, P. Druschel, Pastry:Scalable, centralized object location and routing for large-scale peer-to-peer systems, Proceedings of the 18th IFIF/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany,2001,329-350.
[13]Dahlia Malkhi, Moni Naor, David Ratajczak.Viceroy:A Scalable and Dynamic Emulation of the Butterfly. In:ACM PODC'02,183-192.
[14]N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, A.Wolman. SkipNet: A Scalable Overlay Network with Practical Locality Properties [R]. USITS'03,2003.
[15]M.Miller and J.Siran. Moore graphs and beyond:A survey of the degree/diameter problem [J]. In Proc. Electronic Journal of Combinatorics, December 2005.
[16]孙林林.广义Petersen图和循环图的连通支配研究[D].计算机软件学报,2008.
[17]王雷,林亚平,陈治平.基于Petersen图互连的超立方体网络及其路由算法[J].系统仿真学报2007(06).
[18]徐明曜,徐尚进.交错群A5的小度数Cayley图的对称性.中国科学A辑[J],200434(1).
[19]叶和平,肖文俊,朱小平.Cayley图连通圈的一个代数性质研究.工程数学学报[J].2008,25(12).
[20]Rita H. Wouhaybiand Adnrew T. Campbell. Building resilient low-diameter peer-to-peer topologies. Computer Networks, Volume 52, April,2008,1019-1039.
[21]A. L. Barabasi and R. Albert. Emergence of scaling in random networks [J]. Science,1999,509-512.
[22]Xueyan Tang, Jianliang Xu, Wang-Chien Lee. Analysis of TTL-Based Consistency in Unstructured Peer-to-Peer Networks. IEEE International Conference on Communications, vol.30, June,2009.
[23]John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski. OceanStore:architecture for global-scale persistent storage. Cambridge, MA, USA, November 2000.
[24]William J. Bolosky, John R. Douceur, and Jon Howell, The farsite project:a retrospective, in ACM SIGOPS Operating Systems Review 41 (2), Association for Computing Machinery, Inc., April,2007.
[25]Xi Tong, Dalu Zhang, Zhe Yang, Efficient Content Location Based On Interest-Cluster in Peer-to-Peer System[C]. IEEE international Conference on e-Business Engineering, Oct.,2005,324-331.
[26]Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim. A Survey and Comparison of Peer-to-Peer Overlay Networks Schemes. IEEE Communications Survey and Tutorial,2008, 72-93.
[27]H. Balakrishnan, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica. Looking up data in p2p systems [J]. Communications of the ACM,2003,46(2):43-48.
[28]H. Shen, C. Xu, and G. Chen. Cycloid:A constant degree and lookup-efficient p2p overlay network [C]. In International Parallel and Distributed Processing Symposium (IPDPS2004), Santa Fe, New Mexico, Apr.,2004.
[29]Thara Angskun, Graham Fagg, George Bosilca. Self-healing network for scalable fault-tolerant runtime. Future Generation Computer Systems, Volume 26, March,2009.
[30]Q. B. Zhang, W. Peng, X. C. Lu. ERSN:An efficient and Robust Super-Peer P2P Network [J]. Journal of Computer Research and Development, vol.43,2002.
[31]W. H. Kautz. The design of optimum interconnection networks for multiprocessors [C]. Architecture and Design of Digital Computer. Nato advanced Institute (1969),249-272.
[32]Denis Caromel, Alexandre di Costanzo and Christian Delbe. Peer-to-Peer and Fault-tolerance Towards Deployment-based technical services. Future Generation,Computer Systems, August,2009.
[33]P. Maymounkov, D. Mazires. Kademlia:A peer-to-peer information system based on the xor metric [C]. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPIPS'02), Gambridge, 2002,53-65.
[34]Jun Xu, Abhishek Kumar, Xingxing Yu. On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks [M]. IEEE Journal on Selected'Areas in Communications (JSAC),2004,22(1):151-163.
[35]徐俊明.组合网络理论[M].北京：科学出版社,2007.
[36]D. Loguinov, A. Kumar, V. Rai, and S. Ganesh. Graph-theoretic analysis of structured peer-to-peer systems:routing distances and fault resilience [A]. In ACM Annual Conference on Data Communication, Karlsruhe, Germany, Aug.2008.
[37]侯新民：王天明等.广义Petersen图的宽直径[J].数学研究与评论,2004,12(24).
[38]黄煦艳,李乔等.Petersen图的一致最优可靠性[J].上海交通大学学报,2001,5(15).
[39]徐俊明.图论及其应用[M].安徽：中国科学技术大学出版社,1998.
[40]Yang, Neo, Gene Eu Jan, Shao-Wei Leu, In-Jen Lin:A study of the generalized Peterson Graph and a Novel Graph Y. Algorithms and Computational Molecular Biology,2008,898-909.
[41]Ljubljana, Slovenia. The Remarkable Generalized Petersen Graph, Preprint series, Vol.35,1997.
[42]陈贵海,李振华.对等网络：结构、应用与设计[M].北京：清华大学出版社,2007.
[43]L. Lamport. Using time instead of timeout for fault-tolerant distributed systems [J]. ACM Transactions on Programming Languages and Systems,1984,6(02):254-280.
[44]Changtao Qu, Wolfgang N. Cayley DHTs-A Group-Theoretic Framework for Analyzing DHTs Based on Cayley Graphs [C]. In Proc. of ISPA, Oct.29,2004.
[45]Chao Xie, Guihai Chen, Art Vandenberg, Yi Pan:Analysis of hybrid overlay network topology [J]. Computer Communications,2008,190-200.
[46]Y. Saad, M. H. Shultz. Topological properties of hypercubes [J]. IEEE Trans. on Computers,1998, 37(7):867-872.
[47]J. A. Bondy and U. S. R. Murty. Graph Theory With Applications [C]. The MACMILLAN Press LTD,1976.
[48]D. Malkhi, M. Naor, D. Ratajczak. Viceroy:A Scalable and Dynamic Emulation of the Butterfly [C]. PODC,2002.
[49]M. T. Schlosser, M. Sintek, S. Decker, W. Nejdl. Hypercup-hypercubes, ontologies, and efficient search on peer-to-peer networks [C]. Agents and Peer-to-Peer Computing (AP2PC'02),2002.
[50]Ding-Zhu Du, D. Frank Hsu. Combinatorial Network Theory [M]. Printed in the Netherlands, Kluwer Academic Publishers,1996,65-105.
[51]Rudolf Bayer. Symmetric Binary B-trees:Data Structure and Maintainance Algorithms [J]. Acta Informatica,1972,290-306.
[52]Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim. A Survey and Comparison of Peer-to-Peer Overlay Networks Schiemes. IEEE Communications Survey and Tutorial, Match,2004,72-93.
[53]C. Gkantsidis, M. Mihai, A. Saberi. Hybrid search schemes for unstructured peer-to-peer Networks[C]. Proc. of IEEE INFOCOM,2005.
[54]D. S. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins, Z. Xu. Peer-to-peer computing [R]. Technical Report:HP L-2002-57. Hewlett Packard Laboratories, March 8th,2002.
[55]H. Zhuge, L. Ding, X. Li. Networking scientific resources in the Knowledge Grid environment [J]. Concurrency and Computation:Practice and Experience,2007,7(19):1087-1113.
[56]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci. Wireless Sensor Network:A Survey [J], Computer Networks, vol.38,2008,393-341.
[57]M. Ali, Z. A. Uzmi. CSN:A network protocol for serving dynamic queries in large-scale wireless sensor networks[C]. In Proc. Of CNSR'04, Canada, May 2004.