Conclusions

We introduced a novel anticipatory load matching algorithm for balancing load in peer-to-peer networks. This algorithm makes explicit the workload assignment problem that previous work attempted to solve implicitly. The algorithm works preemptively as the node is joining to shift the ``right'' amount of work to the joining node. Optionally, it can continue to readjust workload mismatch over time.

After examining the k-Choices algorithm independently, we benchmarked its performance and that of other load balancing algorithms for structured overlays under conditions of node heterogeneity, skew, churn, and workload shift using trace-based simulations.

Prior work on load balancing for p2p systems has either focused on namespace balancing or on systems with more heterogeneous characteristics. We showed that even perfect namespace balancing results in poor performance under realistic conditions. Prior algorithms that do work well under these conditions, Transfer and Threshold, both allow the selection of arbitrary IDs, severely circumscribing their utility on insecure networks. We have shown that k-Choices can provide good load balancing under realistic conditions while retaining strong security properties necessary for wide-area applications.