Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-16T21:14:03.914Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastic Bounds for Queueing Systems with Multiple On–Off Sources

Published online by Cambridge University Press:  27 July 2009

Ger Koole  and
Zhen Liu
Ger Koole
Affiliation:
Vrije Universiteit, De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands
Zhen Liu
Affiliation:
INRIA Sophia Antipolis, 2004 Route des Lucioles, B.P. 93, 06902 Sophia Antipolis, France
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider a queueing system where the input traffic consists of background traffic, modeled by a Markov Arrival Process, and foreground traffic modeled by N ≥ 1 homogeneous on–off sources. The queueing system has an increasing and concave service rate, which includes as a particular case multiserver queueing systems. Both the infinite-capacity and the finite-capacity buffer cases are analyzed. We show that the queue length in the infinite-capacity buffer system (respectively, the number of losses in the finite-capacity buffer system) is larger in the increasing convex order sense (respectively, the strong stochastic order sense) than the queue length (respectively, the number of losses) of the queueing system with the same background traffic and M N homogeneous on–off sources of the same total intensity as the foreground traffic, where M is an arbitrary integer. As a consequence, the queue length and the loss with a foreground traffic of multiple homogeneous on–off sources is upper bounded by that with a single on–off source and lower bounded by a Poisson source, where the bounds are obtained in the increasing convex order (respectively, the strong stochastic order). We also compare N ≥ 1 homogeneous arbitrary two-state Markov Modulated Poisson Process sources. We prove the monotonicity of the queue length in the transition rates and its convexity in the arrival rates. Standard techniques could not be used due to the different state spaces that we compare. We propose a new approach for the stochastic comparison of queues using dynamic programming which involves initially stationary arrival processes.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 12 , Issue 1 , January 1998 , pp. 25 - 48
Copyright
Copyright © Cambridge University Press 1998

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.Adan, I., van Houtum, G.-J., & van der Wal, J. (1994). Upper and lower bounds for the waiting time in the symmetric shortest queue system. Annals of Operations Research 48: 197–217.CrossRefGoogle Scholar
2.Asmussen, S. & Koole, G.M. (1993). Marked point processes as limits of Markovian arrival streams. Journal of Applied Probability 30: 365–372.CrossRefGoogle Scholar
3.Baccelli, F. & Brémaud, P. (1994). Elements of queueing theory. Berlin: Springer Verlag (Applications of Mathematics Series).Google Scholar
4.Bean, N.G. (1994). Robust connection acceptance for ATM networks with incomplete source information. Annals of Operations Research 48: 357–379.CrossRefGoogle Scholar
5.Boyer, P.E., Guillemin, F.M., Servel, M.J., & Coudreuse, J.-P. (1992). Spacing cells protects and enhances utilization of ATM network links. IEEE Network 38–49.CrossRefGoogle Scholar
6.Chang, C.S., Chao, X., & Pinedo, M. (1991). Monotonicity results for queues with doubly stochastic Poisson arrivals: Ross's conjecture. Advances in Applied Probability 23: 210–228.CrossRefGoogle Scholar
7.Chang, C.S., Chao, X., Pinedo, M., & Shanthikumar, J.G. (1991). Stochastic convexity for multi-dimensional processes and its applications. IEEE Transactions on Automatic Control 36: 1347–1355.CrossRefGoogle Scholar
8.Chang, C.S. & Pinedo, M. (1990). Bounds and inequalities for single server loss systems. Queueing Systems 6: 425–436.CrossRefGoogle Scholar
9.Çinlar, E. (1975). Introduction to stochastic processes. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
10.Marshall, A.W. & Olkin, I. (1979). Inequalities: Theory of majorization and its applications. New York: Academic Press.Google Scholar
11.Rolski, T. (1981). Queues with non-stationary input stream: Ross's conjecture. Advances in Applied Probability 13: 603–618.CrossRefGoogle Scholar
12.Rolski, T. (1986). Upper bounds for single server queues with doubly stochastic Poisson arrivals. Mathematics of Operations Research 11: 442–450.CrossRefGoogle Scholar
13.Ross, S.M. (1978). Average delay in queues with non-stationary Poisson arrivals. Journal of Applied Probability 15: 602–609.CrossRefGoogle Scholar
14.Ross, S.M. (1983). Stochastic processes. New York: Wiley.Google Scholar
15.Shaked, M. & Shanthikumar, J.G. (1994). Stochastic orders and their applications. Boston: Academic Press.Google Scholar
16.Stoyan, D. (1983). Comparison methods for queues and other stochastic models. English translation, Daley, D.J. (ed.). New York: Wiley.Google Scholar
17.Svoronos, A. & Green, L. (1988). A convexity result for single server exponential loss systems with nonstationary arrivals. Journal of Applied Probability 25: 224–227.CrossRefGoogle Scholar
18.van Dijk, N.M. & Lamond, B.F. (1988). Simple bounds for finite single-server exponential tandem queues. Operations Research 36: 470–477.CrossRefGoogle Scholar
19.van Dijk, N.M. & van der Wal, J. (1989). Simple bounds and monotonicity results for finite multi-server exponential tandem queues. Queueing Systems 4: 1–16.CrossRefGoogle Scholar