# Survey of Network Coding Based P2P File Sharing in Large Scale Networks
## 2 BitTorrent-Like Systems and Network Coding Background
### Detailed Network Coding Tutorial for P2P File Sharing Systems  
Since most of the published papers provide only high level information about implementation of network coding, we provide a thorough tutorial of network coding implementation. The use of network coding requires the use of Galois field (GF) and its operations as well as basics of linear algebra. A GF is a field with finite number of elements. For instance, \(GF(2^{3})\) is a field whose elements are eight and each element is presented by 3-bits. The \(GF(2^{3})\) elements are generated using the following polynomial:  
\[A(x)=a_{2}x^{2}+a_{1}x+a_{0} \tag{1}\]  
Table 1 shows the elements (polynomials) of \(GF(2^{3})\) generated by eqrefeq:1 and their corresponding binary presentation. Figure 3: Butterfly network using network coding [20]. The following four operations over any \(GF(2^{m})\) field are defined:  
* Addition and Subtraction: The sum of two elements is computed according to (2): \[C(x)=A(x)+B(x)=\sum_{i=0}^{m-1}c_{i}x^{i},c_{i}\equiv a_{i}+b_{i}\;mod\;2.\] (2) Addition and subtraction modulo 2 are the same. Moreover, addition modulo 2 is simply equivalent to bitwise XOR. * Multiplication: two elements of \(GF(2^{m})\) are multiplied using the standard polynomial multiplication rule. However, if the product polynomial has a degree higher than \(m-1\), then it has to be reduced. Irreducible polynomials, which are roughly comparable to prime numbers in such that their only factors are 1 and the polynomial itself, are used for the modulo reduction. Let \(P(x)\) be an irreducible polynomial over \(GF(2^{m})\); then, the multiplication of two elements is done as in (3): \[C(x)=A(x)\cdot B(x)\;mod\;P(x).\] (3) To find the product of \(6(x^{2}+x)\) and \(7(x^{2}+x+1)\) in \(GF(2^{3})\), we begin by doing normal polynomial multiplication: \(C(x)=(x^{2}+x)*(x^{2}+x+1)=x^{4}+x\). Since \(x^{4}+x\
otin\;GF(2^{3})\), the irreducible polynomial \(P(x)=x^{3}+x+1\) is needed and thus we calculate \(C(x)=(x^{4}+x)\;mod\;(x^{3}+x+1)=x^{2}\in\;GF(2^{3})\). * Inversion: Every Element (except 0) in \(GF(2^{m})\) has an inverse. The inverse \(A^{-1}\) of a nonzero element \(A\in\;GF(2^{m})\) is defined as in (4): \[A^{-1}(x)\cdot A(x)\equiv 1\;mod\;P(x)\] (4) For example, in \(GF(2^{3})\) and \(P(x)=x^{3}+x+1\), \((x)\) is the inverse of \((x^{2}+1)\) since \(x*(x^{2}+1)\;mod\;(x^{3}+x+1)=1\). To use network coding for sharing a file within a P2P network, it should be started by decomposing the whole file into equal pieces. For example, each piece size is 16 KB, 32 KB, or 64 KB. Furthermore, each piece is divided into equal smaller units called blocks. For example, each block size is 4-bits or 8-bits as shown in Figure 4. Subsequently, network coding is applied per block, but a piece is still the transmission unit. Since \(GF(2^{8})\) is always recommended for real implementation scenarios, an 8-bits block is widely used. \begin{table}
\begin{tabular}{c c} \hline
**Binary** & \(GF(2^{3})\) \\ \hline
000 & 0 \\
001 & 1 \\
010 & \(x\) \\
011 & \(x+1\) \\
100 & \(x^{2}\) \\
101 & \(x^{2}+1\) \\
110 & \(x^{2}+x\) \\
111 & \(x^{2}+x+1\) \\ \hline \end{tabular}
\end{table} 
Table 1: \(GF(2^{3})\) elements presentation. The following example demonstrates how this process works using \(GF(2^{3})\). Assume, without loss of generality, that we want to share a 12-bits file using BitTorrent. Assume that the 12-bits file binary representation is (10001110110):  
* 1 st Step: The seeder decomposes the file into two 6-bit pieces (100011, 110110). * 2 nd Step: For encoding over \(GF(2^{3})\), we should decompose each piece into two 3-bits blocks: \(P_{1}(100,\,011)\), and \(P_{2}(110,\,110)\). * 3 rd Step: Interpret each block as \(GF(2^{3})\) element (using (1)); then, we have \(P_{1}(x^{2},x+1)\), and \(P_{2}(x^{2}+x,x^{2}+x)\). * 4 th Step: Since we have two plain pieces, we need two coded pieces. Randomly draw coefficients from \(GF(2^{3})\) and multiply them by the blocks.