Queuing Network Model

Learned in SE464.

A type of software performance model, specifically a system execution model. QNMs characterize software’s performance in the presence of dynamic factors (other workloads, multiple users) and aim to solve contention for resources.

Performance metrics per server

• Residence time (RT): average time jobs spend in the server (in service + waiting)
• Utilization (U): average percentage of time the server is busy
• Throughput (X): average rate at which jobs complete service
• Queue length (N): average number of jobs at the server (in service + waiting)

Key formulas

Given the busy-time graph (W = area under the graph, B = total busy time, C = completions, T = total time):

• Throughput: X = C / T
• Utilization: U = B / T
• Mean service time: B / C
• Residence time: RT = W / C
• Queue length: N = W / T

And the famous: $N=X\cdot RT$

From ECE459 L32: Queueing for Performance [Wil13c]

Eight-step recipe to apply queueing theory to a real system:

1. Convert to common time units.
2. Calculate visitation ratios $V_i$ (times device used per transaction).
3. Calculate device utilization ${\rho }_i={\lambda }_i{s}_i$.
4. Back out CPU service time.
5. Calculate per-device time $V_i\times S_i$.
6. Identify the bottleneck device (largest $\rho$).
7. Saturation throughput $=1/(S_i{V}_i)$ for the bottleneck.
8. Average transaction time $=\sum V_i{S}_i$.

Worked web-server example

9 000 pages/hr; CPU at 42%; Disk 1 108k/hr $S=11$ ms; Disk 2 72k/hr $S=16$ ms; Network 18k/hr $S=23$ ms.

Device	λ (/s)	S (s)	V	ρ	V·S
Webpages	2.5	n/a	1	n/a	n/a
CPU	57.5	0.0073	23	0.42	0.168
Disk 1	30	0.011	12	0.33	0.132
Disk 2	20	0.016	8	0.32	0.128
Network	5	0.023	2	0.115	0.046

CPU visitation is the sum of all others (every disk/network return hits CPU).

• Bottleneck: CPU (ρ = 0.42).
• Saturation: $1/0.168=5.95$ transactions/sec.
• Average transaction: $\sum V_i{S}_i=0.474$ s.

When service times are unknown [Wil13a]

Monitoring often gives queue length, not service time. For M/M/1, $W={\rho }^2/(1-\rho )=(\lambda s{)}^2/(1-\lambda s)$. Solve for $s$ via quadratic formula: $s=\frac{-W\pm \sqrt{W^2+4W}}{2\lambda }$

Related

• Software Performance Model
• Queueing Theory
• Little’s Law
• Bottleneck Analysis