Bounded delay packet scheduling in a bounded buffer |
| |
Authors: | Stanley P.Y. Fung |
| |
Affiliation: | Department of Computer Science, University of Leicester, Leicester LE1 7RH, United Kingdom |
| |
Abstract: | We study buffer management in QoS-enabled network switches in the bounded delay model where each packet has a weight and a deadline. We consider the more realistic situation where the switch has a finite buffer size. A 9.82-competitive algorithm is known for the case of multiple buffers. Recently, for the single buffer case, a 3-competitive deterministic algorithm and a 2.618-competitive randomized algorithm were found. We give a simple deterministic 2-competitive algorithm for the single buffer case. |
| |
Keywords: | Online algorithms Scheduling Buffer management |
本文献已被 ScienceDirect 等数据库收录! |