# 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 the diagonal grid structure, shown in Figure 8b, supporter generations are diagonally stacked with an angle \(\theta\). The authors aim to mix the benefits of network coding and fountain codes [92,93] such as Luby Transform (LT) code [94] and Raptor [95]. Indeed, a fountain decoder is a propagative decoder that has the feature of achieving a small overhead with a low decoding complexity by allowing back substitution. The authors mainly try to answer the following question: is it possible to use true network coding and at the same time enjoy a fountain-like decoder? A practical simulation shows improved performance over independent generation coding in terms of decoding complexity overhead trade-off. Exactly, the results show that for fixed expected complexity, the overlapped generations codes can reduce the overhead by up to 70%. However, the theoretical analysis is done only for short lengths equal to four groups. [PERSON] et al. [96] propose head-to-toe overlapping that allows a generation of \(k\) pieces to be overlapped with its following neighbor in at least one piece and at most \(k-1\) pieces. The overlapping is allowed between neighboring generations only. More theoretical analysis than [91] is done by measuring the asymptotic performance over a line network, in which a single source is connected to a single sink via intermediate nodes such that each node is connected to exactly one sender and one receiver forming a unidirectional-line network that contains \(n\) nodes and \(n-1\) links. Performance comparison of full codes, disjointed generations codes, and overlapped generation codes is conducted. Results show that the overlapping network coding can exploit the network bandwidth optimally  
Figure 8: (a) square grid overlapping structure, (b) diagonal grid overlapping structure. by reducing the network overhead by nearly 60% and 29% for a line network of lengths 1 and 2, respectively. In addition, they suggest using overlapped chunked codes for multimedia transmission as shown in [97]. [PERSON] et al. [98] propose random annex codes which allow generations to be overlapped by attaching to each generation a random annex of pieces selected randomly from other generations such that the annex size is always smaller than the base generation size. Theoretical analysis and simulations show that the optimal overlap (annex) size that increases the throughput and decreases the decoding latency is around the half of the generation size. Moreover, results show that the proposed scheme outperforms the head-to-toe scheme slightly in terms of throughput and the probability of decoding failure. Both schemes outperform the disjoint generations' coding scheme. [PERSON] et al. [99] propose an expander graph based overlapped generation codes (EOC) which models generations as vertices and overlapping as edges between the vertices. EOC allows each generation to overlap with another generation in one distinct piece only. The authors suggest that the number, \(d\), of generations that overlap vary from a minimum of 3 to a maximum that does not exceed the generation size. Figure 9 shows an example of EOC graph with \(d=3\) and 5 generations, each of seven pieces (four distinct and three overlapped), i.e., generation one's (\(G_{1}\)) pieces are \(P_{1},P_{5},P_{6},P_{8},P_{9},P_{1}0,P_{1}1\). Simulation results show that EOC can achieve throughput rate of 93% while independent generations codes can achieve maximum rate of 73% when the generation size = 32 and \(GF\) size = 16. Additionally, the EOC receiver can decode all the pieces and reconstruct the file faster than random annex and head-to-toe schemes. The extra ratio of encoded pieces needed for decoding all the generations are \(\leq\) 10%, 20%, and 40% for EOC, random annex, and head-to-toe, respectively. [PERSON] et al. [100] proposed overlapping structure similar to EOC in which allowing overlapping between two generations in one piece only.