To reduce computational complexity and delay in randomized network coded content distribution, and for some other practical reasons, coding is not performed simultaneously over all content blocks, but over much smaller, possibly overlapping subsets of these blocks, known as generations. A penalty of this strategy is throughput reduction. To analyze the throughput loss, we model coding over generations with random generation scheduling as a coupon collector's brotherhood problem. This model enables us to derive the expected number of coded packets needed for successful decoding of the entire content as well as the probability of decoding failure (the latter only when generations do not overlap) and further, to quantify the tradeoff between computational complexity and throughput. Interestingly, with a moderate increase in the generation size, throughput quickly approaches link capacity. Overlaps between generations can further improve throughput substantially for relatively small generation sizes.
@cite_9: Network coding is known to improve the throughput and the resilience to losses in most network scenarios. In a practical network scenario, however, the accurate modeling of the traffic is often too complex and or infeasible. The goal is thus to design codes that perform close to the capacity of any network (with arbitrary traffic) efficiently. In this context, random linear network codes are known to be capacity-achieving while requiring a decoding complexity quadratic in the message length. Chunked Codes (CC) were proposed by to improve the computational efficiency of random codes by partitioning the message into a number of non-overlapping chunks. CC can also be capacity-achieving but have a lower encoding decoding complexity at the expense of slower convergence to the capacity. In this paper, we propose and analyze a generalized version of CC called Overlapped Chunked Codes (OCC) in which chunks are allowed to overlap.1 Our theoretical analysis and simulation results show that compared to CC, OCC can achieve the capacity with a faster speed while maintaining almost the same advantage in computational efficiency.
@cite_14: 
@cite_3: This paper presents a novel approach to network coding for distribution of large files. Instead of the usual approach of splitting packets into disjoint classes (also known as generations) we propose the use of overlapping classes. The overlapping allows the decoder to alternate between Gaussian elimination and back substitution, simultaneously boosting the performance and reducing the decoding complexity. Our approach can be seen as a combination of fountain coding and network coding. Simulation results are presented that demonstrate the promise of our approach.
The performance of codes with random scheduling of disjoint generations was first theoretically analyzed in @cite_14 by , who referred to them as chunked codes . Chunked codes allow convenient encoding at intermediate nodes, and are readily suitable for peer-to-peer file dissemination. In @cite_14 , the authors used an adversarial schedule as the network model and characterized the code performance under certain restrictions on the chunk(generation) size when the length of the information to be encoded tends to infinity. Coding with overlapping generations was first studied in @cite_3 and @cite_9 with the goal to improve throughput. Reference @cite_9 studied a head-to-toe'' overlapping scheme in which only contiguous generations overlap for a given number of information packets, and analyzed its asymptotic performance over a line network when the length of information goes to infinity. Another overlapping scheme with a grid structure was proposed in @cite_3 , analyzed for short lengths (e.g., @math generations) and simulated for practical lengths. When properly designed, these codes show improved performance over codes with disjoint generations. In our work, we offer an analysis of coding over disjoint and overlapping generations for finite but practically long information lengths.