Efficient Load Balancing Techniques for Self-organizing Content Addressable Networks
|
| Title | Efficient Load Balancing Techniques for Self-organizing Content Addressable Networks |
| Authors | |
| Abstract | Balancing the load in a decentralized P2P systemis a challenging problem due to the dynamic nature of suchenvironment and the absence of global knowledge about theactual composition of the system.In this paper, we addressthe problem of load balancing in large scale and selforganizingP2P systems managing multidimensional data.We propose simple and efficient decentralized mechanismsto evenly distribute the data load among the participatingnodes in Content Addressable Networks. The basic idea isto enable a new node that joins the system to share the loadwith a heavily loaded node which is already in the system,such that the load is still evenly distributed among all theparticipating nodes. In the multiple random choices method,the new node probes the load of some existing nodes selecteduniformly at random, then chooses the heaviest node amongthem to share the load with. In this paper, we extend thismethod in three ways. First, the new node probes a poolof nodes proportional to the network size and composition.Specifically, the number of probed nodes is logarithmic tothe network size. This property enables to achieve a constantload imbalance factor which is very small without the needto estimate the network size. Second, the probed nodes arenot selected at random, but they are well spread over the keyspace; which enables a good estimation of the actual datadistribution and network composition, which enables to copewell with large-scale data imbalance. Third, the selection ofnodes to probe is restricted to the immediate and distantneighbors of a randomly chosen node. The cost incurred byour join-based load balancing method is very small, sinceall load information is piggybacked to periodic maintenancemessages exchanged between nodes and their neighbors.Unlike other methods, we do not make use of external indexnor assume any global knowledge. We also generalize thefirst method to enable locating a heavily loaded node througha sequential walk starting from a randomly selected node.This new method incurs additional overhead, however itachieves much smaller load imbalance. We also study therobustness of our join-based load balancing method againstadversarial attacks. Using simulation, we analyze the impactof the number of entry points on load balancing. To the bestof our knowledge we are the first to address this problem.We conduct an experimental study using uniform and nonuniformdata distributions to demonstrate the effectivenessand the scalability of our proposals. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2010-03-01 |
| Source | Journal of Networks Vol 5, No 3 (2010): Special Issue: Recent Trends in Wireless Communications and Networking |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |