|
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 node's 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 20% in a widely heterogeneous system
in our experiments.
|
