Linear network coding

In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations.

Linear network coding may be used to improve a network's throughput, efficiency, and scalability, as well as reducing attacks and eavesdropping. The nodes of a network take several packets and combine for transmission. This process may be used to attain the maximum possible information flow in a network.

It has been proven that, theoretically, linear coding is enough to achieve the upper bound in multicast problems with one source. However linear coding is not sufficient in general; even for more general versions of linearity such as convolutional coding and filter-bank coding. Finding optimal coding solutions for general network problems with arbitrary demands remains an open problem.

Encoding and decoding

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 node generates new packets which are linear combinations of past received packets by multiplying them by coefficients chosen from a finite field, typically of size $GF(2^{s})$.

More formally, each node, $p_{k}$ with indegree, $InDeg(p_{k})=S$, generates a message $X_{k}$ from the linear combination of received messages $\{M_{i}\}_{i=1}^{S}$ by the formula:

$X_{k}=\sum _{i=1}^{S}g_{k}^{i}\cdot M_{i}$

Where the values $g_{k}^{i}$ are coefficients selected from $GF(2^{s})$. Since operations are computed in a finite field, the generated message is of the same length as the original messages. Each node forwards the computed value $X_{k}$ along with the coefficients, $g_{k}^{i}$, used in the $k^{\text{th}}$ level, $g_{k}^{i}$.

Sink nodes receive these network coded messages, and collect them in a matrix. The original messages can be recovered by performing Gaussian elimination on the matrix. In reduced row echelon form, decoded packets correspond to the rows of the form $e_{i}=[0...010...0]$

Background

A network is represented by a directed graph ${\mathcal {G}}=(V,E,C)$. $V$ is the set of nodes or vertices, $E$ is the set of directed links (or edges), and $C$ gives the capacity of each link of $E$. Let $T(s,t)$ be the maximum possible throughput from node $s$ to node $t$. By the max-flow min-cut theorem, $T(s,t)$ is upper bounded by the minimum capacity of all cuts, which is the sum of the capacities of the edges on a cut, between these two nodes.

Karl Menger proved that there is always a set of edge-disjoint paths achieving the upper bound in a unicast scenario, known as the max-flow min-cut theorem. Later, the Ford–Fulkerson algorithm was proposed to find such paths in polynomial time. Then, Edmonds proved in the paper "Edge-Disjoint Branchings" the upper bound in the broadcast scenario is also achievable, and proposed a polynomial time algorithm.

However, the situation in the multicast scenario is more complicated, and in fact, such an upper bound can't be reached using traditional routing ideas. Ahlswede et al. proved that it can be achieved if additional computing tasks (incoming packets are combined into one or several outgoing packets) can be done in the intermediate nodes.

The Butterfly Network

Butterfly Network.

The butterfly network is often used to illustrate how linear network coding can outperform routing. Two source nodes (at the top of the picture) have information A and B that must be transmitted to the two destination nodes (at the bottom). Each destination node wants 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 only routing were allowed, then the central link would be only able to carry A or B, but not both. Supposing 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 to both destinations simultaneously. Meanwhile, it takes four time slots in total for both destination nodes to know A and B.

Using a simple code, as shown, A and B can be transmitted to both destinations simultaneously by sending the sum of the symbols through the two relay nodes – encoding A and B using the formula "A+B". The left destination receives A and A + B, and can calculate B by subtracting the two values. Similarly, the right destination will receive B and A + B, and will also be able to determine both A and B. Therefore, with network coding, it takes only three time slots and improves the throughput.

Random Linear Network Coding

Random linear network coding (RLNC) is a simple yet powerful encoding scheme, which in broadcast transmission schemes allows close to optimal throughput using a decentralized algorithm. Nodes transmit random linear combinations of the packets they receive, with coefficients chosen randomly, with a uniform distribution from a Galois field. If the field size is sufficiently large, the probability that the receiver(s) will obtain linearly independent combinations (and therefore obtain innovative information) approaches 1. It should however be noted that, although random linear network coding has excellent throughput performance, if a receiver obtains an insufficient number of packets, it is extremely unlikely that they can recover any of the original packets. This can be addressed by sending additional random linear combinations until the receiver obtains the appropriate number of packets.

