Complex Search In Constant-degree P2P System

In recent years, many Peer-to-Peer (P2P) systems have been proposed and become the applications which dominate the traffic bandwidth of Internet. DHT-based structured system is an important category of P2P system. Each peer in DHT system connects to other peers according to some protocol and all peers form an overlay with specific network topology, which results in the high lookup efficienfy of DHT system. Among lots of DHT based structured P2P systems, the constant-degree system has two novel characteristics: the neighbor degree of each peer is constant and the lookup efficiency is O(logN). The constant-degree system can reduce the number of messages between peers and simplify the system structure. However, it also faces some difficult problems such as fault tolerance, load balance of data and routing message. It is a great challenge to solve these problems in constant-degree DHT-based structures P2P system.Since the number of peers is usually large and peers are distributed geographically abroadly, the lookup efficiency and number of message are two important performance metrics of resource search algorithms in large scale P2P system. Efficient lookup is helpful to reduce the search latency and improve the degree of users'satisfaction. And lower network traffic load is helpful to reduce the demand on network bandwidth and decrease the operation cost. Complex search in P2P system also faces a trade-off between the lookup efficiency and the message overhead.In this thesis, we study above problems deeply. Firstly, we extend the existing CCC topology and construct a new constant-degree P2P overlay by adding three more neighbors to each peer. The new constant-degree P2P overlay, called Cactus, is not worse than other constant-degree system in the area of fault-tolerate, load balance and lookup efficiency. Secondly, on the base of Cactus system, we study the problems of range query and Top-K query in complex search. For these two problems, we propose Smart-broadcast algorithm and IES algorithm separately. Theoretical analysis and simulation results show that the proposed algorithms are superior to the existing algorithms in lookup efficiency and network traffic load.The main contributions of this dissertation are:(1) A constant-degree system called Cactus has been proposed based on CCC hypercube. In Cactus system, the neighbor number of each peer is 6 and the time complexity of key lookup is O(d) when node number is not more than d*2d, where d is the degree of CCC. Extensive experimental results show that Cactus system is not worse than other existing constant-degree systems in the area of fault-tolerate, load balance and lookup efficiency. In case of abnormal leave of nodes, Cactus adapts the feedback fault-tolerant algorithm to restore neighbor relationship. Compared to other constant-degree systems, Cactus can reduce the number of message from log2N to 3logN and reduce the number of hops from logN to 2.(2) A range query algorithm called Smart-Broadcast has been proposed on the base of the Cactus system. Accoding to the seache range, the Smart-Broadcast algorithm dynamically constructs a virtual search tree whose structure is close to the topology of Cactus. Query of node in range can be done in O(logN) hops and the average routing overhead is not more than O(d)+(1+3/d)m, where m is the number of peers in the query range. The lookup efficiency and message load of Smart-Broadcast algorithm are very close to the asymptotic lower bounds of latency and message cost of range queries in constant-degree DHT infrastructures. Simulation results show that the proposed Smart-Broadcast algorithm has higher query efficiency and lower message load than other algorithms.(3) A bottom-up algorithm called IES has been proposed for the k best matching resource in P2P environment. Each resource is taken as a point in m-dimension space and the Top-K query problem is transferred to searching the k closest points to the expected query point. Based on Agrawal's discovery, to search resources, the IES algorithm firstly determines the size of the seach range and then seaches resources in these ranges iteratively using the multi-range query algorithm provided by Cactus sytem. We have proved the correctness of the IES algorithm and analyzed its performance. Analysis and simulation show that the IES algorithm has high lookup efficiency and low network traffic load in the circumstance that the number of resource attributes is much larger than the number of attributes used by consumer.