000126035 001__ 126035
000126035 005__ 20190316234326.0
000126035 037__ $$aREP_WORK
000126035 245__ $$aReal-time Delay with Network Coding and Feedback
000126035 269__ $$a2008
000126035 260__ $$c2008
000126035 336__ $$aReports
000126035 520__ $$aWe 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.
000126035 700__ $$aDrinea, Eleni
000126035 700__ $$0240968$$g161832$$aFragouli, Christina
000126035 700__ $$0241957$$g154399$$aKeller, Lorenzo
000126035 8564_ $$zURL
000126035 8564_ $$uhttps://infoscience.epfl.ch/record/126035/files/techreport.pdf$$zn/a$$s277408
000126035 909C0 $$xU11353$$0252185$$pARNI
000126035 909CO $$qGLOBAL_SET$$preport$$ooai:infoscience.tind.io:126035
000126035 937__ $$aARNI-REPORT-2008-003
000126035 973__ $$sPUBLISHED$$aEPFL
000126035 980__ $$aREPORT