In this paper, we characterize the throughput of a broadcast network with n receivers using rateless codes with block size K. We assume that the underlying channel is a Markov modulated erasure channel that is i.i.d. across users, but can be correlated in time. We characterize the system throughput asymptotically in n. Specifically, we explicitly show how the throughput behaves for different values of the coding block size K as a function of n, as n approaches infinity. For finite values of K and n, under the more restrictive assumption of Gilbert-Elliott channels, we are able to provide a lower bound on the maximum achievable throughput. Using simulations we show the tightness of the bound with respect to system parameters n and K, and find that its performance is significantly better than the previously known lower bounds.
Among the works that investigate the throughput over erasure channels, @cite_10 , @cite_8 , @cite_3 and @cite_0 are the most relevant to this work. In @cite_3 , the authors investigate the asymptotic throughput as a function of @math and @math and also show that the asymptotic throughput will be non-zero only if K at least scales with @math . However, they only consider the channel correlation model with @math and use a completely different proof technique. Moreover, no explicit expression on the asymptotic throughput is provided. In @cite_10 and @cite_8 , two lower bounds on the maximum achievable rate @math are provided. However, their bound does not converge to the asymptotic throughput when @math approaches infinity. Moreover, our bound is shown to be better in a variety of simulation settings with finite @math and @math , as will be showed in . black In @cite_0 , the authors consider the case when instantaneous feedback is provided from every user after the transmission of each decoded packets, while we only assume that feedback is provided after the entire coding block has been decoded.
@cite_0 @cite_10 @cite_3 @cite_8
2097285691 2134109936 2951615571 2018161086
We consider the throughput-delay tradeoff in network coded transmission over erasure broadcast channels. Interested in minimizing decoding delay, we formulate the problem of instantly decodable network coding as an integer linear program and propose algorithms to solve it heuristically. In particular, we investigate channels with memory and propose algorithms that can exploit channel erasure dependence to increase throughput and decrease delay. In this work we compare scheduling and coding strategies for a source node serving multiple multicast flows in a network. The coding strategy we consider is a form of random coding proposed in [6] and involves coding across flows, as treated in [2]. We show that there are configurations for which the coding strategy outperforms any scheduling strategy that uses channel state information. 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. This paper compares scheduling and coding strategies for a multicast version of a classic downlink problem. We consider scheduling strategies where, in each time slot, a scheduler observes the lengths of all queues and the connectivities of all links and can transmit the head-of-the-line packet from a single queue. We juxtapose this to a coding strategy that is simply a form of classical random linear coding. We show that there are configurations for which the stable throughput region of the scheduling strategy is a strict subset of the corresponding throughput region of the coding strategy. This analysis is performed for both time-invariant and time-varying channels. The analysis is also performed both with and without accounting for the impact on throughput of including coding overhead symbols in each encoded packet. Additionally, we compare coding strategies that only code within individual queues against a coding strategy that codes across separate queues. The strategy that codes across queues simply sends packets from all queues to all receivers. As a result, this strategy sends many packets to unnecessary recipients. We show, surprisingly, that there are cases where the strategy that codes across queues can achieve the same throughput region achievable by coding within individual queues.