Instability of FIFO at arbitrarily low rates in the adversarial queueing model

被引：27

作者：

Bhattacharjee, R ^{[1
]}

Goel, A

Lotker, Z

机构：

[1] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA

[2] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA

[3] Tel Aviv Univ, Dept Elect Engn, IL-69978 Tel Aviv, Israel

来源：

SIAM JOURNAL ON COMPUTING | 2004年 / 34卷 / 02期

关键词：

FIFO; stability; adversarial queueing model;

D O I：

10.1137/S0097539703426805

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the stability of the commonly used packet forwarding protocol, FIFO (first in first out), in the adversarial queueing model. We prove that FIFO can become unstable, i.e., lead to unbounded buffer-occupancies and queueing delays, at arbitrarily low injection rates. In order to demonstrate instability at rate r, we use a network of size (O) over tildeO(1/r).

引用

页码：318 / 332

页数：15

共 31 条

[1]

Aiello W, 2003, SIAM PROC S, P771

[2]

Aiello W., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P359, DOI 10.1145/276698.276788

[3] 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

[4] Source routing and scheduling in packet networks [J].

Andrews, M ;

Fernández, A ;

Goel, A ;

Zhang, L .

42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2001, :168-177

[5]

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

[6]

[Anonymous], IMA VOL MATH ITS APP

[7] Delay jitter bounds and packet scale rate guarantee for expedited forwarding [J].

Bennett, JCR ;

Benson, L ;

Charny, A ;

Courtney, WF ;

Le Boudec, JY .

IEEE-ACM TRANSACTIONS ON NETWORKING, 2002, 10 (04) :529-540

[8]

BHATTACHARJEE R, 2002, 02776 U SO CAL

[9] Adversarial queuing theory [J].

Borodin, A ;

Kleinberg, J ;

Raghavan, P ;

Sudan, M ;

Williamson, DP .

JOURNAL OF THE ACM, 2001, 48 (01) :13-38

[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 →