Adversarial queuing theory

被引：145

作者：

Borodin, A ^{[2
]}

Kleinberg, J

Raghavan, P

Sudan, M

Williamson, DP

机构：

[1] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA

[2] Univ Toronto, Dept Comp Sci, Toronto, ON M5S 3G4, Canada

[3] MIT, Comp Sci Lab, Cambridge, MA 02139 USA

[4] IBM Corp, Almaden Res Ctr, San Jose, CA 95120 USA

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

来源：

JOURNAL OF THE ACM | 2001年 / 48卷 / 01期

关键词：

packet routing; stability; scheduling protocols;

D O I：

10.1145/363647.363659

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.

引用

页码：13 / 38

页数：26

共 52 条

[1]

AIELLO W, 1988, P 30 ANN ACM S THEOR, P359

[2]

Andrews M, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P448

[3] Universal-stability results and performance bounds for greedy contention-resolution protocols [J].

Andrews, M ;

Awerbuch, B ;

Fernández, A ;

Leighton, T ;

Liu, ZY ;

Kleinberg, J .

JOURNAL OF THE ACM, 2001, 48 (01) :39-69

[4]

Andrews M, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P440

[5]

[Anonymous], 1979, Reversibility and Stochastic Networks

[6]

Awerbuch B., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P487, DOI 10.1145/195058.195238

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

Bertsimas, D ;

Gamarnik, D ;

Tsitsiklis, JN .

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

[8]

Borodin A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P376, DOI 10.1145/237814.237984

[9]

BORODIN A, 2001, P 12 ANN ACM SIAM S

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

Bramson, M .

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

← 1 2 3 4 5 6 →