Operation and key parameters

There are three key parameters in RLNC. The first one is the generation size. In RLNC, the original data transmitted over the network is divided into packets. The source and intermediate nodes in the network can combine and recombine the set of original and coded packets. The original $M$ packets form a block, usually called a generation. The number of original packets combined and recombined together is the generation size. The second parameter is the packet size. Usually, the size of the original packets is fixed. In the case of unequally-sized packets, these can be zero-padded if they are shorter or split into multiple packets if they are longer. In practice, the packet size can be the size of the maximum transmission unit (MTU) of the underlying network protocol. For example, it can be around 1500 bytes in an Ethernet frame. The third key parameter is the Galois field used. In practice, the most commonly used Galois fields are binary extension fields. And the most commonly used sizes for the Galois fields are the binary field $GF(2)$ and the so-called binary-8 ($GF(2^{8})$). In the binary field, each element is one bit long, while in the binary-8, it is one byte long. Since the packet size is usually larger than the field size, each packet is seen as a set of elements from the Galois field (usually referred to as symbols) appended together. The packets have a fixed amount of symbols (Galois field elements), and since all the operations are performed over Galois fields, then the size of the packets does not change with subsequent linear combinations.

The sources and the intermediate nodes can combine any subset of the original and previously coded packets performing linear operations. To form a coded packet in RLNC, the original and previously coded packets are multiplied by randomly chosen coefficients and added together. Since each packet is just an appended set of Galois field elements, the operations of multiplication and addition are performed symbol-wise over each of the individual symbols of the packets, as shown in the picture from the example.

To preserve the statelessness of the code, the coding coefficients used to generate the coded packets are appended to the packets transmitted over the network. Therefore, each node in the network can see what coefficients were used to generate each coded packet. One novelty of linear network coding over traditional block codes is that it allows the recombination of previously coded packets into new and valid coded packets. This process is usually called recoding. After a recoding operation, the size of the appended coding coefficients does not change. Since all the operations are linear, the state of the recoded packet can be preserved by applying the same operations of addition and multiplication to the payload and the appended coding coefficients. In the following example, we will illustrate this process.

Any destination node must collect enough linearly independent coded packets to be able to reconstruct the original data. Each coded packet can be understood as a linear equation where the coefficients are known since they are appended to the packet. In these equations, each of the original $M$ packets is the unknown. To solve the linear system of equations, the destination needs at least $M$ linearly independent equations (packets).

Example

Coding and recoding process in linear network coding. Each packet is seen as a set of elements from a Galois field. Therefore, multiplying and adding two packets means multiplying each of its symbols by a coding coefficient chosen from the Galois field and then adding the two packets together, symbol-wise.

In the figure, we can see an example of two packets linearly combined into a new coded packet. In the example, we have two packets, namely packet $f$ and packet $e$. The generation size of our example is two. We know this because each packet has two coding coefficents ($C_{ij}$) appended. The appended coefficients can take any value from the Galois field. However, an original, uncoded data packet would have appended the coding coefficients $[0,1]$ or $[1,0]$, which means that they are constructed by a linear combination of zero times one of the packets plus one time the other packet. Any coded packet would have appended other coefficients. In our example, packet $f$ for instance has appended the coefficients $[C_{11},C_{12}]$. Since network coding can be applied at any layter of the communication protocol, these packets can have a header from the other layers, which is ignored in the network coding operations.

Now, lets assume that the network node wants to produce a new coded packet combining packet $f$ and packet $e$. In RLNC, it will randomly choose two coding coefficients, $d_{1}$ and $d_{2}$ in the example. The node will multiply each symbol of packet $f$ by $d_{1}$, and each symbol of packet $e$ by $d_{2}$. Then, it will add the results symbol-wise to produce the new coded data. It will perform the same operations of multiplication and addition to the coding coefficients of the coded packets.

