Validity of heavy traffic steady-state approximations in generalized Jackson networks

被引:90
作者
Gamarnik, D
Zeevi, A
机构
[1] MIT, Sloan Sch Management, Cambridge, MA 02139 USA
[2] Columbia Univ, Grad Sch Business, New York, NY 10027 USA
关键词
diffusion approximations; stationary distribution; weak convergence; Lyapunov functions; Markov processes; reflected Brownian motion;
D O I
10.1214/105051605000000638
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
We consider a single class open queueing network, also known as a generalized Jackson network (GJN). A classical result in heavy-traffic theory asserts that the sequence of normalized queue length processes of the GJN converge weakly to a reflected Brownian motion (RBM) in the orthant. as, the traffic intensity approaches unity. However, barring simple instances, it is still not known whether the stationary distribution of RBM provides a valid approximation for the steady-state of the original network, In this paper we resolve this open problem by proving that the re-scaled stationary distribution of the GJN converges to the stationary distribution of the RBM, thus Validating a so-called "interchange-of-limits" for this class of networks, Our method of proof involves a combination of Lyapunov function techniques. strong approximations and tail probability bounds that yield tightness of the sequence of stationary distributions of the GJN.
引用
收藏
页码:56 / 90
页数:35
相关论文
共 39 条
[1]   Moments and tails in monotone-separable stochastic networks [J].
Baccelli, F ;
Foss, S .
ANNALS OF APPLIED PROBABILITY, 2004, 14 (02) :612-650
[2]  
Bertsimas D, 2001, ANN APPL PROBAB, V11, P1384
[3]   Optimization of multiclass queueing networks with changeover times via the achievable region approach:: Part I, the single-station case [J].
Bertsimas, D ;
Niño-Mora, J .
MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (02) :306-330
[4]   Optimization of multiclass queueing networks with changeover times via the achievable region approach:: Part II, the multi-station case [J].
Bertsimas, D ;
Niño-Mora, J .
MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (02) :331-361
[5]   OPTIMIZATION OF MULTICLASS QUEUEING NETWORKS: POLYHEDRAL AND NONLINEAR CHARACTERIZATIONS OF ACHIEVABLE PERFORMANCE [J].
Bertsimas, Dimitris ;
Paschalidis, Ioannis Ch. ;
Tsitsiklis, John N. .
ANNALS OF APPLIED PROBABILITY, 1994, 4 (01) :43-75
[6]  
Billingsley P., 1999, CONVERGENCE PROBABIL
[7]   DISCRETE FLOW NETWORKS - BOTTLENECK ANALYSIS AND FLUID APPROXIMATIONS [J].
CHEN, H ;
MANDELBAUM, A .
MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (02) :408-446
[8]  
CHEN H, 1991, ANN PROBAB, V19, P1463
[9]  
Chen H., 2001, Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization
[10]   INVARIANCE-PRINCIPLES FOR RENEWAL PROCESSES [J].
CSORGO, M ;
HORVATH, L ;
STEINEBACH, J .
ANNALS OF PROBABILITY, 1987, 15 (04) :1441-1460