Delay with network coding and feedback

We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of μ messages to several receivers over separate erasure channels. The sender can broad- cast a single message or a combination (encoding) of messages at each timestep. Receivers provide feedback as to whether the transmission was received. If at some time step a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. Our setup is novel because it combines coding techniques with feedback information to the end of minimizing delay. It allows Θ(μ) benefits as compared to previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay than online algorithms without feedback. Our main complexity results are that the offline minimization problem is NP-hard when the sender only schedules single messages and that the general problem remains N P -hard even when coding is allowed. However we show that coding does offer delay and complexity gains over scheduling. We also discuss online heuristics and evaluate their performance through simulations.

Real-time Delay with Network Coding and Feedback

Christina Fragouli, Lorenzo Keller

We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of m messages to several receivers. The sender can broadcast a single message or a combination (encoding) of messages to all receivers at each timestep, through separate erasure channels. Receivers provide feedback as to whether the transmission was received. If, at some time step, a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the refinements or different parts of an image. Our setup is novel because it combines coding techniques with feedback information to the end of minimizing delay. Uncoded scheduling or use of multiple description (MDS) codes has been well-studied in the literature. We show that our setup allows O( m ) benefits as compared to both previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay compared to online algorithms without feedback. Our main complexity results are that the offline minimization problem is NP-hard when the sender only schedules single messages and that the general problem remains NP-hard even when coding is allowed. However we show that coding does offer complexity gains by exhibiting specific classes of erasure instances that become trivial under coding schemes. We also discuss online heuristics and evaluate their performance through simulations.

2008

Delay with network coding and feedback

Christina Fragouli, Lorenzo Keller

We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of mu messages to several receivers over separate erasure channels. The sender can broadcast a single message or a combination (encoding) of messages at each timestep. Receivers provide feedback as to whether the transmission was received. If at some time step a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. Our setup is novel because it combines coding techniques with feedback information to the end of minimizing delay. It allows Theta(mu) benefits as compared to previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay than online algorithms without feedback. Our main complexity results are that the offline minimization problem is NP-hard when the sender only schedules single messages and that the general problem remains NP-hard even when coding is allowed. However we show that coding does offer delay and complexity gains over scheduling. We also discuss online heuristics and evaluate their performance through simulations.

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

Delay and coding in multiple-user communications

Stéphane Musy

In multiple-user communications, the bursty nature of the packet arrival times cannot be divorced from the analysis of the transmission process. However, in traditional information theory the random arrival times are smoothed out by appropriated source coding and no consideration is made for the end-to-end delay. In this thesis, using tools from network theory, we investigate simple models that consider the end-to-end delay and/or the variability of the packet arrivals as important parameters, while staying in a information theoretic framework. First, we simplify the problem and focus on the transmission of a bursty source over a single-user channel. We introduce a new measure of channel features that enable us to incorporate the possibility to code among several packets in a scheduling problem. In this setup, we look for policies that minimize the average packet delay. Assuming that the packets are independent and sufficiently large to perform capacity achieving coding, we then consider the problem of allocating rates among a finite number of users communicating through a multiple-user channel. Following the previous work in the context of multiple-access channel, we formulate a scheduling problem in which the rate of each user is chosen from the capacity region of the multiple-user channel. Here, the goal is to find a scheduling policy that minimizes the sum of the transmitter queue lengths, such a policy is called delay optimal. In particular settings, for the additive Gaussian multiple-access channel we show the delay optimality of the Longer Queue Higher Rate policy introduced by Yeh. And, when the users communicate through a symmetric broadcast channel, we propose and show the delay optimality of a Best User Highest Possible Rate policy, among a large class of admissible policies. Finally, in the last part of this thesis, we look at the multiple-user channel coding problem from the perspective of the receivers. By measuring the transmission rates at the receivers, we are able to define variable length codes and to characterize the region of achievable rates when the receivers can decode their intended messages at different instants of time. For the two-user degraded broadcast channel and for the two-user multiple-access channel, we show that the gain in using variable length codes essentially comes from the possibility for the receivers to decode the transmitted messages in non-overlapping periods of time.

EPFL2007

Delay and coding in multiple-user communications

Stéphane Musy

EPFL2007