Random Linear Network Coding for Non-Multicast and Multi-Resolution Multicast Problems

Abstract

In this dissertation, we study two network coding problems. First, we consider a class of networks that we call funnel networks. In this class of networks the total capacity of the incoming links to each intermediate node is not less than the total capacity of its outgoing links. We then prove that any feasible non-multicast problem on funnel networks is solvable by routing. This proves that a linear network coding solution exist for any non-multicast problem on funnel networks. The desirability of network coding in funnel networks may be justified by the other benefits that coding offers. However, we see that in funnel networks, the conventional random approach to linear coding fails with high probability. Hence, we provide a new random linear network coding solution for these non-multicast problems. Second, we study multicast problems in arithmetic network coding (ANC) in which, finite field arithmetic operations are replaced by real or complex arithmetic operations. A major issue in random ANC is that the condition number of the network grows quickly with the network size, hence, small errors in links can cause substantial decoding mistakes at sinks. We propose a new encoding method based on subspace coding along with a rank deficient decoding method. Our simulation results show significant improvements over conventional ANC.