Linear network coding
Like many fundamental concepts, network coding is based on a simple basic idea which was first stated in its beautiful simplicity in the the seminal paper by R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network Information Flow", (IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000). The core notion of network coding is to allow and encourage mixing of data at intermediate network nodes. A receiver sees these data packets and deduces from them the messages that were originally intended for the data sink. In contrast to traditional ways to operate a network that try to avoid collisions of data streams as much as possible, this elegant principle implies a plethora of surprising results. One of the most exciting opportunities of the approach is the use of random mixing of data streams, thus freeing up the symmetrizing properties of random coding arguments in the analysis of networks. Not only is network coding a fresh and sharp tool that has the potential to open up stagnant fundamental areas of research, but due to its cross-cutting nature it naturally suggests a unified treatment of previously segmented areas. A striking example of the type of unification that network coding makes possible is the recently found elegant and complete characterization of the capacity of multicast networks, which was possible only through the joint treatment of coding and routing.
The principle of network coding is easiest explained with an example (from Ahlswede et al.). In this example two sources having access to bits A and B at a rate of one bit per unit time have to communicate these bits to two sinks so that both sinks receive both bits per unit time. All links have a capacity of one bit per unit time. The network problem can be satisfied with the transmissions outlined in the example but cannot be satisfied with only forwarding of bits at intermediate packet nodes.