Abstract:

We consider a scenario where large data frames are broken into a few packets and
transmitted over the network. Our focus is on a bottleneck router: the model
assumes that in each time step, a set of packets (a burst) arrives, from which
only one packet can be served, and all other packets are lost. A data frame is
considered useful only if none of its constituent packets is lost, and otherwise
it is worthless. We abstract the problem as a new type of online set packing, 
present a randomized distributed 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
frame. We also present refined bounds that depend on the uniformity of these
parameters.

Joint work with Emek, Halldorsson, Mansour, Patt-Shamir and Radhakrishnan.