Network-coded multihop multicast: topology and encoding complexity

In this paper, some novel results on the encoding complexity of network coding and its relation with the network topology are reported. The encoding complexity in network coding is defined as the number of nodes which have to perform coding operations in order to achieve the multicast capacity. These nodes are referred to as coding points. Known results state that the number of coding points is cubic in the mincut and quadratic in the number of receivers. In this paper, we show, through extensive simulations and through analysis of these results, that the number of coding points tends to increase linearly in the min-cut and the number of receivers in random graphs. We show that this is correlated to the length of path from the source to the receivers. To verify this, we also analyze pseudo-random graphs with a larger path length.