Varying Skew

Some workloads are heavily skewed and several of the algorithms were able to support up to $\alpha=1.2$ . We wanted to examine how much skew they might support. To test this, we used the synthetic 60 minute average lifetime trace and the capacity distribution from the trace as we varied $\alpha$ . As before, we ran each algorithm with each node initiating 10 queries per second on average.

We plot the results in Figure 16. They show that none of the algorithms can support an extremely skewed workload, e.g., one where the top destination is almost $5\times$ that of the next rank. Not only do the algorithms decline in their average success rates, but they also all become less stable. For example, the standard deviation of success rates sampled over time for k-Choices at uniform is $0.001\%$ and at $\alpha=4.8$ it is $8\%$ . To see if increasing $\kappa$ had an impact at high skew, we ran k-Choices with $\kappa=16$ . We found that it performed better (at $14\%$ ) than $\kappa = 8$ , but also exhibited high variance.

**Figure 16:** Percentage of successfully routed queries for varying rates of skew.
$\includegraphics{graphs/skew-delta}$

Jonathan Ledlie 2006-01-06