×

zbMATH — the first resource for mathematics

Asymptotic analysis of Lévy-driven tandem queues. (English) Zbl 1156.90334
Summary: We analyze tail asymptotics of a two-node tandem queue with spectrally-positive Lévy input. A first focus lies in the tail probabilities of the type \(\mathbb P(Q _{1}>\alpha x,Q _{2}>(1 - \alpha )x)\), for \(\alpha \in (0,1)\) and \(x\) large, and \(Q _{i }\) denoting the steady-state workload in the \(i\)th queue. In case of light-tailed input, our analysis heavily uses the joint Laplace transform of the stationary buffer contents of the first and second queue; the logarithmic asymptotics can be expressed as the solution to a convex programming problem. In case of heavy-tailed input we rely on sample-path methods to derive the exact asymptotics. Then we specialize in the tail asymptotics of the downstream queue, again in case of both light-tailed and heavy-tailed Lévy inputs. It is also indicated how the results can be extended to tandem queues with more than two nodes.

MSC:
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abate, J., Whitt, W.: Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Syst. 25, 173–233 (1997) · Zbl 0894.60088 · doi:10.1023/A:1019104402024
[2] de Acosta, A.: Large deviations for vector-valued Lévy processes. Stoch. Process. Their Appl. 51, 75–115 (1994) · Zbl 0805.60020 · doi:10.1016/0304-4149(94)90020-5
[3] Avi-Itzhak, B.: A sequence of service stations with arbitrary input and regular service times. Manag. Sci. 11, 565–571 (1965) · Zbl 0156.18602 · doi:10.1287/mnsc.11.5.565
[4] Avram, F., Palmowski, Z., Pistorius, M.: A two-dimensional ruin problem on the positive quadrant. Insur. Math. Econ. 42, 227–234 (2008) · Zbl 1141.91482 · doi:10.1016/j.insmatheco.2007.02.004
[5] Avram, F., Palmowski, Z., Pistorius, M.: Exit problem of a two-dimensional risk process from the quadrant: exact and asymptotic result. Ann. Appl. Probab. (2008, to appear) · Zbl 1163.60010
[6] Baccelli, F., Foss, S.: Moments and tails in monotone-separable stochastic networks. Ann. Appl. Probab. 14, 612–650 (2004) · Zbl 1048.60067 · doi:10.1214/105051604000000044
[7] Bekker, R., Mandjes, M.: A fluid model for a relay node in an ad hoc network: the case of heavy-tailed input. Math. Methods Oper. Res. (2008, to appear), url: http://ftp.cwi.nl/CWIreports/PNA/PNA-E0703.pdf · Zbl 1190.93103
[8] Bertoin, J.: Lévy Processes. Cambridge University Press, Cambridge (1996) · Zbl 0861.60003
[9] Bertsimas, D., Paschalidis, J., Tsitsiklis, J.: On the large deviation behavior in acyclic networks of G/G/1 queues. Ann. Appl. Probab. 8, 1027–1069 (1998) · Zbl 0973.90012 · doi:10.1214/aoap/1028903373
[10] Bertsimas, D., Paschalidis, J., Tsitsiklis, J.: Large deviation analysis of the generalized processor sharing policy. Queueing Syst. 32, 319–349 (1999) · Zbl 0937.68011 · doi:10.1023/A:1019151423773
[11] Bingham, N., Doney, R.: Asymptotic properties of subcritical branching processes I: the Galton–Watson process. Adv. Appl. Probab. 6, 711–731 (1974) · Zbl 0297.60044 · doi:10.2307/1426188
[12] Bingham, N., Goldie, C., Teugels, J.: Regular Variation. Cambridge University Press, Cambridge (1987) · Zbl 0617.26001
[13] Borovkov, A.: Stochastic Processes in Queueing Theory. Springer, New York (1976) · Zbl 0319.60057
[14] Borovkov, A., Mogulskii, A.: Large deviations for Markov chains in the quarter plane. Usp. Mat. Nauk 56, 3–115 (2001) · Zbl 0970.60029
[15] Chang, C.-S., Heidelberger, P., Juneja, S., Shahabuddin, P.: Effective bandwidth and fast simulation of ATM in-tree networks. Perform. Eval. 20, 45–65 (1994) · doi:10.1016/0166-5316(94)90005-1
[16] Cohen, J.W.: Some results on regular variation for distributions in queueing and fluctuation theory. J. Appl. Probab. 10, 343–353 (1973) · Zbl 0258.60076 · doi:10.2307/3212351
[17] Cox, D., Smith, W.: Queues. Methuen, London (1961)
[18] Dębicki, K., Dieker, A., Rolski, T.: Quasi-product form for Lévy-driven fluid networks. Math. Oper. Res. 32, 629–647 (2007) · Zbl 1341.60111 · doi:10.1287/moor.1070.0259
[19] Dębicki, K., Mandjes, M., van Uitert, M.: A tandem queue with Lévy input: a new representation of the downstream queue length. Probab. Eng. Inf. Sci. 21, 83–107 (2007) · Zbl 1114.60074
[20] Doetsch, G.: Introduction to the Theory and Applications of the Laplace Transformation. Springer, New York (1974) · Zbl 0278.44001
[21] Es-Saghouani, A., Mandjes, M.: On the correlation structure of a Lévy-driven queue. J. Appl. Probab. (2008, submitted), url: http://ftp.cwi.nl/CWIreports/PNA/PNA-R0711.pdf · Zbl 1154.60348
[22] Friedman, H.: Reduction methods for tandem queueing systems. Oper. Res. 13, 121–131 (1965) · Zbl 0143.40702 · doi:10.1287/opre.13.1.121
[23] Foss, S.: On exact asymptotics for a stationary sojourn time distribution in a tandem of queues for a class of light-tailed distributions. Probl. Inf. Transm. 43, 93–108 (2007) · Zbl 1166.60056 · doi:10.1134/S0032946007040084
[24] Foss, S., Konstantopoulos, T., Zachary, S.: Discrete and continuous time modulated random walks with heavy-tailed increments. J. Theor. Probab. 20, 581–612 (2007) · Zbl 1131.60040 · doi:10.1007/s10959-007-0081-2
[25] Furrer, H.: Risk processes perturbed by \(\alpha\)-stable Lévy motion. Scand. Actuar. J. 1, 59–74 (1998) · Zbl 1026.60516
[26] Ganesh, A., Anantharam, V.: Stationary tail probabilities in exponential server tandems with renewal arrivals. Queueing Syst. 22, 203–247 (1996) · Zbl 0865.60083 · doi:10.1007/BF01149173
[27] Ganesh, A.: Large deviations of the sojourn time for queues in series. Ann. Oper. Res. 79, 3–26 (1998) · Zbl 0896.90095 · doi:10.1023/A:1018930907280
[28] Ignatyuk, I., Malyshev, V., Scherbakov, V.: Boundary effects in large deviations problems. Russ. Math Surv. 49, 41–99 (1994) · doi:10.1070/RM1994v049n02ABEH002204
[29] Kella, O., Whitt, W.: A tandem fluid network with Lévy input. In: Bhat, U.N., Basawa, I.V. (eds.) Queueing and Related Models, pp. 112–128. Oxford University Press, London (1992) · Zbl 0783.60089
[30] Kyprianou, A.: Introductory Lectures on Fluctuations of Lévy Processes with Applications. Springer, Berlin (2006) · Zbl 1104.60001
[31] Lieshout, P., Mandjes, M.: Tandem Brownian queues. Math. Methods Oper. Res. 66, 275–298 (2007) · Zbl 1139.60045 · doi:10.1007/s00186-007-0149-x
[32] Mandjes, M., Borst, S.: Overflow behavior in queues with many long-tailed inputs. Adv. Appl. Probab. 32, 1150–1167 (2000) · Zbl 0987.60094 · doi:10.1239/aap/1013540352
[33] Mandjes, M., van Uitert, M.: Sample-path large deviations for tandem and priority queues with Gaussian inputs. Ann. Appl. Probab. 15, 1193–1226 (2005) · Zbl 1069.60079 · doi:10.1214/105051605000000133
[34] De Meyer, A., Teugels, J.: On the asymptotic behavior of the distributions of the busy period and service time in M/G/1. J. Appl. Probab. 17, 802–813 (1980) · Zbl 0444.60088 · doi:10.2307/3212973
[35] Pakes, A.: On the tails of waiting-time distributions. J. Appl. Probab. 12, 555–564 (1975) · Zbl 0314.60072 · doi:10.2307/3212870
[36] Pecherskii, E., Sukhov, Ju.: Dobrushin’s ideas in the theory of queueing networks. Russ. Math. Surv. 52, 265–269 (1997) · Zbl 0938.60006 · doi:10.1070/RM1997v052n02ABEH001774
[37] Reich, E.: On the integro-differential equation of Takács I. Ann. Math. Stat. 29, 563–570 (1958) · Zbl 0086.33703 · doi:10.1214/aoms/1177706632
[38] Resnick, S., Samorodnitsky, G.: Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues. Queueing Syst. 33, 43–71 (1999) · Zbl 0997.60111 · doi:10.1023/A:1019163826499
[39] Rubin, I.: Path delays in communication networks. Appl. Math. Optim. 1, 193–221 (1974) · Zbl 0309.60066 · doi:10.1007/BF01448181
[40] Tsoucas, P.: Rare events in series of queues. J. Appl. Probab. 29, 168–175 (1992) · Zbl 0765.60100 · doi:10.2307/3214800
[41] Veraverbeke, N.: Asymptotic behavior of Wiener–Hopf factors of a random walk. Stoch. Process. Their Appl. 5, 27–37 (1977) · Zbl 0353.60073 · doi:10.1016/0304-4149(77)90047-3
[42] Zolotarev, V.M.: The first passage time of a level and the behavior at infinity for a class of processes with independent increments. Theory Probab. Appl. 9, 653–661 (1964) · Zbl 0149.12903 · doi:10.1137/1109090
[43] Zwart, B.: Queueing Systems with Heavy Tails. Ph.D. Thesis, Eindhoven University of Technology (2001), url: http://alexandria.tue.nl/extra2/200112999.pdf · Zbl 0988.60095
[44] Zwart, B., Borst, S., Mandjes, M.: Exact asymptotics for fluid queues fed by multiple heavy-tailed on-off sources. Ann. Appl. Probab. 14, 903–957 (2004) · Zbl 1041.60072 · doi:10.1214/aoap/1075828048
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.