【作者】 刘思建；

【导师】 陈元琰；

【作者基本信息】 广西师范大学 ， 计算机软件与理论， 2010， 硕士

【摘要】 对等网络(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系统具有较高的实用性。最后,总结本论文的主要内容,并提出了下一步要研究的主要问题。更多还原

【Abstract】 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.更多还原