Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T08:26:36.445Z Has data issue: false hasContentIssue false
  • English
  • Français

Tail Asymptotics for Monotone-Separable Networks

Part of: Limit theorems Special processes

Published online by Cambridge University Press:  14 July 2016

Marc Lelarge
Marc Lelarge*
Affiliation:
University College Cork
*
∗ Current address: ENS-INRIA, 45 rue d'Ulm, 75005 Paris, France. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A network belongs to the monotone separable class if its state variables are homogeneous and monotone functions of the epochs of the arrival process. This framework contains several classical queueing network models, including generalized Jackson networks, max-plus networks, polling systems, multiserver queues, and various classes of stochastic Petri nets. We use comparison relationships between networks of this class with independent and identically distributed driving sequences and the GI/GI/1/1 queue to obtain the tail asymptotics of the stationary maximal dater under light-tailed assumptions for service times. The exponential rate of decay is given as a function of a logarithmic moment generating function. We exemplify an explicit computation of this rate for the case of queues in tandem under various stochastic assumptions.

Keywords

Large deviationqueueing network

MSC classification

Primary: 60F10: Large deviations
Secondary: 60K25: Queueing theory
Type
Research Article
Information
Journal of Applied Probability , Volume 44 , Issue 2 , June 2007 , pp. 306 - 320
Copyright
Copyright © Applied Probability Trust 2007 

References

Anantharam, V. (1989). How large delays build up in a GI/G/1 queue. Queueing Systems Theory Appl. 5, 345–367.CrossRefGoogle Scholar
Baccelli, F. and Brémaud, P. (2003). Elements of Queueing Theory, 2nd edn. Springer, Berlin.Google Scholar
Baccelli, F. and Foss, S. (1995). On the saturation rule for the stability of queues. J. Appl. Prob. 32, 494–507.Google Scholar
Baccelli, F. and Foss, S. (2004). Moments and tails in monotone-separable stochastic networks. Ann. Appl. Prob. 14, 612–650.CrossRefGoogle Scholar
Baccelli, F., Foss, S. and Lelarge, M. (2005). Tails in generalized Jackson networks with subexponential service-time distributions. J. Appl. Prob. 42, 513–530.Google Scholar
Baccelli, F., Lelarge, M. and Foss, S. (2004). Asymptotics of subexponential max plus networks: the stochastic event graph case. Queueing Systems 46, 75–96.Google Scholar
Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd edn. Springer, New York.Google Scholar
Duffy, K., Lewis, J. T. and Sullivan, W. G. (2003). Logarithmic asymptotics for the supremum of a stochastic process. Ann. Appl. Prob. 13, 430–445.Google Scholar
Ganesh, A. (1998). Large deviations of the sojourn time for queues in series. Ann. Operat. Res. 79, 3–26.CrossRefGoogle Scholar
Iglehart, D. L. (1972). Extreme values in the GI/G/1 queue. Ann. Math. Statist. 43, 627–635.CrossRefGoogle Scholar
Lelarge, M. (2006). Tail asymptotics for discrete event systems. In Proc. 1st Internat. Conf. Performance Eval. Methodol. Tools, ACM Press, New York.Google Scholar
Pakes, A. G. (1975). On the tails of waiting-time distributions. J. Appl. Prob. 12, 555–564.Google Scholar