Coding and scheduling for efficient loss-resilient data broadcasting

Abstract

We examine the problem of sending data to clients over a broadcast channel in a way that minimizes the clients' expected waiting time for this data. This channel, however, is not completely reliable, and packets are occasionally lost. If items consist of k packets, k large, the loss of even a single packet can increase the expected waiting time by 167%. We propose and analyze two solutions that use coding to reduce this degradation. The resulting degradation is 67% for the first solution and less than 1% for the second. The second solution is extended to combat up to t packet losses per data item for any t≪k. This solution maintains near-optimal performance even with packet losses.

Additional details