Trace Results

Figure 13: Percent of successfully routed queries for trace-driven simulations with varying loads.

Our third experiment examines how the load balancing algorithms responded to different degrees of applied workload using trace-driven churn and capacity. In almost all cases, we found k-Choices performed the same as or better than the other algorithms.

Each experiment used the Gnutella trace as described in Section V. Each ran for twelve hours with statistics recorded for the second half of the experiment. We varied the applied query load by orders-of-magnitude and recorded the percentage of queries that reached their destination. This experiment captures factors such as artificial churn and large numbers of VSs per node that some of the algorithms induce.

We plot the results in Figure 13. They show that all of the algorithms, except for Threshold, can sustain high success rates when queries are uniform, although k-Choices and Transfer do slightly better Proportion. At 100 queries/node, the $95^{th}$ percentile of the number of VSs/node was $128$ for Proportion (the maximum), compared to $1.9$ for k-Choices and $16.1$ for Transfer. Performance for k-Choices in passive mode declines after 10 queries/node. We plot $\kappa=16$; $\kappa = 8$ performed about $10\%$ worse and $\kappa=64$ performed about $10\%$ better at this workload level.

When queries are skewed ($\alpha=1.2$), only k-Choices and Transfer can sustain high query rates. At this level, the other algorithms are unable to maintain low utilization of low capacity nodes. Log(N) VS performed worse than No Load Balancing in these experiments and is not shown in the figures.