# Survey of Network Coding Based P2P File Sharing in Large Scale Networks
## 4 Network Coding Based P2P File Sharing Systems
### Full Network Coding  
[PERSON] et al. [42] proposed Avalanche, which is the first P2P file sharing system that applies the concept of network coding for P2P content distribution networks. The main three contributions of that work are: (1) Apply a practical network coding based method which alleviates the piece selection problem across a large scale distributed system and makes better use of the available network bandwidth. (2) Provide experimental evaluation which shows that the network coding outperforms both the encoding at the source approach [43] and no coding at all, by a factor of two and three, respectively. (3) The authors show that, by using network coding, the network is very robust to churns such that peers can finish downloading even if the original seeder is left after uploading exactly one copy of the file to the network. For the evaluation, the authors implement a real system simulator \"Avalanche\" that utilizes network coding. They evaluate the performance for different network topologies, a heterogeneous number of peers, and dynamic peers' arrivals and departures. They calculate the time it takes for one peer to download the file, measuring both the average download time and the maximum. Another performance metric used is the network throughput as the total number of pieces transferred in a unit of time. In general, the results show that network coding performs well when the peers have different link rates, when there is a churn, and when incentive mechanisms [44; 45] such as Tit-for-Tat are in place to reduce free-riders and encourage cooperation. A theoretical analysis of a simplified version of Avalanche can be found in [46]. The study assumes one downloader and multiple servers in which each server contains a small part of the file. Moreover, each server does not have any knowledge of what the others are storing (i.e., stored pieces). The analysis and results show that the encoding vectors generated by network coding, for \(GF(2^{3})\) and a 1 GB file size, require an additional space of around \(10^{-4}\%\) at the sources, whereas the erasure coding [47] (\(\beta=8\)) requires 9 GB storage space at the file server. Furthermore, results show that RLNC is highly applicable for uncoordinated P2P networks by making the system behave as if the different server peers, which the downloader connects to, coordinate effectively for distributing the different pieces of the file. A similar work to [46] was proposed by [PERSON] et al. [48]. The study applied RLNC to gossip-based protocols [49], where nodes act based on their own state only without any knowledge of the contents of other nodes. The model is very similar to the rumor mongering model [50], where each node chooses a partner in a randomly uniform manner and only one piece can be transmitted per round. RLNC is compared with Random Piece Selection (RPS) and modified RPS (mRPS). In the RPS approach, the piece to be sent is selected among other pieces with equal probability, whereas the mRPS approach allows negotiation between the two connected nodes before a piece is sent. The theoretical analysis shows that the computational overhead of RNLC to recover the file is rather reasonable for \(n\leq 1000\), where \(n\) is the number of pieces. Simulation results show that RLNC always outperforms RPS and mRPS for dissemination pieces over the networks. None of the aforementioned studies [42; 46; 48] simulate the computation overhead incurred within the decoding process, which is considered an important issue of the full network coding since it is accomplished by inverting an \(n\)\(x\)\(n\) matrix which requires \(O(n^{3})\) operations. [PERSON] et al. [51] proposed Downloader Initiated Random Linear Network Coding (DRLNC) to solve the problem of generating useless coded piece from two or more useful coded pieces or whatthey called \"unlucky combination\". In DRLNC, each node keeps copies of the current coefficients matrices of its neighbors and updating information exchanged among these nodes once a new innovative piece is received.