Queueing Theory: Lectures & Exercises

Queueing-Theory

Course Overview

This page brings together graduate-level lectures and exercises on queueing theory, the mathematical study of waiting lines. The material covers the foundations of Markov chains (discrete-time and continuous-time), fundamental queueing models, queueing networks (Whittle networks, Jackson networks, quasi-reversible networks), the insensitivity property in queueing systems, generalized semi-Markov processes, and detailed analysis of sojourn duration in processor sharing queues. Each lecture is available as a downloadable PDF. Two of the lectures also include exercises with detailed solutions. This material builds on the foundations established in Measure & Probability and is closely related to Point Processes, with applications to Wireless Networks.

Lectures

1 Discrete-Time Markov Chains

PDF and exercises of the lecture on Discrete-Time Markov Chains, the foundational stochastic processes underpinning queueing theory.
📄 PDF ✏️ Exercises
We begin with the basics of Markov chains, providing a foundational understanding of Markov processes and their significance. We then explore the basics of discrete-time Markov chains in depth, starting with the transition matrix and graph, followed by detailed discussions on the period of a state, irreducible Markov chains, cyclic classes, matrix structure, return set structure, the invariant measure, the strong Markov property, and the number of visits to a state. We examine recurrence, transience, and invariant measure, discussing the invariant measure for a recurrent chain, the invariant distribution for a positive recurrence chain, and the ergodic theorems for Markov chains. We explore the asymptotic behavior of Markov chains with convergence in variation, the coupling method, and convergence to the stationary distribution. We cover the reversed Markov chain with the concept of reversibility and the Kolmogorov criterion for reversibility. Finally, we discuss Foster’s theorem for positive recurrence, a crucial result for establishing the conditions under which a Markov chain exhibits positive recurrence.

Course Outline:

  1. Basics of Markov Chains
  2. Basics of Discrete-Time Markov Chains
    1. Transition Matrix and Graph
    2. Transition Matrix
    3. Transition Graph
    4. Period of a State and an Irreducible Markov Chain
    5. Cyclic Classes and Matrix Structure
    6. Return Set Structure
    7. Further Results on Periodic Markov Chains
    8. Invariant Measure
    9. Strong Markov Property
    10. Number of Visits to a State
  3. Recurrence, Transience and Invariant Measure
    1. Recurrence and Transience
    2. Invariant Measure for a Recurrent Chain
    3. Invariant Distribution for a Positive Recurrence Chain
    4. Ergodic Theorems for Markov Chains
  4. Asymptotic Behavior of Markov Chains
    1. Convergence in Variation
    2. Coupling Method
    3. Convergence to the Stationary Distribution
  5. Reversed Markov Chain
    1. Reversibility
    2. Kolmogorov Criterion for Reversibility
  6. Foster’s Theorem for Positive Recurrence

2 Continuous-Time Markov Chains

PDF and exercises of the lecture on Continuous-Time Markov Chains (CTMCs), exploring their fundamental concepts, practical realizations, properties, and advanced topics.
📄 PDF ✏️ Exercises
We begin with the basics of CTMCs, starting with the family of transition matrices that define the probabilities of moving between states over time, then the transition semigroup as a generalized framework. We introduce the infinitesimal generator, a critical operator capturing the instantaneous rate of change of the process, and present Kolmogorov’s equations, both forward and backward. We conclude this section with the invariant measure and the strong Markov property. We then detail the realization of a generator, exploring filtration and stopping time, the strong Markov property for Poisson point processes, the realization of a generator using Poisson point processes, and regular jump Markov chains with their regenerative structure. We examine regular jump Markov chain properties: irreducibility, recurrence, transience, the invariant measure for a recurrent chain, the relationship between invariant distribution and positive recurrence, with an illustrative example of a birth and death process. We address asymptotic behavior, ergodic theorems, and the flow rate between subsets. Finally, we cover continuous-time reversal, defining the reversed chain, extending to negative times, discussing reversibility and the behavior of the reversed process, presenting a reversal test for generators, the restriction of a Markov chain to a subset of states, and the product of generators.

