1 Introduction
Overthe past years, the immense popularity of peer-to-peer (P2P) resource sharing services has produced a significant stimulus to content-delivery overlay network research [20]. An important class of the overlay networks is the distributed hash tables (DHTs) that map keys to the nodes of a network based on a consistent hashing function; see [17] and references therein for representatives of the DHTs. In a DHT, each node and key has a unique ID, and each key is mapped to a node according to the DHT definition. The ID space of each DHT is partitioned among the nodes, and each node is responsible for those keys whose IDs are located in its space range. However, consistent hashing produces a bound of O(log n) imbalance of keys between nodes, where n is the number of nodes in the system [9]. The objective of load balancing is to prevent nodes from being overloaded by distributing application load among the nodes in proportion to their capacities. An effective load-balancing algorithm should work for DHTs with and without churn and meanwhile be capable of exploiting the physical proximity of the network nodes to minimize operation cost. Network churn represents a situation where a large percentage of nodes and items join, leave, and fail continuously and rapidly, leading to unpredicted P2P network size. By proximity, we mean that the logical proximity abstraction derived from DHTs do not necessarily match the physical proximity information in reality.