Queueing systems with long-range dependent input process and subexponential service times

ABSTRACT

We analyze the asymptotic tail distribution of stationary waiting times and stationary virtual waiting times in a single-server queue with long-range dependent arrival process and subexponential service times. We investigate the joint impact of the long range dependency of the arrival process and of the tail distribution of the service times. We consider two traffic models that have been widely used to characterize the long-range dependence structure, namely, the M/G/8 input model and the Fractional Gaussian Noise (FGN) model. We focus on the response times of the customers in a First-Come First-Serve (FCFS) queueing system, although the results carry through to the backlog distribution of the system with any arbitrary queueing discipline. When the arrival process is driven by an M/G/8 input model we show that if the residual service time tail distribution F_e is lighter than the residual session duration G_e, then the stationary waiting time is dominated by the long-range dependence structure, which is determined by the residual session duration G_e. If the residual service time distribution F_e is heavier than the residual session duration G_e, then the tail distribution of the stationary waiting time is dominated by that of the residual service time. When the arrival process is modeled by an FGN, we show that the waiting time tail distribution is asymptotically equal to the tail distribution of the residual service time if the latter is asymptotically heavier than Weibull distribution with shape parameter 2-2H, where H is the Hurst parameter of the FGN. If, however, this residual service time is asymptotically lighter than Weibull distribution with shape parameter 2-2H, then the waiting time tail distribution is dominated by the dependence structure of the arrival process so that it is asymptotically equal to Weibull distribution with shape parameter 2-2H.

REFERENCES

