# Survey of Network Coding Based P2P File Sharing in Large Scale Networks
## 4 Network Coding Based P2P File Sharing Systems
### Sparse Network Coding
\begin{table}
\begin{tabular}{p{113.8 pt} p{56.9 pt} p{56.9 pt} p{56.9 pt} p{56.9 pt} p{56.9 pt}} \hline \hline
**Reference** & **Approach** & **Main Findings** & **Verification Method** & **Network Topology** & **Performance Metrics** \\ \hline \multirow{3}{*}{[PERSON] et al. [42]} & Utilizing RNLC on P2P file sharing networks. & - RLNC alleviates the pieces selection problem and churns, and accelerates the downloading process. & Numerical Simulation & Single overlay, and Multi-clusters overlay. & - Download time. - Throughput. \\ \hline \multirow{3}{*}{[PERSON] et al. [46]} & Providing extensively theoretical analysis for P2P RNLC-based method. & - RLNC overhead is about \(10^{-4}\) \% of the file size. & Numerical 10\({}^{-1}\)\% of the file size. & Numerical Simulation & Star. & - Probability of completion. - Probability of contents availability. \\ \hline \multirow{3}{*}{[PERSON] et al. [48]} & Proposing RLNC-based approach for P2P gossip protocols. & - Computational overhead of RNLC to reconstruct the file is rather reasonable for \(n\leq 1000\). & Numerical Simulation. & Complete Mesh. & - Download time. \\ \hline \multirow{3}{*}{[PERSON] et al. [51]} & Proposing DRLNC to mitigate unlucky combination problem. & - Unlucky combination problem. & Numerical simulation. & Mesh. & - Rounds to complete download. \\ \hline \multirow{3}{*}{[PERSON] [52]} & Analysis avalanche using graph theory. & - Avalanche can achieve the theoretical lower bound of the file downloading time. & No experimental work. & Mesh. & — \\ \hline \multirow{3}{*}{[PERSON] et al. [13]} & Avalanche is studied by modeling a simple star topology network. & - No advantage of network coding over traditional routing. & No experimental work. & Star. & — \\ \hline \multirow{3}{*}{[PERSON] et al. [54]} & Justifying the feasibility of RNLNC on P2P systems by realistic application layer implementation. & - RNLC performs worse than any conventional store and forward P2P file sharing system. & High performance C++ implementation. & Mesh & - Average downloading/ decoding complexity. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Full network coding approaches and their characteristics. [PERSON] et al. [57] proposed a \"Pairecoding\" scheme. In Pairecoding, each coded piece, \(P_{(i,j)}\), is a linear combination of only two original pieces \((X_{i},X_{j})\) such that the decoding overhead remains quite reasonable. Using this approach, the coded piece given by (9) has half of the information about the original pieces \(X_{i}\) and \(X_{j}\) that it is generated from. If the coefficients are linear independent, two different coded pieces generated from the same original piece contain the original data of the original piece:  
\[P_{(i,j)}=C_{i}X_{i}+C_{j}X_{j} \tag{9}\]  
The authors claim that Pairecoding relatively decodes pieces as good as BitTorrent, and, for some scenarios, it shares pieces as good as full network coding. For the sake of the decoding speed comparison between Pairecoding and BitTorrent, a file of \(n\) pieces (\(n=30\)) is distributed by a seeder to one downloader. For BitTorrent, the seeder selects at random one piece for sharing, while, in Pairecoding, the seeder randomly selects two pieces and then shares a linear combination of them. Experimental results show that, through a file sharing process, BitTorrent can decode (i.e., collects non-redundant pieces) better than Pairecoding in the first quarter of the process, but, as time progresses, Pairecoding outperforms BitTorrent. Pairecoding can start decoding in the best case after receiving two encoded pieces. For the content availability metric, Pairecoding falls in the middle between Avalanche and BitTorrent. Nonetheless, in some scenarios, Pairecoding provides content availability as Avalanche but with very low probability. Fixed-Pairecoding [58; 59] is a variation of Pairecoding in which each encoded piece as shown in (10) is a combination of two adjacent original pieces. Fixing the choice of the two original pieces yields a faster decoding.