Large deviation bounds for single class queueing networks and their calculation (Q702053)

A single class queueing network with \(n\) stations is considered which unifies discrete customer and fluid models. The network primitives (cumulative exogenous arrivals, cumulative number of served customers and cumulative routing decisions) are defined. Assuming stability a set of balance equations determining potential network behaviour (cumulative total arrivals, cumulative idle time and queue length, for each station) are derived. The upper semicontinuity of the set-valued network behavior is used to establish the large deviation principle for network behavior using large deviation principle for the network primitives. Another contribution is the development of a theory for solving corresponding variational problem. This allows to calculate large deviation rates and minimizing path using a piecewise linear approximation of network primitives and behavior. Some specific models are considered in more detail (in particular, constant service rate, exponential interarrival times, Bernoulli routing), and a numerical example is given.