Research On Unstructured Peer-to-peer Network Resource Location

Abstract:In recent years, peer-to-peer (P2P) computing has become a popular network computing technique. Applications of peer-to-peer computing have spread into many fields. Unstructured peer-to-peer systems have been widely used, in which there is no fixed link relationships among nodes and between resource objects and nodes. Resource location is an important basic service in large-scale peer-to-peer systems, which implements topology construction, message routing and resource search. The large-scale, highly dynamic, and widely scattered characteristics bring many challenging problems for resource location technique of unstructured peer-to-peer networks. Usually, resource location technique for unstructured peer-to-peer networks has a low efficiency which is hard to get low query latency and high query hit rate with low cost at the same time if there is no other supporting mechanism, while incremental search has also not been supported by unstructured peer-to-peer networks. This thesis deeply studies unstructured peer-to-peer resource location technique.As for incremental search has not been supported by resource location technique of unstructured peer-to-peer networks, this thesis presents an incremental P2P search algorithm based on social acquaintance relationship (IPSBSAR) and a general incremental search model for unstructured P2P networks . IPSBSAR mimics behaviors of peers in social networks to establish different semantic links among peers according to the level of knowing each other, and introduces a novel access and update mode of neighbor list to do incremental search. The general incremental search model can work with query routing algorithms to make incremental search try to access semantic most related nodes. Analysis and experiment results show that IPSBSAR can achieve high incremental query hit rate with low cost and low latency, and efficiently retrieve most of relevant resources when doing exhaustive incremental search with the same query semantic, the general incremental search model can work with query routing algorithms to implement incremental search.As weak state routing can not do routing properly, this thesis presents a new bloom filter (OBF) oriented at peer-to-peer network probabilistic routing and an efficient peer-to-peer network probabilistic routing scheme (DWalker) based on decaying bloom filters. OBF is based on storing each update and its properties such as source nodes issuing resource object which provides a way for each node to store membership information received only from shortest path, and is able to restrain effects of noise effectively, and therefore OBF is able to make weak state routing schemes do right decisions with high probability. DWalker issues and forwards resource objects meta-information with decaying bloom filters based on directed random network. DWalker makes the max forwarded distance less than the expected distance between any two nodes which effectively constrain the problem of multi-path arriving of decaying bloom filters. DWalker replaces single bloom filter with multiple bloom filters as a routing entry, which can hold more routing information while constraining single bloom filter false positive. DWalker computes the max proportion of bits valued 1 of a bloom filter and the least number of common valued 1 bits of an entry bloom filter with a query bloom filter, which make a query routing in the right direction with high probability while generating redundant error routing with low probability. Analysis and experiment results show that OBF is able to make weak state routing schemes do right decisions with high probability, DWalker can achieve high query hit rate with low cost, low latency, and few number of bloom filters of a routing entry.In order to make any query issued by any node achieve high query hits with low cost and latency, this thesis presents a nodes covering algorithm called DCBF which is based on data copying and bloom filter technique. DCBF makes a few copies of each shared resource object, and places each copy on a random selected node based on a directed random network. Each node forwards a copied object meta-information to neighbor nodes with distributed decaying bloom filters. Analysis and experiment results show that DCBF can make most of nodes feel meta-information of any object by making only a few copies and forwarding a copied object meta-information with distributed decaying bloom filter, and therefore can achieve high query hits with low cost and latency.This thesis also presents a peer-to-peer query routing algorithm based on semantic cluster (SCQR) which is a super-node mode and a self-organizing semantic cluster based peer-to-peer query routing algorithm (SOSC) which is totally distributed. SCQR makes nodes clustered according to their semantic, and each cluster elects a super-node as cluster computing node which is responsible for computing cluster semantic and establishing links with all neighbor cluster computing nodes. Query is routed among cluster computing nodes. Through expressing node semantic by its shared resources'keywords frequency vector, establishing a neighbor link between nodes whose semantic is most relevant, and transmitting node semantic after being decayed, SOSC creatively solves the problem of cluster semantic expressing and transmitting in a distributed environment. SOSC makes a node feel the semantic hierarchy of its nearby nodes, and therefore each node can do message routing based on semantic cluster. Analysis and experiments results show that SCQR and SOSC can achieve high query hit with small routing latency and query cost. Furthermore, detailed implementation of SOSC based on decaying bloom filter is also discussed.