×

On the maximum workload of a queue fed by fractional Brownian motion. (English) Zbl 1073.60089

Summary: Consider a queue with a stochastic fluid input process modeled as fractional Brownian motion (fBM).When the queue is stable, we prove that the maximum of the workload process observed over an interval of length \(t\) grows like \(\gamma(\log t)^{1/(2-2H)}\), where \(H > 1/2\) is the self-similarity index (also known as the Hurst parameter) that characterizes the fBM and can be explicitly computed. Consequently, we also have that the typical time required to reach a level \(b\) grows like \(\exp{b^{2(1-H)}}\). We also discuss the implication of these results for statistical estimation of the tail probabilities associated with the steady-state workload distribution.

MSC:

60K25 Queueing theory (aspects of probability theory)
60G70 Extreme value theory; extremal stochastic processes
Full Text: DOI

References:

[1] Adler, R. J. (1990). An Introduction to Continuity, Extrema, and Related Topics for General Gaussian Processes. IMS, Hayward, CA. · Zbl 0747.60039
[2] Asmussen, S. (1998). Extreme value theory for queues via cycle maxima. Extremes 1 137-168. · Zbl 0926.60072 · doi:10.1023/A:1009970005784
[3] Berger, A. W. and Whitt, W. (1995). Maximum values in queueing processes. Probab.Engrg. Inform.Sci.9 375-409. · Zbl 1335.60168 · doi:10.1017/S0269964800003934
[4] Beran, J., Sherman, R., Taqqu, M. and Willinger, W. (1995). Long-range dependence in variable-bit-rate video traffic. IEEE Trans.Comm.43 1566-1579.
[5] Chang, C.-S., Yao, D. D. and Zajic, T. (1996). Moderate deviations for queues with long-range dependent input. Stochastic Networks. Lecture Notes in Statist. 117 275-298. Springer, New York. · Zbl 0856.60037
[6] Cohen, J. W. (1968). Extreme value distribution for the M/G/1 and the G/M/1 queueing systems. Ann.Inst.H.Poincaré Sec.B 4 83-98. · Zbl 0162.49302
[7] Duffield, N. G. and O’Connell, N. (1995). Large deviations and overflow probabilities with general single-server queue, with applications. Math.Proc.Cambridge Philos.Soc.118 363-374. · Zbl 0840.60087 · doi:10.1017/S0305004100073709
[8] Erramilli, A., Narayan, O. and Willinger, W. (1997). Fractal queueing models. In Frontiers in Queueing 245-269. CRC Press, Boca Raton, FL. · Zbl 0871.60078
[9] Glasserman, P. and Kou, S. (1995). Limits of first passage times to rare sets in regenerative processes. Ann.Appl.Probab.5 424-445. · Zbl 0830.60021 · doi:10.1214/aoap/1177004772
[10] Glynn, P. and Whitt, W. (1988). Ordinary CLT and WLLN versions of L = W. Math.Oper.Res. 13 674-692. JSTOR: · Zbl 0685.90043 · doi:10.1287/moor.13.4.674
[11] Harrison, M. J. (1985). Brownian Motion and Stochastic Flow Systems. Wiley, New York. · Zbl 0659.60112
[12] Heath, D., Resnick, S. and Samorodnitsky, G. (1997). Patterns of buffer overflow in a class of queues with long memory in the input stream. Ann.Appl.Probab.7 1021-1057. · Zbl 0905.60070 · doi:10.1214/aoap/1043862423
[13] Heath, D., Resnick, S. and Samorodnitsky, G. (1998). Heavy tails and long range dependence in on/off processes and associated fluid models. Math.Oper.Res.23 145-165. JSTOR: · Zbl 0981.60092 · doi:10.1287/moor.23.1.145
[14] Hsu, I. and Walrand, J. (1996). Dynamic bandwidth allocation for ATM switches. J.Appl.Probab. 33 758-771. JSTOR: · Zbl 0860.90053 · doi:10.2307/3215357
[15] H üsler, J. and Piterbarg, V. (1999). Extremes of a certain class of Gaussian processes. Stochastic Process.Appl.83 257-271. · Zbl 0997.60057 · doi:10.1016/S0304-4149(99)00041-1
[16] Iglehart, D. L. (1972). Extreme values in the GI/G/1 queue. Ann.Math.Statist.43 627-635. · Zbl 0238.60072 · doi:10.1214/aoms/1177692642
[17] Konstantopoulos, T. and Lin, S. J. (1996). Fractional Brownian approximations of queueing networks. Stochastic Networks. Lecture Notes in Statist. 117 257-273. Springer, New York. · Zbl 0856.60097
[18] Konstantopoulos, T., Zazanis, M. and De Veciana, G. (1996). Conservation laws and reflection mappings with an application to multiclass mean value analysis for stochastic fluid queues. Stochastic Process.Appl.65 139-146. · Zbl 0889.60094 · doi:10.1016/S0304-4149(96)00103-2
[19] Krishnan, K. R. (1996). A new class of performance results for a fractional Brownian traffic model. Queueing Systems 22 277-285. · Zbl 0860.60084 · doi:10.1007/BF01149175
[20] Leadbetter, M. R., Lindgren, G. and Rootzén, H. (1983). Extremes and Related Properties of Random Sequences and Processes. Springer, New York. · Zbl 0518.60021
[21] Leland, W. E., Taqqu, M. S., Willinger, W. and Willson, D.V. (1993). On the self-similar nature of Ethernet traffic. In SIGCOMM93.
[22] Lions, P.-L. and Sznitman, A.-S. (1984). Stochastic differential equations with reflecting boundary conditions. Comm.Pure Appl.Math.37 511-537. · Zbl 0598.60060 · doi:10.1002/cpa.3160370408
[23] Mandelbrot, B. B. and Van Ness, J. W. (1968). Fractional Brownian motion, fractional noises and applications. SIAM Rev. 10 422-437. JSTOR: · Zbl 0179.47801 · doi:10.1137/1010093
[24] Massoulie, L. and Simonian, A. (1999). Large buffer asymptotics for the queue with FBM input J.Appl.Probab.36, 894-906. · Zbl 0955.60096 · doi:10.1239/jap/1032374642
[25] Narayan, O. (1998). Queue length distribution for fractional Brownian traffic. Advances in Performance Analysis 1 39-65.
[26] Norros, I. (1994). A storage model with self-similar input. Queueing Systems 16 387-396. · Zbl 0811.68059 · doi:10.1007/BF01158964
[27] O’Connell, N. and Procissi, G. (1998). A variational approach to performance evaluation for a queue loaded by fractional Brownian motion. Technical Report HPL-BRIMS-98-18, HP Labs.
[28] Rozanov, Y. A. (1967). Stationary Random Processes. Holden-Day, San Francisco. · Zbl 0152.16302
[29] Samorodnitsky, G. and Taqqu, M. S. (1994). Stable Non-Gaussian Random Processes. Chapman & Hall, New York. · Zbl 0925.60027
[30] Whitt, W. (1998). Non-Brownian FCLTS for the single server queue. Technical report, AT&T Labs. · Zbl 0967.60038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.