On the Distribution of Sojourn Times in Tandem Queues

The paper studies the (end-to-end) waiting and sojourn times in tandem queues with general arrivals and light-tailed service times. It is shown that the tails of the corresponding distributions are subject to polynomial-exponential upper bounds, whereby the degrees of the polynomials depend on both the number of bottleneck queues and the 'light-tailedness' of the service times. Closed-form bounds constructed for a two-queue tandem with exponential service times are shown to be numerically sharp, improve upon alternative large-deviations bounds by many orders of magnitude, and recover the exact results in the case of Poisson arrivals.