On the Tradeoffs of Implementing Randomized Network Coding in Multicast Networks

Randomized network coding (RNC) has greatly reduced complexity of implementing network coding in large-scale, heterogeneous networks. Two tradeoffs are studied here that further reduce the overhead in applying RNC. The first examines how RNC performance varies with a node´s randomizing capabilities. Specifically, a limited randomized network coding (L-RNC) scheme - in which intermediate nodes perform randomized encoding based on only limited number of random coefficients - is proposed and its performance bounds are analyzed. L-RNC is applicable to networks in which nodes have either limited computation/storage capacity or have ambiguity about downstream edge connectivity (e.g., as in ad hoc sensor networks). A second tradeoff studied here examines the relationship between reliability and capacity gains of RNC, i.e., how the outage probability of RNC relates to the transmission rate at source node. This tradeoff reveals that significant reductions in outage probability are possible when the source deliberately transmit at (only slightly) below network capacity. It therefore provides an effective alternative to improve RNC feasibility when the size of finite field is fixed.