Real Waiting Time in Single-Server Resource Queue with Markovian Arrival Process

Anatoly Nazarov, Alexander Moiseev, Ivan Lapatin, Svetlana Paul, Olga Lizyura, Pavel Pristupa, Xi Peng, Li Chen, Bo BaiCommunications 2023 · DOI · OpenAlex

TL;DR

This paper tackles the discrepancy between "virtual" and "real" waiting times in telecommunication networks with correlated traffic. By modeling a single-server queue with a Markovian Arrival Process (MAP), the authors derive the exact probability distribution for real waiting time and propose a simple, highly accurate exponential approximation that significantly reduces computational overhead for network engineers.

What Problem Does This Paper Address?

In classical queueing theory (like the simple M/M/1 model), we often assume arrivals follow a Poisson process. In these systems, "virtual waiting time"—the delay a hypothetical customer would face if they arrived at an arbitrary moment—is identical to the "real waiting time" experienced by actual customers.

However, modern telecommunication traffic is rarely Poisson; it is often correlated, meaning the timing of one packet influences the next. In these scenarios, virtual and real waiting times diverge. Because packets in a correlated flow (like a Markovian Arrival Process) cannot arrive at just any instant, the "average" state of the system at an arrival moment is different from the "average" state of the system at any random time. Most existing research focuses on virtual waiting time because it is mathematically easier to handle, but this leads to inaccurate predictions of actual packet latency. The authors aim to bridge this gap by providing a rigorous way to calculate what a packet actually experiences.

Methods

The authors model the system as a single-server resource queue:

  • Input: A Markovian Arrival Process (MAP), which captures the correlation between inter-arrival times.
  • Buffer: An unlimited, continuous-type buffer (fluid model).
  • Service: A server that processes information at a constant speed $v$.

To solve this, they employ a two-dimensional Markov process $\{k(t), S(t)\}$, where $k(t)$ is the state of the arrival process and $S(t)$ is the amount of work in the buffer. They derive the Kolmogorov system of equations for the steady state and use Laplace-Stieltjes Transforms (LST) to find the vector characteristic function of the waiting time.

The most practical contribution is their approximation method. Recognizing that calculating the exact inverse Fourier transform is computationally expensive, they propose a simple exponential approximation for the Cumulative Distribution Function (CDF): $$\tilde{F}(x) = 1 - (1 - L)e^{-\gamma x}$$ where $L$ is the probability of zero waiting time and $\gamma$ is a parameter estimated using the method of moments.

Datasets

The paper does not use external real-world datasets. Instead, it validates the mathematical model using a numerical simulation of a MAP/GI/1 system.

  • The arrival process was defined by specific 4x4 matrices ($D_0, D_1$).
  • Packet lengths followed a Gamma distribution (shape = 2, scale = 8).
  • The system was tested across various loads ($\rho = 0.3, 0.5, 0.7, 0.9$) to ensure the model holds up under both light and heavy traffic.

Key Insights and Ideas

  • The "Arrival Gap": The paper highlights that the difference between virtual and real waiting time is most pronounced when the system load is low. As the system becomes more congested, the two distributions begin to converge.
  • Correlation is Key: The structure of the flow matters. In non-Poisson flows, there are "forbidden" periods where a request simply cannot be received due to the internal state of the arrival process, which shifts the real waiting time distribution away from the virtual one.
  • Computational Efficiency: While the exact theoretical distribution (Equation 18 in the paper) is accurate, it is difficult to compute. The proposed approximation (Equation 19) provides a "good enough" result for engineering purposes with a fraction of the math.

Key Results

The authors used the Kolmogorov distance ($\Delta_T$) to measure the error between their theoretical formulas, their approximation, and the simulation results.

  • Accuracy: The distance between the theoretical distribution and the simulation ($\Delta_{T\_Sim}$) was extremely low, ranging from 0.0006 to 0.0072, proving the math is sound.
  • Approximation Performance: The proposed simple exponential approximation ($\Delta_{T\_App}$) also performed remarkably well, with errors staying between 0.0018 and 0.0078.
  • Visual Confirmation: Plots in the paper show that the "Approx_WT" and "Theor_WT" lines are virtually indistinguishable from the simulation results, while the "VWT" (Virtual Waiting Time) line clearly deviates, especially at the start of the curve.

Limitations and Future Work

  • Single Server Focus: The model is strictly for a single-server system. Real-world nodes often involve multi-server configurations or complex scheduling priorities.
  • Infinite Buffer Assumption: The paper assumes an unlimited buffer. In high-speed hardware, buffers are finite, and packet loss (dropping) becomes a factor that this specific model doesn't account for.
  • Parameter Sensitivity: The approximation relies on the method of moments to find $\gamma$. While it worked well for the Gamma distribution used in the study, its performance on "heavy-tailed" distributions (common in some types of internet traffic) remains to be seen.

The authors suggest that these results will be particularly helpful for designing systems where "Quality of Service" (QoS) guarantees are required, as real waiting time is the metric that actually defines user experience.

Summary updated

BibTeX
@inproceedings{nazarov2023real,
  author = {Anatoly Nazarov and Alexander Moiseev and Ivan Lapatin and Svetlana Paul and Olga Lizyura and Pavel Pristupa and Xi Peng and Li Chen and Bo Bai},
  title = {{Real Waiting Time in Single-Server Resource Queue with Markovian Arrival Process}},
  booktitle = {Communications},
  year = {2023},
  doi = {10.1007/978-3-031-32990-6\_10},
}

Loading related content...

Figure