Network coding

From Wikipedia, the free encyclopedia

Network coding is a field of information theory and coding theory and is a method of attaining maximum information flow in a network.

1 General principle
2 Linear network coding
- 2.1 Theory
3 Example
4 History
5 Applications
6 External links

[edit] 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 (2000, Ahlswede et al.) that this max-flow value is achievable, but that routing is not capable of achieving it.

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.

[edit] Linear network coding

Although the max-flow was shown to be achievable, it was shown using a random code. In 2003, it was shown (by Li, Yeung, and Cai) 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.

In 2004, it was shown (by Dougherty, Freiling, and Zeger) that linear network codes are not sufficient in general. 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 insufficiency of linear codes applies to multiple unicast networks.

[edit] Theory

In a Linear Network coding problem a group of nodes $P$ are involved in moving the data from $S$ source nodes to $K$ sink nodes. Each nodes generates a new packet, which is a linear combination of the earlier received packets on the link, by coefficients in the finite field.

A message generated so $X k$ is related to the received messages $M i$ by the relation
$X_k = \sum_{i=1}^{S}g_k^i.M_i$ . Each node forwards the computed value $X k$ along with the all the coefficients used in the $k t h$ level, $g_k^i$ .

The values $g_k^i$ are the coefficients from the Galois field $G F (2 s)$ . Since the operations are computed in the finite field, the result of the operation is also of the same length, as the size of each vector $M$ .

Each node produces a similar output, as computed above. This yields a linear problem of the type $X = G M$ ,
where with the knowledge of the $X, G$ we need to compute $M$ . Each of the receivers in $K$ , try to solve this linear equation, and for which at least $N \ge S$ packets must be received. The received packets are continually used in the Gaussian elimination method to reduce $G$ matrix into the row-echelon form. Finally the resulting values of $X = G e c h e l o n M$
are solved to obtain $M$ .

[edit] Example

Butterfly Network.

In the butterfly network, there are two sources (at the top of the picture), each having knowledge of some value A and B. There are two destination nodes (at the bottom), which each want to know both A and B. Each edge can carry only a single value (we can think of an edge transmitting a bit in each time slot).

If we only used routing, then the central line would be able to carry A or B, but not both. Suppose we send A through the center; then the left destination would receive A twice and not know B at all. Sending B poses a similar problem for the right destination. We say that routing is insufficient because no routing scheme can transmit both A and B simultaneously to both destinations.

Using a simple code, as shown, we do get both A and B to both destinations simultaneously by sending the sum of the symbols through the center (in other words, we encode A and B using the formula "A+B"). The left destination receives A and A+B, and can find B by subtracting the two values. This is a linear code because the encoding and decoding schemes are linear operations.

[edit] History

The fundamental concept of network coding was introduced for satellite communication networks in a paper by R. W. Yeung and Z. Zhang, "Distributed Source Coding for Satellite Communications" (IEEE Transactions on Information Theory, IT-45, pp. 1111-1120. 1999). The concept was fully developed in a subsequent 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), where the term `network coding' was coined. In this paper, the advantage of network coding over routing, the traditional way of operating a network, was pointed out for the first time by means of a very simple example known as the butterfly network.

[edit] Applications

Network coding is seen to be useful in the following areas:

Alternative to FEC and ARQ in traditional networks.
Robust and resilient to network attacks like snooping, eavesdropping or replay attacks.
Digital file distribution and P2P file sharing. eg: Avalanche from Microsoft
Bidirectional low energy transmission in wireless sensor networks.
Many-to-Many broadcast network capacity augmentation.