Research On Peer-to-Peer Resource Location In Large-scale Distributed Systems

In recent years, peer-to-peer (P2P) computing has become a popular network computing paradigm. Researches and applications of peer-to-peer computing have spread into many fields. Resource location is an important basic service in large-scale peer-to-peer systems. Resource location technique implements three basic functions of peer-to-peer systems: topology construction, message routing and resource search, thus it has very important influence on the scalability, robustness and performance of peer-to-peer systems. Compared with other distributed systems, peer-to-peer systems exhibit some special characteristics, such as large-scale, dynamic, and heterogeneity, which have brought many challenging problems for peer-to-peer resource location technique. According to their topologies, peer-to-peer systems can be divided into two categories: unstructured topology and structured topology. Based on characteristics of different topologies, this thesis deeply studies peer-to-peer resource location technique and its applications.Distributed hash table (DHT) scheme is the core technique to locate resources in structured peer-to-peer systems. Currently many researches have concentrated on constant degree and high performance DHT schemes. Compared with the hypercube, the de Bruijn or the d-torus topology that used in existing DHT schemes, the Kautz graph has optimal diameter and other better properties. This thesis analyzes the properties of the Kautz graph, and proves that the Kautz graph with long path routing is (1+o(1))-congestion-free. Then the thesis proposes FissionE, the first effective DHT scheme based on the Kautz graph. FissionE is a novel constant degree, O(logN) diameter and (1+o(1))-congestion-free DHT scheme. Some novel algorithms and mechanisms are proposed in FissionE, such as neighborhood invariant topology rule, Kautz_hash naming algorithm and local optimum self-stabilization mechanism. FissionE can achieve good load balance, high performance, and low congestion and these properties are carefully evaluated by formal proofs or simulations. The average degree of FissionE is 4, the average routing latency is less than log₂N (N is the number of peers in the system), and the maintenance cost is less than 3log₂N. FissionE can achieve better performance than CAN or Koorde when peer-to-peer systems are large-scale.Usually, DHTs only support exact-match search. As DHTs are adopted in many fields, more and more applications require DHTs to support range query. This thesis proposes Armada, an efficient range query technique based on FissionE. In order to meet the different requirements of single-attribute and multiple-attribute range queries, Armada respectively proposes order-preserving naming algorithms Object_hash and Armada_hash, range queries algorithms PIRA and MAPRA, and Balancing mechanisms. Armada effectively solves the problem that the latency of range queries on general DHT infrastructure can't be guaranteed, and it can support efficient single-attribute and multiple-attribute range queries and achieve...