The Design And Analysis Of Peer-to-peer Overlay Network Based On Petersen Graph And Cayley Graph

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.