Proportion

Figure: Proportion: Underloaded nodes create new virtual servers (up to some maximum). Overloaded nodes destroy their own virtual servers (keeping one).

Proportion targets heterogeneity primarily, not workload skew. An administrator initially configures a node with a number of VSs in proportion to its capacity. In addition, previously observed workload may be taken into account. After this initial step, each node adds or sheds load without any communication with other nodes. It was first proposed by Dabek et al. [12].

After setup, each node periodically follows Proportion- Adjust, shown in Figures 5 and 6. A node running Proportion independently creates and destroys virtual servers. If a node is overloaded and is running more than one virtual server, it selects the least loaded VS that will make it underloaded and deletes it (lines 2-3). If a node is underloaded and believes that adding a VS will not put it over its target load, it creates a virtual server (lines 4-6). Without any extra communication, underloaded nodes actively take on more work. The goal of the algorithm is that, over time, this will ease the burden on overloaded nodes because they will assume a smaller percentage of the workload as the number of VSs increases.

Figure 6: Proportion's Adjust algorithm.

Load balancing in complete isolation has its drawbacks. First, a node with only a few VSs may not be able to form a good estimate of what the cost of creating a new one will be. Second, a meager machine still might be overloaded even if it is only running one VS. If a new physical server enters and has significantly less capacity than the current low-end servers, the system may take a long time to adjust to this new lowest common denominator. Third, if an overloaded node deletes one of its VSs, this may overload its neighbor, resulting in cascades of deletes. Finally, when the system is underloaded, Proportion can cause all nodes to create their maximum number of VSs, greatly increasing state, routing hops, and churn.