Distributed Join-Idle-Queue Load Balancing With Redundant Tokens

The class of Join-Idle-Queue load balancing algorithms was designed for Cloud service data centers. These algorithms have low overhead and achieve high performance for low to medium loads. In high load scenarios several variations have been proposed to improve the performance. These improvements either put work on the critical path or require two-way communication. In this paper we investigate the impact of adding redundant tokens to the Join-Idle-Queue load balancing algorithm to improve the performance under high loads. This approach is orthogonal to the existing approaches and does not add work on the critical path or require two-way communication. The communication overhead of this approach is upper bounded by one message per job. To assess the performance of the Join-Idle-Queue algorithm with redundant tokens we develop a fluid model that yields numerical results in a fraction of a second and is highly accurate for large systems. Further, the Join-Idle-Queue algorithm with redundant tokens is compared and combined with the so-called early threshold variation to demonstrate that adding redundant tokens is more effective than introducing an early threshold.