Packet Scheduling
Packet Scheduling
复制标题
数据包调度
DOI：
10.1145/3471469.3471481
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
C. Sedikides
中科院分区：
文献类型：
--
作者：
Alison P. Lenton;Letitia Slabu;Martin Bruder;C. Sedikides
带截止期的在线分组调度是缓冲区管理的基本模型之一。最近，作者与Chrobak，Jez和Sgall（SODA 2019）一起设计了一个最优的竞争算法，其中1.618是黄金比例。在本专栏中，我们概述了导致我们开发该算法的思想，并概述了其分析中的概念。我们还突出了开放的问题，在数据包调度。
Online packet scheduling with deadlines is one of the fundamental models in buffer management. Recently, the author together with Chrobak, Jez, and Sgall (SODA 2019) designed an optimal ϕ-competitive algorithm for this problem, where ϕ ≈1.618 is the golden ratio. In this column, we sketch ideas that led us to the development of this algorithm and outline the concepts in its analysis. We also highlight open questions in packet scheduling.