Fast estimation of probabilities of soft deadline misses in layered software performance models

ABSTRACT

Quality of service requirements are normally given in terms of soft deadlines, such as "90% of responses should complete within one second". To estimate the probability of meeting the target delay, one must estimate the distribution of response time, or at least its tail. Exact analytic methods based on state-space analysis suffer from state explosion, and simulation, which is also feasible, is very time consuming. Rapid approximate estimation would be valuable, especially for those cases which do not demand great precision, and which require the exploration of many alternative models.This work adapts layered queueing analysis, which is highly scalable and provides variance estimates as well as mean values, to estimate soft deadline success rates. It evaluates the use of an approximate Gamma distribution fitted to the mean and variance, and its application to examples of software systems. The evaluation finds that, for a definable set of situations, the tail probabilities over 90% are estimated well within a margin of 1% accuracy, which is useful for practical purposes.

References

1. S. W. M. AuYeung, N. J. Dingle, and W. J. Knottenbelt, "Efficient Approximation of Response Time Densities and Quantiles in Stochastic Models," in Fourth Int. Workshop on Software and Performance (WOSP 04), Redwood City, CA, Jan. 2004, pp. 151--155.
2. S. G. G. Bolch, H. de Meer, K. S. Trivedi, Queueing Networks and Markov Chains. John Wiley and Sons, 1998
3. J.T. Bradley, N. J. Dingle, P. G. Harrison, and W. J. Knottenbelt, "Distributed Computation of Transient State Distributions and Passage Time Quantiles in Large Semi-Markov Models", Future Generation Computer Systems, 2004
4. N. J. Dingle, P. G. Harrison, and W. J. Knottenbelt, Response Time Densities in Generalised Stochastic Petri Net Models, in 3rd Int. Workshop on Software and Performance (WOSP 2002), Rome, July, 2002, pp. 46--54
5. G. Franks, Performance Analysis of Distributed Server Systems, PhD, Dept. of Systems and Computer Engineering, Carleton, Ottawa, Canada, 2000
6. G. Franks, S. Majumdar, J. Neilson, D. Petriu, J. Rolia, and M. Woodside, "Performance Analysis of Distributed Server Systems", Proc. Sixth International Conference on Software Quality (6ICSQ), Ottawa, Ontario, 1996, pp. 15--26.
7. H. Gautama and A. J. C. van Gemund, "Static Performance Prediction of Data-Dependent Programs," in Proceedings of the Second International Workshop on Software and Performance (WOSP2000), Ottawa, Canada, September 17-20, 2000, pp. 216--226.
8. H. Gautama and A. J. C. v. Gemund, "Symbolic Performance Prediction of Speculative Parallel Programs," Parallel Processing Letters, vol. 13, no. 4 pp. 513--524, Dec 2003.
9. P. G. Harrison, "The Distribution of Cycle Times in Tree-Like Networks of Queues," Computer Journal, vol. 27, no. 1 pp. 27--36.
10. R. Jain, The Art of Computer Systems Performance Analysis. John Wiley & Sons Inc., 1991
11. Z. Karian and E. Dudewicz, Fitting Statistical Distributions: The Generalized Lambda Distribution and Generalized Bootstrap Methods. CRC Press, Boca Raton, 2000.
12. V. Mainkar, K. S. Trivedi, S. Woolet, "Fast Approximate Computation of Response Time Distribution in Open Markovian Network of Queues", 7th Int. Conf. on Modelling Techniques and Tools for Computer Performance Evaluation, May 3-6, 1994 Vienna, Austria
13. J. McKenna, "Asymptotic expansion of the sojourn time distribution functions of jobs in closed product-form queueing networks," J. of ACM, vol. 34, pp. 985--1003, 1987
14. J. Muppala, K. S. Trivedi, V. Mainkar, and V. Kulkarni, "Numerical Computation of Response Time Distributions Using Stochastic Reward Nets," Annals of Operations Research, vol. 48, pp. 155--184, 1994.
15. K. Raatikainen, "Approximating Response Time Distributions," in Proc. ACM Sigmetrics 89, Berkeley, CA, 1989, pp. 190--199.
16. Rolia, J. R., Sevcik, K. The method of layers. IEEE Transactions on Software Engineering, Vol. 21, No. 8, pp. 689--700, 1995.
17. S. Salza, S. S. Lavenberg, "Approximating Response Time Distributions in Closed Queueing Network Models of Computer Performance", Proc. Performance '81, F. J. Kylstra (ed), North-Holland Publishing Company, 1981
18. P. Tregunno, Practical Analysis of Software Bottlenecks, M.A.Sc thesis, Dept. of Systems and Computer Engineering, Carleton University, May 2003.
19. Wong, J. W., "Distribution of End-to-End Delay in Message-Switched Networks," Computer Networks, Vol. 2, 1978.
20. Woodside, C. M. "Throughput calculation for basic stochastic rendezvous networks". Performance Evaluation, Vol. 9, No. 2, pp. 143--160, 1989.
21. T. Zheng and M. Woodside, "Heuristic Optimization of Scheduling and Allocation for Distributed Systems with Soft Deadlines," in Proc. 13th Int. Conf. on Modelling Techniques and Tools for Computer Performance Evaluation (TOOLS 03), Urbana, USA, Sept. 2003