FIFO queueing policies for packets with heterogeneous processing

DOI10.1007/978-3-642-34862-4_18MaRDI QIDQ4916048zbMATH OpenOpenAlexFDO

Authors Kirill Kogan, Sergey Nikolenko, Alexander V. Sirotkin, Denis Tugaryov, Alejandro Lopez-Ortiz

Publication date 19 April 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5443

zbMATH Keywords

buffer managementcompetitive analysisfirst-in-first-out queueingonline algorithmsschedulingswitches

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Abstract: We consider the problem of managing a bounded size First-In-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.

Recommendations

• Online scheduling FIFO policies with admission and push-out
• The impact of processing order on performance: a taxonomy of semi-FIFO policies
• The best and worst packet transmission policies
• Nearly optimal FIFO buffer management for two packet classes.
• Nearly optimal FIFO buffer management for DiffServ

Cited in

(5)

• Online buffer management for transmitting packets with processing cycles
• Admission control in shared memory switches
• The impact of processing order on performance: a taxonomy of semi-FIFO policies
• Online scheduling FIFO policies with admission and push-out
• Essential traffic parameters for shared memory switch performance

This page was built for publication: FIFO queueing policies for packets with heterogeneous processing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4916048)