Varying Churn

Figure 14: Percentage of successfully routed queries for varying rates of churn.

Because k-Choices helps nodes make good load balancing choices proactively, we hypothesized that at high churn rates, it would offer better performance than the other algorithms. To test this, we created a set of synthetic churn traces with varying average lifetimes and used the same capacity distribution from the trace. We ran each algorithm with each node initiating 10 queries per second on average.

We plot the results from uniform and skewed ($\alpha=1.2$) query distributions in Figure 14. The data confirm our hypothesis that k-Choices adapts well to rates of high churn. We found that both Transfer and Proportion were able to sustain high natural churn rates for uniform queries, but that they induced $1.1-1.5\times$ and $5-10\times$ more artificial churn, respectively, than k-Choices. Again, the variation in success rates is more prominent with skewed queries. This is because k-Choices monitors workload before insertion. No Load Balancing improves slightly as lifetimes increase because fingers remain valid for longer. Again log(N) VS had worse performance than No Load Balancing.

In both uniform and Zipf, Threshold's success rate declines as nodes' lifetimes increase. This occurs because Threshold makes the gaps between VSs so non-uniform that it significantly increases the average number of hops, e.g., from $5.6$ for 15 minute lifetimes to $7.3$ for 4 hour lifetimes for uniform queries. Because queries are taking more hops and nodes are similarly load balanced, each query is less likely to succeed.