A joint moments based analysis of networks of MAP/MAP/1 queues

András Horváth, Gábor Horväth, Miklós TelekPerformance Evaluation 2010 · DOI

TL;DR

This paper introduces a novel "moments-based" approximation method for analyzing complex queueing networks with correlated arrival and service processes. By focusing on a compact set of moments rather than the full Markovian process description, it significantly reduces computational complexity, enabling the analysis of larger and more intricate networks that were previously intractable.

What Problem Does This Paper Address?

Analyzing queueing networks, which are fundamental to understanding systems like computer networks and telecommunication infrastructure, is challenging when the traffic and service times are not simple Poisson processes or exponential distributions. Real-world systems often exhibit bursty, correlated traffic and service times. While Markov Arrival Processes (MAPs) offer a powerful way to model these complex behaviors, analyzing networks of MAP-based queues (MAP/MAP/1) can become computationally prohibitive due to the exponential growth of state spaces. Existing methods for approximating the output process of these queues often lead to large, complex MAPs, hindering scalability. This paper aims to bridge this gap by providing a more efficient and scalable approximation technique.

Methods

The core of this paper's contribution lies in its "moments-based" approach to approximating the output process of MAP/MAP/1 queues. Instead of directly modeling the output as a complex MAP, the authors first compute the joint moments of consecutive inter-departure times. These moments capture essential statistical properties of the departure process.

The key steps are:

  1. Moments-Based Representation of MAPs: Leveraging recent results, the paper uses a compact set of joint moments (specifically, the first 2n-1 moments and (n-1)² joint moments for an order-n MAP) to uniquely characterize a MAP. This is a more parsimonious representation than the full matrix description (Do, D1).
  2. Output Process Approximation: For a MAP/MAP/1 queue, the paper derives a method to compute the joint moments of consecutive inter-departure times. This involves analyzing the queue's internal dynamics and constructing a new MAP that matches these computed moments. This constructed MAP then serves as the approximate output process.
  3. Network Analysis: This approximated output MAP is then used as the input to subsequent nodes in the queueing network. The moments-based representation allows for flexible "model reduction" by simply truncating the moment set, keeping the complexity manageable even for large networks.

This approach contrasts with existing methods that often rely on truncating the exact, potentially infinite, MAP representation of the output process, leading to large state spaces.

Datasets

Not discussed in the paper. The paper uses simulated queueing network examples for evaluation.

Key Insights and Ideas

  • Parsimony is Power: The central idea is that a few key moments can capture the essential behavior of a complex stochastic process, making it computationally tractable. This is a significant departure from methods that require full process descriptions.
  • Scalability Achieved: By using moments as the basis for approximation and model reduction, the paper demonstrates a method that scales well with network size. The complexity of the approximate MAPs remains small, regardless of the number of nodes in the network.
  • Flexibility in Model Reduction: The moments-based representation allows for easy control over the complexity of the approximate MAPs by simply choosing the number of moments to match. This offers a natural way to balance accuracy and computational cost.
  • Bridging Theory and Practice: The paper connects theoretical advancements in MAP characterization with practical needs for analyzing complex queueing networks, offering a viable solution for previously intractable problems.

Key Results

The paper presents numerical examples demonstrating the effectiveness of the proposed moments-based approximation method.

  • Accuracy: The method achieves reasonable accuracy compared to simulation results, often outperforming existing truncation-based methods, especially when those methods require very high truncation levels. For instance, in Case a of Example 1, a 2-state moments-based approximation was more accurate than truncation methods with 12 states.
  • Efficiency: The computational complexity is significantly reduced. The paper highlights that analysis of complex networks that would be infeasible with truncation-based methods (due to massive state spaces) becomes manageable with the moments-based approach. For example, a 4-node network analysis took only 1-2 seconds.
  • Compact Models: The approximate MAPs generated by the moments-based method are significantly smaller (e.g., 2 or 3 states) compared to those produced by truncation methods, which can grow to tens or hundreds of states.

Limitations and Future Work

  • MAP Fitting: The paper acknowledges that sometimes the computed moments might not perfectly correspond to a valid MAP of a desired order. In such cases, a "MAP fitting" procedure would be needed to find a MAP whose moments are "as close as possible" to the target moments. The authors mention that their current MAP fitting procedures are not yet stable enough for this purpose, limiting their examples to cases where direct matching is feasible. This is identified as a direction for future work.
  • Theoretical Foundation for Moments: While the paper demonstrates the effectiveness of using moments, further theoretical exploration into why specific moment sets are sufficient for certain approximations could be beneficial.
  • Generalization: The paper focuses on MAP/MAP/1 queues. Extending this moments-based approach to more general queueing network structures (e.g., with different service disciplines or multiple servers) would be a valuable future direction.

Summary updated

BibTeX
@inproceedings{horvath2010joint,
  author = {András Horváth and Gábor Horväth and Miklós Telek},
  title = {{A joint moments based analysis of networks of MAP/MAP/1 queues}},
  booktitle = {Performance Evaluation},
  year = {2010},
  doi = {10.1016/j.peva.2009.12.006},
}

Loading related content...

Figure