Bound analysis of closed queueing networks with workload burstiness

ABSTRACT

Burstiness and temporal dependence in service processes are often found in multi-tier architectures and storage devices and must be captured accurately in capacity planning models as these features are responsible of significant performance degradations. However, existing models and approximations for networks of first-come first-served (FCFS) queues with general independent (GI) service are unable to predict performance of systems with temporal dependence in workloads.

To overcome this difficulty, we define and study a class of closed queueing networks where service times are represented by Markovian Arrival Processes (MAPs), a class of point processes that can model general distributions, but also temporal dependent features such as burstiness in service times. We call these models MAP queueing networks. We introduce provable upper and lower bounds for arbitrary performance indexes (e.g., throughput, response time, utilization) that we call Linear Reduction (LR) bounds. Numerical experiments indicate that LR bounds achieve a mean accuracy error of 2 percent.

The result promotes LR bounds as a versatile and reliable bounding methodology of the performance of modern computer systems.

REFERENCES

• 1: A. T. Andersen and B. F. Nielsen. A Markovian approach for modeling packet traffic with long-range dependence. IEEE JSAC, 16(5):719--732, 1998.
• 2: Martin F. Arlitt , Carey L. Williamson, Web server workload characterization: the search for invariants, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.126-137, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 3: M. Arlitt and T. Jin. Workload characterization of the 1998 world cup web site. TR HPL-1999-35R1, HP Labs, 1999.
• 4: S. Asmussen and F. Koole. Marked point processes as limits of Markovian arrival streams. J. App. Prob., 30:365--372, 1993.
• 5: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 6: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 7: Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor Shridharbhai Trivedi, Queueing Networks and Markov Chains, Wiley-Interscience, 2005
• 8: A B Bondi , W Whitt, The influence of service-time variability in a closed network of queues, Performance Evaluation, v.6 n.3, p.219-234, Sept. 1986 [doi>10.1016/0166-5316(86)90019-2]
• 9: G. Casale, N. Mi, and E.Smirni. Bound analysis of closed queueing networks with nonrenewal workloads. TR WM-CS-2008-03, College of William and Mary, 2008.
• 10: Giuliano Casale, An efficient algorithm for the exact analysis of multiclass queueing networks with large population sizes, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 11: G. Casale, E.Z. Zhang, and E. Smirni. Interarrival Times Characterization and Fitting for Markovian Traffic Analysis. TR WM-CS-2008-02, College of William and Mary, 2008.
• 12: K. M. Chandy, U. Herzog, and L. Woo. Parametric analysis of queueing networks. IBM J. Res. Dev., 19(1):36--42, 1975.
• 13: P. J. Courtois, Decomposability, instabilities, and saturation in multiprogramming systems, Communications of the ACM, v.18 n.7, p.371-377, July 1975 [doi>10.1145/360881.360887]
• 14: D. R. Cox and P. A. W. Lewis. The Statistical Analysis of Series of Events. John Wiley and Sons, New York, 1966.
• 15: MAP Queueing Networks Webpage. http://www.cs.wm.edu/MAPQN/.
• 16: Derek L. Eager , Daniel J. Sorin , Mary K. Vernon, AMVA techniques for high service time variability, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.217-228, June 18-21, 2000, Santa Clara, California, United States
• 17: Wolfgang Fischer , Kathleen Meier-Hellstern, The Markov-modulated Poisson process (MMPP) cookbook, Performance Evaluation, v.18 n.2, p.149-171, Sept. 1993 [doi>10.1016/0166-5316(93)90035-S]
• 18: R. Fourer and D. M. Gay and B. W. Kernighan. AMPL - A Modeling Language for Mathematical Programming. Springer-Verlag, 1995.
• 19: GNU GLPK 4.8. http://www.gnu.org/software/glpk/.
• 20: András Horváth , Miklós Telek, Markovian Modeling of Real Data Traffic: Heuristic Phase Type and MAP Fitting of Heavy Tailed and Fractal Like Samples, Performance Evaluation of Complex Systems: Techniques and Tools, Performance 2002, Tutorial Lectures, p.405-434, January 2002
• 21: S. Kounev and A. Buchmann. Performance modeling and evaluation of large-scale J2EE applications. In Proc. of the 29th International Conference of the Computer Measurement Group (CMG), pages 273--283, 2003.
• 22: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 23: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 24: Zhen Liu, Long range dependence and heavy tail distributions, Performance Evaluation, v.61 n.2-3, p.91-93, July 2005 [doi>10.1016/j.peva.2005.04.001]
• 25: Ningfang Mi , Qi Zhang , Alma Riska , Evgenia Smirni , Erik Riedel, Performance impacts of autocorrelated flows in multi-tiered systems, Performance Evaluation, v.64 n.9-12, p.1082-1101, October, 2007 [doi>10.1016/j.peva.2007.06.016]
• 26: J. R. Morrison , P. R. Kumar, New Linear Program Performance Bounds for Closed QueueingNetworks, Discrete Event Dynamic Systems, v.11 n.4, p.291-317, October 2001 [doi>10.1023/A:1011217024661]
• 27: R. R. Muntz and J. W. Wong. Asymptotic properties of closed queueing network models. In Proc. Ann. Princeton Conf. on Inf. Sci. and Sys., pp. 348--352, 1974.
• 28: M. F. Neuts. Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, NY, 1989.
• 29: M. Reiser. A queueing network analysis of computer communication networks with window flow control. IEEE T. Comm., 27(8):1199--1209, 1979.
• 30: M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980 [doi>10.1145/322186.322195]
• 31: Alma Riska , Erik Riedel, Long-Range Dependence at the Disk Drive Level, Proceedings of the 3rd international conference on the Quantitative Evaluation of Systems, p.41-50, September 11-14, 2006 [doi>10.1109/QEST.2006.27]
• 32: J. Zahorjan, E. D. Lazowska, and R. L. Garner. A decomposition approach to modelling high service time variability. Perf. Eval., 3:35--54, 1983.
• 33: Qi Zhang , Ningfang Mi , Alma Riska , Evgenia Smirni, Performance-Guided Load (Un)balancing under Autocorrelated Flows, IEEE Transactions on Parallel and Distributed Systems, v.19 n.5, p.652-665, May 2008 [doi>10.1109/TPDS.2007.70775]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Performance, Theory

Keywords:
bound analysis, burstiness, closed systems, markovian arrival processes, nonrenewal service, queueing networks, temporal dependence