Course Outline:

  1. Basics of Continuous-Time Markov Chains
    1. Family of Transition Matrices
    2. Transition Semigroup
    3. Infinitesimal Generator
    4. Kolmogorov’s Equations
    5. Invariant Measure
    6. Strong Markov Property
  2. Realization of a Generator
    1. Filtration and Stopping Time
    2. Strong Markov Property for Poisson Point Processes
    3. Realization of a Generator Using Poisson Point Processes
    4. Regular Jump Markov Chain
    5. Regenerative Structure
  3. Regular Jump Markov Chain Properties
    1. Irreducibility, Recurrence and Transience
    2. Invariant Measure for a Recurrent Chain
    3. Invariant Distribution and Positive Recurrence
    4. Example: Birth and Death Process
    5. Asymptotic Behavior
    6. Ergodic Theorems
    7. Flow Rate Between Subsets
  4. Continuous-Time Reversal
    1. Reversed Chain
    2. Extension to Negative Times
    3. Reversibility
    4. Behaviour of Reversed Process
    5. Reversal Test for Generators
    6. Restriction of a Markov Chain
    7. Product of Generators

3 Fundamental Queues

PDF of the lecture on Fundamental Queues, the mathematical study of waiting lines and queueing systems.
📄 PDF
We begin by introducing the essential terminology and notation used in queueing theory, including Kendall’s notation, a standardized method for describing the characteristics of different queueing systems. We then focus on processor sharing queues, a class of models where multiple users or tasks share the service capacity of a single server. We examine the single-class processor sharing queue, where all users belong to a single class and share the server’s capacity equally. The discussion extends to multi-class processor sharing queues, accommodating multiple user classes with distinct arrival and service characteristics. We explore class-dependent service rates, generalized processor sharing, and discriminatory processor sharing. Finally, we address infinite server queues and capacity constraints, starting with the M/M/∞ queue, a fundamental model for systems with an unlimited number of servers, and the Erlang queue (M/M/C/C), where a finite number of servers and no waiting room introduce blocking probabilities. We extend the analysis to multi-class infinite server queues and multi-class Erlang queues, highlighting their ergodic behavior, invariant distributions, and blocking probabilities.

Course Outline:

  1. Queue Terminology and Notation
  2. Processor Sharing Queues
    1. Single Class Processor Sharing Queue
    2. Multi-Class Processor Sharing Queue
    3. Class-Dependent Service Rates
    4. Generalized Processor Sharing
    5. Discriminatory Processor Sharing
  3. Infinite Server Queues and Capacity Constraints
    1. Infinite Server Queue
    2. Erlang Queue
    3. Multi-Class Infinite Server Queue
    4. Multi-Class Erlang Queue

4 Whittle Queueing Networks

PDF of the lecture on Whittle Queueing Networks, exploring the theoretical foundations and practical applications of this advanced analytical framework.
📄 PDF
We begin with the essential definitions and notations that form the backbone of Whittle queueing networks, including state spaces, transition rates, and queueing disciplines. We then focus on the Markovian modeling of Whittle networks, covering the formulation of traffic equations, the invariant distribution for the Whittle generator, the conditions for irreducibility and ergodicity of the Whittle process, and the concept of time reversal and its relation to Burke’s theorem. We illustrate the theoretical concepts with practical examples of Whittle networks, demonstrating that the balance property of service rates is an intrinsic characteristic, exploring Jackson queueing networks, and examining queues in series. We investigate various performance metrics within Whittle networks, including the Gibbs distribution characterizing equilibrium, the interpretation of traffic intensity, the analysis of sojourn time, and user throughput. Finally, we address the restriction of a Whittle process, exploring the restricted Whittle generator, blocking probabilities in restricted Whittle networks, and the number of users in restricted Whittle processes.

Course Outline:

  1. Basic Definitions and Notations
  2. Markovian Modeling of Whittle Network
    1. Traffic Equations
    2. Invariant Distribution for Whittle Generator
    3. Irreducibility and Ergodicity of Whittle Process
    4. Time Reversal and Burke’s Theorem
  3. Examples of Whittle Networks
    1. Service Rates Balance
    2. Multiclass Queues as Whittle Networks
    3. Jackson Queueing Networks
    4. Queues in Series
  4. Performance in Whittle Networks
    1. Gibbs Distribution
    2. Interpretation of Traffic Intensity
    3. Sojourn Time
    4. User Throughput
  5. Restriction of a Whittle Process
    1. Restricted Whittle Generator
    2. Blocking Probabilities in Restricted Whittle Networks
    3. User Number in Restricted Whittle Processes

