07.11.2012 – Tutorial by Andrea Marin

Title: From M/M/1 queues to Quasi Birth and Death Processes
Date: 7 November, 2012 – 12.30
Type: tutorial
Speaker: Andrea Marin (Ca’ Foscari, Venice)

Abstract: Markov chains are an important framework for studying queueing systems. However, deriving the steady-state behavior of a queue may be a really hard task because of the large number of states (possibly infinite) of the process. Indeed, the brute-force numerical algorithms quickly become numerically unstable and time-expensive. This tutorial aims at showing how the geometric structure of the Markov chains underlying a class of queues called “Quasi Birth and Death” can be exploited to derive its stationary state probabilities and performance indices.

Prerequisites: Matrix manipulation (product, sum, transposed), solution of linear systems in matrix form (including matrix inversion), rank of a matrix, continuous/discrete time Markov chains (stationary analysis)