Abstract
An efficient yet accurate estimation of the tail distribution of the queue length has been considered as one of the most important issues in call admission and congestion controls in ATM networks. The arrival process in ATM networks is essentially a superposition of sources which are typically bursty and periodic either due to their origin or their periodic slot occupation after traffic shaping. In this paper, we consider a discrete-time queue where the arrival process is a superposition of general periodic Markov sources. The general periodic Markov source is rather general since it is assumed only to be irreducible, stationary and periodic. Note also that the source model can represent multiple time-scale correlations in arrivals. For this queue, we obtain upper and lower bounds for the asymptotic tail distribution of the queue length by bounding the asymptotic decay constant. The formulas can be applied to a queue having a huge number of states describing the arrival process. To show this, we consider an MPEG-like source which is a special case of general periodic Markov sources. The MPEG-like source has three time-scale correlations: peak rate, frame length and a group of pictures. We then apply our bound formulas to a queue with a superposition of MPEG-like sources, and provide some numerical examples to show the numerical feasibility of our bounds. Note that the number of states in a Markov chain describing the superposed arrival process is more than 1.4 × 1088. Even for such a queue, the numerical examples show that the order of the magnitude of the tail distribution can be readily obtained.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Abate, G.L. Choudhury and W. Whitt, Asymptotics for steady-state tail probabilities in structured Markov chains of M/G/1-type, Stochastic Models 10 (1994) 99–144.
F. Baccelli and P. Brémaud, Elements of Queueing Theory (Springer, New York, 1994).
C.-S. Chang, Sample path large deviations and intree networks, Queueing Systems 20 (1995) 7–36.
G.L. Choudhury, D.M. Lucantoni and W. Whitt, Squeezing the most out of ATM, IEEE Trans. Commun. 44 (1996) 203–217.
I. Cidon, R. Guérin, I. Kessler and A. Khamisy, Analysis of a statistical multiplexer with generalized periodic sources, Queueing Systems 20 (1995) 139–169.
N.G. Duffield, Exponential bounds for queues with Markovian arrivals, Queueing Systems 17 (1994) 413–430.
E. Falkenberg, On the asymptotic behavior of the stationary distribution of Markov chains of M/G/1-type, Stochastic Models 10 (1994) 75–98.
A. Graham, Kronecker Products and Matrix Calculus with Applications (Ellis Horwood, Chichester, UK, 1981).
P. Humblet, A. Bhargava and M.G. Hluchyj, Ballot theorems applied to the transient analysis of nD=D=1 queues, IEEE/ACM Trans. Net. 1 (1993) 81–95.
F. Ishizaki and T. Takine, Bounds for the tail distribution in a queue with the superposition of general periodic Markov sources, in: Proc. IEEE INFOCOM '97 (1997) pp. 1090–1097.
F. Ishizaki and T. Takine, Loss probability in a finite discrete-time queue in terms of the steady state distribution of an infinite queue, Queueing Systems 31 (1999) 317–326.
F. Ishizaki and T. Takine, Cell loss probability approximations and their application to call admission control, submitted for publication.
F. Ishizaki, T. Takine, H. Terada and T. Hasegawa, Loss probability approximation of a statistical multiplexer and its application to call admission control in high-speed networks, in: Proc. IEEE GLOBECOM '95 (1995) pp. 417–421.
S. Karlin and H.M. Taylor, A Second Course in Stochastic Processes (Academic Press, London, 1981).
G. Kesidis, J. Walrand and C.-S. Chang, Effective bandwidths for multiclass Markov fluids and other ATM sources, IEEE/ACM Trans. Net. 1 (1993) 424–428.
R.M. Loynes, The stability of a queue with non-independent interarrival and service times, Proc. Cambridge Phil. Soc. 58 (1962) 497–520.
M.F. Neuts, Structured Stochastic Matrices of M/G/1 Type and Their Applications (Marcel Dekker, New York, 1989).
G. Ramamurthy and B. Sengupta, Delay analysis of a packet voice multiplexer by the PDi/D/1 queue, IEEE Trans. Commun. 39 (1991) 1107–1114.
J.W. Roberts and J.T. Virtamo, The superposition of periodic cell arrival streams in an ATM multiplexer, IEEE Trans. Commun. 39 (1991) 298–303.
E. Seneta, Non-negative Matrices and Markov Chains, 2nd ed. (Springer, New York, 1981).
K. Sohraby, On the asymptotic behavior of heterogeneous statistical multiplexer with applications, in: Proc. IEEE INFOCOM '92 (1992) pp. 839–847.
T. Takine, B. Sengupta and T. Hasegawa, An analysis of a discrete-time queue for broadband ISDN with priorities among traffic classes, IEEE Trans. Commun. 42 (1994) 1837–1845.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ishizaki, F., Takine, T. Bounds for the tail distribution in a queue with a superposition of general periodic Markov sources: theory and application. Queueing Systems 34, 67–100 (2000). https://doi.org/10.1023/A:1019148817838
Issue Date:
DOI: https://doi.org/10.1023/A:1019148817838