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. 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 customer at queue i when there are 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 are 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

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

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

\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}\lambda _{m}W_{k}(m).

End repeat.

Schweitzer's approximation

Schweitzer's approximation estimates the average number of jobs at node k to be^[1]^[7]

L_{k}(m-1)\approx {\frac {m-1}{m}}L_{k}(m)

which from the above formulas yields fixed-point relationships which can be solved numerically. This iterative approach is typically faster than the recursive approach of MVA.^[8]^:38

Pseudo-code

set L_k(m) = M/K

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

Multiclass networks

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, the number of multiplications and additions required for MVA grows exponentially with the number of customer classes. Practically, the algorithm works for 3-4 customer classes.^[9] The method of moments is an exact method which required log-quadratic time and can solve in practice models with up to 10 classes of customers.^[9] Approximate algorithms have also been proposed with lower complexity.^[10]

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.^[11]

Software

JMVA, a tool written in Java which implements MVA.^[12]
queueing, a library for GNU Octave which includes MVA.^[13]

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 2 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. 729. p. 491. doi:10.1007/BFb0013865. ISBN 3-540-57297-X.
↑ Bard, Yonathan (1979). "Some Extensions to Multiclass Queueing Network Analysis". Proceedings of the Third International Symposium on Modelling and Performance Evaluation of Computer Systems: Performance of Computer Systems. North-Holland Publishing Co.: 51–62. ISBN 0-444-85332-4.
↑ Adan, I.; Wal, J. (2011). "Mean Values Techniques". Queueing Networks. International Series in Operations Research & Management Science. 154. p. 561. doi:10.1007/978-1-4419-6472-4_13. ISBN 978-1-4419-6471-7.
↑ 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.
↑ Reiser, M. (2000). "Mean Value Analysis: A Personal Account". Performance Evaluation: Origins and Directions. Lecture Notes in Computer Science. 1769. pp. 491–504. doi:10.1007/3-540-46506-5_22. ISBN 978-3-540-67193-0.
↑ Bose, Sanjay K. (2001). An introduction to queueing systems. Springer. p. 174. ISBN 0-306-46734-8.
↑ Schweitzer, Paul (1979). "Approximate analysis of multiclass closed networks of queues". Proceedings of International Conference on Stochastic Control and Optimization.
↑ Tay, Y. C. (2010). "Analytical Performance Modeling for Computer Systems". Synthesis Lectures on Computer Science. 2: 1–0. doi:10.2200/S00282ED1V01Y201005CSL002.
1 2 Casale, G. (2011). "Exact analysis of performance models by the Method of Moments" (PDF). Performance Evaluation. 68 (6): 487–506. doi:10.1016/j.peva.2010.12.009.
↑ Pattipati, Krishna R.; Kostreva, Michael Martin; Teele, J. L. (1990). "Approximate mean value analysis algorithms for queuing networks: Existence, uniqueness, and convergence results". Journal of the ACM. 37 (3): 643. doi:10.1145/79147.214074.
↑ 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.
↑ 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.
↑ Marzolla, M. (2014). "The Octave Queueing Package". Quantitative Evaluation of Systems. Lecture Notes in Computer Science. 8657. p. 174. doi:10.1007/978-3-319-10696-0_14. ISBN 978-3-319-10695-3.

Queueing theory

Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue

Arrival processes	Poisson process Markovian arrival process Rational arrival process

Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network

Service policies	FIFO LIFO Processor sharing Round-robin Shortest job first Shortest remaining time

Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method

Limit theorems	Fluid limit Mean field theory Heavy traffic approximation Reflected Brownian motion

Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue

Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering

Category

This article is issued from Wikipedia - version of the 10/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.