Wednesday, September 4, 2002 Volen 101, 2:00-3.00 pm
We consider a FIFO buffer with finite storage space. An arbitrary input stream of packets arrives at the buffer, but the output drain rate is bounded, so overflows may occur. To model communication with different Quality of Service levels, we assume that each packet has an intrinsic value. The buffer management task is to minimize the damage due to overflows: it decides which packets to drop so as to maximize the total value transmitted, subject to the link rate bound, the buffer space bound, and the FIFO order of sent packets. To allow comparison of algorithms, we use competitive analysis.
In this talk we explain the model, motivate the competitive analysis approach, and discuss a few recent results. In particular, we present a few results regarding the natural greedy algorithm, the optimal (off-line) algorithm, and a new algorithm that achieves a competitive ratio of 1.30 for the two value model (compared to the 1.28 lower bound for this case.)
Based on joint work with Kesselman, Lotker and Mansour (TAU), Schieber and Sviridenko (IBM).
Host: Liuba Shrira