Approximately optimal assignment for unequal loss protection

Abstract

This paper describes an algorithm that achieves an approximately optimal assignment of forward error correction to progressive data within the unequal loss protection framework. It first finds the optimal assignment under convex hull and fractional bit allocation assumptions. It then relaxes those constraints to find an assignment that approximates the global optimum. The algorithm has a running time of O(hNlogN) where h is the number of points on the convex hull of the source's utility-cost curve and N is the number of packets transmitted.