The Component Queues Method for Quasi-Birth-Death Process Fitting and Analysis
Julianna Bor, Giuliano Casale, Evgenia Smirni
Markovian queueing analysis requires fitting models of arrival and service processes, such as phase-type (PH) distributions, to represent system measurements accurately. However, fitting real-world data is challenging in practice due to model over-parameterization, the large order of the fitting equations, and the limited understanding of the impact of fitting decision on queueing. Motivated by these issues, we present a methodology that uses quasi-birth-death (QBD) processes to fit PH distributions directly from measured queueing data. Core to the proposed method is a new result that reduces the solution of a broad class of QBD processes to the analysis of a collection of simpler queueing systems featuring PH distributions of small order, leading to exact or approximate solutions depending on the chosen arrival process. The proposed method reduces the computational complexity of solving a QBD process from cubic to quadratic for this special class of QBD processes. Numerical results on real traces demonstrate that this feature enables accurate PH fitting from real-world system data