• 1: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 2: S. Asmussen, H. Schmidli and V. Schmidt. Tail probabilities for non-standard risk and queueing processes with subexponential jumps, Adv. in Appl. Probab. 31 (1999) 422--447.
• 3: F. Baccelli and A. M. Makowski. Queueing Models for Systems with Synchronization Constraints Proceedings of the IEEE, 77, Special Issue on Dynamics of Discrete Event Systems, 1989, pp. 138--161.
• 4: Sem C. Borst , Onno J. Boxma , R. Nunez Queija, Heavy Tails: The Effect of the Service Discipline, Proceedings of the 12th International Conference on Computer Performance Evaluation, Modelling Techniques and Tools, p.1-30, April 14-17, 2002
• 5: Cheng-Shang Chang, Performance Guarantees in Communication Networks, Springer-Verlag, London, 2000
• 6: V.P. Chistakov. A theorem on sums of independent positive random variables and its application to branching random process. In Theor. Probab. Appl., 9:640:648, 1964.
• 7: Gagan L. Choudhury , Ward Whitt, Long-tail buffer-content distributions in broadband networks, Performance Evaluation, v.30 n.3, p.177-190, Sept. 1997 [doi>10.1016/S0166-5316(96)00059-4]
• 8: D.B.H. Cline. Convolution tails, product tails and domains of attraction. Prob. Theory Related Fields, 72 (1986) 529--557.
• 9: D.B.H. Cline. Intermediate regular and p variation. Proc. London Math. Soc., 1994.
• 10: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, ACM SIGMETRICS Performance Evaluation Review, v.24 n.1, p.160-169, May 1996
• 11: D.R. Cox. Long-range dependence: A review. Statistics: An Appraisal. H.A. David and H.T. David, Eds., The Iowa State University Press, Ames. (IA), 1984, pp 55--74.
• 12: Allen B. Downey, The Structural Cause of File Size Distributions, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.361, August 15-18, 2001
• 13: N.G. Duffield and N. O'Connell. Large deviation and overflow probabilities for the general single-server queue, with applications. In Mathematical Proceedings of the Cambridge Philosophical Society, 118 (1995) 363--375.
• 14: Paul Embrechts , Thomas Mikosch , Claudia Klüppelberg, Modelling extremal events: for insurance and finance, Springer-Verlag, London, 1997
• 15: P.V. Glynn and W. Whitt. Longarithmic asymptotics for steady-state tail probabilities in a single-server queue. J. Appl. Prob., 31A (1994) 131--156.
• 16: F.Guillemin, R. Mazumdar and A. Simonian. On heavy traffic approximations for transient characteristics of M/M/8 queues, J. Appl. Prob., 33, No. 2, 1996, pp. 490--506.
• 17: Arun K. Iyengar , Mark S. Squillante , Li Zhang, Analysis and characterization of large-scale Web server access patterns and performance, World Wide Web, v.2 n.1-2, p.85-100, 1999 [doi>10.1023/A:1019244621570]
• 18: P. Jelenkovic. On the asymptotic behavior of a fluid queue with a heavy-tailed M/G/8 arrival process. June 2000, preprint.
• 19: P. Jelenkovic and A.A. Lazar. Subexponential asymptotics of a Markov-modulated random walk with queueing applications, J. Appl. Prob., June 1998.
• 20: P. Jelenkovic and P. Momcilovic. Resource Sharing with Subexponential Distributions. In Proceedings of IEEE INFOCOM, June 2002, Vol. 3, 1316--1325.
• 21: 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]
• 22: Z. Liu, P. Nain, D. Towsley and Z.-L. Zhang. Asymptotic behavior of a multiplexer fed by a long-range dependent process. J. Appl. Probab. 36 (1999) 105--118.
• 23: Zhen Liu , Nicolas Niclausse , César Jalpa-Villanueva, Traffic model and performance evaluation of Web servers, Performance Evaluation, v.46 n.2-3, p.77-100, October 2001 [doi>10.1016/S0166-5316(01)00046-3]
• 24: R.M. Loynes. The stability of a queue with non-independent inter-arrival and service times. In Proc. Cambridge Philos Soc., 58 (1968) 497--520.
• 25: K. Maulik, S. Resnick, and H. Rootzen. A network traffic model with random transmission rate. Preprint, 2000.
• 26: I. Norros. A storage model with self-similar input. Queueing Systems, 16:387--396, 1994.
• 27: A. Pakes. On the tails of waiting time distributions, J. Appl. Probab. 12 (1975) 555--564.
• 28: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 29: M. Parulekar and A.M. Makowski. Tail probabilities for a multiplexer with self-similar traffic. Proc. IEEE INFOCOM, 1996.
• 30: E.J.G. Pitman, Subexponential distribution functions. J. Austral. Math. Soc. Ser. A 29 (1980) 337--347.
• 31: S. Resnick and G. Samorodnitsky. Steady state distribution of the buffer content fro M/G/8 input fluid queues. preprint, 1999.
• 32: G. Samorodnitsky and M.S. Taqqu, Stable Non-Gaussian Random Processes: Stochastic Models With Infinite Variance, Chapman and Hal, New York (NY), 1994.
• 33: Karl Sigman, Appendix: A primer on heavy-tailed distributions, Queueing Systems: Theory and Applications, v.33 n.1-3, p.261-275, 1999 [doi>10.1023/A:1019180230133]
• 34: D. Stoyan. Comparison Methods for Queues and Other Stochastic Models. (English translation ed. D. J. Daley). Wiley, New York, 1983.
• 35: S. Vanichpun and A.M. Makowski. Positive correlations and buffer occupancy: lower bounds via supermodular ordering. Proc. of IEEE INFOCOM, June 2002, Vol. 3, 1298--1306.
• 36: Walter Willinger , Murad S. Taqqu , Robert Sherman , Daniel V. Wilson, Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.71-86, Feb. 1997 [doi>10.1109/90.554723]
• 37: C.H. Xia and Z. Liu. Queueing Systems with Long-range Dependent Input Process and Subexponential Service Times. IBM Technical Report, 2002.
• 38: C.H. Xia, Z. Liu, M.S. Squillante, L. Zhang and N. Malouch. Analysis of performance impact of drill-down techniques for Web traffic models. Dec. 2002, submitted for publication.
• 39: C.H. Xia, Z. Liu, M.S. Squillante, L. Zhang. Lower bounds for LRD/GI/1 queues with subexponential service times. Dec. 2002, submitted for publication.
• 40: A.J. Zeevi and P.W. Glynn. On the maximum workload of a queue fed by fractional Brownian motion. Ann. Appl. Probab. 10 (2000), no. 4, 1084--1099.
• 41: A. P. Zwart , O. J. Boxma, Sojourn time asymptotics in the M$/$G$/$1 processor sharing queue, Queueing Systems: Theory and Applications, v.35 n.1-4, p.141-166, 2000 [doi>10.1023/A:1019142010994]

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Performance, Theory

Keywords:
FGN, M/G/8, asymptotic queueing analysis, long-range dependency, subexponential distributions