Network coding delay: A brute-force analysis

Understanding the delay behavior of network coding with a fixed number of receivers, small field sizes and a limited number of encoded symbols is a key step towards its applicability in real-time communication systems with stringent delay constraints. Previous results are typically asymptotic in nature and focus mainly on the average delay performance. Seeking to characterize the complete delay distribution of random linear network coding, we present a brute-force methodology that is feasible for up to four receivers, limited field and generation sizes. The key idea is to fix the pattern of packet erasures and to try out all possible encodings for various system and channel parameters. Our findings, which are valid for both decoding delay and ordered-delivery delay, can be used to optimize network coding protocols with respect not only to their average but also to their worst-case performance.