Paper Info
Title
Geometric aspects of online packet buffering: an optimal randomized algorithm for two buffers
Abstract
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.
Year
DOI
Venue
2008
10.1007/978-3-540-78773-0_22
LATIN
Keywords
Field
DocType
optimal randomized algorithm,13-competitive randomized online algorithm,basic problem,geometric aspect,geometrical transformation,packet buffering,arbitrary size,extremal competitive ratio,input buffer,online packet buffering,competitive ratio,online algorithm,online algorithms,randomized algorithm
Randomized algorithm,Online algorithm,Computer science,Network packet,Network switch,Theoretical computer science,Competitive analysis
Conference
Volume
ISSN
ISBN
4957
0302-9743
3-540-78772-0
Citations 
PageRank 
References 
5
0.43
13
Authors
2
Name
Order
Citations
PageRank
Marcin Bienkowski125427.18
Aleksander Mądry296145.38