QUEUEING NETWORKS IN HEAVY TRAFFIC
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.
Stanford UniversityDepartment of Operations Research
Stanford, CA United States 94305
- Reiman, M I
- Publication Date: 1977-9-17
- Pagination: 106 p.
- TRT Terms: Network analysis (Planning); Queuing theory; Railroad facility operations; Routing; Transportation planning
- Uncontrolled Terms: Line capacity
- Subject Areas: Data and Information Technology; Railroads;
- Accession Number: 00175390
- Record Type: Publication
- Source Agency: National Technical Information Service
- Report/Paper Numbers: TR-76 Tech Rpt.
- Files: TRIS
- Created Date: Jul 19 1978 12:00AM