Linear network coding

In a linear network coding problem, a group of nodes ${\displaystyle P}$ are involved in moving the data from ${\displaystyle S}$ source nodes to ${\displaystyle K}$ sink nodes. Each node generates new packets which are linear combinations of earlier received packets, multiplying them by coefficients chosen from a finite field, typically of size ${\displaystyle GF(2^{s})}$.

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

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

where the values ${\displaystyle g_{k}^{i}}$ are the coefficients selected from ${\displaystyle GF(2^{s})}$. Note that, 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 ${\displaystyle X_{k}}$ along with the coefficients, ${\displaystyle g_{k}^{i}}$, used in the ${\displaystyle k^{\text{th}}}$ level, ${\displaystyle 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.[5] In reduced row echelon form, decoded packets correspond to the rows of the form ${\displaystyle e_{i}=[0...010...0]}$.

A network is represented by a directed graph ${\displaystyle {\mathcal {G}}=(V,E,C)}$. ${\displaystyle V}$ is the set of nodes or vertices, ${\displaystyle E}$ is the set of directed links (or edges), and ${\displaystyle C}$ gives the capacity of each link of ${\displaystyle E}$. Let ${\displaystyle T(s,t)}$ be the maximum possible throughput from node ${\displaystyle s}$ to node ${\displaystyle t}$. By the max-flow min-cut theorem, ${\displaystyle 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.[2]

Butterfly Network.

The butterfly network [2] 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), 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 only routing were allowed, then the central link would be only 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, A and B can be transmitted 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 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.

Random linear network coding [6] 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 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.

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.[7] 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.[8]

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

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 to real world applications.[9] In fact, it was found that BitTorrent approach is far superior than network coding.

It is envisaged that network coding is 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. [10]
• Alternative to forward error correction and ARQ in traditional and wireless networks with packet loss. e.g.: Coded TCP,[11] Multi-user ARQ[12]
• Robust and resilient to network attacks like snooping, eavesdropping, replay or data corruption attacks.[13][14]
• Digital file distribution and P2P file sharing. e.g.: Avalanche from Microsoft
• Distributed storage.[15][16][17]
• Throughput increase in wireless mesh networks. e.g. : COPE,[18] CORE,[19] Coding-aware routing,[20][21] B.A.T.M.A.N.[22]
• Buffer and Delay reduction in spatial sensor networks: Spatial buffer multiplexing [23]
• Reduce the number of packet retransmission for a single-hop wireless multicast transmission, and hence improve network bandwidth.[24]
• Distributed file sharing [25]
• Low-complexity video streaming to mobile devices [26]
• Device-to-Device (D2D) extensions[27][28][29][30][31]

There are new methods emerging to use Network Coding in multiaccess systems to develop Software Defined Wire Area Networks (SD-WANs) that can offer lower delay, jitter and high robustness. [32]The proposal mentions that the method is agnostic to underlying technologies like LTE, Ethernet, 5G.[33]

Since this area is relatively new and the mathematical treatment of this subject is currently limited to a handful of people, network coding has yet found its way to commercialization in products and services. It is unclear at this stage if this subject will prevail, or cease as a good mathematical exercise.[34]

Researchers have clearly pointed out that special care is needed to explore how network coding can co-exist with existing routing, media access, congestion, flow control algorithms and TCP protocol. If not, network coding may not offer much advantages and can increase computation complexity and memory requirements.[35]

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

• 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.

• 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/