首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号