Online Scheduling of Packets with Deadlines in a Bounded Buffer

12:00pm, March 03, Tuesday, 2009, ST2, 430

Speaker

Fei Li
Assistant Professor
Department of Computer Science
GMU

Abstract

Motivated by the Quality-of-Service buffer management problem, we consider online scheduling of packets with deadlines in a size-bounded buffer. This model is called bounded-buffer model. Time is discrete. Packets arrive at a buffer over time. Each packet p has an integer release time r_p, a non-negative value w_p, and an integer deadline d_p. d_p specifies the time by which p should be sent. If p is transmitted by its deadline d_p, p contributes our objective its value w_p. At any time, the buffer can store no more than b packets. In each time step, at most one packet can be sent. This model is preemptive: packets already existing in the buffers can be dropped at any time before they are sent and the dropped packet cannot be delivered any more. Our objective is to maximize the total value of the packets sent by their deadlines. This bounded-buffer model generalizes the bounded-delay model proposed in (INFOCOM 00, CISS 01, STOC 01) in which the buffer's size b is assumed larger than any packet's slack time (a packet p's slack time is defined as d_p - r_p).

In SWAT 06, Azar and Levy consider a model called multi-buffer model with multiple size-bounded buffers. The lower bound of competitive ratio 1.618 (INFOCOM 00, CISS 01, Algorithmica 03) for the bounded-delay model applies to the multi-buffer model. The authors (Azar and Levy, SWAT 2006) developed a deterministic 9.82-competitive algorithm which applies to the bounded-buffer model as well.

For the bounded-buffer model, we present a deterministic 3-competitive online algorithm and a randomized 2.618-competitive online algorithm. We also show that the lower bound of competitive ratio for a broad family of deterministic algorithms is improved from 1.618 to 2.

Short Bio

Dr. Fei Li is an assistant professor at Computer Science Department of George Mason University since Fall 2007. His major research interests are online algorithms, approximation algorithms, randomized algorithms and online learning algorithms. He got his PhD in February 2008 from Columbia University, in computer science.