In this paper we study the problem of increasing the decoding success probability of random linear fountain code over GF (2) for small packet lengths used in delay-intolerant applications such as multimedia streaming. Such code over GF (2) are attractive as they have lower decoding complexity than codes over larger field size, but suffer from high transmission redundancy. In our proposed coding scheme we construct a codeword which is not a linear combination of any γ codewords previously transmitted to mitigate such transmission redundancy. We then note the observation that the probability of receiving a linearly dependent codeword is highest when the receiver has received k − 1 linearly independent codewords. We propose using the BlockACK frame so that the codeword received after k − 1 linearly independent codeword is always linearly independent, this reduces the expected redundancy by a factor of three.
Sorensen have proposed to use overlapping generations to minimize the decoding complexity @cite_10 . The general idea of performing encoding on overlapping generation is to divide the @math input packets into smaller sub-generations, each sub-generations having smaller number of input packets. By reducing the value of @math the decoding complexity is also minimized, however this approach adversely affect the network throughput @cite_2 , and the use of overlapping sub-generations has been shown to improve throughput. In a multicast network this approach may lead to redundant codewords being received by some receivers, as few receivers are satisfied before others.
@cite_10 @cite_2
2006799289 2100134469
Traditionally, the idea of overlapping generations in network coding research has focused on reducing the complexity of decoding large data files while maintaining the delay performance expected of a system that combines all data packets. However, the effort for encoding and decoding individual generations can still be quite high compared to other sparse coding approaches. This paper focuses on an inherently different approach that combines (i) sparsely coded generations configured on-the- fly based on (ii) controllable and infrequent feedback that allows the system to remove some original packets from the pool of packets to be mixed in the linear combinations. The latter is key to maintain a high impact of the coded packets received during the entire process while maintaining very sparsely coded generations. Interestingly, our proposed approach naturally bridges the idea of overlapping generations with that of tunable sparse network coding, thus providing the system with a seamless and adaptive strategy to balance complexity and delay performance. We analyze two families of strategies focused on these ideas. We also compare them to other standard approaches both in terms of delay performance and complexity as well as providing measurements in commercial devices to support our conclusions. Our results show that a judicious choice of the overlapping of the generations provides close-to-optimal delay performance, while reducing the decoding complexity by up to an order of magnitude with respect to other schemes. 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.