Towards optimal buffer management for streams with packet dependencies

We study the problem of managing a FIFO queue where traffic is an interleaving of multiple streams that have inter-packet dependencies. This situation is common when dealing with multimedia streaming traffic, where large data frames are fragmented into smaller IP packets sent independently through the network. The main difficulty in such systems is to decide which packets to discard in case of overflow, where the system's goal is to maximize the goodput, namely, the number of frames that are successfully delivered. Previous results for this problem in the presence of bounded buffers obtained a competitive ratio which was exponential in the number of packets each data frame is decomposed into. We show both randomized and deterministic algorithms with polynomial competitive ratio in all system parameters thus exhibiting an exponential improvement over the best previously known algorithm for the problem.