# Survey of Network Coding Based P2P File Sharing in Large Scale Networks
## 4 Network Coding Based P2P File Sharing Systems
### Multi-Generation Mixing (MGM) and Overlapping Network Coding  
In MGM [88, 89], a file is chunked into \(g\) generations. Each of these generations contains \(p\) pieces. Additionally, among all the generations, \(m\) generations are grouped in a mixing set where \(m\leq g\). In such a scheme, in addition to the trivial coding per generation, pieces are encoded/decoded per the mixing set as well. Precisely, the first generation's pieces in the mixing set are just encoded as they are encoded in the classical generation coding, but the second generation's pieces in the same mixing set are encoded separately in their separate generation \(k\) times and then combined and encoded with either some or all the pieces of the first generation at least once, continually, the third generation is combined with the first and the second generations and so on. By this scheme, each earlier generation could be considered as a subgroup of the subsequent generations. Figure 7 shows a simple example which illustrates how MGM encoding is done where \(E_{x}\) denotes an encoded piece and \(c_{x}\) denotes a coefficient. The main advantage of this scheme is that an extra encoded piece received with a generation of a higher position index in the mixing set may assist with decoding generations of lower position indices in the same mixing set resulting in robustness to churn and a wide piece diversity. \begin{table}
\begin{tabular}{p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline \hline
**Reference** & **Approach** & **Main Findings** & **Verification Method** & **Network Topology** & **Performance Metrics** \\ \hline [PERSON] et al. [82] & Introducing and adjusting new parameters (generation size and encoding size) & - If parameters are well tuned, network coding outperform other traditional P2P schemes. Otherwise, network coding performs worse. & Simulation on NS-2 platform & Partially Meshed & - Download time. Robustness to churn. \\ \hline [PERSON] et al. [63] & Studying the effect of the generation and encoding sizes on download time and churn. & - The download time is shortened compared with Avalance and ReferenceWT 10% and 20%-30  
Similarly, in the overlapping coding scheme, generations are prepared in such a way that the same piece/s are available in more than one generation. Two generations \(g_{0}\) and \(g_{1}\) overlap if they have a non-empty intersection. For instance, \(g_{0}\cap g_{1}=p_{i}\). By this scheme, generations that are fast decoded can assist other generations in decoding when some generation's pieces are rare or missed by allowing back substitution. As a result, the number of innovative coded pieces is reduced, which in turn enhances the throughput of the network. [PERSON] et al. [90] propose a P2P Content-propagation Mechanism that utilizes Network Coding (PCMNC) based on MGM. PCMNC is similar to PPFEED, whence it uses network combination topology and selects the coefficients deterministically. On the other hand, it differs from PPFEED by applying MGM coding rather than generation coding. The authors argue that PCMNC can achieve the maximum network coding gain by suggesting optimal size of the mixing set, \(m=3\). Additionally, PCMNC is superior in performance to PPFEED by allowing more piece diversity and thus lower chances of decoding failure. Empirical evaluation shows that PCMNC can shorten the download time by 26% and 13% when compared to BitTorrent and P2P randomized-generation coding, respectively. In literature, this is the only study that has been found that applies MGM to P2P content distribution networks. [PERSON] et al. [91] propose the first overlapping coding scheme by introducing both square and diagonal grid structures. In the square grid structure, shown in Figure 8a, base generations are horizontally arranged while overlapping (supporters) generations are vertically stacked in such a way that each overlapping generation overlaps with all base generations by exactly one piece per generation.