How Helpful is Network Coding?

With network coding, intermediate nodes between the source and the receivers of an end-to-end communication session are not only capable of relaying and replicating data messages, but also of coding incoming messages to produce coded outgoing ones. Research in network coding has attracted substantial interests from both theoretical and practical perspectives. In this talk, we present our recent work on both theoretical investigations and practical implementations of network coding, with a focus on its benefits and advantages in practical scenarios.

From a theoretical perspective, we present efficient solutions to the problem of achieving optimal throughput in undirected data networks. Although previous approaches lead to solving NP-complete problems, we show that, facilitated by network coding, computing the strategies to achieve optimal end-to-end throughput can be performed in polynomial time. We show that in most topologies, applying network coding may not improve the achievable optimal throughput; rather, it facilitates the design of more efficient algorithms to achieve such optimality.

From a practical perspective, recent studies have shown that randomized network coding is beneficial for peer-to-peer content distribution, since it eliminates the need for content reconciliation, and is highly resilient to peer failures. Is randomized network coding helpful in practice? We present our recent and ongoing work on a high-performance C++ implementation of randomized network coding at the application layer. We present our observations based on a series of experiments, and draw conclusions from a range of scenarios.