Course AlQT: Algorithmic Methods in Queuing Theory

Important information

Course description

This course focuses on the algorithmic aspects of stochastic operations research, with a particular emphasis on Markov processes and queueing theory. It explores both exact and approximate solutions for performance measures, such as the mean and distribution of customer numbers and sojourn times in various systems.

For certain Markov processes and queueing systems, exact expressions for these performance measures can be derived, but they are often challenging to handle numerically. In many cases, even for seemingly simple systems, obtaining exact solutions is impossible, but accurate approximations can be developed. This course introduces and examines algorithmic techniques that enable the exact and approximate analysis of a wide range of systems.

Topics and techniques covered

• Direct and indirect algorithmic solution methods:
  • The course begins by analyzing the two-server queue under the join-the-shortest-queue protocol, which is used in data and communication centers to optimize resource allocation. This system generates Markov processes with two infinite dimensions, which are beyond the reach of standard techniques for finite-dimensional Markov chains and one-dimensional queueing systems.
  • We will study three distinct algorithmic solution methods:
    • The compensation approach and power series algorithm, which directly solve the equilibrium (balance) equations.
    • A third approach based on generating functions, which provides an indirect solution.
  • While all three methods yield the same results, they vary in complexity and application, offering insights into approximations, bounds, and numerical outcomes.
  • Additionally, we will demonstrate how these methods can be extended to handle higher-dimensional systems, as well as other protocols, and conclude by broadening their applicability across various other systems.
• Numerical methods for Markov processes:
  • The course covers methods to solve both the steady-state and transient behavior of finite-state Markov processes. We will also focus on constructing error bounds for steady-state distributions.
• Numerical methods for polling models:
  • Polling models are multi-queue single-server models, a versatile class of models that are widely applicable in many application areas. Exploiting the branching structure in a wide class of polling models, several techniques for efficiently calculating the waiting-time performance in polling models will be discussed, including the Buffer Occupancy Method, the Station-Time Approach, and the Descendant Set Approach. Moreover, several approximation methods for waiting-time distributions based on heavy-traffic limits and interpolation methods will be discussed.
• Advanced queueing models:
  • We extend basic queueing models by introducing more complex elements such as Renewal phase-type arrival processes and phase-type service times. These additions often result in multi-dimensional Markov processes confined to a strip (i.e., one finite dimension). By exploiting the specific structure of these stochastic processes, we will demonstrate how one can extend the results of the M/M/1 queue by clustering states, extending the classical geometric results of the M/M/1 model from a scalar to a matrix.
  • Techniques for analyzing such models include spectral expansion, matrix-analytic methods, and generating function techniques.
• Additional topics:
  • The course also covers advanced topics such as the numerical inversion of generating functions and Laplace transforms, critical for practical applications.
  • Approximation techniques like Whitt’s Queueing Network Analyzer, alongside data-driven approaches, including symbolic regression.

By the end of the course, students will have mastered a range of algorithmic techniques for analyzing complex stochastic systems, with a strong focus on both exact and approximate methods for Markov processes and queueing models.

Detailed content

• Direct, indirect, and iterative solution methods for the equilibrium/balance equations
• Algorithmic methods for transient analysis of Markov chains
• Matrix-analytic methods, Markov chains on a strip, M/M/1-type models
• Spectral expansion method
• Polling methods: buffer occupancy method, station-time approach, descendant set approach
• Approximation methods: Whitt’s Queueing Network Analyzer, heavy-traffic methods, interpolation methods
• Data-driven methods, symbolic regression
• Generating function (or boundary value) method
• Compensation method
• Power series method

Literature

Prerequisites

Examination

Address of the lecturers

Dr. S. Kapodistria
Dept. of Mathematics & Computer Science
Eindhoven University of Technology
P.O. Box 513, 5600 MB Eindhoven
Phone: 040-2475825
E-mail: s.kapodistria@tue.nl

Prof.dr. R.D. van der Mei
CWI, Stochastics group
Science Park 123
1098XG Amsterdam
Phone: 020-5929333
E-mail: mei@cwi.nl