April 12, 2016, 10:15 a.m.
[COG seminar]. Pavel Veselý, Martin Böhm: Online Packet Scheduling With and Without Lookahead
Tuesday 10:15-12:00, room 140.
Abstract. Our talk will focus on Online Packet Scheduling (also known as "buffer management in QoS switches" or "online throughput maximization with unit jobs"), which is a basic variant of online scheduling with motivation arising from network router design. In this problem, unit sized packets arrive in an online fashion, each with an associated deadline and weight. The packets can be kept in memory indefinitely, but can be sent only before their deadline. Only one packet can be transmitted in each timeslot. The goal is to maximize weight of the transmitted packets. The problem can also be parametrized by setting an upper bound k on the length of the "time window" between arrival time and deadline — this variant is called k-Bounded Online Packet Scheduling.
In the first part of the talk, we will describe the current state of the art of the problem for the general and parametrized cases. In particular, we will state the best-known lower bound and the tight algorithm for the 3-bounded instances. In the second part of the talk, we will discuss our recent results on the problem. We consider a natural resource augmentation which enables an online algorithm to know what packets arrive in the next time step. We call this problem Online Packet Scheduling with Lookahead. We show a lower bound of 1.280 using 2-bounded instances and a nearly tight algorithm for 2-bounded instances which is 1.303-competitive. We also list several open problems. The second part of the talk is a joint work with Marek Chrobak, Łukasz Jeż, Fei Li and Jiří Sgall.