Overflow management with multipart packets
We study an abstract setting, where the basic information units (called "superpackets") do not fit into a single packet, and are therefore spread over multiple packets. We assume that a superpacket is useful only if the number of its delivered packets is above a certain threshold. Our focus of attention is communication link ingresses, where large arrival bursts result in dropped packets. The algorithmic question we address is which packets to drop so as to maximize goodput. Specifically, suppose that each superpacket consists of k packets, and that a superpacket can be reconstructed if at most beta . k of its packets are lost, for some given parameter 0   0. Finally, we present some simulation results that demonstrate that the behavior of our algorithm in practice is far better than our worst-case analytical bounds. (C) 2012 Elsevier B.V. All rights reserved.
competitive analysis forward error correction packet drop packet fragmentation and reassembly randomized algorithms