ISSN:
1572-9443
Keywords:
stochastic networks
;
(max,+)-linear systems
;
tandem queues
;
response times
;
stationary distribution
;
tail asymptotics
;
subexponential service times
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract 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 queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i 0 ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i 0 asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i 0. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated 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 Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival 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 asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent 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 size processes are also considered.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1019176129224
Permalink
