Design and Analysis of Random Linear Network Coding Schemes: Dense Codes, Chunked Codes and Overlapped Chunked Codes.

摘要

In this thesis, the problem of designing and analyzing network codes that are both communicationally and computationally efficient over unicast (one-source one-sink) networks (particularly, line networks) is considered.;Thereafter, we analyze the coding delay and the average coding delay of dense codes and CC over some well-known probabilistic traffics (delay-free deterministic regular or Poisson transmissions and Bernoulli losses). Our results are (i) for dense codes, in some cases more general, and in some other cases tighter, than the existing bounds, and provide a more clear picture of the speed of convergence of dense codes to the capacity of line networks; and (ii) the first of their kind for CC (with or without precoding) over networks with such probabilistic traffics.;Finally, the problem of designing and analyzing efficient feedback-based scheduling policies for CC is considered. We propose two new scheduling policies, referred to as minimum-distance-first (MDF) and minimum-current-metric-first (MCMF). Unlike the existing policies, the MDF and MCMF policies incorporate transmission, loss and delay models of the link in the selection process of the chunk to be transmitted. Our simulations show that the MDF and MCMF policies significantly reduce the expected decoding time compared to the existing policies over line networks.;At first, we revise the existing analysis of chunked codes (CC), which are a low-complexity version of random linear network codes (a.k.a. dense codes), over worst-case (arbitrary deterministic) traffics, and derive tighter bounds on the performance of CC. Next, to improve the speed of convergence of CC (with or without precoding), while maintaining their advantage in reducing the computational complexity, we propose and analyze a new CC scheme with overlapping chunks, called overlapped chunked codes (OCC). We prove that for smaller chunks, which are advantageous due to lower computational complexity, OCC with larger overlaps provide a better tradeoff between the computational complexity and the speed of convergence or the message/packet error rate. We also prove that a linear-time OCC (i.e., with a chunk size constant in the message size) has a superior performance compared to a CC with the same computational complexity.