5 Quasi-reversible Queues and Networks

PDF of the lecture on Quasi-reversible Queues and Networks, focusing on their unique properties and the simplifications they offer in analyzing complex queueing systems.
📄 PDF
We begin with quasi-reversible queues, starting with a formal definition accompanied by basic examples to illustrate the concept. We then delve into the key properties of quasi-reversible queues, highlighting their significance in simplifying the analysis of queueing systems, with further examples to deepen the understanding of these properties in various contexts. We discuss partial balance equations, essential for understanding the flow of entities through the system. We extend the concept of quasi-reversibility to quasi-reversible queueing networks, defining these networks and examining their basic properties. We demonstrate that quasi-reversible queueing networks admit an invariant distribution with a product-form structure, discuss the conditions under which these networks are ergodic, and present the Arrival Theorem, which extends the PASTA property to quasi-reversible settings and provides insights into the state distribution observed by users during transitions.

Course Outline:

  1. Quasi-reversible Queues
    1. Definition and Basic Examples
    2. Properties of Quasi-reversible Queues
    3. Further Examples
    4. Partial Balance Equations
  2. Quasi-reversible Queueing Networks
    1. Definition and Basic Properties
    2. Invariant Distribution and Ergodicity
    3. The Arrival Theorem

6 Insensitivity in Queues and Networks to Service Distribution

PDF of the lecture on Insensitivity in Queues and Networks to Service Distribution, a property ensuring that the equilibrium distribution remains unaffected by the specific form of the service distribution.
📄 PDF
We lay the groundwork by introducing the fundamental concepts of equilibrium distribution and insensitivity in queueing systems, covering the essential principles and theoretical results that form the basis for understanding insensitivity to service distributions. We then delve into symmetric queues and their insensitivity, beginning with an introduction to phase-type distributions, instrumental in modeling service times. We explore the Markov renewal process for phase-type distributions and the concept of time reversal in such processes. We introduce the symmetric multiclass M/PH/· queue and discuss its Markovian modeling, leading to the derivation of the invariant distribution of symmetric queues and the analysis of their distributional properties. Finally, we extend the discussion to Whittle networks insensitivity, presenting the insensitivity theorem for Whittle networks and its converse, establishing the conditions under which the insensitivity property holds, and extending performance results to a more general class of networks.

Course Outline:

  1. Equilibrium Distribution and Insensitivity
  2. Symmetric Queues and Their Insensitivity
    1. Phase-type Distribution
    2. Markov Renewal Process for Phase-type Distributions
    3. Time Reversal of Markov Renewal Process
    4. Symmetric Multiclass M/PH/· Queue
    5. Markovian Modeling of Symmetric Queues
    6. Invariant Distribution of Symmetric Queues
    7. Distributional Properties of Symmetric Queues
  3. Whittle Networks Insensitivity
    1. Preliminary Concepts and Properties
    2. Insensitivity Theorem for Whittle Networks
    3. Converse Insensitivity Theorem for Whittle Networks
    4. Extension of Performance Results in Whittle Networks

7 Generalized Semi-Markov Processes

PDF of the lecture on Generalized Semi-Markov Processes (GSMP), robust frameworks for modeling complex queuing systems including multiclass queues and networks.
📄 PDF
We begin by examining the GSMP model, starting with its fundamental components: the state space, sources of events, and transition mechanisms. We define the probability space for GSMPs, the distribution of GSMP’s point processes, and cover the time evolution of GSMPs. We address the insensitivity property of GSMPs, presenting the key assumptions required for a GSMP to exhibit insensitivity, examples of insensitive sources, useful lemmas for analyzing insensitivity, the impact of scaling on point processes, and the GSMP Insensitivity Theorem from the Palm point of view. We transition from the Palm to the stationary point of view, extending the GSMP framework to include negative times, introducing the Slivnyak inverse construction, and revisiting the GSMP Insensitivity Theorem in the stationary framework. We explore the necessity of insensitivity balance equations with the converse theorem on GSMP insensitivity, establishing the conditions under which insensitivity is not only sufficient but also necessary. We illustrate the theory with examples of queue sensitivity, presenting cases of queues that exhibit insensitivity and others that lack it. Finally, we introduce Reallocatable Generalized Semi-Markov Processes (R-GSMPs), discussing their insensitivity properties and applications to symmetric M/GI/· queues and symmetric multiclass M/GI/· queues.

