Load Balancing in P2P Networks: Using Statistics to Fight Data and Execution Skew

In recent years, structured peer-to-peer (P2P) have gained an important role in the design of large-scale distributed systems. However, due to their strict data placement rules, they are often prone to three main load imbalances, i.e., range, data, and execution skew. Many of today’s load balancing algorithms focus only on range skew and assume the network data rate to be the bottleneck. In applications that focus on distributed request processing, those assumptions are not valid as messages are typically small but can produce significant load at the application level. Examples of such applications are complex name resolution mechanisms that, e.g., involve security checks, or multi-dimensional search. Here, data skew and execution skew are most important and the system performance is limited by the number of application requests a peer can process. To provide a solution for such scenarios, we have developed a new load balancing algorithm which is based on ID management. Our algorithm collects statistics of overlay link usage during normal operation and uses this information to provide suitable IDs to joining peers. Without using regular maintenance messages, it improves the rate of successfully answered requests by a factor of up to 3 in typical scenarios. We have evaluated the algorithm via extensive simulation that also includes scenarios with churn and heterogeneous peers. This work presents the first load balancing algorithm that can handle all three types of skew in scenarios that focus on processed application requests as the bottleneck.