A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines
复制标题
一种具有截止日期的数据包调度竞争算法
DOI：
10.1137/21m1469753
复制
发表时间：
2022
影响因子：
1.6
通讯作者：
Sgall, Jiří
中科院分区：
文献类型：
--
作者：
Veselý, Pavel;Chrobak, Marek;Jeż, Łukasz;Sgall, Jiří
在有截止日期的在线数据包调度问题（简称）中，目标是调度在网络交换机中随时间到达并且需要通过链路发送的数据包的传输。每个包都有一个截止日期，代表它的紧急程度，还有一个非负的权重，代表它的优先级。在任何时隙中只能传输一个数据包，因此如果系统过载，一些数据包将不可避免地错过截止日期而被丢弃。在此场景中，自然的目标是计算一个传输调度，使成功传输的数据包的总权重最大化。这个问题本质上是在线的，在不知道未来数据包到达的情况下做出调度决策。自2001年以来，确定在线算法的最优竞争比是一个核心问题，即一个调度的最优总权重（由离线算法计算）与一个（确定性）在线算法计算的调度权重之间的最坏情况之比。我们通过提出一个竞争性的在线算法来解决这个开放问题（黄金分割率在哪里），匹配先前建立的下界。
In theonline packet scheduling problem with deadlines(, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a nonnegative weight, which represents its priority. Only one packet can be transmitted in any time slot, so if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets that are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerningthat has been a subject of intensive study since 2001 is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a-competitive online algorithm for(whereis the golden ratio), matching the previously established lower bound.
登录
查看更多内容
QoS交换机中的排队策略分析
DOI：
--
发表时间：
2004
期刊：
J. Algorithms
影响因子：
--
作者：
An Zhu
通讯作者：
An Zhu
从动态队列中收集加权项目
影响因子：
1.1
作者：
Marcin Bienkowski;M. Chrobak;C. Dürr;M. Hurand;Artur Jeż;Lukasz Jez;Grzegorz Stachowiak
通讯作者：
Grzegorz Stachowiak
DOI：
10.4230/lipics.isaac.2016.21
发表时间：
2016-06
期刊：
ArXiv
影响因子：
--
作者：
Martin Böhm;M. Chrobak;Lukasz Jez;Fei Li;J. Sgall;P. Veselý
通讯作者：
Martin Böhm;M. Chrobak;Lukasz Jez;Fei Li;J. Sgall;P. Veselý
数据包调度
DOI：
10.1145/3471469.3471481
发表时间：
2021
期刊：
ACM SIGACT News
影响因子：
--
作者：
Alison P. Lenton;Letitia Slabu;Martin Bruder;C. Sedikides
通讯作者：
C. Sedikides
考虑抑制数据包可改善服务质量交换机中的缓冲区管理
DOI：
--
发表时间：
2012
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Matthias Englert;Matthias Westermann
通讯作者：
Matthias Westermann