Misconceptions

Linear network coding is still a relatively new subject. However, the topic has been vastly researched over the last twenty years. Nevertheless, there are still some misconceptions that are no longer valid:

Decoding computational complexity: Network coding decoders have been improved over the years. Nowadays, the algorithms are highly efficient and parallelizable. In 2016, in i5 processors with SIMD instructions enabled, the decoding goodput of network coding was 750 MB/s for a generation size of 16 packets and 250 MB/s for a generation size of 64 packets. Furthermore, today's algorithms can be vastly parallelizable, increasing the encoding and decoding goodput even further.

Transmission Overhead: It is usually thought that the transmission overhead of network coding is high due to the need to append the coding coefficients to each coded packet. In reality, this overhead is negligible in most applications. The overhead due to coding coefficients can be computed as follows. Each packet has appended $M$ coding coefficients. The size of each coefficient is the number of bits needed to represent one element of the Galois field. In practice, most network coding applications use a generation size of no more than 32 packets per generation and Galois fields of 256 elements (binary-8). With these numbers, each packet needs $M*log_{2}(s)=32$ bytes of appended overhead. If each packet is 1500 bytes long (i.e. the Ethernet MTU), then 32 bytes represent an overhead of only 2%.

Expected linearly dependent packets at different stages of transmission for a Galois field $GF(2)$ and a generation size of 16 packets. At the beginning of the transmission, the linear dependencies are minimal. It is the last packet of the transmssion that is more likely to be linearly dependent.

The expected number of linearly dependent packets per generation is practically independent of the generation size.

Overhead due to linear dependencies: Since the coding coefficients are chosen randomly in RLNC, there is a chance that some transmitted coded packets are not beneficial to the destination because they are formed using a linearly dependent combination of packets. However, this overhead is negligible in most applications. The linear dependencies depend on the Galois fields' size and are practically independent of the generation size used. We can illustrate this with the following example. Let us assume we are using a Galois field of $q$ elements and a generation size of $M$ packets. If the destination has not received any coded packet, we say it has $M$ degrees of freedom, and then almost any coded packet will be useful and innovative. In fact, only the zero-packet (only zeroes in the coding coefficients) will be non-innovative. The probability of generating the zero-packet is equal to the probability of each of the $M$ coding coefficient to be equal to the zero-element of the Galois field. I.e., the probability of a non-innovative packet is of ${\frac {1}{q^{M}}}$. With each successive innovative transmission, it can be shown that the exponent of the probability of a non innovative packet is reduced by one. When the destination has received $M-1$ innovative packets (i.e., it needs only one more packet to fully decode the data). Then the probability of a non innovative packet is of ${\frac {1}{q}}$. We can use this knowledge to calculate the expected number of linearly dependent packets per generation. In the worst-case scenario, when the Galois field used contains only two elements ($q=2$), the expected number of linearly dependent packets per generation is of 1.6 extra packets. If our generation size if of 32 or 64 packets, this represents an overhead of 5% or 2.5%, respectively. If we use the binary-8 field ($q=256$), then the expected number of linearly dependent packets per generation is practically zero. Since it is the last packets the major contributor to the overhead due to linear dependencies, there are RLNC-based protocols such as tunable sparse network coding that exploit this knowledge. These protocols introduce sparsity (zero-elements) in the coding coefficients at the beginning of the transmission to reduce the decoding complexity, and reduce the sparsity at the end of the transmission to reduce the overhead due to linear dependencies.

Wireless network coding

The broadcast nature of wireless (coupled with network topology) determines the nature of interference. Simultaneous transmissions in a wireless network typically result in all of the packets being lost (i.e., collision, see Multiple Access with Collision Avoidance for Wireless). A wireless network therefore requires a scheduler (as part of the MAC functionality) to minimize such interference. Hence any gains from network coding are strongly impacted by the underlying scheduler and will deviate from the gains seen in wired networks. Further, wireless links are typically half-duplex due to hardware constraints; i.e., a node can not simultaneously transmit and receive due to the lack of sufficient isolation between the two paths.

