In this paper, we deal with the problem of jointly determining the optimal coding strategy and the scheduling decisions when receivers obtain layered data from multiple servers. The layered data is encoded by means of prioritized random linear coding (PRLC) in order to be resilient to channel loss while respecting the unequal levels of importance in the data, and data blocks are transmitted simultaneously in order to reduce decoding delays and improve the delivery performance. We formulate the optimal coding and scheduling decisions problem in our novel framework with the help of Markov decision processes (MDP), which are effective tools for modeling adapting streaming systems. Reinforcement learning approaches are then proposed to derive reduced computational complexity solutions to the adaptive coding and scheduling problems. The novel reinforcement learning approaches and the MDP solution are examined in an illustrative example for scalable video transmission . Our methods offer large performance gains over competing methods that deliver the data blocks sequentially. The experimental evaluation also shows that our novel algorithms offer continuous playback and guarantee small quality variations which is not the case for baseline solutions. Finally, our work highlights the advantages of reinforcement learning algorithms to forecast the temporal evolution of data demands and to decide the optimal coding and scheduling decisions .
Unfortunately, digital Fountain codes such as Raptor codes and LT codes may perform poorly in terms of delay @cite_16 @cite_24 . To this aim, systematic Random Linear Codes (RLC) with feedback have been studied in @cite_16 for minimizing the average delay in database replication systems. The feedback messages contain information about the packets that have been delivered to the receivers. These messages are used to optimize the coding decisions such that the decoding delay is small. The decoding delay distribution has been investigated in @cite_24 for RLC systems. Markov chains are utilized in order to find the optimal coding solution for the case of two receivers. However, this problem is computationally intractable for three or more receivers and hence only a heuristic solution is presented. The delay benefits of a RLC based scheme have been examined in @cite_14 , where repair packets are generated on-the-fly through RLC according to feedback messages that are periodically received by the servers. This scheme copes efficiently with the packet erasures and is appropriate for real-time sources such as video. From the above studies, the advantages of RLC over Fountain codes in terms of delay become clear.
@cite_24 @cite_14 @cite_16
2099479177 2115512986 1996340076
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). This paper introduces a robust point-to-point transmission scheme: Tetrys, that relies on a novel on-the-fly erasure coding concept which reduces the delay for recovering lost data at the receiver side. In current erasure coding schemes, the packets that are not rebuilt at the receiver side are either lost or delayed by at least one RTT before transmission to the application. The present contribution aims at demonstrating that Tetrys coding scheme can fill the gap between real-time applications requirements and full reliability. Indeed, we show that in several cases, Tetrys can recover lost packets below one RTT over lossy and best-effort networks. We also show that Tetrys allows to enable full reliability without delay compromise and as a result: significantly improves the performance of time constrained applications. For instance, our evaluations present that video-conferencing applications obtain a PSNR gain up to 7 dB compared to classic block-based erasure codes. 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.