Network coding

-------------------------------------------------
Network coding

Jump to: navigation, search
Network coding is a field of information theory and coding theory and is a method of attaining maximum information flow in a network. Contents[hide] * 1 General principle * 2 Linear network coding * 2.1 Theory * 3 Example * 3.1 Throughput * 4 Coding-aware Routing * 5 History * 6 Applications * 7 Network Coding and P2P * 8 References * 9 External links |
-------------------------------------------------
General principle
A network is a directed graph, where the edges represent pathways for information. Using the max-flow min-cut theorem, one can calculate the maximum amount of information that can be pushed through this network between two nodes. It was shown that this max-flow value is achievable, but that routing is not capable of achieving it.[1]
The core notion of network coding is to allow mixing of data at intermediate network nodes. A receiver sees these data packets and deduces from them the messages that were originally intended for that data sink.
In the butterfly example below, it is easy to see that no routing scheme can achieve the maximum flow, but that by using a simple coding scheme, the full flow can be attained.
-------------------------------------------------
Linear network coding
Although the max-flow was shown to be achievable, it was shown using a random code. In 2003, it was shown that linear codes will achieve the max-flow in single-source multicast (every destination node receives all the source information) networks, provided the alphabet size is large enough.[2]
In 2004, it was shown that linear network codes are not sufficient in general.[3] An example in the paper is not solvable using any linear code over any field size or in any dimension; further, it is not asymptotically linear nor is it linearly solvable using convolutional codes or time-sharing methods. They also showed that the