Composite Extension Finite Fields for Low Overhead Network Coding: Telescopic Codes

Although Network Coding (NC) has been proven to increase throughput and reliability in communication networks, its adoption is typically hindered by the additional complexity it introduces at various nodes in the network and the overhead to signal the coding coefficients associated with each coded packet. This work advocates the use of multiple composite extension finite fields to address these challenges. The key of our approach is to design a series of finite fields where increasingly larger fields are based on a previous smaller field. For example, the design of a field with 256 elements F2222 is based on polynomial arithmetic over a field with 16 elements F222, in turn based on a field with 4 elements F22. We propose a technique to modify standard Random Linear Network Coding (RLNC) to utilize a set of these fields instead of a single field and analyze the performance. The results show that total overhead is reduced due to reduced size of the coding vector, while maintaining low linear dependency between coded packets. The overhead can in some cases be reduced to less than one-fifth compared to standard RLNC and importantly the ability to recode is preserved.