Data load balancing is a challenging task in the P2P systems. Distributed hash table (DHT) abstraction, heterogeneous nodes, and non uniform distribution of objects are the reasons to cause load imbalance in structured P2P overlay networks. Previous works solved the load balancing problem by assuming the homogeneous capabilities of nodes, unawareness of the link latency during transferring load, and imposing logical structures to collect and reassign load. We propose a distributed load balancing algorithm with the topology awareness feature by using the concept of virtual servers. In our approach, each node collects neighborhood load information from physically close nodes and reassigns virtual servers to overlay nodes based upon the topology of underlying network. Consequently, our approach converges data load balancing quickly and it also reduces the load transfer cost between nodes. Moreover, our approach increases the quality of load balancing among close nodes of overlay and it also introduces a new tradeoff between the quality of load balancing and load transfer cost among all overlay nodes. Our simulations show that our approach reduces the load transfer cost and it saves network bandwidth respectively. Finally, we show that the in-degree imbalance of nodes, as a consequence of topology awareness, cannot lead to a remarkable problem in topology aware overlays.
Karger and Ruhl @cite_20 present dynamic load balancing algorithms without using virtual servers. In their algorithms, lightly loaded nodes should be neighbors of heavily loaded nodes in order to reassign their load. They maximize utilization of load in nodes but they do not completely consider different node capacities. Moreover, It is not clear whether their algorithms are practical or not.
@cite_20
2109440766
In this paper we examine the problem of balancing load in a large-scale distributed system when information about server loads may be stale. It is well known that sending each request to the machine with the apparent lowest load can behave badly in such systems, yet this technique is common in practice. Other systems use round-robin or random selection algorithms that entirely ignore load information or that only use a small subset of the load information. Rather than risk extremely bad performance on one hand or ignore the chance to use load information to improve performance on the other, we develop strategies that interpret load information based on its age. Through simulation, we examine several simple algorithms that use such load interpretation strategies under a range of workloads. Our experiments suggest that by properly interpreting load information, systems can (1) match the performance of the most aggressive algorithms when load information is fresh relative to the job arrival rate, (2) outperform the best of the other algorithms we examine by as much as 60 when information is moderately old, (3) significantly outperform random load distribution when information is older still, and (4) avoid pathological behavior even when information is extremely old.