Online Scheduling FIFO Policies with Admission and Push-Out

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...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2016-02, Vol.58 (2), p.322-344
Main Authors: Kogan, Kirill, López-Ortiz, Alejandro, Nikolenko, Sergey I., Sirotkin, Alexander V.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Buffers
Competition
Computer Science
Computer simulation
FIFO
Job shops
Laboratories
Optimization
Packet transmission
Policies
Queuing
Scheduling
Studies
Theory of Computation
Traffic congestion
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 a policy is permitted to drop already admitted packets) and non-push-out cases. We provide worst-case guarantees for the throughput performance of our algorithms, proving both lower and upper bounds on their competitive ratio against the optimal algorithm, and conduct a comprehensive simulation study that experimentally validates predicted theoretical behavior.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-015-9626-4