Geometric aspects of online packet buffering: An optimal randomized algorithm for two buffers

被引：9

作者：

Bienkowski, Marcin ^{[1
]}

Madry, Aleksander ^{[1
]}

机构：

[1] Univ Wroclaw, Inst Comp Sci, PL-50138 Wroclaw, Poland

来源：

LATIN 2008: THEORETICAL INFORMATICS | 2008年 / 4957卷

关键词：

online algorithms; network problems; packet buffering;

D O I：

10.1007/978-3-540-78773-0_22

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study packet buffering, a basic problem occurring in network switches. We construct an optimal 16/13-competitive randomized online algorithm PB for the case of two input buffers of arbitrary sizes. Our proof is based on geometrical transformations which allow to identify the set of sequences incurring extremal competitive ratios. Later we may analyze the performance of PB on these sequences only.

引用

页码：252 / 263

页数：12

共 13 条

[1]

ALBERS S, 2004, P 36 ACM S THEOR COM, V36, P35

[2]

AZAR Y., 2003, P 35 ACM S THEOR COM, P82

[3]

CHROBAK M, 1993, J ALGORITHM, V24, P406

[4]

Englert M, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P209

[5]

Englert M, 2006, LECT NOTES COMPUT SC, V4168, P352

[6] Improved competitive guarantees for QoS buffering [J].

Kesselman, A ;

Mansour, Y ;

van Stee, R .

ALGORITHMICA, 2005, 43 (1-2) :63-80

[7]

KOUTSOUPIAS E, 1995, P 26 STOC, P507

[8] ON THE SELF-SIMILAR NATURE OF ETHERNET TRAFFIC (EXTENDED VERSION) [J].

LELAND, WE ;

TAQQU, MS ;

WILLINGER, W ;

WILSON, DV .

IEEE-ACM TRANSACTIONS ON NETWORKING, 1994, 2 (01) :1-15

[9] Simple performance models of differentiated services schemes for the Internet [J].

May, M ;

Bolot, JC ;

Jean-Marie, A ;

Diot, C .

IEEE INFOCOM '99 - THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-3, PROCEEDINGS: THE FUTURE IS NOW, 1999, :1385-1394

[10] RANDOMIZED ROUNDING - A TECHNIQUE FOR PROVABLY GOOD ALGORITHMS AND ALGORITHMIC PROOFS [J].

RAGHAVAN, P ;

THOMPSON, CD .

COMBINATORICA, 1987, 7 (04) :365-374

← 1 2 →