Linear network coding

Network coding is a field of research founded in a series of papers from the late 1990s to the early 2000s. However, the concept of network coding, in particular linear network coding, appeared much earlier. In a 1978 paper, a scheme for improving the throughput of a two-way communication through a satellite was proposed. In this scheme, two users trying to communicate with each other transmit their data streams to a satellite, which combines the two streams by summing them modulo 2 and then broadcasts the combined stream. Each of the two users, upon receiving the broadcast stream, can decode the other stream by using the information of their own stream. Network coding is a field of research founded in a series of papers from the late 1990s to the early 2000s. However, the concept of network coding, in particular linear network coding, appeared much earlier. In a 1978 paper, a scheme for improving the throughput of a two-way communication through a satellite was proposed. In this scheme, two users trying to communicate with each other transmit their data streams to a satellite, which combines the two streams by summing them modulo 2 and then broadcasts the combined stream. Each of the two users, upon receiving the broadcast stream, can decode the other stream by using the information of their own stream. The 2000 paper gave the butterfly network example (discussed below) that illustrates how linear network coding can outperform routing. This example is equivalent to the scheme for satellite communication described above. The same paper gave an optimal coding scheme for a network with one source node and three destination nodes. This is the first example illustrating the optimality of convolutional network coding (a more general form of linear network coding) over a cyclic network. Linear network coding may be used to improve a network's throughput, efficiency and scalability, as well as resilience to attacks and eavesdropping. Instead of simply relaying the packets of information they receive, the nodes of a network take several packets and combine them together for transmission. This may be used to attain the maximum possible information flow in a network. It has been mathematically proven in theory that linear coding is enough to achieve the upper bound in multicast problems with one source. However linear coding is not sufficient in general (e.g. multisource, multisink with arbitrary demands), 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. In a linear network coding problem, a group of nodes P {displaystyle P} are involved in moving the data from S {displaystyle S} source nodes to K {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 G F ( 2 s ) {displaystyle GF(2^{s})} . Each node, p k {displaystyle p_{k}} with indegree, I n D e g ( p k ) = S {displaystyle InDeg(p_{k})=S} , generates a message X k {displaystyle X_{k}} from the linear combination of received messages { M i } i = 1 S {displaystyle {M_{i}}_{i=1}^{S}} by the relation: where the values g k i {displaystyle g_{k}^{i}} are the coefficients selected from G F ( 2 s ) {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 X k {displaystyle X_{k}} along with the coefficients, g k i {displaystyle g_{k}^{i}} , used in the k th {displaystyle k^{ ext{th}}} level, g k i {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. In reduced row echelon form, decoded packets correspond to the rows of the form e i = [ 0...010...0 ] {displaystyle e_{i}=} . A network is represented by a directed graph G = ( V , E , C ) {displaystyle {mathcal {G}}=(V,E,C)} . V {displaystyle V} is the set of nodes or vertices, E {displaystyle E} is the set of directed links (or edges), and C {displaystyle C} gives the capacity of each link of E {displaystyle E} . Let T ( s , t ) {displaystyle T(s,t)} be the maximum possible throughput from node s {displaystyle s} to node t {displaystyle t} . By the max-flow min-cut theorem, T ( s , t ) {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.