Structured Peer-to-peer Network Routing Study Load Balancing Problems

P2P networks have become one of the most important popular Internet applications. Distributed hash tables (DHTs) based structured P2P networks have attracted a lot of attention because they are highly efficient in object location, robust, scalable and fully self-organized as well. However, DHT networks have an inherent load imbalance factor. What's more, heterogeneity of node capacity, skewness of workload and dynamism of network could aggravate the load imbalance problem, thus degrading the quality of service and availability of the network.In DHT networks, the load of a node consists of two parts: object load, which is caused by serving objects, and routing load, which is caused by forwarding lookups. Current researches on load balance mostly focus on object load, while ignoring routing load. If some nodes are overloaded with too much routing traffic, then the successful rate and latency of the queries must deteriorate. So it remains an open problem to deal with routing hotspots. This dissertation concentrates on handling routing load imbalance in DHT based P2P networks. In summary, the major contributions of this dissertation are as follows:(1) Indegree adjustment is an effective, light-weighted and heterogeneity-aware approach to balance lookup traffic. To improve the efficiency of indegree adjustment approach in DHT based P2P networks, we propose a fairly layered load balancing algorithm (FLLB). FLLB is designed based on the concept of fairness and uses the fairness index to measure how equally the load is distributed among nodes. It splits the indegree and load of a node into several sublayers. Each node measures the fairness index of each layer periodically, then dynamically adjusts indegree of each layer according to the fairness index and directs the routing load from heavy loaded nodes to underloaded nodes, leading to more efficient and finer-grained adjustment. Simulation results show that FLLB algorithm could improve the fairness of routing load distribution with low overhead.(2) In structured P2P networks, the skewness in query pattern can result in load imbalance and even congestion. To address the problem, we propose a dynamic congestion control algorithm based on indegree adjustment approach (HGCG). The basic idea behind the algorithm is that it dynamically identifies and forms the nodes near a hotspot into a hotspot group, and then reallocates loads among them by indegree migration. To account for node heterogeneity, we further divide a hotspot group into several capacity groups according to node capacity, and then schedule inter and intra capacity group adaptation respectively. In order to prevent node congestion, we also propose to use the average residue capacity of an inlink as the metric to guide the adjustment. Results from experimental evaluation demonstrate that HGCG algorithm can effectively reduce the level of congestion in case of load burst compared with existing approaches.(3) In DHT based P2P networks, routing load can only be redistributed locally, but not globally, via indegree adjustment. We propose a hybrid algorithm combining indegree adjustment and virtual server (VS) approaches to address both local and global lookup imbalance in DHT networks. We divide local nodes into zones, and select strong nodes to form a virtual server group (VSG). Hot zones can apply for virtual servers from VSG in order to distribute load in system wide. Nodes and VSs in the zones use indegree adjustment to maintain zone balance. In order to save the cost of creating and maintaining VS, we only initiate relevant part of VS's routing table and modify the object publishing process to ignore VS when choosing the target nodes of the objects. To prevent malicious nodes from launching Sybil attack, we borrow the idea of secure ID to assign verifiable IDs to VS. The results of our simulation experiments show that VSG algorithm, combining the merits of indegree adjustment and virtual server (VS) approaches, is able to cope with routing load imbalance problem in DHT networks.(4) To alleviate the impact of lookup skewness on routing load distribution, we propose a routing load dispersion (RLD) mechanism for structured P2P networks. RLD mechanism manages to disperse the routing load to more nodes such that the original underloaded nodes in the network have a chance to dedicate their free capacities for routing. RLD mechanism guarantees that lookups can be routed to the correct destinations without extra hops with high probability, and this can be achieved by a simple extension to the underlying DHT network. Current routing load-balancing algorithms, such as HGCG and VSG, can accommodate RLD mechanism to further improve their performance. Results from theoretical analysis and experimental evaluation demonstrate the correctness and effectiveness of RLD mechanism.