Online Scheduling of Similarly Ordered Packets

Lukasz Jez

Institute of Computer Science,University of Wroclaw

Abstract

(joint work with F. Li, J. Sethuraman, C. Stein) In packet scheduling problem, packets with weights and deadlines arrive at a network switch over time, and the goal is to send those packets on the outgoing link while maximizing the total weight of the packets that are sent before their deadlines. As this simple problem turns out rather hard, numerous restricted variants have been studied. Instances with similarly ordered packets (aka packets with agreeable deadlines) are one such variant, studied for example in the paper by Chrobak et al. that gave the first non-trivial deterministic algorithm, i.e. one with competitive ratio smaller than 2.

In 2005 Li et al. gave a phi-competitive algorithm for this variant. Its analysis introduce a novel technique: instead of employing a potential function or a charging scheme directly, the analysis aims at judiciously modifying the adversary's buffer content (set of pending packets) so that it always equals the algorithm's buffer. The algorithm is known to be optimal as similarly ordered instances properly contain 2-bounded instances, and yet its analysis is strikingly simple. We present a simplified deterministic algorithm with the same competitive ratio, and show how these ideas extend to randomized algorithms. As a result we obtain a 4/3-competitive randomized algorithm. This one, however, is not known to be optimal, as the respective lower bound (for 2-bounded instances) is only 5/4.