Analytical methods and distribution fitting for response times in markovian queueing systems
File(s)
Author(s)
Bor, Julianna
Type
Thesis or dissertation
Abstract
Markovian queueing systems are popular in performance modelling due to their analytical tractability and ability to represent diverse real-life systems. In this thesis, we calculate response time distributions --- essential for quantile-based international standards and quality of service requirements --- for various queueing models and develop an efficient method for model parameterization required by analytical tools calculating response times.
We first focus on the processor-sharing (PS) queueing discipline, known for its analytical complexity.
Using the generating function method, we calculate the Laplace-Stieltjes transform of the unconditional response time distribution in an M/M/1-PS queue.
We then consider two M/M/1-PS queues in tandem and derive the response time distribution numerically for the first time.
Next, we consider two parallel PS queues with Join-the-Shortest-Queue (JSQ) scheduling.
The functional equations obtained contain partial generating functions and their partial derivatives, and therefore cannot be solved by commonly used techniques.
We solve these equations numerically and derive the first-ever solution for the response time distribution in two parallel JSQ-PS queues.
Finally, we focus on queues with phase-type (PH) arrival and PH or matrix exponential (ME) service processes, as real-world systems often deviate from exponential assumptions. Accurate response time calculations require properly parameterised distributions, but fitting real-world data to distributions is challenging due to over-parameterization and large equation orders.
We introduce a novel fitting method using quasi-birth-death processes parameterised by compositional PH distributions, and a novel ME fitting algorithm.
Unlike existing fitting methods which are typically limited to a few states, our methods can fit PH and ME distributions with hundreds of states.
The novel methods proposed in this dissertation advance both the theoretical and practical aspects of performance modelling.
Given the importance of response time distributions in performance analysis—a relevance unlikely to diminish—we hope these methods inspire continued innovation in the field.
We first focus on the processor-sharing (PS) queueing discipline, known for its analytical complexity.
Using the generating function method, we calculate the Laplace-Stieltjes transform of the unconditional response time distribution in an M/M/1-PS queue.
We then consider two M/M/1-PS queues in tandem and derive the response time distribution numerically for the first time.
Next, we consider two parallel PS queues with Join-the-Shortest-Queue (JSQ) scheduling.
The functional equations obtained contain partial generating functions and their partial derivatives, and therefore cannot be solved by commonly used techniques.
We solve these equations numerically and derive the first-ever solution for the response time distribution in two parallel JSQ-PS queues.
Finally, we focus on queues with phase-type (PH) arrival and PH or matrix exponential (ME) service processes, as real-world systems often deviate from exponential assumptions. Accurate response time calculations require properly parameterised distributions, but fitting real-world data to distributions is challenging due to over-parameterization and large equation orders.
We introduce a novel fitting method using quasi-birth-death processes parameterised by compositional PH distributions, and a novel ME fitting algorithm.
Unlike existing fitting methods which are typically limited to a few states, our methods can fit PH and ME distributions with hundreds of states.
The novel methods proposed in this dissertation advance both the theoretical and practical aspects of performance modelling.
Given the importance of response time distributions in performance analysis—a relevance unlikely to diminish—we hope these methods inspire continued innovation in the field.
Version
Open Access
Date Issued
2025-03-04
Date Awarded
2026-01-01
Copyright Statement
Attribution-NonCommercial 4.0 International Licence (CC BY-NC)
License URL
Advisor
Knottenbelt, William
Casale, Giuliano
Publisher Department
Department of Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)