Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 38 ยท Networks of Queues

Closed Networks and Mean Value Analysis

Analyze closed networks with a fixed population: service demands, the bottleneck, and the mean value analysis algorithm for throughput and response time.

In an open network customers come and go. In a closed network a fixed number N of customers circulate forever. This models a computer with N jobs cycling between CPU and disk, a factory with a fixed number of pallets, or N users who each send a request, wait for the reply, think for a while, and send again.

Because the population is fixed, throughput is limited by the system, not by an external arrival rate. The question changes to: for each population N, what are the throughput and response time, and who is the bottleneck?

Service demands

For each station i, let V_i be the average number of visits one customer makes per cycle, and S_i the average service time per visit. The service demand is:

Text
D_i = V_i ยท S_i

It is the total service time a customer needs from station i per cycle. Two bounds follow immediately, with D = ฮฃD_i and D_max = max D_i:

Text
X(N) โ‰ค min( N / (D + Z),  1 / D_max )

Here X is system throughput (cycles per time) and Z is the average think time (use 0 if there is none). The first term is the "customers never wait" bound and the second is the bottleneck bound: the busiest station can complete at most one cycle's demand every D_max.

Mean value analysis (MVA)

For networks of single-server FCFS stations with exponential service (a Gordon-Newell closed network), the exact algorithm mean value analysis builds the answers one customer at a time, using the arrival theorem: a customer arriving at a station sees the other N - 1 customers distributed as in the network with N - 1 customers.

Start with Q_i(0) = 0. For n = 1..N:

Text
R_i(n) = D_i ยท (1 + Q_i(n - 1))        residence time at station i
X(n)   = n / (Z + ฮฃ R_i(n))            system throughput
Q_i(n) = X(n) ยท R_i(n)                 mean number at station i

R_i is the total time per cycle spent at station i (waiting plus service, over all visits). Little's Law gives Q_i = X R_i and the response time is R(n) = ฮฃ R_i(n).

Python Mean value analysis for a closed network

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Watch the table: throughput climbs and then flattens at 1/D_max = 3.33 jobs per second as the disk A utilization approaches 1. Adding more customers does not raise throughput; it only raises response time. The bottleneck is the station with the largest demand.

Think time and interactive systems

With think time Z, a user cycles between "thinking" and "using the system". The response-time law is R(N) = N/X(N) - Z. For small N the system is nearly idle; for large N the bottleneck dominates and R(N) โ‰ˆ N ยท D_max - Z. The saturation point where the two bounds cross is:

Text
N* = (D + Z) / D_max
Python Interactive users: where does the system saturate?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Below N* response time stays close to D; beyond it response time grows by about D_max per added user.

Where MVA applies

MVA gives exact results for single-server stations with product form. Multi-server stations need a modified recursion that tracks marginal queue-length probabilities, and non-product-form systems use approximate MVA. Product form for closed networks (the Gordon-Newell and BCMP results) is the closed-network cousin of Jackson's theorem.

Use "demand" thinking whenever you size a system: the station with the largest D_i caps throughput at 1/D_max, so improving other stations does nothing until the bottleneck is fixed.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A job needs 3 visits of 0.05 s each at a disk per cycle. What is the disk's service demand?

    D = V ยท S = 3 ร— 0.05 = 0.15 s.
  2. 2. What is the maximum throughput of a closed system with demands 0.2, 0.5 and 0.1 s?

    The bottleneck bound is 1/D_max = 1/0.5 = 2 cycles per second.
  3. 3. In MVA, the arrival theorem says an arriving customer sees

    That is the basis for R_i(n) = D_i(1 + Q_i(n - 1)).
  4. 4. Adding more users beyond the saturation point mainly

    The bottleneck is already fully busy, so extra users just queue.

Summary

  • Closed network: fixed population N; service demand D_i = V_i S_i.
  • Throughput is bounded by min(N/(D + Z), 1/D_max).
  • MVA computes R_i, X and Q_i for n = 1..N exactly (single-server product-form stations).
  • The saturation population is N* = (D + Z)/D_max.

Next: Decomposition and Bottlenecks in Non-Product-Form Networks