Query Routing And Reconfiguration Mechanism In Peer-to-Peer Networks

With the rapid growth of the Internet, traditional Client/Server model is unable to meet the requests of millions of users from all of the world, which causes service bottlenecks at the server side. On the other hand, the development of computer hardwares enables clients to execute more complicated tasks. Moreover, a great variety of devices are connected to the Internet and a large amount of resources stored on the devices are available. Under such circumstances, Peer-to-Peer (P2P) networks emerge as a new distributed computing model for resource sharing over the Internet.Peer-to-peer networks can be roughly classified into two types according to their over-lay topologies:structured and unstructured. One major challenge facing P2P networks is how to find the required resources efficiently. Query routing algorithms are designed for finding resources in P2P networks and the efficiency of query routing algorithms determines the per-formance of P2P networks. In addition, data objects in P2P nodes change rapidly as nodes continuously join and leave the networks, and different types of node and/or link failures may occur frequently, which all impact query hit rate substantially. Static network reconfiguration methods based on backup paths mechanism are not suitable for dealing with such a dynamic environment, while dynamic network reconfiguration algorithms purely based on the exchange of messages will produce much network cost. Therefore, it is necessary to explore adaptive reconfiguration mechanisms for dynamic P2P environments.This thesis is devoted to the issues of query routing and reconfiguration mechanism with the following major contributions:1. A novel hierarchical overlay structure called SkipCluster is proposed, which can effectively support exact-match and multi-dimensional range queries. SkipCluster is built on a two-tier hierarchical architecture. The higher tier consists of super-peers representing different clusters and the lower tier consists of nodes in clusters. A novel data structure called Triple Linked List (simply TLL) is designed to store each super-peer's pointers in the higher tier, which can be used to find the longest prefix and speed up query routing from one cluster to another. Intra-cluster nodes have internal pointers with exponential growth of sizes from two directions. Each segement-h pointer traverses nearly 2h nodes if and only if not all nodes in a segment leave the network. Experimental results show that SkipCluster can speed up exact-match and range queries without consumption of extra memory space in different network sizes.2. A novel query routing mechanism called Path-traceable Query Routing (simply PQR) is presented for improving query performance in unstructured P2P networks. PQR is built on a novel data structure called traceable gain matrix (TGM) that records every query's gain at each node along the query hit path, and allows for optimizing query routing decision effectively. After a query hit happens at a target node, the gain will be transferred itera-tively between adjacent nodes along the path from the target node to the source node with exponential decay of distance. When a node receives a new query message, it will calculate the gain values of its neighbors to which the query has been forwarded and terminated with query hit. The neighbor with the highest gain value of current query will be selected as candidate with the highest probability to forward the query message. Experimental results show that PQR achieves relatively high query hit rate with low bandwidth consumption in different types of network topologies under static and dynamic network environments.3. A mobile agent based reconfiguration mechanism is proposed for dealing with both node and link failures in P2P networks. Three types of failures:single link failure, multiple links failure and node failure are considered. A Two-Stage Failure Diagnosis (simply TSFD) mechanism and three failure recovery algorithms are proposed to handle three types of failures for increasing the availability of P2P networks. Experimental results show that TSFD, consuming relatively lower storage cost and network cost, performs better than existing methods.4. A lecture notes searching and sharing system called LESSON (LEcture notes Searching and Sharing Over InterNet) is implemented based on P2P overlay network. LESSON em-ploys metasearch engines for lecture notes searching from the Web and P2P overlay net-work for lecture notes sharing among the users. A heuristic strategy called RSF (Rank, Similarity and Features) is proposed for merging the results returned from various compo-nent search engines into a single ranked list. Experimental results show that the average effectiveness of RSF is higher than that of single component search engine as well as other results merging algorithms without consideration of lecture notes'unique features.