Dynamic Scheduling for Markov Modulated Single-server Multiclass Queueing Systems in Heavy Traffic

Amarjit Budhiraja, Arka P. Ghosh, Xin LiuarXiv 2012 · DOI · arXiv

TL;DR

This paper extends the classic $c\mu$ scheduling rule to queueing systems operating in fluctuating environments (e.g., wireless networks affected by weather). The authors prove that a modified "$c\mu^*$" rule—which prioritizes tasks based on averaged service rates—is asymptotically optimal in heavy traffic, regardless of whether the environment changes faster or slower than the arrival of jobs.

What Problem Does This Paper Address?

In traditional queueing theory, we often assume that arrival and service rates are constant. However, modern systems—especially wireless communication networks—operate in "changing environments." External factors like temperature, humidity, or physical interference can cause the quality of a channel (and thus the service rate) to fluctuate over time.

The challenge is determining how to schedule different classes of jobs (e.g., voice vs. data) to minimize long-term costs when the system is under "heavy traffic" (operating near its maximum capacity). Specifically, if the environment is constantly shifting, should the scheduler try to react to every tiny change, or is there a simpler, more robust strategy?

Methods

The authors use Heavy Traffic Analysis to simplify a complex, discrete queueing system into a more tractable continuous model.

  1. Markov Modulation: They model the environment as a finite-state Markov process that "modulates" the arrival and service rates.
  2. Three Time-Scale Regimes: They analyze three distinct scenarios based on a scaling parameter $\nu$:
  3. Fast-changing environment: The environment fluctuates much faster than the jobs arrive.
  4. Same-scale environment: The environment and job processes change at similar speeds.
  5. Slow-changing environment: The environment shifts slowly compared to the arrival/service rates.
  6. Brownian Control Problem (BCP): By applying functional central limit theorems, they show that the scaled queueing system converges to a "Brownian Control Problem." This is a continuous-time optimization problem where the "noise" is represented by Brownian motion.
  7. The $c\mu^*$ Rule: They propose a priority policy where classes are ranked by the product of their holding cost ($c$) and their average service rate ($\mu^*$), where the average is taken over the environment's stationary distribution.

Datasets

As a theoretical paper in probability and operations research, no real-world datasets were used. Instead, the authors conducted numerical simulations to validate their theorems. They simulated a system with 2 job classes and 2 environment states to compare the performance of their proposed $c\mu^*$ rule against a "dynamic" $c\mu$ rule that attempts to react to the environment's instantaneous state.

Key Insights and Ideas

  • Averaging is Optimal: The most significant insight is that you don't need to know the exact state of the environment at every moment to be optimal. Simply knowing the statistical average of the service rates ($\mu^*$) is enough to achieve asymptotic optimality in heavy traffic.
  • State Space Collapse: In the heavy traffic limit, the multi-dimensional system (one dimension per job class) "collapses" into a one-dimensional workload process. The optimal strategy is to keep all buffers empty except for the one with the lowest $c\mu^*$ value.
  • Robustness to Observation: Because the $c\mu^*$ rule relies on averages, it is highly robust. Even if the environment is not directly observable (you can only estimate its statistical properties), the rule remains effective.
  • Counter-intuitive Superiority: Numerical results suggest that the $c\mu^*$ rule can actually outperform a "dynamic" $c\mu$ rule that tries to be "smarter" by reacting to the current environment state. This happens because the dynamic rule can lead to excessive switching or "chatter" that doesn't benefit the system in the long run.

Key Results

  • Asymptotic Optimality: The authors prove (Theorem 3.1) that the $c\mu^*$ priority policy minimizes the infinite horizon discounted cost as the system scaling $n$ goes to infinity for all three environmental regimes.
  • Convergence to BCP: They successfully characterize the limit of the cost function in terms of the solution to a Brownian Control Problem (Theorem 4.1).
  • Simulation Validation: In a test case with $n=100$, the $c\mu^*$ rule consistently yielded lower discounted costs than the dynamic $c\mu$ rule across various environmental speeds (e.g., a cost of 60.18 vs 61.87 in a fast-changing scenario).

Limitations and Future Work

  • Service Rate Constraints: For the "same-scale" and "slow-changing" regimes, the authors assumed service rates were independent of the environment to make the proofs work. While their simulations suggest the $c\mu^*$ rule still works when service rates are environment-dependent in these cases, they leave the formal proof as an open mathematical problem.
  • Single Server Focus: The paper focuses on a single-server system. Extending this to multi-server systems or complex networks with multiple nodes would be a natural next step.
  • Linear Costs: The model assumes linear holding costs. Future research could explore convex cost functions, which might lead to different optimal policies (like the "generalized $c\mu$ rule").

Summary updated

Abstract

This paper studies a scheduling control problem for a single-server multiclass queueing network in heavy traffic, operating in a changing environment. The changing environment is modeled as a finite state Markov process that modulates the arrival and service rates in the system. Various cases are considered: fast changing environment, fixed environment and slow changing environment. In each of the cases, using weak convergence analysis, in particular functional limit theorems for renewal processes and ergodic Markov processes, it is shown that an appropriate "averaged" version of the classical cμ-policy (the priority policy that favors classes with higher values of the product of holding cost c and service rate μ) is asymptotically optimal for an infinite horizon discounted cost criterion.
BibTeX
@misc{budhiraja2012dynamic,
  author = {Amarjit Budhiraja and Arka P. Ghosh and Xin Liu},
  title = {{Dynamic Scheduling for Markov Modulated Single-server Multiclass Queueing Systems in Heavy Traffic}},
  year = {2012},
  eprint = {1211.6831},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1211.6831},
}
Figure