Generalized switch scheduling improves mean response time in heavy traffic
Optimal Scheduling in Generalized Switch in Heavy Traffic
Performance
Summary
Scheduling tasks efficiently when there are many different types of jobs and limited resources is a tough problem. The authors study a flexible model called the generalized switch that represents many real-world systems with multiple job types and servers. They introduce a new scheduling method called Smallest Equalizing Bucket (SEB) that groups jobs by how long they take and balances service among these groups to reduce waiting times, especially when the system is very busy. They prove SEB is the best possible method in heavy traffic and show simulations that support its effectiveness.
What this means in practice
- •For network schedulers: Reduce delays in handling different types of network traffic by balancing scheduling across job duration groups under heavy load.
- •For data center operators: Improve overall job turnaround times by grouping and scheduling tasks based on known execution times in complex multiresource systems.
Authors
Runhan Xie, Ziv Scully, Rhonda Righter, Izzy Grosof
Abstract
The generalized switch is a highly flexible queueing model, covering multiclass, multiserver, and multiresource queueing systems as well as a wide variety of stochastic networks. Although many scheduling policies have been developed for this model, they almost entirely address unknown job duration settings. How to optimally use known job durations in the generalized switch has remained open. Moreover, optimizing mean response time remains open in both settings. We introduce the first policy to guarantee heavy-traffic optimal mean response time in the generalized switch, our Smallest Equalizing Bucket (SEB) policy. The key challenge in designing an optimal scheduling policy is that we must simultaneously prioritize small jobs and also minimize resource waste, all while fitting within the generalized switch's service options. SEB overcomes this challenge by grouping jobs into duration-based buckets and enforcing an "equalizing" service structure that keeps each bucket balanced while still prioritizing the smallest jobs. We prove SEB's heavy-traffic optimality. Simulations further confirm the effectiveness of SEB-inspired heuristics.