Resilient and efficient load balancing in distributed hash tables

As a fundamental problem in distributed hash table (DHT)-based systems, load balancing is important to avoid performance degradation and guarantee system fairness. Among existing migration-based load balancing strategies, there are two main categories: (1) rendezvous directory strategy (RDS) and (2) independent searching strategy (ISS). However, none of them can achieve resilience and efficiency at the same time. In this paper, we propose a group multicast strategy (GMS) for load balancing in DHT systems, which attempts to achieve the benefits of both RDS and ISS. GMS does not rely on a few static rendezvous directories to perform load balancing. Instead, load information is disseminated within the formed groups via a multicast protocol. Thus, each peer has enough information to act as the rendezvous directory and perform load balancing within its group. Besides intra-group load balancing, inter-group load balancing and emergent load balancing are also supported by GMS. In GMS, the position of the rendezvous directory is randomized in each round, which further improves system resilience. In order to have a better understanding of GMS, we also perform analytical studies on GMS in terms of its scalability and efficiency under churn. Finally, the effectiveness of GMS is evaluated by extensive simulation under different workload and churn levels. (C) 2008 Elsevier Ltd. All rights reserved.