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