Structured P2p Overlay Network Design And Search Mechanism

Peer-to-Peer (P2P) overlay networks are distributed systems which contain self-organized nodes to share resources, such as CPU, bandwidth and storage. They can adapt to nodes' failure, accommodate changing number of nodes, and maintain acceptable connectivity and performance without the support or intermediation of global central servers. Structured P2P overlay networks based on distributed hash table are significant part of P2P overlay networks. And they become the research focus for their advantages of effective routing, robust, scalability, load balance and determinacy of data location.The thesis mainly studies the design and search mechanisms of structured P2P overlay networks, and is divided into five chapters. In the first chapter, we briefly introduce the corresponding concepts and search methods of P2P, and indicate the structure and main innovative points of the thesis.In the second chapter, we propose a structured P2P overlay network with constant degree based on Cycloid and folded hypercube, namely FCycloid. It employs the concept of complementary edges in folded hypercube to optimize some searches in Cycloid. In FCycloid, nodes' degrees (also known as the numbers of links or neighbors) are constants and don't change with the change of the size of the network. And this feature guarantees that the overlay network can keep less maintenance costs while the size of the network is continuously growing. In FCycloid with N= (d+1)*2d nodes, each node only has to keep O(1) neighbors and each lookup just needs O(d) steps. At the same time, the improvement of search efficiency of FCycloid has been proven and corresponding performances are analyzed by the simulation.In the third chapter, we design a hierarchical BGKR overlay network. It limits the query requests in a specific area, and enhances search efficiency. BGKR used generalized Kautz digraph and ring as its topology which made each joining of a new node lead to some changes in the connection relationship between parts of nodes. Hence, the hierarchical BGKR overlay network takes Kautz digraph and ring as its basic structure and stratifies BGKR based on a specific ontology. Performances of lookup efficiency and load distribution are verified by the simulation.In chapter 4, we study the mechanism of similarity search in M-Chord. Similarity search has been widely used in many fields. For database, similarity search is based on gradual rather than exact relevance. A distance between objects is used to quantify the proximity, similarity or dissimilarity of a query object versus the objects stored in a database to be searched. A similarity query is defined by a query object and a constraint on the proximity required for an object to be in the result set. Range query and k-nearest neighbor query are two basic types of the similarity queries. M-Chord adopted metric spaces and an order-preserving function to realize these two kinds of queries in Chord. In this part, considering disadvantages of above two query algorithms, improvement proposals are put forward.In chapter 5, the conclusion is given and the future work is pointed out.