Queuing Models

Queuing models predict how response time, throughput, and queue length change as load increases. They transform the operational laws from statements about averages into predictions about system behavior under varying workloads [1].

Single-Queue Models

M/M/1: The Foundational Model

The simplest useful model: Poisson arrivals (M), exponential service (M), one server (1) [2]:

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#019546', 'lineColor': '#2D6E2A'}}}%%
graph LR
    Src["📥 Source"] --> Q["▐▐▐▐ Queue"] --> S(("Server")) --> Out["📤"]

    style Src fill:#f0f8f0,stroke:#019546,color:#282828
    style Q fill:#c8e6c9,stroke:#019546,color:#282828
    style S fill:#c8e6c9,stroke:#019546,color:#282828
    style Out fill:#f0f8f0,stroke:#019546,color:#282828
Metric Formula
Response time R = S / (1 − U)
Queue length L = U / (1 − U)
Wait time W = R − S = U · S / (1 − U)

Where S is mean service time and U is utilization (λ/μ). The key insight is the 1/(1-U) multiplier — it creates the hockey stick curve [3]:

  • At U = 0.5: response time is 2× service time
  • At U = 0.8: response time is 5× service time
  • At U = 0.9: response time is 10× service time
  • At U → 1.0: response time → ∞

M/M/c: Multiple Servers

When c parallel servers share a single queue (e.g., thread pool of size c), the model becomes M/M/c [4].

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#019546', 'lineColor': '#2D6E2A'}}}%%
graph LR
    Src["📥 Source"] --> Q["▐▐▐▐ Queue"]
    Q --> S1(("Server 1"))
    Q --> S2(("Server 2"))
    Q --> Sn(("Server n"))

    style Src fill:#f0f8f0,stroke:#019546,color:#282828
    style Q fill:#c8e6c9,stroke:#019546,color:#282828
    style S1 fill:#c8e6c9,stroke:#019546,color:#282828
    style S2 fill:#c8e6c9,stroke:#019546,color:#282828
    style Sn fill:#c8e6c9,stroke:#019546,color:#282828

Multiple servers delay the hockey stick — a 4-server system can sustain higher total utilization before response time explodes:

Servers (c) Total utilization at 3× service time
1 67%
2 80%
4 88%
8 93%

The Erlang C formula gives the probability of waiting in an M/M/c queue and is widely used for staffing decisions (call centers, support teams) [3].

M/G/m/m+r: General Service with Finite Buffer

For systems where service times are not exponential and queue capacity is finite, the M/G/m/m+r model captures realistic behavior [5]:

  • G (General service): task durations follow arbitrary distributions — critical for cloud workloads with high variability
  • m+r (finite capacity): m servers processing + r positions in buffer; arrivals beyond capacity are rejected (blocking)

Khazaei et al. showed that using M/M/m instead of M/G/m significantly underestimates performance degradation when task durations are variable [5]. The coefficient of variation of service time has a major impact on both response time and blocking probability.

Queuing Networks

Real software systems are not single queues — they are networks of interconnected queues [6]. A three-tier web application has at least three queuing centers (web, app, database), each with its own service demand.

Open vs. Closed Networks

Type Population Use Case Solvability
Open Infinite (requests arrive from outside) OLTP, API traffic Analytically tractable [7]
Closed Fixed (N users cycle through system) Interactive users, batch jobs Requires iterative solution (MVA)

Open network — requests arrive from outside and exit after service:

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#019546', 'lineColor': '#2D6E2A'}}}%%
graph LR
    Src["📥 Source"] --> Q1["▐▐▐▐"] --> S1(("Server 1")) --> Q2["▐▐▐▐"] --> S2(("Server 2")) --> Q3["▐▐▐▐"] --> S3(("Server 3")) --> Out["📤 Exit"]

    style Src fill:#f0f8f0,stroke:#019546,color:#282828
    style Q1 fill:#c8e6c9,stroke:#019546,color:#282828
    style Q2 fill:#c8e6c9,stroke:#019546,color:#282828
    style Q3 fill:#c8e6c9,stroke:#019546,color:#282828
    style S1 fill:#c8e6c9,stroke:#019546,color:#282828
    style S2 fill:#c8e6c9,stroke:#019546,color:#282828
    style S3 fill:#c8e6c9,stroke:#019546,color:#282828
    style Out fill:#f0f8f0,stroke:#019546,color:#282828

Closed network — fixed population recirculates through the system:

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#019546', 'lineColor': '#2D6E2A'}}}%%
graph LR
    Src["📥 Source"] --> Q1["▐▐▐▐"] --> S1(("Server 1")) --> Q2["▐▐▐▐"] --> S2(("Server 2")) --> Q3["▐▐▐▐"] --> S3(("Server 3")) --> Src

    style Src fill:#f0f8f0,stroke:#019546,color:#282828
    style Q1 fill:#c8e6c9,stroke:#019546,color:#282828
    style Q2 fill:#c8e6c9,stroke:#019546,color:#282828
    style Q3 fill:#c8e6c9,stroke:#019546,color:#282828
    style S1 fill:#c8e6c9,stroke:#019546,color:#282828
    style S2 fill:#c8e6c9,stroke:#019546,color:#282828
    style S3 fill:#c8e6c9,stroke:#019546,color:#282828

