Asymptotics of stochastic networks with subexponential service times

We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as ( max,+)-linear systems. For a K-station tandem network of single server queu es with infinite buffer capacity, which is one of the simplest models in th is class, we first show that if the tail of the service time distribution o f one server, say server i(0) is an element of {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribut ion of the response time until the completion of service at server j greate r than or equal to i(0) asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i(0). Sim ilar asymptotics are given in the case when several service time distributi ons are subexponential and asymptotically tail-equivalent. This result is t hen extended to the asymptotics of general (max,+)-linear systems associate d with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cra mer case: the asymptotics only involve the excess distribution of the domin ant diagonal entry, the mean value of this entry, the intensity of the arri val process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotic s of stationary response times in a class of stochastic Petri nets called e vent graphs. This is based on the assumption that the firing times are inde pendent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue si ze processes are also considered.