|
|||||
|
|
Online Scheduling FIFO Policies with Admission and Push-Out |
|
| Authors: | Kirill Kogan Alejandro López-Ortiz Sergey I. Nikolenko Alexander V. Sirotkin |
| Affiliation: | 1. IMDEA Networks Institute, Madrid, Spain 2. School of Computer Science, University of Waterloo, Waterloo, Canada 3. Laboratory for Internet Studies, National Research University Higher School of Economics, St. Petersburg, Russian Federation 4. Laboratory of Mathematical Logic, Steklov Mathematical Institute at St. Petersburg, St. Petersburg, Russian Federation 5. International Laboratory for Applied Network Research, National Research University Higher School of Economics, Moscow, Russia 6. Theoretical and Interdisciplinary Computer Science Laboratory, St. Petersburg Institute for Informatics and Automation of the RAS, St. Petersburg, Russia |
| 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 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |