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
1589020577
Load sharing is a technique to improve the performance of distributed systems by distributing the system workload from heavily loaded nodes, where service is poor, to lightly loaded nodes in the system. Previous studies have considered two adaptive load sharing policies: sender-initiated and receiver-initiated. In the sender-initiated policy, a heavily loaded node attempts to transfer work to a lightly loaded node and in the receiver-initiated policy a lightly loaded node attempts to get work from a heavily loaded node. Almost all the previous studies assumed the first-come first-served node scheduling policy; furthermore, analysis and simulations in these studies have been done under the assumption that the job service times are exponentially distributed and the job arrivals form a Poisson process (i.e., job inter-arrival times are exponentially distributed). The goal of this paper is to fill the void in the existing literature. We study the impact of these assumptions on the performance of the sender-initiated and receiver initiated policies. We consider three node scheduling policies-first-come first-served (FCFS), shortest job first (SJF), and round robin (RR) policies. Furthermore, we also look at the impact of variance in the inter-arrival times and in the job service times. Our results show that: (i) When non-preemptive node scheduling policies (FCFS and SJF) are used, the receiver-initiated policy is (substantially) more sensitive to variance in inter-arrival times than the sender-initiated policies and the sender-initiated policies are relatively more sensitive to the variance in job service times; (ii) When the preemptive node scheduling policy (RR) is used, the sender-initia