Competitive buffer management with packet dependencies

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 c...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2013-06, Vol.489-490, p.75-87
Main Authors: Kesselman, Alex, Patt-Shamir, Boaz, Scalosub, Gabriel
Format: Article
Language:English
Subjects:
Buffer management
Competitive analysis
Online algorithms
Packet dependencies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. This problem has a variety of applications, e.g., Internet video streaming, where video frames are segmented and encapsulated in IP packets sent over the Internet. We study the complexity of the above problem in both the offline and online settings. We give upper and lower bounds on the performance of algorithms using competitive analysis.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2013.04.007