Integrating Sparsity into Fulcrum Codes: Investigating Throughput, Complexity and Overhead

Abstract

Real-world communication systems consist of heterogeneous devices and network nodes with diverse computation capabilities. Even though it can improve the system's throughput and end-to-end delay, the use of a network code such as RLNC in communication networks may be inefficient. The coding complexity of using a single finite field along the communication path can become too computationally demanding for some nodes and eventually degrade the end-to-end performance. Fulcrum network codes employ a combination of a large and a small finite field in the encoding process and subsequently allows intermediate and end nodes to select, depending on their computation power, the field size they want to operate. However, it is still unclear how to reduce Fulcrum's decoding complexity especially for a high generation size. In this paper, we integrate sparsity at the encoding process, meaning to reduce the number of non-zero coefficients, resulting in three Fulcrum variations and conduct a thorough performance evaluation. Our simulation results show that sparsity significantly improves Fulcrum codes, increasing encoding and decoding speeds by 20x and 1.8, respectively, while maintaining a low overhead. This gains are on top of the gains provided by Fulcrum codes over RLNC.