Retransmissions serve as the basic building block that communication protocols use to achieve reliable data transfer. Until recently, the number of retransmissions was thought to follow a geometric (light-tailed) distribution. However, recent work shows that when the distribution of the packet sizes have infinite support, retransmission-based protocols may result in heavy-tailed delays and possibly zero throughput even when the aforementioned distribution is light-tailed. In reality, however, packet sizes are often bounded by the maximum transmission unit (MTU), and thus the aforementioned result merits a deeper investigation. To that end, in this paper, we allow the distribution of the packet size$L$to have finite support. Under mild conditions, we show that the transmission duration distribution exhibits a transition from a power-law main body to an exponential tail. The timescale to observe the power-law main body is roughly equal to the average transmission duration of the longest packet. The power-law main body, if significant, may cause the channel throughput to be very close to zero. These theoretical findings provide an understanding on why some empirical measurements suggest heavy tails. We use these results to further highlight the engineering implications of distributions with power-law main bodies and light tails by analyzing two cases: 1) the throughput of on–off channels with retransmissions, where we show that even when packet sizes have small means and bounded support the variability in their sizes can greatly impact system performance; 2) the distribution of the number of jobs in an$M/M/\infty$queue with server failures. Here, we show that retransmissions can cause long-range dependence and quantify the impact of the maximum job sizes on the long-range dependence.

In an unreliable single-hop broadcast network setting, we investigate the throughput and decoding-delay performance of random linear network coding as a function of the coding window size and the network size. Our model consists of a source transmitting packets of a single flow to a set of n users over independent time-correlated erasure channels. The source performs random linear network coding (RLNC) over k (coding window size) packets and broadcasts them to the users. We note that the broadcast throughput of RLNC must vanish with increasing n, for any fixed k. Hence, in contrast to other works in the literature, we investigate how the coding window size k must scale for increasing n. Our analysis reveals that the coding window size of Θ(ln(n)) represents a phase transition rate, below which the throughput converges to zero, and above which, it converges to the broadcast capacity. Further, we characterize the asymptotic distribution of decoding delay and provide approximate expressions for the mean and variance of decoding delay for the scaling regime of k=ω(ln(n)). These asymptotic expressions reveal the impact of channel correlations on the throughput and delay performance of RLNC. We also show that how our analysis can be extended to other rateless block coding schemes such as the LT codes. Finally, we comment on the extension of our results to the cases of dependent channels across users and asymmetric channel model.

This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing architecture and a dynamic routing-scheduling-coding strategy are introduced for serving multiple sessions when linear network coding is allowed across sessions. This policy provides a novel extension to the class of back-pressure policies by incorporating inter-session coding decisions via simple rules on the relevant queue-length levels. Despite the fact that the capacity region of inter-session coding is a challenging open problem, in this paper, we prove that our algorithm can support any set of rates in a nontrivial characterized region of achievable rates. In addition to its practical implications, this work also provides a theoretical framework in which the gains of inter-session network coding and pure routing can be compared.