Numerous proposals exist for load balancing in peer-to-peer (p2p)
networks. Some focus on namespace balancing, making the distance
between nodes as uniform as possible. This technique works well
under ideal conditions, but not under those found empirically.
Instead, researchers have found heavy-tailed query distributions
(skew), high rates of node join and leave (churn), and wide
variation in node network and storage capacity (heterogeneity).
Other approaches tackle these less-than-ideal conditions, but give
up on important security properties. We propose an algorithm that
both facilitates good performance and does not dilute security. Our
algorithm,
k-Choices, achieves load balance by greedily
matching nodes' target workloads with actual applied workloads
through limited sampling, and limits any fundamental decrease in
security by basing each nodes' set of potential identifiers on a
single certificate. Our algorithm compares favorably to four others
in trace-driven simulations. We have implemented our algorithm and
found that it improved aggregate throughput by
in a widely
heterogeneous system in our experiments.
