Online Packet Scheduling with Bounded Delay and Lookahead
Online Packet Scheduling with Bounded Delay and Lookahead
复制标题
DOI：
10.4230/lipics.isaac.2016.21
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
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ý
我们研究了在线有界延迟的数据包调度问题（PacketScheduling），单位大小的数据包随着时间的推移到达路由器，需要通过网络链路传输。每个数据包都有两个属性：非负权重和传输截止日期。目标是最大化传输的数据包的总重量。这个问题已经在文献中得到了很好的研究，但其最佳竞争比仍然是未知的：最佳上限是1.828 [Englert和Westermann，SODA 2007]，仍然离phi的最佳下限（约1.618）相当远[Hajek，CISS 2001; Andelman等人，SODA 2003; Chin和Fung，Micromica，2003]。在具有s-边界实例的PacketScheduling的变体中，每个数据包可以在最多s个连续时隙中被调度，从其释放时间开始。phi的下界甚至适用于2-有界实例的特殊情况，并且在[Chin et al，JDA，2006]中给出了3-有界实例的phi竞争算法。改进这个结果，并解决Goldwasser提出的问题[SIGACT News，2010]，我们提出了一个4-有界实例的phi竞争算法。我们还研究了PacketScheduling的一个变体，其中在线算法具有1-lookahead的额外能力，知道在时间t哪些数据包将在时间t+1到达。对于PacketScheduling与1-lookahead限制到2-bounded实例，我们提出了一个在线算法的竞争比frac{1}{2}（sqrt{13} - 1）约1.303，我们证明了一个几乎紧的下限frac{1}{4}（1 + sqrt{17}）约1.281。
We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phi-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13} - 1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.