Linear network coding
It has been proven that, theoretically, linear coding is enough to achieve the upper bound in multicast problems with one source.
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
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.
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.
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.
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".
Therefore, with network coding, it takes only three time slots and improves the throughput.
Random linear network coding[9] (RLNC) is a simple yet powerful encoding scheme, which in broadcast transmission schemes allows close to optimal throughput using a decentralized algorithm.
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.
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 number of original packets combined and recombined together is the generation size.
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.
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.
Therefore, each node in the network can see what coefficients were used to generate each coded packet.
After a recoding operation, the size of the appended coding coefficients does not change.
Any destination node must collect enough linearly independent coded packets to be able to reconstruct the original data.
However, an original, uncoded data packet would have appended the coding coefficients
In 2016, with Intel Core 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.
[10] Furthermore, today's algorithms can be vastly parallelizable, increasing the encoding and decoding goodput even further.
The size of each coefficient is the number of bits needed to represent one element of the Galois field.
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.
We can use this knowledge to calculate the expected number of linearly dependent packets per generation.
), 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[12] that exploit this knowledge.
Over the years, multiple researchers and companies have integrated network coding solutions into their applications.
