Moments and tails in monotone-separable stochastic networks

François Baccelli, Serguei Foss

Research output: Contribution to journalArticle

Abstract

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, which was first introduced to derive the stability region for stochastic networks with stationary and ergodic driving sequences, is revisited. It contains several classical queueing network models, including generalized Jackson networks, max-plus networks, polling systems, multiserver queues, and various classes of stochastic Petri nets. Our purpose is the analysis of the tails of the stationary state variables in the particular case of i.i.d. driving sequences. For this, we establish general comparison relationships between networks of this class and the GI/G/I/1/8 queue. We first use this to show that two classical results of the asymptotic theory for GI/GI/1/8 queues can be directly extended to this framework. The first one concerns the existence of moments for the stationary state variables. We establish that for all a = 1, the (a + 1)-moment condition for service times is necessary and sufficient for the existence of the a-moment for the stationary maximal dater (typically the time to empty the network when stopping further arrivals) in any network of this class. The second one is a direct extension of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We show that under subexponential assumptions for service times, the stationary maximal dater in any such network has tail asymptotics which can be bounded from below and from above by a multiple of the integrated tails of service times. In general, the upper and the lower bounds do not coincide. Nevertheless, exact asymptotics can be obtained along the same lines for various special cases of networks, providing direct extensions of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We exemplify this on tandem queues (maximal daters and delays in stations) as well as on multiserver queues. © Institute of Mathematical Statistics, 2004.

Original languageEnglish
Pages (from-to)612-650
Number of pages39
JournalAnnals of Applied Probability
Volume14
Issue number2
DOIs
Publication statusPublished - May 2004

Fingerprint

Stochastic Networks
Tail
Monotone
Queue
Moment
Tail Asymptotics
Multi-server
Stationary States
Waiting Time
Polling Systems
Jackson Networks
Tandem Queues
Queueing Network Models
Stochastic Petri Nets
Homogeneous Function
Moment Conditions
Stability Region
Monotone Function
Asymptotic Theory
Sufficient

Keywords

  • Ergodicity
  • Generalized jackson network
  • Queueing network
  • Subexponential random variable
  • Tail asymptotics
  • Veraverbeke's theorem

Cite this

@article{fd2b9a518cc54486b6f827a8be0e3156,
title = "Moments and tails in monotone-separable stochastic networks",
abstract = "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, which was first introduced to derive the stability region for stochastic networks with stationary and ergodic driving sequences, is revisited. It contains several classical queueing network models, including generalized Jackson networks, max-plus networks, polling systems, multiserver queues, and various classes of stochastic Petri nets. Our purpose is the analysis of the tails of the stationary state variables in the particular case of i.i.d. driving sequences. For this, we establish general comparison relationships between networks of this class and the GI/G/I/1/8 queue. We first use this to show that two classical results of the asymptotic theory for GI/GI/1/8 queues can be directly extended to this framework. The first one concerns the existence of moments for the stationary state variables. We establish that for all a = 1, the (a + 1)-moment condition for service times is necessary and sufficient for the existence of the a-moment for the stationary maximal dater (typically the time to empty the network when stopping further arrivals) in any network of this class. The second one is a direct extension of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We show that under subexponential assumptions for service times, the stationary maximal dater in any such network has tail asymptotics which can be bounded from below and from above by a multiple of the integrated tails of service times. In general, the upper and the lower bounds do not coincide. Nevertheless, exact asymptotics can be obtained along the same lines for various special cases of networks, providing direct extensions of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We exemplify this on tandem queues (maximal daters and delays in stations) as well as on multiserver queues. {\circledC} Institute of Mathematical Statistics, 2004.",
keywords = "Ergodicity, Generalized jackson network, Queueing network, Subexponential random variable, Tail asymptotics, Veraverbeke's theorem",
author = "Fran{\cc}ois Baccelli and Serguei Foss",
year = "2004",
month = "5",
doi = "10.1214/105051604000000044",
language = "English",
volume = "14",
pages = "612--650",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "2",

}

Moments and tails in monotone-separable stochastic networks. / Baccelli, François; Foss, Serguei.

In: Annals of Applied Probability, Vol. 14, No. 2, 05.2004, p. 612-650.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Moments and tails in monotone-separable stochastic networks

AU - Baccelli, François

AU - Foss, Serguei

PY - 2004/5

Y1 - 2004/5

N2 - 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, which was first introduced to derive the stability region for stochastic networks with stationary and ergodic driving sequences, is revisited. It contains several classical queueing network models, including generalized Jackson networks, max-plus networks, polling systems, multiserver queues, and various classes of stochastic Petri nets. Our purpose is the analysis of the tails of the stationary state variables in the particular case of i.i.d. driving sequences. For this, we establish general comparison relationships between networks of this class and the GI/G/I/1/8 queue. We first use this to show that two classical results of the asymptotic theory for GI/GI/1/8 queues can be directly extended to this framework. The first one concerns the existence of moments for the stationary state variables. We establish that for all a = 1, the (a + 1)-moment condition for service times is necessary and sufficient for the existence of the a-moment for the stationary maximal dater (typically the time to empty the network when stopping further arrivals) in any network of this class. The second one is a direct extension of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We show that under subexponential assumptions for service times, the stationary maximal dater in any such network has tail asymptotics which can be bounded from below and from above by a multiple of the integrated tails of service times. In general, the upper and the lower bounds do not coincide. Nevertheless, exact asymptotics can be obtained along the same lines for various special cases of networks, providing direct extensions of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We exemplify this on tandem queues (maximal daters and delays in stations) as well as on multiserver queues. © Institute of Mathematical Statistics, 2004.

AB - 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, which was first introduced to derive the stability region for stochastic networks with stationary and ergodic driving sequences, is revisited. It contains several classical queueing network models, including generalized Jackson networks, max-plus networks, polling systems, multiserver queues, and various classes of stochastic Petri nets. Our purpose is the analysis of the tails of the stationary state variables in the particular case of i.i.d. driving sequences. For this, we establish general comparison relationships between networks of this class and the GI/G/I/1/8 queue. We first use this to show that two classical results of the asymptotic theory for GI/GI/1/8 queues can be directly extended to this framework. The first one concerns the existence of moments for the stationary state variables. We establish that for all a = 1, the (a + 1)-moment condition for service times is necessary and sufficient for the existence of the a-moment for the stationary maximal dater (typically the time to empty the network when stopping further arrivals) in any network of this class. The second one is a direct extension of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We show that under subexponential assumptions for service times, the stationary maximal dater in any such network has tail asymptotics which can be bounded from below and from above by a multiple of the integrated tails of service times. In general, the upper and the lower bounds do not coincide. Nevertheless, exact asymptotics can be obtained along the same lines for various special cases of networks, providing direct extensions of Veraverbeke's tail asymptotic for the stationary waiting times in the GI/GI/1/8 queue. We exemplify this on tandem queues (maximal daters and delays in stations) as well as on multiserver queues. © Institute of Mathematical Statistics, 2004.

KW - Ergodicity

KW - Generalized jackson network

KW - Queueing network

KW - Subexponential random variable

KW - Tail asymptotics

KW - Veraverbeke's theorem

UR - http://www.scopus.com/inward/record.url?scp=10244261296&partnerID=8YFLogxK

U2 - 10.1214/105051604000000044

DO - 10.1214/105051604000000044

M3 - Article

VL - 14

SP - 612

EP - 650

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 2

ER -