Poly-Exp Bounds in Tandem Queues

arXiv2304.10162MaRDI QIDQ6433718FDOQ6433718

Authors: Florin Ciucu, Sima Mehri 

Publication date: 20 April 2023

Abstract: When the arrival processes are Poisson, queueing networks are well-understood in terms of the product-form structure of the number of jobs $N_i$ at the individual queues; much less is known about the waiting time $W$ across the whole network. In turn, for non-Poisson arrivals, little is known about either $N_i$'s or $W$. This paper considers a tandem network ${\displaystyle }$GI/G/1 ightarrow cdot/G/1 ightarrowdots ightarrowcdot/G/1${\displaystyle }$ with general arrivals and light-tailed service times. The main result is that the tail $P(W>x)$ has a polynomial-exponential (Poly-Exp) structure by constructing upper bounds of the form ${\displaystyle }$(a_{I}x^{I}+dots+a_1x+a_0)e^{- heta x}~.${\displaystyle }$ The degree $I$ of the polynomial depends on the number of bottleneck queues, their positions in the tandem, and also on the `light-tailedness' of the service times. The bounds hold in non-asymptotic regimes (i.e., for extit{finite} $x$), are shown to be sharp, and improve upon alternative results based on large deviations by (many) orders of magnitude. The overall technique is also particularly robust as it immediately extends, for instance, to non-renewal arrivals.

This page was built for publication: Poly-Exp Bounds in Tandem Queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433718)