Locality-aware randomized load balancing algorithms for DHT networks

Structured P2P overlay networks based on a consistent hashing function have an aftermath load balance problem that needs to be dealt with. A load balancing method should take into account both proximity and dynamic features of DHTs, Randomized matching between heavily loaded nodes with lightly loaded nodes can deal with the dynamic feature. But current randomized methods are unable to consider physical proximity of the node simultaneously. There are locality-aware methods that rely on an additional logical network to capture the physical locality in load balancing. Due to the cost for network construction and maintenance, these locality-aware algorithms can hardly deal with DHTs with churn. This paper presents a locality-aware randomized load balancing algorithm to deal with both of the proximity and dynamic features of DHTs. We introduce a factor of randomness in the probing process in a range of proximity to deal with the DHT churn. We further improve the randomized load balancing efficiency by d-way probing. Simulation results show the superiority of a locality-aware 2-way randomized load balancing in DHTs, in comparison with other pure random policies and locality-aware sequential algorithms. In DHTs with churn, it performs no worse than the best churn resilient algorithm.