Search papers, labs, and topics across Lattice.
This paper introduces an expectation-maximization (EM) algorithm designed to estimate parameters of Markovian arrival process (MAP)-driven quasi-birth-death (QBD) queueing systems using only utilization data, which is more readily available in practical computer systems. By formulating the queueing dynamics as a QBD process, the authors derive expected sufficient statistics for various queueing metrics, allowing for iterative updates of MAP and service parameters within a maximum likelihood framework. The inclusion of Akaike's information criterion aids in selecting the optimal number of MAP phases, addressing the challenge of overfitting when working with incomplete data.
Utilizing only CPU utilization data, this method unlocks accurate parameter estimation for complex queueing systems that typically rely on detailed event-level observations.
Parameter estimation for queueing systems is commonly performed using inter-arrival times, waiting times, or queue-length observations. However, such detailed observations are often unavailable in practical computer systems, where utilization data, such as CPU utilization, is much easier to collect. Utilization data provides only the fraction of time during which the system is busy within each monitoring interval, while the exact arrivals, services, phase transitions, and system states in unobservable periods remain hidden. This paper proposes an expectation-maximization (EM) algorithm for estimating the parameters of Markovian arrival process (MAP)-driven quasi-birth-death (QBD) queueing systems from utilization data. The proposed method formulates the underlying queueing dynamics as a QBD process and derives the expected sufficient statistics for sojourn times, phase transitions, arrivals, and services over both observable and unobservable intervals. These expectations are then used to iteratively update the MAP and service parameters under the maximum likelihood framework. In addition, Akaike's information criterion is introduced to select the appropriate number of MAP phases and mitigate overfitting. The proposed framework enables MAP-based queueing parameter estimation from incomplete utilization observations and provides a practical modeling approach for systems where detailed event-level measurements are difficult to obtain.
