Threshold

Figure 9: Threshold's load balancing algorithm.

Threshold focuses on keeping all nodes' utilizations within a ratio $\rho$, as opposed to between target overload and underload values like the other algorithms. It also keeps the number of VSs to a minimum (one per node). Threshold allows the selection of arbitrary IDs in both its neighbor adjustment and VS relocation phases. We present a modified version of Ganesan et al.'s algorithm [20]. We made two modifications: (a) we use utilization instead of workload because the original algorithm assumes homogeneous capacities and (b) nodes only initiate rebalancing when they increase in level.

Each node has exactly one VS whose ID is initially chosen at random. The rebalancing algorithm shown in Figure 9 is called by a node with VS $v$ at time $t$. Nodes set their current utilization level such that a level increases by one if work has increased by a factor $\rho$, where $c$ is some small constant (line 1). If a node's level has increased, it starts load balancing (line 2). It first attempts to make adjustments with its neighbors (lines 4-9). VS $v$ first sees if local adjustments in the IDs of its successor or predecessor are feasible, potentially shifting some work to them. If the predecessor is lightly loaded compared to $v$, its ID is shifted toward $v$ (line 8). This action should result in its taking some of $v$'s load. $v$ can also move its own ID closer to its predecessor, which potentially shifts work from $v$ to its successor (line 9). If making neighbor adjustments fails, it relocates a lightly loaded node to be its new predecessor (lines 10-15). Ties between successor and predecessor are broken arbitrarily. If neither of these options is available, $v$ attempts to find a new predecessor to take (ideally) half of $v$'s load. $v$ picks a set of VS's at random and relocates the most underutilized whose departure will not overload its successor (line 11-15).

Threshold diminishes the importance of the tuning parameter $\delta$, but introduces a significant parameter in $\rho$. If $\rho$ is too large, load balancing will occur too slowly. If it is too small, nodes will make many unnecessary adjustments. A compromise is to set $\rho$ for slow adjustments but to induce load balancing if the node becomes overloaded even if levels have not changed. We included this compromise in our implementation. Because Threshold always chooses the least utilized VS to relocate, VSs with very high capacity (and therefore low utilization) may tend to be relocated frequently.