Delay-Optimal Scheduling for Queueing Systems with Switching Overhead.

Ping-Chun Hsieh, I-Hong Hou, Xi LiuarXiv 2017 · OpenReview

Introduction

In modern communication and transportation systems, the efficiency of scheduling algorithms is often undermined by physical constraints known as switching overheads. Whether it is the time required to reconfigure directional beam patterns in 60GHz wireless networks or the "all-red" clearance intervals at traffic intersections, these delays represent a significant bottleneck. Traditional scheduling policies, such as the Max-Weight algorithm, are designed for systems where switching is instantaneous. However, in the presence of overhead, these policies often lead to instability or excessive delays by switching too frequently.

This paper introduces the Biased Max-Weight (BMW) policy, a novel class of scheduling algorithms specifically designed to handle switching overhead. BMW ensures maximum throughput and achieves near-optimal average delay by incorporating a strategic bias toward the current schedule, effectively amortizing the cost of transitions.

The Problem: The Cost of Switching

The classic Max-Weight policy is celebrated for its throughput-optimality and delay-optimality in ideal settings. However, its performance degrades sharply when a server incurs a time penalty $T_s$ to switch between different sets of queues. In such scenarios, Max-Weight tends to "jitter," switching between queues as soon as a marginal weight difference is detected. This results in the server spending a disproportionate amount of time in transition rather than serving packets, which can lead to system instability even under moderate loads.

Existing solutions, such as Variable Frame-Based Max-Weight (VFMW), attempt to mitigate this by grouping time into frames. However, VFMW requires careful manual tuning of parameters that are highly sensitive to specific traffic patterns, making it impractical for dynamic, real-world environments.

The Biased Max-Weight (BMW) Policy

The core innovation of the BMW policy is a decision-making process that favors the status quo unless a change is significantly beneficial. The server maintains its current schedule $I(t_k)$ until the weight of an alternative schedule exceeds the current weight by a factor determined by the switching overhead and the current state of the system.

The paper defines the switching condition as: $$\left(1 + \frac{T_s}{F(\mathbf{Q}(t_k))}\right) \times (\text{Current Weight}) \leq (\text{Max Possible Weight})$$ where $F(\cdot)$ is a slowly increasing function of the queue lengths. This mechanism ensures that as queue lengths grow, the relative cost of switching decreases, allowing the system to adapt its schedule only when necessary.

Variants: Q-BMW and W-BMW

The authors propose two implementations of this logic:

  1. Q-BMW (Queue-based): Uses queue lengths to calculate weights. While effective for throughput, it can lead to high delays for queues with low arrival rates.
  2. W-BMW (Waiting-time-based): Uses Head-of-Line (HOL) waiting times. This variant provides a much fairer distribution of delay across all queues, ensuring that no single task is neglected for an extended period.

Theoretical Results and Performance

Using Lyapunov drift analysis with a novel "hypothetical observation window," the authors prove that BMW is throughput-optimal. More importantly, they demonstrate that the total average queue length under BMW scales as $O(1/\epsilon^*)$, where $\epsilon^*$ represents the distance to the capacity boundary. This matches the theoretical lower bound for delay scaling in heavy traffic.

Numerical Validation

The policies were tested across several high-stakes scenarios, including 60GHz wireless networks and traffic signal control. In these simulations, BMW consistently outperformed VFMW. A key advantage of BMW is its robustness; unlike VFMW, which requires different parameters for different traffic intensities, BMW achieves optimal performance as its bias parameter $\alpha$ approaches zero, regardless of the traffic scenario. Furthermore, W-BMW demonstrated superior fairness, reducing delays for light-traffic queues by nearly 5x compared to Q-BMW in asymmetric scenarios.

Conclusion and Future Work

The Biased Max-Weight policy represents a significant advancement in scheduling for systems with switching overhead. By intelligently amortizing transition costs, it provides a robust, parameter-free solution that achieves theoretical optimality. While the current work focuses on centralized single-server systems, future research could extend these principles to multi-server environments and distributed networks, as well as testing against non-stationary, real-world traffic traces.

Summary updated

Abstract

We study the scheduling polices for asymptotically optimal delay in queueing systems with switching overhead. Such systems consist of a single server that serves multiple queues, and some capacity is lost whenever the server switches to serve a different set of queues. The capacity loss due to this switching overhead can be significant in many emerging applications, and needs to be explicitly addressed in the design of scheduling policies. For example, in 60GHz wireless networks with directional antennas, base stations need to train and reconfigure their beam patterns whenever they switch from one client to another. Considerable switching overhead can also be observed in many other queueing systems such as transportation networks and manufacturing systems. While the celebrated Max-Weight policy achieves asymptotically optimal average delay for systems without switching overhead, it fails to preserve throughput-optimality, let alone delay-optimality, when switching overhead is taken into account. We propose a class of Biased Max-Weight scheduling policies that explicitly takes switching overhead into account. The Biased Max-Weight policy can use either queue length or head-of-line waiting time as an indicator of the system status. We prove that our policies not only are throughput-optimal, but also can be made arbitrarily close to the asymptotic lower bound on average delay. To validate the performance of the proposed policies, we provide extensive simulation with various system topologies and different traffic patterns. We show that the proposed policies indeed achieve much better delay performance than that of the state-of-the-art policy.
BibTeX
@misc{hsieh2017delay,
  author = {Ping-Chun Hsieh and I-Hong Hou and Xi Liu},
  title = {{Delay-Optimal Scheduling for Queueing Systems with Switching Overhead.}},
  year = {2017},
  eprint = {1701.03831},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1701.03831},
}
Figure