Research On The Key Technology Of Routing Algorithms In Structured Peer To Peer Networks

Structured peer to peer networks are service discovery models that utilize pure distributed routing mechanisms and discovery the services by key, and there are a lot of applications built on them, for example, distributed storage systems, application layer multicast systems and file sharing systems. Many issues relative to routing algorithms have been raised in structured peer to peer protocols, for example, state-efficiency tradeoff, query hotspots, topology mismatch, and heterogeneity. This dissertation mainly focuses on heterogeneity, query hotspots, and how to decrease system load in structured peer to peer networks. The main works are as follows:(1) It is commonly believed that extending structured peer to peer overlays to be capacity-aware will increase maintenance overhead, and it is important to build a capacity aware protocol that is effective and has low maintenance overhead. This paper analyzes the reason why the traditional capacity aware mechanisms implemented by exchanging routing states between peers have long convergence time and increase maintenance overhead inevitably, and then presents an effective capacity-aware structured peer to peer protocol—HeteroChord. HeteroChord implements the capacity aware mechanisms in the peer's joining algorithm, updating algorithm and maintenance algorithms. In HeteroChord, the peers whose routing tables should be updated can be calculated when a new peer joins the system, so the capacity aware mechanisms are efficient. Simulation results indicate that the overhead of the updating algorithm to build a same size network in HeteroChord is far less than the overhead of the updating algorithm in Chord, and the maintenance overhead of HeteroChord is less than that of Chord under churn.(2) This paper presents a virtual double layer structured peer to peer model called Vring based on HeteroChord. The outer layer structure of Vring is HeteroChord which includes all peers, and the inner layer structure is Chord which only includes super peers. There are many differences between Vring and other superpeer-based structured models. In Vring, the routing tables of all peers are the same size, and the superpeers only maintain a super leaf set more than common peers, so the maintenance algorithm of superpeers is simple,and there is no single point of failure. Lastly this paper proposes three application models based on Vring, and tests the characteristics of local indies-based data sharing system by simulation. (3) Peer to peer systems are distributed systems, and decreasing system load is important for improving the scalability of the systems. Caching is always used to achieve load balance in structured p2p systems currently, but none of the current caching algorithms have mechanisms to compute whether a caching is worthwhile, so the current caching algorithms are blindness and always increase system load. This paper presents a caching model in structured peer to peer systems. In order to reduce system load, this caching model uses a passive file requested statistic method which records the current accessing times of each neighbor,and then estimates the reducible query load on the assumption that we cache the file to each neighbor. The reducible query load and the overhead caused by caching determine whether it is worthwhile to cache the file to a neighbor. Simulation results indicate the caching model can reduce system load effectively.(4) Algorithms using virtual server, power of two choices, or replication can not balance the load of peers under Zipf-like requests distribution. This paper presents a self-adaptive load balancing algorithm, in which each peer creates a local load distribution view using a passive load statistic method and a local file requested view using file requested statistic method. When load imbalance exists in the system, the heavy loaded peer will make the logical links which point to itself to point to a light loaded peer in its local load distribution view, with the indegree of the heavy loaded peer decreasing and the indegree of the light loaded peer increasing, the load imbalance magnitude will decrease. When the request load of the heavy loaded peer is high, the peer will use its local file request view to get the popular file and cache the file to corresponding target peer. Simulation results indicate that the system has a good load balance under Zipf-like requests distribution if it runs the balancing algorithm.(5) This paper analyzes the reason for load imbalance under Zipf-like requests distribution in unlimited-state-per-node architecture, and presents a load balancing algorithm called PLC for this kind of structured overlays. PLC uses load aware reactive routing state maintenance strategy and probability-based routing algorithm to improve the probability of the light loaded peers as the intermediate peers forwarding messages, and uses a caching mechanism to decrease the request load of the heavy loaded peers that store popular objects. Results from the simulation experiments indicate that the system has a good load balance under Zipf-like requests distribution if it runs PLC algorithm.