## 2 Background
### Random Linear Network Coding  
To fully leverage the potential benefits of the network coding technique in a practical system, the encoding and decoding operations must be fast enough (_i.e._, they must not act as bottlenecks to the transmission process). The execution time of the network coding is primarily dependent upon the coding method used. We employ the random linear coding [27] in our Cell BE implementations, as it is widely used and known to be asymptotically optimal in any network format. A given segment of data, such as a single file, will be divided into a specific number of blocks, referred to as _packets_, prior to being transferred over a network, as shown in Figure 3. In this figure, \(\textbf{p}_{k}\) represents \(k^{th}\) block and \(\textbf{c}_{i}\) is a coded data, which is a linear combination of blocks. In other words, \(\textbf{c}_{i}=\sum_{k=1}^{n}e_{i,k}\textbf{p}_{k}\) where \(n\) is the number of blocks and the coefficient \(\textbf{e}_{i}\) is an element vector that is selected at random from a finite field, \(F\). The coded data \(\textbf{c}_{i}\) is combined with the coefficient vector; \([e_{i,1},\ldots,e_{i,n}]\) is stored in the header and broadcast to the destination. A transfer unit, comprised of the coded data and coefficient block, is presented in Figure 4.  
While the packets are being routed, the packets are re-encoded within nodes along the pathways to their destinations before being passed to downstream nodes. When a packet arrives at its destination node, it is stored in local memory so the coded data can be decoded and recovered to the original data set \([p_{1},\ldots,p_{n}]^{T}\). To decode encoded data, the destination node must have all \(n\) transfer units, with  
Figure 2: Advantage of using network coding. linearly independent coefficient vectors. Suppose a destination node has collected \(n\) transfer units and that the coefficient vector, original data, and coded data set are represented by \(E^{T}=[\textbf{e}_{1}^{T},\ldots,\textbf{e}_{n}^{T}]\), \(C^{T}=[\textbf{e}_{1}^{T},\ldots,\textbf{e}_{n}^{T}]\), \(P^{T}=[\textbf{p}_{1}^{T},\ldots,\textbf{p}_{n}^{T}]\), respectively, where superscript \(T\) implies a matrix transpose operation. Since we multiply the matrices with formula \(C=EP\) to encode original data, we can rearrange this to obtain \(P=E^{-1}C\), allowing us to recover the original data by multiplying the inverse matrix of \(E\) with \(C\). To perform the decoding operation, the coefficient matrix, E, must be an invertible matrix, thus all coefficient vectors, \(\textbf{e}_{i}\), should be linearly independent of each other. Using a variant of _Gaussian Elimination_, we can obtain matrix \(P\). When the destination receives transfer units, it constructs coefficient and coded data matrices, as shown in Figure 4, to prepare for the process of Gaussian elimination. Typical Gaussian elimination or LU decomposition for the purpose of decoding at the destination requires that all \(n\) transfer units first be collected, before starting the process. However, we can use progressive decoding instead of multiplying by the inverse matrix. With the progressive decoding [28], we do not need to wait until all transfer units to be received. Although all units may not have been received, the decoding process can still be initiated, and continue to progress as each unit is made available. In addition, the progressive network coding can be processed regardless of the arrival order of the coded packet. It is due to the fact that changing of the row order does not affect the decoding results as it uses linearly independent coefficient matrix. Let \(n\) represent the number of blocks and \(m\) represent the block size. The computation complexity of standard Gaussian Elimination is \(O(n^{3})\). However in the decoding process associated with network  
Figure 4: Data received at the receiving node. Figure 3: Data encoding at the sending node.