Open networks are simpler for back-of-the-envelope calculations. Closed networks model the think time between requests and the feedback effect where slow responses reduce the arrival rate [8].

Finite Capacity Networks

When queues have bounded sizes (thread pools, connection limits, container memory), blocking occurs — requests are rejected or stalled when a downstream queue is full [6]. Balsamo et al. surveyed blocking mechanisms for software architectures:

  • BAS (Blocking After Service): A completed job at node i is blocked if the destination queue is full
  • BBS (Blocking Before Service): A job cannot begin service until the downstream queue has space

This models real software constraints: a web server with a connection pool of 100 to the database will block application threads when all 100 connections are in use.

Mean-Value Analysis (MVA)

MVA is the standard algorithm for solving closed queuing networks [9]. It computes performance metrics recursively without solving global balance equations — avoiding the exponential state space explosion.

The Arrival Theorem

MVA relies on a key insight: in a closed system, a job arriving at a resource sees the system as if it were in steady state with one fewer job [9]. This allows computing performance for n users from the solution for n − 1 users.

The Three Recursive Equations

Starting from n = 1 and iterating to N users:

1. Residence Time:

R’i[n] = Di · (1 + Qi[n−1])

Time at resource i = service demand + waiting for jobs already in queue.

2. System Throughput:

X[n] = n / (Z + Σ R’i[n])

Where Z is think time.

3. Queue Length:

Qi[n] = X[n] · R’i[n]

This is Little’s Law applied per resource.

Why MVA Matters

Advantage Explanation
Intuitive inputs Requires only service demand Di — measured from system counters
Simple implementation Three equations iterated in a loop — implementable in a spreadsheet [7]
Numerically stable Avoids overflow issues of older convolution algorithms
Finds the knee Reveals the saturation point where throughput flattens and response time goes linear [10]

MVA is implemented in tools like PDQ (Pretty Damn Quick) [11] and JMT (Java Modelling Tools) [12].

Model Selection Guide

Scenario Recommended Model Rationale
Quick estimate, one resource M/M/1 Simple formula R = S/(1-U)
Thread pool or server farm M/M/c Multiple servers, shared queue
Cloud VMs with variable tasks M/G/m/m+r General service times, finite buffer
Interactive users, multi-tier app Closed QN + MVA Fixed population, feedback effects
API gateway with bounded queues Finite-capacity QN Blocking when downstream full

References

  1. J. F. Shortle, J. M. Thompson, D. Gross, and C. M. Harris, Fundamentals of Queueing Theory, 5th ed. Wiley, 2018. doi: 10.1002/9781119453765.
  2. D. G. Kendall, “Stochastic Processes Occurring in the Theory of Queues and Their Analysis by the Method of the Imbedded Markov Chain,” The Annals of Mathematical Statistics, vol. 24, no. 3, pp. 338–354, 1953, doi: 10.1214/aoms/1177728975.
  3. C. Shallahamer, “Practical Queuing Theory,” in Forecasting Oracle Performance, Apress, 2007.
  4. F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, 7th ed. McGraw-Hill, 2001.
  5. H. Khazaei, J. Misić, and V. B. Misić, “Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 5, pp. 936–943, 2012, doi: 10.1109/tpds.2011.199.
  6. S. Balsamo, V. De Nitto Personé, and P. Inverardi, “A review on queueing network models with finite capacity queues for software architectures performance prediction,” Performance Evaluation, vol. 51, no. 2–4, pp. 269–288, 2003, doi: 10.1016/S0166-5316(02)00099-8.
  7. H. H. Liu, Software Performance and Scalability: A Quantitative Approach. Wiley, 2009. doi: 10.1002/9780470465394.
  8. P. J. Denning and J. P. Buzen, “The Operational Analysis of Queueing Network Models,” ACM Computing Surveys, vol. 10, no. 3, pp. 225–261, 1978, doi: 10.1145/356733.356735.
  9. M. Reiser and S. S. Lavenberg, “Mean-Value Analysis of Closed Multichain Queuing Networks,” Journal of the ACM, vol. 27, no. 2, pp. 313–322, 1980, doi: 10.1145/322186.322195.
  10. N. J. Gunther, Guerrilla Capacity Planning: A Tactical Approach to Planning for Highly Scalable Applications and Services. Springer, 2007.
  11. N. J. Gunther, “Performance Measurement and Modeling.” 2005.
  12. “JMT – Java Modelling Tools.” 2023. Available at: http://jmt.sourceforge.net/

Disclaimer: AI is used for text summarization, polishing and explaining. Authors have verified all facts and claims. In case of an error, feel free to file an issue.

This site uses Just the Docs, a documentation theme for Jekyll.