Coding vs. packet retransmission over noisy channels

In many packet-based communication systems such as TCP/IP-based systems, packets are communicated over a noisy physical layer (a channel), and if a packet cannot be decoded correctly, then the transport layer retransmits it. Of course, retransmissions consume significant resources and their use should be limited. However, decreasing the likelihood of retransmission requires to encode the packets with strong channel codes in the physical layer, which also requires additional channel resources. In this paper, we study the cross-layer tradeoff between coding and packet retransmissions, and optimize over the total channel resource consumption. We show that as the packet length k increases, the redundancy r beyond the k/C channel uses implied by Shannon's channel capacity C is ⊖(√k In(k)) extra channel uses. Moreover, as k increases we must use stronger channel codes. We then apply these results to universal coding over a piecewise memoryless channel with transitions between unknown i.i.d. statistics. Our constructive universal algorithm has redundancy r = O(k ^2/3 √In(k)) using packets of polynomially increasing lengths while accounting for possible packet drops caused by transitions in the statistics.