TY - GEN
T1 - FIFO Queueing Policies for Packets with Heterogeneous Processing
AU - Kogan, Kirill
AU - López-Ortiz, Alejandro
AU - Nikolenko, Sergey I.
AU - Sirotkin, Alexander V.
AU - Tugaryov, Denis
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2012.
PY - 2012
Y1 - 2012
N2 - We consider the problem of managing a bounded size FirstIn-First-Out (FIFO) queue buffer, where each incoming unit-sized packet requires several rounds of processing before it can be transmitted out. Our objective is to maximize the total number of successfully transmitted packets. We consider both push-out (when the policy is permitted to drop already admitted packets) and non-push-out cases. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study which experimentally validates the predicted theoretical behaviour.
AB - We consider the problem of managing a bounded size FirstIn-First-Out (FIFO) queue buffer, where each incoming unit-sized packet requires several rounds of processing before it can be transmitted out. Our objective is to maximize the total number of successfully transmitted packets. We consider both push-out (when the policy is permitted to drop already admitted packets) and non-push-out cases. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study which experimentally validates the predicted theoretical behaviour.
KW - Buffer management
KW - Competitive analysis
KW - First-in-first-out queueing
KW - Online algorithms
KW - Scheduling
KW - Switches
UR - https://www.scopus.com/pages/publications/84961225265
U2 - 10.1007/978-3-642-34862-4_18
DO - 10.1007/978-3-642-34862-4_18
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84961225265
SN - 9783642348617
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 248
EP - 260
BT - Design and Analysis of Algorithms - 1st Mediterranean Conference on Algorithms, MedAlg 2012, Proceedings
A2 - Even, Guy
A2 - Rawitz, Dror
PB - Springer Science and Business Media Deutschland GmbH
T2 - 1st Mediterranean Conference on Algorithms, MedAlg 2012
Y2 - 3 December 2012 through 5 December 2012
ER -