Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-29T00:18:36.834Z Has data issue: false hasContentIssue false

A TANDEM QUEUE WITH LÉVY INPUT: A NEW REPRESENTATION OF THE DOWNSTREAM QUEUE LENGTH

Published online by Cambridge University Press:  15 December 2006

Krzysztof Debicki
Affiliation:
Mathematical Institute, University of Wrocław, 50-384 Wrocław, Poland, E-mail: [email protected]
Michel Mandjes
Affiliation:
CWI, 1090 GB Amsterdam, The Netherlands, Korteweg-de Vries Institute, University of Amsterdam, 1018 TV Amsterdam, The Netherlands, and, EURANDOM, 5600 MB Eindhoven, The Netherlands, E-mail: [email protected]
Miranda van Uitert
Affiliation:
The Netherlands Cancer Institute, 1066 CX Amsterdam, The Netherlands, and Information and Communication Theory Group, Delft University of Technology, 2600 GA Delft, The Netherlands, E-mail: [email protected]

Abstract

In this article we present a new representation for the steady-state distribution of the workload of the second queue in a two-node tandem network. It involves the difference of two suprema over two adjacent intervals. In the case of spectrally positive Lévy input, this enables us to derive the Laplace transform and Pollaczek–Khintchine representation of the workload of the second queue. Additionally, we obtain the exact distribution of the workload in the case of Brownian and Poisson input, as well as some insightful formulas representing the exact asymptotics for α-stable Lévy inputs.

Type
Research Article
Copyright
© 2007 Cambridge University Press

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

REFERENCES

