Prior Load Balancing Techniques

In this section, we discuss the four existing load balancing algorithms against which we will compare k-Choices: log(N) VS, Proportion, Transfer, and Threshold. The first, log(N) VS, solely attempts to evenly partition the namespace between nodes, ignoring heterogeneity and skew. Proportion creates VSs in proportion to capacity at join time and makes adjustments based on workload. Transfer and Threshold use arbitrary VS relocation to adjust to skew and heterogeneity.

Transfer and Threshold, in particular, are representative of the current state-of-the-art in load balancing algorithms for structured overlays. Proportional is particularly interesting because of its complete decentralization. log(N) VS allows us to show the pros and cons of pure namespace balancing. Because Proportional limits VSset.size to some well-known maximum, it also does not fundamentally change the security characteristics of the system. However, its performance is significantly inferior to Transfer, Threshold, and k-Choices.