An optimal algorithm for 2-bounded delay buffer management with lookahead

An optimal algorithm for 2-bounded delay buffer management with lookahead
复制标题

DOI：
10.1007/978-3-030-26176-4_29
复制
发表时间：
2018-06
期刊：
ArXiv
影响因子：
--
通讯作者：
Koji M. Kobayashi
Koji M. Kobayashi
中科院分区：
其他
文献类型：
--
作者：
Koji M. Kobayashi

文献摘要

相似文献

Kesselman等人提出了有界延迟缓冲区管理问题。(STOC 2001和SIAM Journal on Computing 33（3），2004）是一个在线问题，其关注于支持服务质量（QoS）的交换机的缓冲器管理。问题定义如下：数据包随时间到达缓冲区，每个数据包由释放时间、截止日期和值指定。一个算法可以在每一个整数时间内从缓冲区中发送最多一个数据包，如果在数据包的释放时间之后的截止时间内发送数据包，则可以获得其价值作为利润。这个问题的目标是最大化获得的利润。Hajek（CISS 2001）证明了，对于任意s≥ 2，确定性算法的竞争比至少为（1+ 5）/2≥ 1.618。最近，Veselektor et al. (SODA 2019）设计了一个匹配下界的在线算法。Böhm等人（ISAAC 2016和理论计算机科学，2019）引入了在线算法的前瞻能力。在时间t，该算法获得了关于在时间t+ 1到达的数据包的信息，并证明了对于s= 2，存在一个算法，该算法实现了（− 1+ 13）/2≤ 1.303的竞争比。此外，他们还证明了任何确定性算法的竞争比至少为（1+ 17）/4≥ 1.280。本文针对具有前瞻的2-有界模型，设计了一个匹配竞争比为（1+ 17）/4的算法。
The bounded delay buffer management problem, which was proposed by Kesselman et al.(STOC 2001 and SIAM Journal on Computing 33 (3), 2004), is an online problem focusing on buffer management of a switch supporting Quality of Service (QoS). The problem definition is as follows: Packets arrive to a buffer over time and each packet is specified by the release time, deadline and value. An algorithm can transmit at most one packet from the buffer at each integer time and can gain its value as the profit if transmitting the packet by its deadline after its release time. The objective of this problem is to maximize the gained profit. We say that an instance of the problem is s-bounded if for any packet, an algorithm has at most s chances to transmit it. For any s≥ 2, Hajek (CISS 2001) showed that the competitive ratio of any deterministic algorithm is at least (1+ 5)/2≥ 1.618. Recently, Veselý et al.(SODA 2019) designed an online algorithm matching the lower bound. Böhm et al.(ISAAC 2016 and Theoretical Computer Science, 2019) introduced the lookahead ability to an online algorithm. At a time t, the algorithm obtains information about packets arriving at time t+ 1, and showed that for s= 2, there is an algorithm which achieves the competitive ratio of (− 1+ 13)/2≤ 1.303. Also, they showed that the competitive ratio of any deterministic algorithm is at least (1+ 17)/4≥ 1.280. In this paper, for the 2-bounded model with lookahead, we design an algorithm with a matching competitive ratio of (1+ 17)/4.