Completion Delay Minimization for Instantly Decodable Network Coding

Instantly Decodable Network Coding (IDNC) is a subclass of opportunistic network coding that has numerous desirable properties for a wide spectrum of applications, namely its faster decoding delay, simpler coding and decoding processes, and no decoding buffer requirements. Nonetheless, IDNC suffers from two main problems that may limit its attractiveness, as an implementable solution in future wireless networks, against full network coding (FNC), widely studied in the literature. First, it cannot guarantee the decoding of a new packet at each receiver in each transmission, which may severely affect its completion delay. Second, it requires full feedback in order to operate properly, which may be prohibitive for several practical network settings. In this thesis, we aim to reduce the effect of these drawbacks by studying the problems of minimizing the IDNC completion delay in full and limited feedback scenarios. Since completion delay cannot be optimized only through local decisions in each of the transmissions, we first study the evolution of the IDNC coding opportunities and determine the strategies maximizing them, not only for one transmission, but for all future transmissions. We then formulate the completion delay problem as a stochastic shortest path (SSP) problem, which turns out to be of extremely large dimensions that makes its optimal solution intractable. Nonetheless, we exploit the structure of this SSP and the evolution of the coding opportunities to design efficient algorithms, which outperform FNC in most multicast scenarios and achieve a near-optimal performance in broadcast scenarios. However, since FNC still outperforms IDNC in some network scenarios, we design an adaptive selection algorithm that efficiently selects, between these two schemes, the one that achieves the smaller completion delay. To study the effect of feedback reduction, we formulate the completion delay minimization problem, for the cases of intermittent and lossy feedback, as extended SSP and partially observable SSP problems, respectively. We show that these new formulations have the same structure of the original SSP. We thus extend the designed algorithms to operate in intermittent and lossy feedback scenarios, after taking update decisions on the attempted and un-acknowledged packets. These redesigned algorithms are shown to achieve tolerable degradation for relatively low feedback frequencies and high feedback loss rates.

Department dc:contributor.department

Electrical and Computer Engineering

Year dc:date.issued

2011

Author dc:creator

• Sorour, Sameh

Advisor dc:contributor.advisor

• Valaee, Shahrokh

Statement dc:rights

• Attribution-NonCommercial-ShareAlike 3.0 Unported

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-sa/3.0/

Language dc:language.iso

en_ca

Handle dc:identifier.uri

http://hdl.handle.net/1807/29876

OAI identifier oai:identifier

oai:utoronto.scholaris.ca:1807/29876