George Mason University
DEPARTMENT OF COMPUTER SCIENCE

## CS571 - Operating Systems - Fall 2001 Summary of Queueing Network Formulas

```basic parameters:
Si = mean service time per visit server i
Vi = mean number of visits to server i
Di = demand for server i = Vi*Si
Z  = think time (for time sharing system)

basic metrics:
Ui = utilization server i
Xi = throughput server i
Qi = mean queue length server i
Ri = mean response time per visit server i (includes service)
Ti = mean total residence time server i (Ti = Vi*Ri)
R  = system response time
X  = system throughput

Add parameter N after any of the above
Xi(N), Qi(N), R(N), X(N), etc.

utilization law
Ui = Xi*Si = X*Di

Little's law
Qi = Xi*Ri = X*Ti

Forced flow law:
Xi = X*Vi

Response time law:
R  = sum(Vi*Ri) = sum(Ti)

Response time formula for time sharing system
R = N/X - Z

Response time estimator for open system
Ri = Si/(1-Si*Xi), and then R = sum{ Vi*Ri }

system bottleneck
server b for which {Di} is largest; Db = max{Di}
X(N) < 1/Db
R(N) > NDb - Z

---------------------

Recursive Mean Value Algorithm (MVA)
with parameters Vi, Si, N, and Z:

Initialize Qi[0]=0 all i
For k=1,2,...,N do {
for all i {Ri[k] = Si*(1+Qi[k-1]) }
R[k]  = SUM {Vi*Ri[k]}
X[k]  = k/(R[k]+Z)
for all i {Qi[k] = X[k]*Vi*Ri[k] }
}

Recursive Mean Value Algorithm (MVA)
with parameters Di, N, and Z and Ti=Vi*Ri
is total residence time at server i:

Initialize Qi[0]=0 all i
For k=1,2,...,N do {
for all i {Ti[k] = Di*(1+Qi[k-1]) }
R[k]  = SUM {Ti[k]}
X[k]  = k/(R[k]+Z)
for all i {Qi[k] = X[k]*Ti[k] }
}

NOTE: if you use this algorithm with Di that depend on N,
choose a particular n of interest, set Di=Di(n), and run
the algorithm until k=n.  The final values R[n] and X[n] are
valid, but the values for k<n are not valid.

Iterative Mean Value Algorithm:
(A shortcut for calculating for just one N)

Initialize {Qi=0, Ri=0, Xi=0, all i}
repeat {
for all i {Ti  =  Di*(1+Qi*(N-1)/N) }
R   =  SUM{Ti}
oldX = X
X   =  N/(R+Z)
for all i {Qi  =  X*Ti }
} until {|oldX-X| < e}

(For example e = 0.001 is good to two significant digits)```