CS471 - Operating Systems - Spring 2000


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)
   N  = load (closed 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

load-dependent:
   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)