Competitive Scheduling and Overflow Management of Multipart Packets
Abstract: The following basic situation often occurs in communication systems. There is a data unit that needs to be sent, but it is too big for the available communication primitive. It is therefore broken into a number of packets, which are sent separately. Since communication may be unreliable, some packets may not arrive at the receiver. (In the network layer, losses are primarily due to buffer overflows.) We assume that the basic data unit, called ``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.
We present a simple online distributed randomized algorithm and a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximal burst size and the maximal number of packets per superpacket. We also present refined bounds that depend on the uniformity of these parameters. Our results extend to a more general redundancy model and to the case where the stream of packets arrives at a router with multiple bounded-capacity outgoing links. We also analyze the effect of buffers on the goodput under the assumption of fixed burst size, and show that in this case, when the buffer is not too small, our algorithm can attain, with high probability, $(1-\epsilon)$ good put utilization for any $\epsilon>0$. Finally, we present simulation results that demonstrate that the behavior of our algorithm in practice is far better than our worst-case analytical bounds.