Please use this identifier to cite or link to this item:
Title: The delay of open Markovian queueing networks: Uniform functional bounds, heavy traffic pole multiplicities, and stability
Authors: Humes Jr., C.
Ou, J. 
Kumar, P.R.
Keywords: Delay
Heavy traffic behavior
Open networks
Performance evaluation
Queueing networks
Scheduling policies
Issue Date: Nov-1997
Source: Humes Jr., C.,Ou, J.,Kumar, P.R. (1997-11). The delay of open Markovian queueing networks: Uniform functional bounds, heavy traffic pole multiplicities, and stability. Mathematics of Operations Research 22 (4) : 921-954. ScholarBank@NUS Repository.
Abstract: For open Markovian queueing networks, we study the functional dependence of the mean number in the system (and thus also the mean delay since it is proportional to it by Little's Theorem) on the arrival rate or load factor. We obtain linear programs (LPs) which provide bounds on the pole multiplicity M of the mean number in the system, and automatically obtain lower and upper bounds on the coefficients {C1} of the expansion ρCM/(1 - ρ)M + ρCM-1/(1 - ρ)M-1 + ⋯ + ρC1/(1 - ρ) + ρC0, where p is the load factor, which are valid for all p ∈ [0, 1), Our LPs can thus establish the stability of open networks for all arrival rates within capacity, while providing uniformly bounding functional expansions for the mean delay, valid for all arrival rates in the capacity region. The coefficients {C1} can be optimized to provide the best bound at any desired value of the load factor, while still maintaining its validity for all ρ ∈ [0, 1). While the above LPs feature L(L + 1)(M + 1)/2 variables where L is the number of buffers in the network, for balanced systems we further provide a lower dimensional LP featuring just S(S + 1)/2 variables, where S is the number of stations in the network. This bound asymptotically dominates in heavy traffic a bound obtainable from the Pollaczek-Khintchine formula, and can capture interactions between multiple bottleneck stations in heavy traffic. We also provide an explicit upper bound for all scheduling policies in acyclic networks, and for the FBFS policy in open re-entrant lines.
Source Title: Mathematics of Operations Research
ISSN: 0364765X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Jan 13, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.