Topology Construction And Resource Locating Of Structured P2P Overlay Network Based Cayley Graph

Overlay network technology based on application-layer is rapidly emerging and has beenwidely used in the Internet. Structured Peer-to-Peer overlay networks demonstrate many goodfeatures such as decentralization, scalability and fault tolerance, hence it indeed has a greatpotential to become a major technology for sharing information. Topology construction andthe resource locating are two important research fields of structured overlay network, whichdirectly affect the usability and efficiency of network.1. Topological properties determine the costs of topology maintenance and the routingperformance between nodes. Constant degree structure P2P overlay network provides notonly efficient routing but strong stability, less control message and network overhead, besides,low average distance and high clustering coefficient are two main attractive properties ofSmall-world network for overlay network which implies a small latency lookup andpreferable routing efficiency. These two factors have already had a significant impact uponresearch of overlay network topology. Combining these factors to construct a structurednetwork topology with good properties is an important research direction in P2P networktopology construction.2. By utilizing distributed hash tables, structured peer-to-peer network can provide exact-match search and locate the resource effectively. However, it is difficult to locate a resourcethat does not own an exact identifier when facing diversified search styles and complexqueries. Therefore, on the premise of lacking directory server and global index an efficientnovel distributed retrieval model that support complex queries is the key issue whether thestructure overlay network can be widely used.The thesis focuses on these two problems, and makes the main research subjects andcontributions as follows:1. Construction of constant degree structure P2P overlay network topology with small-world features. Based on the semidirect products of finite group and Cayley graph with small-world features, a new constant degree P2P overlay network CayDHT is proposed. CayDHTinherits the vertex-transitive property of Cayley graph, its simple routing scheme and constantrout table make it possible to construct large scale network. The simulations and experimentsshowed that this model provides O(1) routing table, O(logN) query path, good robustness andsmallworld properties.2. Multi-keyword search of Structured P2P overlay network. Generally speaking, instructured P2P network to locate a resource by multi-keywords requires additional mechanism such as distributed inverted index. Horizontal partition and vertical partition are two principalpattern of distributed inverted index. We discuss and analyses the key problem of multi-keyword superset search under these two patterns, and we also evaluate exhaustively thesetwo patterns by simulation and theoretical analysis under CayDHT.3. Complex/blind search of CayDHT. Like other structured P2P overlay networks,CayDHT does not provide any methods for complex/blind search too, so introducing flexibleblind search of traditional unstructured P2P network is necessary. By analyzing the topologyproperty of CayDHT, an efficient blind search scheme named Virtual Tree based ComplexSearch of CayDHT (VTCS) is proposed. The algorithm guarantees that query messages canvisit every node within O(logN) hops while does not need to maintain extra data structure, andwhat's more, the algorithm shows good load-balancing.4. Complex/blind search base on partition. Typically, the blind search depends on theTTL parameter to control the scope of the search and reduce the redundant messages.However, many studies have shown the TTL mechanism has some defects. By introducingthe advantage of super-peer based P2P network, with the help of dominating sets of graphtheory and solution to resource placement of network, we propose a novel search algorithmbased on partitioning the whole network. The algorithm can guarantees the completeness ofsearch result while only need to search the subzone with small TTL parameter. Theoreticalanalysis and simulation show that the method can control the search scope more effectively.