Network Coding
Network coding is a networking technology in which transmitted data is encoded and decoded to increase network throughput, reduce delays and make the network more robust.
Background
In communication networks, the data is transferred in the form of packets from the source to the destination(s). The intermediate nodes store the incoming packets and forward them to the next node. In 2000, a group of professors from The Chinese University of Hong Kong, Hong Kong, and Bielefeld University, Germany, published a seminal paper “Network information flow” that challenged this notion of store-and-forward. The paper introduced a notion of compute-and-forward and referred it to as network coding.
Why use it?
Network coding is a very general technique, and it provides various benefits in terms of enhanced data rate, reduced latency, and increased bandwidth efficiency. Consider the
- Point-to-point networks: In the case of point-to-point networks, network coding helps in improving bandwidth efficiency. This is because the receiver does not have to send an acknowledgment for each packet. The feedback is hence simplified and bandwidth is saved.
- Point-to-multipoint networks: In these networks, network coding can provide tremendous throughput gains and reduced latency. Network coded data is broadcasted from the transmitter to all the receivers. If any receiver misses one of the packets, then the transmitter does not have to resend that individual packet for one receiver (the missed packet if retransmitted will be useful for only one receiver). The transmitter can keep sending the new network coded packet that is useful for all the receivers.
- Multihop networks: In these networks, the intermediate nodes can recode and regenerate the information without getting any feedback from the source. Hence the throughput is improved. Consider an example. The source performs network coding on 80 original packets and creates and transmits 100 network-coded packets to the subsequent node. But due to packet losses, only 90 packets are received. These 90 packets are good enough for the subsequent node and using these received network-coded packets, the subsequent node can regenerate packets to create 100 network-coded packets. In this way, transmission carries on from one hop to the next until it reaches the destination. Only the destination has to perform decoding. The intermediate nodes only perform recoding (which has low complexity and can be performed even if partial data is received).
Apart from communication networks, network coding can be used for cloud storage applications. Instead of storing copies of data at multiple data centers, network-coded data can be stored. This provides benefits in terms of security, privacy, fault-tolerance, efficient storage, and reduced repair bandwidth in terms of cloud failures.
Network coding can also be used for smart city applications, the internet of things (IoT), industrial internet of things (IIoT). Network coding technology can be integrated seamlessly with these applications. In all these applications, network coding provides unique benefits concerning increased throughput, reliability, and bandwidth saving.
Further Read on Network Coding
In network-coded communication, the intermediate node can compute functions of the incoming packets and send those network coded packets (instead of copies of packets) to the next node. The next node can then do the recoding or apply network coding again. That is, the next node computes the functions of the received (network coded) packets and transmits those to its subsequent node. This process is repeated until the destination nodes receive the network coded packets. The destination can recover the original information as soon as it obtains sufficient “evidence” of the original packets through the functions of the received packets. The function can simply be to compute the sum (i.e., XOR) of packets or some linear combination of the packets. In the case where linear combinations of, let’s assume, k incoming packets are computed at the intermediate node and sent to the next node, the destination can recover the original information as soon as it has k linearly independent combinations of the k original packets.
This new idea is called network coding. It has been shown by research that sending functions (e.g., linear combinations) of packets instead of original packets can help not only to improve the data rates and bandwidth efficiency but also to reduce the communication latency.
In the above, we introduced network coding considering a multihop network where an intermediate node computes functions (e.g., linear combinations) of incoming packets and transmits those to the next node. Network coding, however, is quite general, and the multihop network is not the only scenario where network coding can be applied. Network coding can be applied in single-hop communication networks as well. In such networks, functions (e.g., linear combinations) of the original packets can be computed by the source itself and transmitted to one destination (point-to-point communications) or multiple destinations (multicast or broadcast communications).
In the figure below, we show the fundamental principle of network coding. At the transmitter, network coding is applied to the k original packets to obtain n network-coded packets where n>k. We may assume that n linear combinations of the k packets are generated to obtain the n network-coded packets. These network-coded packets are then transmitted via the channel to the receiver. The channel, however, is lossy, and as a result, some of the packets are lost. The received network-coded packets are then given to the decoder. As soon as the receiver obtains k or greater than k linearly independent network-coded packets, the receiver can perform network decoding to decode the k original packets.