Online Algorithms for Scheduling Weighted Packets with Deadlines in Bounded Buffers
Fei Li · arXiv (Cornell University) · 2008
We consider online algorithms for scheduling weighted packets with deadlines in multiple sizebounded buffers. There are m ≥ 1 buffers B1, B2,..., Bm. At any time, a buffer Bi can store at most bi ∈ Z + packets. Packets arrive over time. Each packet is associated with a non-negative value, an integer deadline, and a target buffer that it can reside in. In each time step, only one pending packet is allowed to be sent. Our objective is to maximize the total value gained by delivering packets before their respective deadlines in an online manner. We call this model a single-buffer model (when m = 1) or a multi-buffer model (when m> 1). The single-buffer model generalizes the bounded-delay model (Hajek. CISS 2001. Kesselman et al. STOC 2001). Competitive analysis is employed to measure an online algorithm’s performance. For the single-buffer model, we first show that the lower bound of competitive ratios of a family of deterministic online algorithms is 2 — all previously known deterministic algorithms for the boundeddelay model fall in this category. Then we present a 3-competitive deterministic algorithm and a randomized 2.618-competitive algorithm. For the single-buffer model, no previously known algorithm has a competitive ratio better than 9.82 (Azar, Levy. SWAT 2006). The multi-buffer model has