Networks of multi-server queues with parallel processing

Thomas Bonald, Céline ComtearXiv 2016 · arXiv

Introduction

In modern large-scale computer clusters, efficient load balancing is complicated by the inherent heterogeneity of both tasks and resources. Servers are often not interchangeable; specific jobs may require data locality—access to datasets available only on a subset of nodes—or specialized hardware. This creates a complex bipartite compatibility graph between job classes and server pools. Traditional scheduling policies, such as First-Come, First-Served (FCFS), frequently struggle in these environments because they are highly sensitive to job-size variance. In the presence of "elephant" jobs (extremely large tasks), FCFS systems often suffer from the tail-sensitivity problem, where a few massive jobs clog the system and degrade performance for all users.

This research addresses the challenge of implementing "balanced fairness"—a theoretical resource allocation policy that ensures system performance depends only on average workloads rather than the specific distribution of job sizes. The authors propose a practical scheduling mechanism that bridges the gap between theoretical insensitivity and real-world cluster management.

Theoretical Framework: OI Queues and Whittle Networks

The authors' approach is grounded in the mathematical modeling of clusters as multi-server queues. They demonstrate that these systems can be classified as Order Independent (OI) queues. A critical property of OI queues is that they are "quasi-reversible," meaning the system's aggregate state (the number of active jobs per class) can be analyzed independently of the specific arrival sequence.

Furthermore, the research shows that the aggregate state of the cluster behaves like a Whittle network. In such networks, service rates are state-dependent but maintain a local balance, allowing for predictable performance metrics even as the complexity of the compatibility graph increases. By establishing these properties, the authors provide a formal stability condition (Theorem 1) that defines the maximum arrival rates a cluster can sustain before becoming overloaded.

The Re-entrant Algorithm

To implement balanced fairness in practice, the paper introduces the Re-entrant Algorithm. This mechanism relies on two primary components: resource pooling and random service interruptions.

  1. Resource Pooling: When a job reaches the head of its virtual queue, it is processed by all compatible idle servers simultaneously. This maximizes resource utilization across the bipartite graph.
  2. Random Service Interruptions: To prevent large jobs from monopolizing servers, the algorithm uses exponential timers. When a timer expires, the current job is interrupted, its resources are released, and it is moved to the end of the queue.

This frequent interruption effectively transforms the multi-server FCFS system into a Processor-Sharing (PS) environment. In a PS system, resources are distributed more equitably among all active jobs, which is the fundamental requirement for achieving insensitivity to job-size variance.

Performance Evaluation and Results

The algorithm was evaluated using stochastic simulations across three distinct job-size distributions: Bimodal, Hyperexponential, and Zipf-distributed phases. These distributions were chosen specifically to test the system's robustness against high-variance and heavy-tailed workloads.

Key Findings:

  • The Impact of Interruption Frequency: While perfect balanced fairness theoretically requires infinite interruptions, the authors found that even a single interruption per job on average ($m=1$) significantly improves performance over standard FCFS. When the average number of interruptions is increased to five ($m=5$), the system's performance becomes nearly indistinguishable from the theoretical ideal of balanced fairness.
  • Robustness to Heavy Tails: Under the Zipf distribution—the most challenging "worst-case" scenario—the Re-entrant Algorithm maintained stable mean delays. In contrast, standard FCFS performance degraded significantly as the tail of the job-size distribution grew heavier.
  • Scalability: The algorithm's benefits were consistent across various system sizes, from small 3-server models to larger simulated environments with 100 servers.

Limitations and Practical Considerations

While the Re-entrant Algorithm provides a robust solution for tail-sensitivity, the authors acknowledge several hurdles for real-world implementation. The current model assumes that context switching and moving data between servers are "zero-cost" operations. In practice, frequent interruptions can lead to cache misses and significant coordination overhead.

Additionally, the use of exponential timers may be difficult to implement precisely in high-speed networking environments. The authors suggest that "pre-cutting" jobs into smaller, fixed-size tasks might serve as a more practical alternative to random timers. Future research is also needed to adapt this model for more complex job structures, such as "fork-join" tasks where a single job is split into multiple parallel sub-tasks that must be synchronized upon completion.

Conclusion

By combining the mathematical rigor of OI queues with a novel re-entrant scheduling mechanism, this work provides a path toward more predictable and fair resource allocation in heterogeneous clusters. The ability to achieve insensitivity through simple random interruptions offers a powerful tool for engineers to build systems that remain performant regardless of the presence of occasional "elephant" jobs.

Summary updated

BibTeX
@misc{bonald2016networks,
  author = {Thomas Bonald and Céline Comte},
  title = {{Networks of multi-server queues with parallel processing}},
  year = {2016},
  eprint = {1604.06763},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1604.06763},
}
Figure