Optimal FEC strategies in connections with large delay-bandwidth products

We study the problem of optimal packet coding for connections with large delay-bandwidth products. Generally, for a given loss rate, using a higher coding redundancy achieves a higher average throughput, but also incurs higher transmission costs (e.g. in terms of energy of a wireless device) and creates a higher load on the network. We define an optimal coding strategy as one that minimizes the expected cost/throughput ratio, for a connection that has a cost per unit time and a cost per transmitted packet. We present an algorithm for computing the optimal strategy and study its properties. We demonstrate that the cost/throughput ratio can be significantly better than with simple retransmission schemes, showing, in particular, that it strongly depends on the decoding buffer size, and obtain several asymptotic bounds on the optimal strategy performance for both unlimited and fixed-size decoding buffers.