Tails for (max, plus) recursions under subexponentiality

Abstract

We study the stationary solution of a (max, plus)-linear recursion. Under subexponentiality assumptions on the input to the recursion, we obtain the tail asymptotics of certain (max, plus)-linear functionals of this solution. (Max, plus)-linear recursions arise from FIFO queueing networks; more specifically, from stochastic event graphs. In the event graph setting, two special cases of our results are of particular interest and have already been investigated in the literature. First, the functional may correspond to the end-to-end sojourn time of a customer. Second, for two queues in tandem, the functional may correspond to the sojourn time in the second queue. Our results allow for more general networks, which we illustrate by studying the tail asymptotics of the resequencing delay due to multi-path routing. © Springer Science + Business Media, LLC 2006.