A large number of streaming applications use reliable transport protocols such as TCP to deliver content over the Internet. However, head-of-line blocking due to packet loss recovery can often result in unwanted behavior and poor application layer performance. Transport layer coding can help mitigate this issue by helping to recover from lost packets without waiting for retransmissions. We consider the use of an on-line network code that inserts coded packets at strategic locations within the underlying packet stream. If retransmissions are necessary, additional coding packets are transmitted to ensure the receiver's ability to decode. An analysis of this scheme is provided that helps determine both the expected in-order packet delivery delay and its variance. Numerical results are then used to determine when and how many coded packets should be inserted into the packet stream, in addition to determining the trade-offs between reducing the in-order delay and the achievable rate. The analytical results are finally compared with experimental results to provide insight into how to minimize the delay of existing transport layer protocols.
On the other hand, a large body of research investigating the delay of coding in different settings has taken place. In general, most of these works can be summarized by Figure . The coding delay of chunked and overlapping chunked codes ( @cite_5 ) (shown in Figure (a)), network coding in time-division duplexing (TDD) channels ( @cite_17 @cite_10 @cite_0 ), and network coding in line networks where coding also occurs at intermediate nodes ( @cite_7 ) is well understood. In addition, a non-asymptotic analysis of the delay distributions of random linear network coding (RLNC) ( @cite_20 ) and various multicast scenarios ( @cite_4 @cite_13 @cite_9 ) using a variant of the scheme in Figure (b) have also been investigated. Furthermore, the research that looks at the in-order packet delay is provided in @cite_19 and @cite_23 for uncoded systems, while @cite_14 , @cite_3 , and @cite_1 considers the in-order packet delay for non-systematic coding schemes similar to the one shown in Figure (b). However, these non-systematic schemes may not be the optimum strategy in networks or communication channels with a long @math .
@cite_13 @cite_14 @cite_4 @cite_7 @cite_9 @cite_1 @cite_3 @cite_0 @cite_19 @cite_23 @cite_5 @cite_10 @cite_20 @cite_17
2099479177 2951615571 2032843418 2131646038
A fundamental understanding of the delay behavior of network coding is key towards its successful application in real-time applications with strict message deadlines. Previous contributions focused mostly on the average decoding delay, which although useful in various scenarios of interest is not sufficient for providing worst-case delay guarantees. To overcome this challenge, we investigate the entire delay distribution of random linear network coding for any field size and arbitrary number of encoded symbols (or generation size). By introducing a Markov chain model we are able to obtain a complete solution for the erasure broadcast channel with two receivers. A comparison with Automatic Repeat reQuest (ARQ) with perfect feedback, round robin scheduling and a class of fountain codes reveals that network coding on GF(24) offers the best delay performance for two receivers. We also conclude that GF(2) induces a heavy tail in the delay distribution, which implies that network coding based on XOR operations although simple to implement bears a relevant cost in terms of worst-case delay. For the case of three receivers, which is mathematically challenging, we propose a brute-force methodology that gives the delay distribution of network coding for small generations and field size up to GF(24). 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 @math users over independent erasure channels. The source performs random linear network coding (RLNC) over @math (coding window size) packets and broadcasts them to the users. We note that the broadcast throughput of RLNC must vanish with increasing @math , for any fixed @math Hence, in contrast to other works in the literature, we investigate how the coding window size @math must scale for increasing @math . Our analysis reveals that the coding window size of @math 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 @math These asymptotic expressions reveal the impact of channel correlations on the throughput and delay performance of RLNC. We also show 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. 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. We study an online random linear network coding approach for time division duplexing (TDD) channels under Poisson arrivals. We model the system as a bulk-service queue with variable bulk size and with feedback, i.e., when a set of packets are serviced at a given time, they might be reintroduced to the queue to form part of the next service batch. We show that there is an optimal number of coded data packets that the sender should transmit back-to-back before stopping to wait for an acknowledgement from the receiver. This number depends on the latency, probability of packet erasure, degrees of freedom at the receiver, the size of the coding window, and the arrival rate of the Poisson process. Random network coding is performed across a moving window of packets that depends on the packets in the queue, design constraints on the window size, and the feedback sent from the receiver. We study the mean time between generating a packet at the source and it being seen", but not necessarily decoded, at the receiver. We also analyze the mean time between a decoding event and the next, defined as the decoding of all the packets that have been previously seen" and those packets involved in the current window of packets. Inherently, a decoding event implies an in-order decoding of a batch of data packets. We present numerical results illustrating the trade-off between mean delay and mean time between decoding events.