Mean value analysis

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 ^[1] and Bard, ^{[2] [3]} followed later by an exact version by Lavenberg and Reiser published in 1980. ^{[4] [5]}

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 p_ij 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 L_i(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 W_j(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 ^[6] 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 L_k(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:

${\displaystyle W_{k}(m)={\frac {1+L_{k}\left(m-1\right)}{\mu _{k}}}.}$

2. Then compute the system throughput using Little's law:

${\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:

${\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: ^{[1] [7]}

${\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. ^{[8] : 38}

Pseudocode

set L_k(m) = M/K

repeat until convergence:

${\displaystyle \lambda _{m}={\frac {m}{\sum _{k=1}^{K}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}v_{k}}}}$

${\displaystyle L_{k}(m)=v_{k}\lambda _{m}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}}$

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 W_k,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:

${\displaystyle W_{k,r}(\mathbb {m} )={\frac {1+L_{k}\left(\mathbb {m} -1_{r}\right)}{\mu _{k,r}}}.}$

where ${\displaystyle \mathbb {m} =(m_{1},\ldots ,m_{R})}$ is a vector of customer population for the R classes and ${\displaystyle 1_{r}}$ subtracts one from the r-th element of ${\displaystyle \mathbb {m} }$, assuming that ${\displaystyle m_{r}\geq 1}$.

For networks with a single customer class the MVA algorithm is very fast and time taken grows linearly with the number of customers and number of queues. However, in multiclass models the number of multiplications and additions and the storage requirements for MVA grow exponentially with the number of customer classes. Practically, the algorithm works well for 3-4 customer classes, ^[9] although this generally depends on the implementation and the structure of the model. For example, the Tree-MVA method can scale to larger models if the routing matrix is sparse. ^[10]

Exact values for mean performance metrics can be obtained in large models using the method of moments, which requires log-quadratic time. The method of moments can solve in practice models with up to 10 classes of customers or sometimes larger, which are typically inaccessible by means of exact MVA. ^{[9] [11]} This technique however does not use the arrival theorem and relies on solving systems of linear equations involving the normalizing constant of state probabilities for the queueing network.

Approximate MVA (AMVA) algorithms, such as the Bard-Schweitzer method, offer instead an alternative solution technique that provides low complexity also on multiclass networks and typically deliver highly accurate results. ^[12]

Extensions

The mean value analysis algorithm has been applied to a class of PEPA models describing queueing networks and the performance of a key distribution center. ^[13]

Software

• JMVA, a tool written in Java which implements MVA. ^[14]
• queueing, a library for GNU Octave which includes MVA. ^[15]
• Line, a MATLAB toolbox that includes exact and approximate MVA algorithms.

See also

• Queueing theory

References

1. Schweitzer, P. J.; Serazzi, G.; Broglia, M. (1993). "A survey of bottleneck analysis in closed networks of queues". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. Vol. 729. p. 491. doi:10.1007/BFb0013865. ISBN   978-3-540-57297-8.
2. Bard, Yonathan (1979). Some Extensions to Multiclass Queueing Network Analysis. North-Holland Publishing Co. pp. 51–62. ISBN   978-0-444-85332-5.{{cite book}}: |journal= ignored (help)
3. Adan, I.; Wal, J. (2011). "Mean Values Techniques". Queueing Networks. International Series in Operations Research & Management Science. Vol. 154. pp. 561–586. doi:10.1007/978-1-4419-6472-4_13. ISBN   978-1-4419-6471-7.
4. Reiser, M.; Lavenberg, S. S. (1980). "Mean-Value Analysis of Closed Multichain Queuing Networks". Journal of the ACM . 27 (2): 313. doi: 10.1145/322186.322195 . S2CID   8694947.
5. Reiser, M. (2000). "Mean Value Analysis: A Personal Account". Performance Evaluation: Origins and Directions. Lecture Notes in Computer Science. Vol. 1769. pp. 491–504. doi:10.1007/3-540-46506-5_22. ISBN   978-3-540-67193-0.
6. Bose, Sanjay K. (2001). An introduction to queueing systems. Springer. p. 174. ISBN   978-0-306-46734-9.
7. Schweitzer, Paul (1979). "Approximate analysis of multiclass closed networks of queues". Proceedings of International Conference on Stochastic Control and Optimization.
8. Tay, Y. C. (2010). "Analytical Performance Modeling for Computer Systems". Synthesis Lectures on Computer Science. 2: 1–116. doi:10.2200/S00282ED1V01Y201005CSL002. S2CID   207318911.
9. Casale, G. (2011). "Exact analysis of performance models by the Method of Moments" (PDF). Performance Evaluation. 68 (6): 487–506. CiteSeerX   10.1.1.302.1139 . doi:10.1016/j.peva.2010.12.009.
10. Hoyme, K. P.; Bruell, S. C.; Afshari, P. V.; Kain, R. Y. (1986). "A tree-structured mean value analysis algorithm". ACM Transactions on Computer Systems. 4 (2): 178–185. doi: 10.1145/214419.214423 .
11. Casale, G. (2008). "CoMoM: A Class-Oriented Algorithm for Probabilistic Evaluation of Multiclass Queueing Networks". IEEE Transactions on Software Engineering. 35 (2): 162–177. CiteSeerX   10.1.1.302.1139 . doi:10.1016/j.peva.2010.12.009.
12. Zahorjan, John; Eager, Derek L.; Sweillam, Hisham M. (1988). "Accuracy, speed, and convergence of approximate mean value analysis". Performance Evaluation. 8 (4): 255–270. doi:10.1016/0166-5316(88)90028-4.
13. Thomas, N.; Zhao, Y. (2010). "Mean value analysis for a class of PEPA models". Comput. J. 54 (5): 643–652. doi:10.1093/comjnl/bxq064. S2CID   12824669.
14. Bertoli, M.; Casale, G.; Serazzi, G. (2009). "JMT: performance engineering tools for system modeling" (PDF). ACM SIGMETRICS Performance Evaluation Review. 36 (4): 10. doi:10.1145/1530873.1530877. S2CID   6920559.
15. Marzolla, M. (2014). "The Octave Queueing Package". Quantitative Evaluation of Systems. Lecture Notes in Computer Science. Vol. 8657. pp. 174–177. doi:10.1007/978-3-319-10696-0_14. ISBN   978-3-319-10695-3. S2CID   4978676.

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.