Systematic network coding for lossy line networks

Abstract

Esta tesis doctoral se centra en esquemas de codificación de red sistemáticos (SNC por sus siglas en inglés para systematic network coding) a nivel de paquete para proporcionar resistencia a la pérdida de paquetes en redes lineales con pérdidas. En la teoría, la codificación de red ( network coding ) es conocida por la mejora en rendimiento y fiabilidad en redes con pérdidas. Sin embargo, la traducción de la teoría del network coding en soluciones prácticas comprende algunos desafíos críticos. Esta tesis aborda estos desafíos e investiga soluciones de network coding que puedan ser usadas en la práctica para diferentes instancias de redes lineales con pérdidas. Los objetivos principales de esta tesis doctoral son: 1) desarrollar un modelo matricial que permita el tratamiento analítico de network coding para redes con pérdidas, 2) investigar de manera semi-analítica el rendimiento alcanzable y la fiabilidad para redes lineales, un simple pero útil modelo de red conceptual, 3) desarrollar esquemas prácticos de network coding para redes lineales que superen significativamente el rendimiento del estado del arte en esquemas basados puramente en la correción de borrado hacia adelante (FEC por sus siglas en ingles para forward erasure correction), y 4) estar en línea con los esfuerzos del equipo de trabajo de la investigación en internet, Internet Research Task Force (IRTF) y presentar contribuciones. Las contribuciones de esta tesis, tal que se cumplen los objetivos son las siguientes. Primero, investigamos el uso de SNC en redes con pérdida de un solo salto. Desarrollamos un modelo matricial para este caso sin re-codificar en la red. Esto nos permite comparar códigos separables de máxima distancia (MDS por su sigla en inglés) con SNC cuando se usan únicamente como FEC. Derivamos la mínima distancia de SNC y mostramos que SNC puede proporcionar fiabilidad tan cercana al MDS como se desee y lo permita el tamaño del campo. Simulamos aplicaciones prácticas a nivel de capa de aplicación de la pila de protocolos con dos resultados concretos. Primero, se muestra que utilizando decodificación progresiva de SNC se alcanzan retardos más bajos que con un código MDS y segundo, se obtiene una distribución óptima del ancho de banda para la tasa de network coding mientras se aplica SNC in redes con bandas limitadas. Segundo, investigamos la aplicación de SNC en redes de dos saltos con pérdidas. Extendemos el modelo matricial para redes con un nodo intermedio. Usando el planteamiento semi-análitico, estudiamos y caracterizamos la fiabilidad y tasa alcanzable como una función de la tasa de network coding y de la capacidad de la red. Simulamos las aplicaciones prácticas en la capa de enlace del estándar Digital Video Broadcasting via Satellite-Second Generation (DVB-S2). Proponemos un marco con arquitectura y encapsulamiento tal que se pueda usar network coding en protocolos de la capa de enlace del DVB-S2. Tercero, extendemos el modelo matricial para una red con varios nodos intermedios. Esto nos permite entender el marco matemático de mapear entidades de comunicaciones con entidades matemáticas en diferentes nodos intermedios de la red. Analizamos la fiabilidad, las tasas alcanzables, el retardo y la complejidad de los esquemas de network coding de manera semi-analítica y probamos que nuestros resultados están en línea con los resultados de la teoría de la información. Finalmente, desarrollamos un esquema inteligente de re-codificación de network coding que incluye la planificación de paquetes en los nodos intermedios. Nuestra propuesta proporciona menor retardo y menor complejidad comparada con el estado del arte en esquemas de network coding.

This dissertation focuses on packet-level systematic network coding (SNC) schemes to provide resilience to packet losses in lossy line networks. In theory, network coding is known to improve throughput and reliability of lossy networks. However, the translation of the network coding theory into efficient practical network coding solutions involves some critical challenges. This dissertation addresses those challenges and investigates on network coding solutions that can be utilized in practice for different instances of the lossy line networks. The main objectives of this dissertation are: 1) to develop a matricial model that allows analytical treatment of network coding for lossy networks, 2) semi-analytical investigation of achievable throughput and reliability for line networks, a simple yet useful conceptual network model, 3) to develop practical network coding schemes for line networks that significantly outperform state-of-the-art purely forward erasure correction (FEC)-based schemes and 4) to be in line with Internet Research Task Force (IRTF) efforts and eventually contribute. The contributions of this thesis, such that the objectives are met are as follows. First, we investigate the application of SNC in one-hop lossy networks. We develop a matricial model for the case without re-encoding in the network. This allows us to compare maximum distance separable (MDS) codes with SNC when used as FEC only. We derive the minimum distance of SNC and show that SNC can provide as closed as wished to MDS reliability as the field sizes is allowed to grow. We simulate practical applications at application layer of the protocol stack with two concrete results. First, it is shown that by using progressive decoding SNC achieves smaller delay than the MDS code and second, an optimal bandwidth distribution for network coding rate is obtained while applying SNC in band-limited networks. Second, we investigate the application of SNC in two-hop lossy networks. We extend the matricial model for the networks with one intermediate node. Using the semi-analytical approach, we study and characterize the reliability and achievable rate as a function of network coding rate and capacity of the network. We simulate practical applications at link layer of Digital Video Broadcasting via Satellite-Second Generation (DVB-S2). We propose an architectural and encapsulation framework so that network coding can be used over the state-of-the-art protocols at link layer of DVB-S2. Third, we extend the matricial model for the network with several intermediate nodes. This allows us to understand the mathematical framework of mapping communication entities to mathematical entities at different intermediate nodes of the network. We analyze semi-analytically reliability, achievable rates, delay and complexity of network coding schemes and prove that our results are inline with information theoretical results. Finally, we develop a smart re-encoding network coding scheme that includes packet scheduling at the intermediate nodes. Our proposal is shown to provide smaller delay and smaller complexity than state-of-the-art network coding schemes.