The Limitation of Random Network Coding
Source: Cornell University
It is already known that in multicast (single source, multiple sinks) network, random linear network coding can achieve the maximum flow upper bound. In this paper, the authors investigate how random linear network coding behaves in general multi-source multi-sink case, where each sink has different demands, and they characterize all achievable rate of random linear network coding by a simple maximum flow condition. In an information transmission network, allowing coding operation at intermediate nodes will increase the capacity of the network than simply relaying the packets. In multicast (single-source, multiple sinks) scenario, Ahlswede, Cai, Li, and Yeung proved that the maximum flow upper bound can be achieved by network coding in this paper.