Competitive Buffer Management with Packet Dependencies

Alex Kesselman, Boaz Patt-Shamir, and Gabriel Scalosub

Abstract:

We introduce the problem of managing a FIFO buffer of bounded space, where arriving packets have dependencies among them. Our model is motivated by the scenario where large data frames must be split into multiple packets, because maximum packet size is limited by data-link restrictions. A frame is considered useful only if sufficiently many of its constituent packets are delivered. The buffer management algorithm decides, in case of overflow, which packets to discard and which to keep in the buffer. The goal of the buffer management algorithm is to maximize throughput of useful frames. We study the complexity of the above problem for various settings in both the offline and online settings. We give upper and lower bounds on the performance of algorithms using competitive analysis.

Links:

paper, slides