The delay of open Markovian queueing networks: Uniform functional bounds, heavy traffic pole multiplicities, and stability

摘要

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 {C-i} of the expansion rho C-M/(1 - rho)(M) + rho CM-1/(1 - rho)(M-1) + ... + rho C-1/(1 - rho) + rho C-0, where rho is the load factor, which are valid for all rho is an element of [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 {C-i} can be optimized to provide the best bound at any desired value of the load factor, while still maintaining its validity for all rho is an element of [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.