Using fluid models to prove stability of adversarial queueing networks

被引：18

作者：

Gamarnik, D ^{[1
]}

机构：

[1] IBM Corp, Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA

来源：

IEEE TRANSACTIONS ON AUTOMATIC CONTROL | 2000年 / 45卷 / 04期

关键词：

packet routing; queueing networks; stability;

D O I：

10.1109/9.847114

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A digital communication network can be modeled as an adversarial queueing network. An adversarial queueing network is defined to be stable if the number of packets stays bounded over time. A central question is to determine which adversarial queueing networks are stable under every work-conserving packet routing policy. Our main result is that stability of an adversarial queueing network is implied by stability of an associated fluid queueing network.

引用

页码：741 / 746

页数：6

共 22 条

[1] Universal stability results for greedy contention-resolution protocols [J].

Andrews, M ;

Awerbuch, B ;

Fernandez, A ;

Kleinberg, J ;

Leighton, T ;

Liu, ZY .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :380-389

[2]

[Anonymous], 1992, PROBLEMY PEREDACHI I

[3] Stability conditions for multiclass fluid queueing networks [J].

Bertsimas, D ;

Gamarnik, D ;

Tsitsiklis, JN .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1996, 41 (11) :1618-1631

[4]

BORODIN A, 1996, P 28 ACM S THEOR COM

[5] Convergence to equilibria for fluid models of FIFO queueing networks [J].

Bramson, M .

QUEUEING SYSTEMS, 1996, 22 (1-2) :5-45

[6] Stability of multiclass queueing networks under FIFO service discipline [J].

Chen, H ;

Zhang, HQ .

MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (03) :691-725

[7] FLUID APPROXIMATIONS AND STABILITY OF MULTICLASS QUEUEING NETWORKS: WORK-CONSERVING DISCIPLINES [J].

Chen, Hong .

ANNALS OF APPLIED PROBABILITY, 1995, 5 (03) :637-665

[8] A CALCULUS FOR NETWORK DELAY .2. NETWORK ANALYSIS [J].

CRUZ, RL .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1991, 37 (01) :132-141

[9]

Dai JG, 1996, ANN APPL PROBAB, V6, P751

[10] ON POSITIVE HARRIS RECURRENCE OF MULTICLASS QUEUEING NETWORKS: A UNIFIED APPROACH VIA FLUID LIMIT MODELS [J].

Dai, J. G. .

ANNALS OF APPLIED PROBABILITY, 1995, 5 (01) :49-77

← 1 2 3 →