Research On Optimization Technology Of Constant Degree P2P Systems' Loading Balance And Overlay Topology

Peer-to-peer (P2P) technique has become a popular network computing paradigm since the end of last century, which emphasizing all nodes should have equal functions. Comparing with traditional distributed computing techniques, such as C/S or B/S, P2P technique can make full use of idle resources at internet's edge, thus has attracted wide attention from industry, academe and common network users. Constant degree P2P systems belong to the third generation structural P2P technique, with constant peers'degree ensuring not only efficient routing but strong stability, less control message and network overhead. Due to these good properties, constant degree DHTs are turning into the P2P domain's new rising star and promising hotspot in recent years. However, it is often hard to convert a standard constant degree digraph to a flexible DHT schema adapting to dynamic P2P environments. Thus, most research about constant degree P2P focus on DHT's construction and maintenance, while leaving optimization and supporting to upper-layer application behind and restricting constant degree P2P's applications and development to a large extent. This thesis deeply studies the optimization technology of constant degree P2P's loading balance and topology, and presents solutions for dealing with four unsolved key problems of constant degree P2P:How to build balanced topology? All DHTs include ID assignment methods to select proper ID for new joining peers. As foundation to implement and maintain DHT overlays, an ideal ID assignment method should be simple, decentralize and beneficial to load balancing, and assure peer IDs'uniformity in the name space as well. However, the bit-shifting routing schema of the constant digraph de Bruijn and Kautz induces that, the constant degree P2P systems'ID assignment can't adopt former randomization or other improved methods simply. To address this problem, this thesis presents an ID Assignment method based on the internal structure Routing Forest in the topologies, which regularly aggregates local balancing information to guide new nodes'joinness for overall balance, and the maintenance algorithm is proposed as well. The experimental results shows, with low maintenance and routing message overhead, the length of IDs differ by at most 2, thus the system's loading balance is efficiently ensured. This method can expand to a construction, maintenance and load balance technology easily.How to achieve system's load balancing? Load balancing is the importance guarantee that P2P system will perform better by against several specific peers storing too much and becoming system's bottleneck. However, All known methods either can't fit dynamically for different load distributions, or bring too much overhead, or can't fulfill the requirement for balanced toplogy of constant degree P2P. To address this problem, this thesis presents an efficient load balancing algorithm called Routing Information Statistic (RIS) for constant degree P2P systems. With the statistic of routing information, RIS judges how many Virtual Server (VS) that a new join super peer can run, and then join all VSs evenly and fast with low cost based on the Spanning Tree Peer Set, assuring each peer of owning a key space proportional to its capability; RIS also judges whether a new join data object should be redirected and which peer is the most suitable redirect storage. Experimental results show, with low redirect overhead, RIS keeps the constant degree P2P system load-balanced under different load distributions without additional data structure.How to make P2P system support complex queries as well as range query? More and more applications require the structural P2P systems to support not only exact-match key searching, but other kinds of complex query such as range query. However, the hardness to construct the constant degree P2P make related studies behind classical structural P2P. Aiming at this problem, this thesis first analyzes the data locality according to the logical construction process of P2P, and educed that the routing locality can't be guaranteed under the classical construction technology. And then a general-purpose construction optimizing technique towards efficient complex queries is proposed, which adds an embedding transformation layer between data layer and DHT overlay. In this way, adjacent data objects are stored in overlay's adjacent peers and the data locality is improved, so that the number of peers referred in complex queries can be minimized with a limited time overhead. To validate this technology, the first constant degree P2P system based on Kautz digraph FissionE is reconstructed as a typical example, which including the re-allocating of resources, query algorithm and locality maintenance strategies. Experimental results show this construction optimizing technique can assure data locality, reduce query cost and leads to systems'efficiency without changing the underlying DHT layer.How to construct the geographic delay incorporated constant degree topology? All incorporating geographic delay technologies try to reduce communication overhead between peers through matching the overlay topology and the geographic network. Although lots of ways of coping this problem have been proposed in academe, but these existing technologies can't be replanted to the constant degree P2P systems simply for the constant degree digraphs'special naming and routing schema. Aiming at this problem, this thesis proposes the CO-FissionE hierarchical topology construction technology for constant degree P2P system FissionE. In CO-FissionE, peers are firstly clustered to form the lower level overlay, and in the higher level, a"coincide lower bound"rule is used to construct inter-cluster links which guarantee efficient inter-cluster communication and limit the number of inter-cluster neighbors. At the same time, in order to make clusters with internal hierarchical structure to be geographically-aware, Corresponding to constant degree topologies'bit-shifting schema and strict balance demand, this thesis also proposes an efficient sub-cluster merge method. It firstly relaxes the high-level topology's balance demand to reduce the number of redirected peers, and then using the joined peer's information to guide joining peers efficiently. The experiment results show that CO-FissioinE achieves incorporating geographic delay with limited overhead and reduce the query cost efficiently, and the sub-cluster merge method enhances the merge efficiency while ensuring matchint to the inter-cluster delay property. The CO-FissionE schema can not only reserve the routing merit of FissionE, but also strengthen the communication's localization; what's more, they can be replanted to other constant degree P2P systems with other optimization technology.