Course Outline:

  1. The GSMP Model
    1. Components of GSMP
    2. Probability Space for GSMP
    3. Distribution of GSMP’s Point Processes
    4. Time Evolution of GSMP
    5. Further Examples of GSMP for Queues
  2. Insensitivity of GSMP
    1. Assumptions for GSMP
    2. Examples of Insensitive Sources
    3. Useful Lemmas for Insensitivity
    4. Change of Scale of Point Processes in GSMP
    5. GSMP Insensitivity Theorem: Palm Point of View
  3. From Palm to Stationary Point of View
    1. Extension of GSMP to Negative Times
    2. Slivnyak Inverse Construction for GSMP
    3. GSMP Insensitivity Theorem: Stationary Point of View
  4. Necessity of Insensitivity Balance Equations
    1. The Converse Theorem on GSMP Insensitivity
  5. Examples of Queue Sensitivity
    1. Examples of Queues Exhibiting Insensitivity
    2. Examples of Queues Lacking Insensitivity
  6. Reallocatable Generalized Semi-Markov Processes
    1. R-GSMP Definition and Insensitivity
    2. Symmetric M/GI/· Queue
    3. Symmetric Multiclass M/GI/· Queue

8 Sojourn Duration in Processor Sharing Queues

PDF of the lecture on Sojourn Duration in Processor Sharing Queues, a critical metric for performance analysis closely related to delay and latency in communication networks.
📄 PDF
We build on previously discussed formulas for the average sojourn duration in various queueing systems by presenting complementary results. Specifically, we explore the mean and distribution of the sojourn duration given the required service amount. We cover the expected sojourn duration in single-class and multi-class processor sharing queues, the conditional distribution of sojourn duration in these queues, and extensions to scenarios with class-dependent service rates and discriminatory processor sharing.

Course Outline:

  1. Single Class PS Queue
  2. Multiclass PS Queue
    1. Class-Dependent Service Rates
    2. Discriminatory Processor Sharing

About These Topics

These graduate-level lectures on queueing theory are designed for students and researchers seeking a rigorous mathematical treatment of stochastic systems with waiting lines. The material develops the theory from foundational Markov chain results through to advanced topics in queueing networks and insensitivity theory, with applications to telecommunications, computer networks, service industries, and operations research. We begin with the rigorous foundations of discrete-time and continuous-time Markov chains, including transition matrices and graphs, the infinitesimal generator and Kolmogorov’s equations, the strong Markov property, invariant measures and distributions, recurrence and transience, ergodic theorems, the coupling method for convergence to the stationary distribution, time reversal and the Kolmogorov criterion for reversibility, and Foster’s theorem for positive recurrence. The realization of a generator via Poisson point processes and the regenerative structure of regular jump Markov chains are also developed. The lectures then turn to fundamental queueing models, including Kendall’s notation, processor sharing queues (single-class, multi-class, with class-dependent service rates, generalized, and discriminatory), infinite server queues (M/M/∞), and the Erlang queue (M/M/C/C) with blocking probabilities. We then develop Whittle queueing networks with traffic equations, invariant distributions, Burke’s theorem, the Gibbs distribution, and applications to Jackson queueing networks and queues in series. The course concludes with advanced topics: quasi-reversible queues and networks with the Arrival Theorem and the PASTA property, insensitivity to service distributions with phase-type distributions, Markov renewal processes, and symmetric queues; generalized semi-Markov processes (GSMP) with the GSMP Insensitivity Theorem from both the Palm point of view and the stationary point of view, the Slivnyak inverse construction, and reallocatable GSMPs; and the detailed study of sojourn duration in processor sharing queues, a critical metric for delay and latency in communication networks.

Last Updated on 25 mai 2026 by Mohamed Kadhem KARRAY

Laisser un commentaire