Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Gauri Joshi

In this thesis, we consider the problem of minimizing playback delay in streaming over a packet erasure channel with fixed bandwidth. In recent years, there has been a rapid increase in live streaming applications where packets have to be played back at the receiver in order. With instantaneous feedback, the automatic-repeat-request (ARQ) protocol is delay optimal. However, with no feedback or delayed feedback, there is a trade-off between transmitting new packets and retransmitting old packets, to reduce the playback delay. Existing erasure codes such as Reed-Solomon codes and fountain codes that operate without feedback have delay proportional to the length of the stream, and hence are not suitable for streaming applications. Other coding schemes specifically de- signed for delay-constrained packet transmission aim to minimize the decoding delay. However, playback delay is a more natural metric for applications requiring in-order playback at the receiver. We aim to find good streaming codes that minimize playback delay for such channels with limited or no feedback. We analyze three cases, namely no-feedback, delayed feedback and broadcast with instantaneous feedback. We find that in all cases the playback delay grows logarithmically with the time elapsed since the start of trans- mission, and we evaluate the growth constant, i.e. the pre-log term, as a function of the transmission bandwidth (relative to the source bandwidth). The main tool used in the analysis of delay in all cases is to model packet decoding in terms of threshold crossing of a random walk. We can show that the expected playback delay is asymptotically equal to 1=z[lambda] log n where [lambda] is referred to as the growth constant. For the no-feedback case, the optimal value is [lambda] = D(1/b [rho]) where b is the bandwidth in packets per slot and [rho] is the success probability of the erasure channel. We prove that the simple coded repetition scheme where the source transmits combinations all packets generated so far in every slot achieves this optimal growth constant. With instantaneous feedback, the ARQ scheme is optimal and we can determine the exact expression for [lambda]. For the delayed feedback case we propose a greedy coding scheme and use it to determine a lower bound on [lambda]d as a function of feedback delay d. We can prove that the growth constant with feedback is strictly better that the one without, but they have the same asymptotic value in the limit of infinite bandwidth. We further extend the analysis to a broadcast streaming scenario with instantaneous feedback where the source is transmitting a common packet stream to N users over independent erasure channels. We determine how the growth constant [lambda]N scales with the number of the users N. It can be shown that greedy coding is optimal for the without feedback and instantaneous feedback cases, however we have not yet proved its optimality for the delayed feedback and broadcast streaming. This is the major part of ongoing research efforts. Other future research directions include extending the results to packet networks and considering more general channel models.

Gauri Joshi

About

Books

Join the club