Load balancing in a hierarchical DHT-based P2P system

Hierarchical DHT (HDHT) systems, outperforming flat DHTs with respect to scalability and network locality, became an important P2P research area in recent years. Appropriate load balancing algorithms, which are available only for flat DHTs so far, are also required for the reliability and scalability of HDHTs. However, their impact is different. In HDHTs, failures caused by overloaded nodes in higher hierarchical layers affect larger portions of the network than overloaded nodes in lower layers. In comparison to flat DHTs, HDHTs offer an additional dimension of balancing load, i.e., through varying relevant parameters of the hierarchical organization. This makes load balancing in HDHTs significantly different from load balancing in flat DHTs. In this paper, we exploit this possibility and present a novel load balancing algorithm for a two-tier HDHT system. Analytically and by simulations we show that our algorithm provides good load balancing performance, while at the same time generating less overhead than, e.g., the renowned "power of two choices" algorithm.