Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T15:05:30.108Z Has data issue: false hasContentIssue false
  • English
  • Français

A reduced-peak equivalence for queues with a mixture of light-tailed and heavy-tailed input flows

Part of: Special processes Computer system organization Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Sem Borst  and
Bert Zwart
Sem Borst*
Affiliation:
CWI, Amsterdam
Bert Zwart*
Affiliation:
Eindhoven University of Technology
*
∗ Postal address: CWI, PO Box 94079, 1090 GB Amsterdam, The Netherlands. Email address: [email protected]
∗∗ Postal address: Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands.
Get access Rights & Permissions [Opens in a new window]

Abstract

We determine the exact large-buffer asymptotics for a mixture of light-tailed and heavy-tailed input flows. Earlier studies have found a ‘reduced-load equivalence’ in situations where the peak rate of the heavy-tailed flows plus the mean rate of the light-tailed flows is larger than the service rate. In that case, the workload is asymptotically equivalent to that in a reduced system, which consists of a certain ‘dominant’ subset of the heavy-tailed flows, with the service rate reduced by the mean rate of all other flows. In the present paper, we focus on the opposite case where the peak rate of the heavy-tailed flows plus the mean rate of the light-tailed flows is smaller than the service rate. Under mild assumptions, we prove that the workload distribution is asymptotically equivalent to that in a somewhat ‘dual’ reduced system, multiplied by a certain prefactor. The reduced system now consists of only the light-tailed flows, with the service rate reduced by the peak rate of the heavy-tailed flows. The prefactor represents the probability that the heavy-tailed flows have sent at their peak rate for more than a certain amount of time, which may be interpreted as the ‘time to overflow’ for the light-tailed flows in the reduced system. The results provide crucial insight into the typical overflow scenario.

Keywords

Fluid queuesheavy-tailed on periodslarge deviationsqueue length asymptotics

MSC classification

Primary: 60K25: Queueing theory
Secondary: 68M20: Performance evaluation; queueing; scheduling 90B18: Communication networks 90B22: Queues and service
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 35 , Issue 3 , September 2003 , pp. 793 - 805
Copyright
Copyright © Applied Probability Trust 2003 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Agrawal, R., Makowski, A. M. and Nain, Ph. (1999). On a reduced load equivalence for fluid queues under subexponentiality. Queueing Systems 33, 5–41.Google Scholar
[2] Anantharam, V. (1988). How large delays build up in a GI/G/1 queue. Queueing Systems 5, 345–368.Google Scholar
[3] Asmussen, S. (1982). Conditioned limit theorems relating a random walk to its associate, with applications to risk reserve processes and the GI/G/1 queue. Adv. Appl. Prob. 14, 143–170.CrossRefGoogle Scholar
[4] Asmussen, S. (1994). Busy period analysis, rare events and transient behavior in fluid flow models. J. Appl. Math. Stoch. Anal. 7, 269–299.CrossRefGoogle Scholar
[5] Beran, J., Sherman, R., Taqqu, M. S. and Willinger, W. (1995). Long-range dependence in variable-bit-rate video traffic. IEEE Trans. Commun. 43, 1566–1579.CrossRefGoogle Scholar
[6] Bingham, N. H., Goldie, C. and Teugels, J. (1987). Regular Variation. Cambridge University Press.CrossRefGoogle Scholar
[7] Boxma, O. J. and Kurkova, I. A. (2001). The M/G/1 queue with two different service speeds. Adv. Appl. Prob. 33, 520–540.Google Scholar
[8] Boxma, O. J., Deng, Q. and Zwart, A. P. (2002). Waiting-time asymptotics for the M/G/2 queue with heterogeneous servers. Queueing Systems 40, 5–31.Google Scholar
[9] Çinlar, E., (1975). Introduction to Stochastic Processes. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
[10] Cline, D. (1994). Intermediate regular and Π variation. Proc. London Math. Soc. 68, 594–616.Google Scholar
[11] Crovella, M. and Bestavros, A. (1996). Self-similarity in World Wide Web traffic: evidence and possible causes. In Proc. ACM Sigmetrics '96, ACM, New York, pp. 160–169.CrossRefGoogle Scholar
[12] Duffield, N. G. and O'Connell, N. (1995). Large deviations and overflow probabilities for the general single-server queue, with applications. Math. Proc. Camb. Phil. Soc. 118, 363–374.Google Scholar
[13] Dumas, V. and Simonian, A. (2000). Asymptotic bounds for the fluid queue fed by sub-exponential on/off sources. Adv. Appl. Prob. 32, 244–255.Google Scholar
[14] Glynn, P. W. and Whitt, W. (1994). Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. In Studies in Applied Probability (J. Appl. Prob. Spec. Vol. 31A), eds Galambos, J. and Gani, J., Applied Probability Trust, Sheffield, pp. 131–156.Google Scholar
[15] Heath, D., Resnick, S. and Samorodnitsky, G. (1998). Heavy tails and long-range dependence in on–off processes and associated fluid models. Math. Operat. Res. 23, 145–165.Google Scholar
[16] Jelenković, P. R. and Lazar, A. A. (1999). Asymptotic results for multiplexing subexponential on–off processes. Adv. Appl. Prob. 31, 394–421.CrossRefGoogle Scholar
[17] Kella, O. and Whitt, W. (1992). A storage model with a two-stage random environment. Operat. Res. 40, S257–S262.CrossRefGoogle Scholar
[18] Klüppelberg, C., (1988). Subexponential distributions and integrated tails. J. Appl. Prob. 25, 132–141.CrossRefGoogle Scholar
[19] Leland, W. E., Taqqu, M. S., Willinger, W. and Wilson, D. V. (1994). On the self-similar nature of ethernet traffic (extended version). IEEE/ACM Trans. Networking 2, 1–15.Google Scholar
[20] Pakes, A. G. (1975). On the tails of waiting-time distributions. J. Appl. Prob. 12, 555–564.CrossRefGoogle Scholar
[21] Paxson, A. and Floyd, S. (1995). Wide area traffic: the failure of Poisson modeling. IEEE/ACM Trans. Networking 3, 226–244.CrossRefGoogle Scholar
[22] Veraverbeke, N. (1977). Asymptotic behaviour of Wiener–Hopf factors of a random walk. Stoch. Process. Appl. 5, 27–37.Google Scholar
[23] Willinger, W., Taqqu, M. S., Sherman, R. and Wilson, D. V. (1997). Self-similarity through high-variability: statistical analysis of ethernet LAN traffic at the source level. IEEE/ACM Trans. Networking 5, 71–86.CrossRefGoogle Scholar
[24] Zwart, A. P., Borst, S. C. and Mandjes, M. (2003). Exact asymptotics for fluid queues fed by multiple heavy-tailed on–off flows. To appear in Ann. Appl. Prob. Google Scholar