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:
- 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.
- 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