2015 | OriginalPaper | Chapter
Buffer Management for Packets with Processing Times
Authors : Yossi Azar, Oren Gilon
Published in: Algorithms - ESA 2015
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We discuss the well known job scheduling problem with release times and deadlines, alongside an extended model - buffer management for packets with processing requirements. For job scheduling, an
$\Omega(\sqrt{\frac{\log{\kappa}}{\log{\log{\kappa}}}})$
lower bound for any randomized preemptive algorithm was shown by Irani and Canetti (1995), where
κ
is the the maximum job duration or the maximum job value (the minimum is assumed to be 1). The proof of this well-known result is fairly elaborate and involved. In contrast, we show a significantly improved lower bound of Ω(log
κ
) using a simple proof. Our result matches the easy upper bound and closes a gap which was supposedly open for 20 years.
We also discuss an interesting extension of job scheduling (for tight jobs). We discuss the problem of handling a FIFO buffer of a limited capacity, where packets arrive over time and may be preempted. Most of the work in buffer management considers the case where each packet has unit processing requirement. We consider a model where packets require some number of processing cycles before they can be transmitted. We aim to maximize the value of transmitted packets. We show an
$\Omega(\frac{\log{\kappa}}{\log{\log{\kappa}}})$
lower bound on the competitive ratio of randomized algorithms in this setting. We also present bounds for several special cases. For packets with unit values we also show a
ϕ
≈ 1.618 lower bound on the competitive ratio of deterministic algorithms, and a 2-competitive algorithm for this problem. For the case of packets with constant densities we present a 4-competitive algorithm.