Queueing Networks in Heavy Traffic.
Abstract
The principle purpose of this report is to state and prove a limit theorem which justifies a diffusion approximation for general queueing networks. The K-dimensional vector queue length process is investigated for the network. Because of the general form assumed for the interarrival and service distributions, the process has no special structure such as the Markov property. In this generality, the network has proven to be intractable, hence the desire for an approximation. It is possible to define a traffic intensity for each station in the network. Heavy traffic is said to hold when all stations have traffic intensities close to unity. Mathematically, heavy traffic is interpreted through consideration of a sequence of queueing networks indexed (say) by n, each with its own parameters, defined in such a way that the traffic intensity of each station approaches unity as n approaches infinity. The state space of the limit process is the K-dimensional non-negative orthant. On the interior of its state space the process behaves as a multidimensional Brownian motion with an easily computed drift vector and covariance matrix. At each boundary surface the process reflects instantaneously. The directions of reflection are given by a simple expression involving only the routing matrix. After proving that the limit process is a diffusion, its generator is computed, justifying the above description.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 17, 1977
- Accession Number
- ADA049594
Entities
People
- Martin Ira Reiman
Organizations
- Stanford University