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.
Many load balancing methods have been suggested to handle this problem in P2P systems. The first work has been done by Chord @cite_16 . They diminish load of overlay nodes by using the concept of virtual servers. They allocate @math virtual servers per physical node and suppose that all overlay nodes are similar. However, their approach does not practically resolve the load balancing problem.
@cite_16
1589020577 2120849241 2963728009 2396984061
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant factor of optimal. First, we give an improved version of consistent hashing, a scheme used for item to node assignments in the Chord system. In its original form, it required every network node to operate O(log n) virtual nodes to achieve a balanced load, causing a corresponding increase in space and bandwidth usage. Our protocol eliminates the necessity of virtual nodes while maintaining a balanced load. Improving on related protocols, our scheme allows for the deletion of nodes and admits a simpler analysis, since the assignments do not depend on the history of the network. We then analyze several simple protocols for load sharing by movements of data from higher loaded to lower loaded nodes. These protocols can be extended to preserve the ordering of data items. As an application, we use the last protocol to give an efficient implementation of a distributed data structure for range searches on ordered data. Load balancing for distributed servers is a common issue in many applications and has been extensively studied. Several distributed load balancing schemes have been proposed that proactively route individual requests to appropriate servers to best balance the load and shorten request response time. These schemes do not require a centralized load balancer. Instead, each server is responsible for determining, for each request it receives from a client, to which server in the pool the request should be forwarded for processing. We propose a new request routing scheme that is more scalable to increasing number of servers and request load than the existing schemes. The method combines random server selection and next-neighbor load sharing techniques that together prevent the staleness of load information from building up when the number of servers increases. Our simulation shows that it outperforms existing schemes under a piggyback-based load update model. We consider load balancing in a network of caching servers delivering contents to end users. Randomized load balancing via the so-called power of two choices is a well-known approach in parallel and distributed systems. In this framework, we investigate the tension between storage resources, communication cost, and load balancing performance. To this end, we propose a randomized load balancing scheme which simultaneously considers cache size limitation and proximity in the server redirection process. In contrast to the classical power of two choices setup, since the memory limitation and the proximity constraint cause correlation in the server selection process, we may not benefit from the power of two choices. However, we prove that in certain regimes of problem parameters, our scheme results in the maximum load of order @math (here @math is the network size). This is an exponential improvement compared to the scheme which assigns each request to the nearest available replica. Interestingly, the extra communication cost incurred by our proposed scheme, compared to the nearest replica strategy, is small. Furthermore, our extensive simulations show that the trade-off trend does not depend on the network topology and library popularity profile details. Load balancing is important for the efficient execution of numerical simulations on parallel computers. In particular when the simulation domain changes over time, the mapping of computational tasks to processors needs to be modified accordingly. Most state-of-the-art libraries addressing this problem are based on graph repartitioning with a parallel variant of the Kernighan-Lin (KL) heuristic. The KL approach has a number of drawbacks, including the optimized metric and solutions with undesirable properties. Here we further explore the promising diffusion-based multilevel graph partitioning algorithm DibaP. We describe the evolution of the algorithm and report on its MPI implementation PDibaP for parallelism with distributed memory. PDibaP is targeted at small to medium scale parallelism with dozens of processors. The presented experiments use graph sequences that imitate adaptive numerical simulations. They demonstrate the applicability and quality of PDibaP for load balancing by repartitioning on this scale. Compared to the faster ParMETIS, PDibaP’s solutions often have partitions with fewer external edges and a smaller communication volume in an underlying numerical simulation.