In queueing theory, a discipline within the mathematical theory of probability, mean value analysis (MVA) is a recursive technique for computing expected queue lengths, waiting time at queueing nodes and throughput in equilibrium for a closed separable system of queues. The first approximate techniques were published independently by Schweitzer and Bard, followed later by an exact version by Lavenberg and Reiser published in 1980. It is based on the arrival theorem, which states that when one customer in an M-customer closed system arrives at a service facility he/she observes the rest of the system to be in the equilibrium state for a system with M − 1 customers.
Problem setup Consider a closed queueing network of K M/M/1 queues, with M customers circulating in the system. Suppose that the customers are indistinguishable from each other, so that the network has a single class of customers. To compute the mean queue length and waiting time at each of the nodes and throughput of the system we use an iterative algorithm starting with a network with 0 customers. Write μi for the service rate at node i and P for the customer routing matrix where element pij denotes the probability that a customer finishing service at node i moves to node j for service. To use the algorithm, we first compute the visit ratio row vector v, a vector such that v = v P. Now write Li(n) for the mean number of customers at queue i when there is a total of n customers in the system (this includes the job currently being served at queue i) and Wj(n) for the mean time spent by a customer in queue i when there is a total of n customers in the system. Denote the throughput of a system with m customers by λm.
Algorithm The algorithm starts with an empty network (zero customers), then increases the number of customers by 1 at each iteration until there are the required number (M) of customers in the system. To initialise, set Lk(0) = 0 for k = 1,...,K. (This sets the average queue length in a system with no customers to zero at all nodes.) Repeat for m = 1,...,M:
1. For k = 1, ..., K compute the waiting time at each node using the arrival theorem:
W k ( m ) = 1 + L k ( m − 1 ) μ k . {\displaystyle W_{k}(m)={\frac {1+L_{k}\left(m-1\right)}{\mu _{k}}}.}
2. Then compute the system throughput using Little's law:
λ m = m ∑ k = 1 K W k ( m ) v k . {\displaystyle \lambda _{m}={\frac {m}{\sum _{k=1}^{K}W_{k}(m)v_{k}}}.}
3. Finally, use Little's law applied to each queue to compute the mean queue lengths for k = 1, ..., K:
L k ( m ) = v k λ m W k ( m ) . {\displaystyle L_{k}(m)=v_{k}\lambda _{m}W_{k}(m).}
End repeat.
Bard–Schweitzer method The Bard–Schweitzer approximation estimates the average number of jobs at node k to be:
L k ( m − 1 ) ≈ m − 1 m L k ( m ) {\displaystyle L_{k}(m-1)\approx {\frac {m-1}{m}}L_{k}(m)}
which is a linear interpolation. From the above formulas, this approximation yields fixed-point relationships which can be solved numerically. This iterative approach often goes under the name of approximate MVA (AMVA) and it is typically faster than the recursive approach of MVA.
Pseudocode
Multiclass networks In the case of multiclass networks with R classes of customers, each queue k can feature different service rates μk,r for each job class r=1,...,R, although certain restrictions exist in the case of first-come first-served stations due to the assumptions of the BCMP theorem in the multiclass case. The waiting time Wk,r experienced by class-r jobs at queue k can still be related to the total mean queue-length at node k using a generalization of the arrival theorem:
W k , r ( m ) = 1 + L k ( m − 1 r ) μ k , r . {\displaystyle W_{k,r}(\mathbb {m} )={\frac {1+L_{k}\left(\mathbb {m} -1_{r}\right)}{\mu _{k,r}}}.}
… excerpt ends here. Continue reading the full article.
