Mean value analysis

In queueing theory, a specialty within the mathematical theory of probability, mean value analysis is a technique for computing expected queue lengths in equilibrium for a closed separable system of queues. It was developed by Reiser and Lavenberg^[1] 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 queues, with M customers circulating in the system.

Let μ_j be the (known) service rate for queue j, i.e. 1 / μ_j is the service time.

Let P be the (known) routing matrix, where each element p_ij is the probability that after visiting queue i the customer will visit queue j. From this matrix we can calculate the vector $V=\{v_1,\cdots,v_K\}$ known as the visit-ratio vector by solving the eigenvector-like equation VP = V.

Let N_j(n) be the mean number of customers in queue j when there are a total of n customers in the system; this includes the job currently being served in queue j.

Let W_j(n) be the mean time spent by a customer in queue j when there are a total of n in the system; it is the total delay at this queue including the customer service time.

Algorithm

The algorithm^[2] starts with an empty network (zero customers), then increases the number of customers by 1 until it reaches the desired number of customers M.

Initialization. Let N_k(0) = 0 for k = 1 to K

Repeat for m = 1 to M:

Step 1. For k = 1 to K let $W_k(m)=\frac{N_k(m-1)+1}{\mu_k}$. (This is based on the arrival theorem).

Step 2. Let $\lambda=\frac{m}{\sum_{k=1}^K W_k(m) v_k}$. (This is an application of Little's Law to find the system throughput).

Step 3. Let N_k(m) = v_kλW_k(m) for k = 1 to K. (This is another application of Little's law to each individual queue).

End repeat.

External links

• J. Virtamo: Queuing networks. Handout from Helsinki Tech gives good overview of Jackson's Theorem and MVA.
• Simon Lam: A simple derivation of the MVA algorithm. Shows relationship between Buzen's algorithm and MVA.

References

1. ^ Reiser, M.; Lavenberg, S. S. (April 1980). "Mean Value Analysis on Closed Multichain Queueing Networks". Journal of the ACM 27 (2). doi:10.1145/322186.322195. 
2. ^ Bose, Sanjay K. (2001). An introduction to queueing systems. Springer. p. 174. ISBN 0306467348. http://books.google.com/books?id=39-jISti_zkC.