Research On Peer-to-Peer Networks Based On Kautz Digraph And Bloom Filters

Peer-to-Peer (P2P) networks are distributed and highly volatile systems in which all peers are equivalent in functionality and perform similar tasks. Peers communicate through a fault tolerant overlay network on top of the physical network. P2P networks play a significant role in many important and popular distributed applications.P2P networks must successfully address three fundamental issues: topology construction, resource placement, and resource localization, and can be classified based on the control over topology construction and resource placement. They are unstructured, structured, and hybrid P2P networks. This thesis deeply studies the structured P2P networks possessing the optimal topological properties, the data-centric routing and indices routing mechanisms in unstructured P2P networks, and one important application based on a unstructured P2P Network.Structured P2P networks have emerged as a good candidate infrastructure for building novel large-scale and robust network applications. They impose a certain structure on the overlay network and control the placement of data. In general, the topological properties are critical factors that dominate the performance of structured P2P networks. It is well known that complete Kautz digraph achieves optimal topological properties among all non-trivial digraphs. P2P networks need a topology with an arbitrary size. The complete Kautz digraph, however, requires that the number of peers must be some given values determined by the peer degree and the network diameter. This thesis proposes Moore: the first effective and practical peer-to-peer network based on the incomplete Kautz digraph with O(logd N) diameter and constant degree even the number of peers is an arbitrary value. The diameter and average routing path length of MOORE are shorter than that of CAN, butterfly, and cube-connected-cycle, and are close to that of complete De Bruijn and Kautz digraphs. The message cost of node joining and departing operations are at most 2:5d logd N and (2:5d + 1) logd N. Moore can achieve optimal diameter, high performance, good connectivity and low congestion evaluated by formal proofs and simulations.Moore can only work under relative static or moderately dynamic environment, and suffers large overhead due to maintaining its topology and resource placement strategy in large scale and highly dynamic environments. To address these issues, this thesis propose BAKE scheme based on balanced Kautz tree structure with logdN diameter and constant degree even the number of peers is an arbitrary value. By keeping a total ordering of peers and employing a robust locality-preserved resource placement strategy, resources that are similar in single or multi-dimensional attributes space are stored on a same peer or neighboring peers. The comprehensive analysis and extensive simulations show that BAKE achieves optimal diameter and good connectivity as the complete Kautz digraph does, and supports both exact and range queries efficiently. Indeed, the concepts of balanced Kautz tree and Kautz ring introduced in this work can also be extended and applied to other interconnection networks after minimal modifications, for example, De Bruijn digraph. BAKE has a small overhead and more robust routing scheme than Moore in dynamic environments.The unstructured P2P networks have become the most popular applications due to their simplicity, robustness and scalability. A unstructured P2P Network alone, however, cannot locate resources in a reasonable delay without propagating large query messages, especially when locating rare resources. To address the issues, the data-centric routing and indices routing based on Bloom filters are proposed.Full state routing using Bloom filters has been widely studied in the field of data-centric routing. This thesis shows that, the existing designs of Bloom filters, however, cannot effectively support in-network queries since the majority of queries are routed towards many wrong nodes besides those destinations. To address this issue, we propose a receiver-oriented design of Bloom filters to sufficiently restrict the probability of a wrong routing decision. The theoretical analysis and experimental results demonstrate that our approach apparently outperforms the existing designs of Bloom filers in terms of success probability and traffic cost in data-centric routing.Weak state routing using decay Bloom filters has been widely studied in the field of data-centric routing. This thesis shows that, given a query for any item at an arbitrary node, the noise in an unrelated routing entries is very likely equal to the useful information in the right routing entries. Consequently, queries are routed by means of network flooding. We study the impact of decay model on the membership information in the routing entries, and evaluate the negative impact of noise on a routing decision. We then derive the necessary and sufficient condition of a feasible weak state routing. Accordingly, we design a novel receiver-oriented approach for Bloom filters which satisfies the above condition. The simulation results match well with our theoretical analysis, which demonstrate that our approach guarantees the correctness and efficiency of weak state routing with high probability.In moderate scale networks, it is not necessary to adopt data-centric routing since the indices routing is sufficient and more suitable. In this scenario, the challenge issue is to control the false positive probability of Bloom filters at a low level, and then avoid producing large number redundant queries for each query. This thesis reveals that dynamic data sets are more common and important than static sets. Traditionally, Bloom filters just focus on static set. This thesis proposes dynamic Bloom filters to represent dynamic sets as well as static sets. Dynamic Bloom filters can control the false positive probability at a low level by expanding its capacity as the increase of set cardinality. Mathematical analysis shows that dynamic Bloom filter uses less expected memory than Bloom filters when representing dynamic sets with an upper bound on set cardinality, and is also stable than Bloom filter due to infrequent reconstruction when addressing dynamic sets without an upper bound on set cardinality.On the other hand, many efforts have been done in the field of Web service which is a popular distributed computing technology. A challenge issue is how to dynamically select, bind and invoke Web service that can best meet the requirements of service consumer. This thesis proposes a QoS-Guaranteed and distributed mechanism for Web service discovery, which supports Web service discovery with QoS constraints and enhances the QoS of service discovery system. We propose a unstructured peer-to-peer network of UDDI, which uses an incomplete Kautz digraph as the topology and adopts the probabilistic routing based on Bloom filters. The experimental results show that the new mechanism for Web service discovery possesses higher recall rate, query response rate, and better load balance. Furthermore, the unstructured peer-to-peer network guarantees the query performance, and improves the stability and usability of the service discovery system.