New Linear Program Performance Bounds for Queueing Networks

被引:0
作者
J. R. Morrison
P. R. Kumar
机构
[1] University of Illinois,PhD Candidate and Graduate Student, Coordinated Science Laboratory
[2] University of Illinois,Coordinated Science Laboratory
来源
Journal of Optimization Theory and Applications | 1999年 / 100卷
关键词
Queueing networks; scheduling; stability; performance evaluation;
D O I
暂无
中图分类号
学科分类号
摘要
We obtain new linear programs for bounding the performance and proving the stability of queueing networks. They exploit the key facts that the transition probabilities of queueing networks are shift invariant on the relative interiors of faces and the cost functions of interest are linear in the state. A systematic procedure for choosing different quadratic functions on the relative interiors of faces to serve as surrogates of the differential costs in an inequality relaxation of the average cost function leads to linear program bounds. These bounds are probably better than earlier known bounds. It is also shown how to incorporate additional features, such as the presence of virtual multi-server stations to further improve the bounds. The approach also extends to provide functional bounds valid for all arrival rates.
引用
收藏
页码:575 / 597
页数:22
相关论文
共 50 条
[41]   Performance bounds and suboptimal policies for linear stochastic control via LMIs [J].
Wang, Yang ;
Boyd, Stephen .
INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL, 2011, 21 (14) :1710-1728
[42]   TRANSIENCE OF MULTICLASS QUEUEING NETWORKS VIA FLUID LIMIT MODELS [J].
Meyn, Sean P. .
ANNALS OF APPLIED PROBABILITY, 1995, 5 (04) :946-957
[43]   Using fluid models to prove stability of adversarial queueing networks [J].
Gamarnik, D .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2000, 45 (04) :741-746
[44]   Performance analysis of cognitive wireless retrial queueing networks with admission control for secondary users [J].
Kumar, B. Krishna ;
Krishnan, R. Navaneetha ;
Sankar, R. ;
Rukmani, R. .
QUALITY TECHNOLOGY AND QUANTITATIVE MANAGEMENT, 2023, 20 (05) :633-670
[45]   A two-layer queueing model to predict performance of packet transfer in broadband networks [J].
Inai, H ;
Yamakita, J .
ANNALS OF OPERATIONS RESEARCH, 1998, 79 (0) :349-371
[46]   Fundamental performance bounds for multi-performance criteria in wireless ad hoc networks [J].
Wang, Qi ;
Jaffrès-Runser, Katia ;
Sun, Yi ;
Li, Jun ;
Zhang, Jun ;
Da, Bin ;
Li, Zhong-Cheng .
Tongxin Xuebao/Journal on Communications, 2015, 36 (06)
[47]   On exponential ergodicity of multiclass queueing networks [J].
David Gamarnik ;
Sean Meyn .
Queueing Systems, 2010, 65 :109-133
[48]   UTILITY OPTIMIZATION IN CONGESTED QUEUEING NETWORKS [J].
Walton, N. S. .
JOURNAL OF APPLIED PROBABILITY, 2011, 48 (01) :68-89
[49]   Algebraic multigrid method for queueing networks [J].
Chang, QS ;
Ma, SQ ;
Lei, GY .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1999, 70 (03) :539-552
[50]   Pathwise stability of multiclass queueing networks [J].
Kan Wu ;
Yichi Shen .
Discrete Event Dynamic Systems, 2021, 31 :5-23