Abate, J. & Whitt, W. (1997). Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems 25: 173233.Google Scholar
Adan, I. & Resing, J. (1996). A note on a fluid queue driven by an M/M/1 queue. Queueing Systems 22: 171174.Google Scholar
Asmussen, S. (2000). Ruin probabilities. London: World Scientific.CrossRef
Asmussen, S. (2003). Applied probability and queues. New York: Springer-Verlag.
Avi-Itzhak, B. (1965). A sequence of service stations with arbitrary input and regular service times. Management Science 11: 565571.Google Scholar
Baxter, G. & Donsker, M.D. (1957). On the distribution of the supremum functional for the processes with stationary independent increments. Transactions of the American Mathematical Society 85: 7387.Google Scholar
Bertoin, J. (1996). Lévy processes. Cambridge: Cambridge University Press.
Bingham, N. (1975). Fluctuation theory in continuous time. Advances in Applied Probability 7: 705766.Google Scholar
Boxma, O. & Dumas, V. (1998). The busy period in the fluid queue. Performance Evaluation Review 26: 100110.Google Scholar
Cao, J. & Ramanan, K. (2002). A Poisson limit for buffer overflow probabilities. In Proceedings IEEE INFOCOM, New York, pp. 9941003.CrossRef
Chang, C.-S., Heidelberger, P., Juneja, S., & Shahabuddin, P. (1994). Effective bandwidth and fast simulation of ATM intree networks. Performance Evaluation 20: 4565.Google Scholar
Cline, D.B.H. (1986). Convolution tails, product tails and domains of attraction. Probability Theory and Related Fields 72: 529557.Google Scholar
Cox, D. & Smith, W. (1961). Queues. London: Methuen.
Debicki, K. & Mandjes, M. (2004). Traffic with an fBm limit: Convergence of the stationary workload process. Queueing Systems 46: 113127.Google Scholar
Debicki, K. & Palmowski, Z. (1999). On–off fluid models in heavy traffic environment. Queueing Systems 33: 327338.Google Scholar
Embrechts, P. & Goldie, C.M. (1982). On convolution tails. Stochastic Processes and Their Applications 13: 263268.Google Scholar
Embrechts, P., Goldie, C.M., & Veraverbeke, N. (1979). Subexponentiality and infinite divisibility. Zeitschrift für Wahrscheinlichkeitstheorie und Verwunde Gebiete 49: 335347.Google Scholar
Friedman, H. (1965). Reduction methods for tandem queueing systems. Operations Research 13: 121131.Google Scholar
Fristedt, B. (1974). Sample functions of stochastic processes with stationary independent increments. Advances in Probability 3: 241396.Google Scholar
Furrer, H. (1997). Risk theory and heavy-tailed Lévy processes. Ph.D. dissertation, ETH, Zurich. Available at http://www.math.ethz.ch/∼hjfurrer/.
Humblet, P., Bhargava, A., & Hluchyj, M. (1993). Ballot theorems applied to the transient analysis of nD/D/1 queues. IEEE/ACM Transactions on Networking 1: 8195.Google Scholar
Kaj, I. & Taqqu, M. (2004). Convergence to fractional Brownian motion and to the Telecom process: The integral representation approach. Available at http://www.math.uu.se/∼ikaj/preprints/kajtaqqu040712.pdf.
Kella, O. (1993). Parallel and tandem fluid networks with dependent Lévy inputs. Annals of Applied Probability 3: 682695.Google Scholar
Kella, O. (2001). Markov-modulated feedforward fluid networks. Queueing Systems 37: 141161.Google Scholar
Kella, O. & Whitt, W. (1992). A tandem fluid network with Lévy input. In U. Bhat & I. Basawa (eds.), Queueing and related models. Oxford: Clarendon Press.
Mandjes, M. & van Uitert, M. (2005). Sample-path large deviations for tandem and priority queues with Gaussian inputs. Annals of Applied Probability 15: 11931226.Google Scholar
Mikosch, T., Resnick, S., Rootzén, H., & Stegeman, A. (2002). Is network traffic approximated by stable Lévy motion or fractional Brownian motion? Annals of Applied Probability 12: 2368.Google Scholar
Pitman, E.J.G. (1980). Subexponential distribution functions. Journal of the Australian Mathematical Society A 29: 337347.Google Scholar
Port, S. (1989). Stable processes with drift on the line. Transactions of the American Mathematical Society 313: 805841.Google Scholar
Reich, E. (1958). On the integrodifferential equation of Takács I. Annals of Mathematical Statistics 29: 563570.Google Scholar
Roberts, J., Mocci, U., & Virtamo, J. (1996). Broadband network teletraffic. Final report of action COST 242. Berlin: Springer-Verlag.CrossRef
Roberts, J. & Virtamo, J. (1991). The superposition of periodic cell arrival streams in an ATM multiplexer. IEEE Transactions on Communications 39: 298303.Google Scholar
Rubin, I. (1974). Path delays in communication networks. Applied Mathematics and Optimization 1: 193221.Google Scholar
Samorodnitsky, G. & Taqqu, M. (1994). Stable non-Gaussian random processes. London: Chapman & Hall.
Sato, K. (1999). Lévy processes and infinitely divisible distributions. Cambridge: Cambridge University Press.
Scheinhardt, W. & Zwart, B. (2002). A tandem fluid queue with gradual input. Probability in the Engineering and Informational Sciences 16: 2945.Google Scholar
Shalmon, M. & Kaplan, M. (1984). A tandem network of queues with deterministic service and intermediate arrivals. Operations Research 32: 753773.Google Scholar
Takács, L. (1965). On the distribution of the supremum of stochastic processes with exchangeable increments. Transactions of the American Mathematical Society 119: 367379.Google Scholar
Takács, L. (1967). Combinatorial methods in the theory of stochastic processes. New York: Wiley.
Takagi, H. (1991). Queueing analysis. A Foundation of Performance Evaluation. Vol. I: Vacation and Priority Systems, Part 1. Amsterdam: North-Holland.
Taqqu, M., Willinger, W., & Sherman, R. (1997). Proof of a fundamental result in self-similar traffic modeling. Computer Communications Review 27: 523.Google Scholar
Zolotarev, V.M. (1964). The first passage time of a level and the behaviour at infinity for a class of processes with independent increments. Theory of Probability and Its Applications 9: 653661.Google Scholar