Although, originally network coding was proposed to be used at Network layer (see OSI model), in wireless networks, network coding has been widely used in either MAC layer or PHY layer. It has been shown that network coding when used in wireless mesh networks need attentive design and thoughts to exploit the advantages of packet mixing, else advantages cannot be realized. There are also a variety of factors influencing throughput performance, such as media access layer protocol, congestion control algorithms, etc. It is not evident how network coding can co-exist and not jeopardize what existing congestion and flow control algorithms are doing for our Internet.

Applications

A short illustration of network coding as applied to device-to-device communication. D1 and D2 are the devices, BS is the base station and M1, M2 and M3 are the messages sent.

Since linear network coding is a relatively new subject, its adoption in industries is still pending. Unlike other coding, linear network coding is not entirely applicable in a system due to its narrow specific usage scenario. Theorists are trying to connect it to real world applications. It is envisaged that network coding may be useful in the following areas:

• Owing to multi-source, multicast content-delivery nature of information-centric networking in general and Named Data Networking; in particular, the linear coding can improve over all network efficiency.
• Alternative to forward error correction and automatic repeat requests in traditional and wireless networks with packet loss, such as Coded TCP and Multi-user ARQ
• Robust and resilient to network attacks like snooping, eavesdropping, replay, or data corruption attacks.
• Digital file distribution and P2P file sharing, e.g. Avalanche filesystem from Microsoft
• Distributed storage
• Throughput increase in wireless mesh networks, e.g.: COPE, CORE, Coding-aware routing, B.A.T.M.A.N.
• Buffer and delay reduction in spatial sensor networks: Spatial buffer multiplexing
• Reduce the number of packet retransmission for a single-hop wireless multicast transmission, and hence improve network bandwidth
• Distributed file sharing
• Low-complexity video streaming to mobile device
• Device-to-device extensions

There are new methods emerging to use network coding in multiaccess systems to develop Software Defined Wire Area Networks that can offer lower delay, jitter and high robustness. The proposal mentions that the method is agnostic to underlying technologies like LTE, Ethernet, 5G.

See also

• Secret sharing protocol
• Homomorphic signatures for network coding
• Triangular network coding

References

• Fragouli, C.; Le Boudec, J. & Widmer, J. "Network coding: An instant primer" in Computer Communication Review, 2006.
• Ali Farzamnia, Sharifah K. Syed-Yusof, Norsheila Fisa "Multicasting Multiple Description Coding Using p-Cycle Network Coding", KSII Transactions on Internet and Information Systems, Vol 7, No 12, 2013.

External links

• Network Coding Homepage
• A network coding bibliography
• Raymond W. Yeung, Information Theory and Network Coding, Springer 2008, http://iest2.ie.cuhk.edu.hk/~whyeung/book2/
• Raymond W. Yeung et al., Network Coding Theory, now Publishers, 2005, http://iest2.ie.cuhk.edu.hk/~whyeung/netcode/monograph.html
• Christina Fragouli et al., Network Coding: An Instant Primer, ACM SIGCOMM 2006, http://infoscience.epfl.ch/getfile.py?mode=best&recid=58339.
• Avalanche Filesystem, http://research.microsoft.com/en-us/projects/avalanche/default.aspx
• Random Network Coding, https://web.archive.org/web/20060618083034/http://www.mit.edu/~medard/coding1.htm
• Digital Fountain Codes, http://www.icsi.berkeley.edu/~luby/
• Coding-Aware Routing, https://web.archive.org/web/20081011124616/http://arena.cse.sc.edu/papers/rocx.secon06.pdf
• MIT offers a course: Introduction to Network Coding
• Network coding: Networking's next revolution?
• Coding-aware protocol design for wireless networks: http://scholarcommons.sc.edu/etd/230/