Análisis de algoritmos de codificación de redes

Abstract

Esta memoria tiene como objetivo el análisis de un modelo de transmisión de datos bajo el contexto de network coding. El modelo fue inspirado en un estudio de comunicación en redes inalámbricas. En el escenario a estudiar, se desea enviar información particionada en paquetes, que llegan a un transmisor, a múltiples receptores. Se considera que el tiempo está particionado en períodos de tiempo iguales. Los paquetes, modelados como vectores de un espacio vectorial, llegan al transmisor mediante un proceso de Bernoulli de tasa $\lambda$. El transmisor puede enviar, en cada período, una combinación lineal de paquetes por igual a cada uno de los receptores. Las transmisiones pueden fallar en cada período con probabilidad $1-\mu$ de manera independiente entre cada receptor. Los receptores deben ser capaces de recuperar cada paquete de información original. En el contexto descrito, el principal parámetro de estudio es el retraso de decodificación de un paquete, definido como el tiempo esperado que transcurre entre que llega el paquete al transmisor y el instante en que un receptor logra decodificarlo (es decir, ser capaz de calcular una combinación lineal entre las transmisiones que el receptor ha recibido, cuyo resultado sea el paquete en consideración). El caso de interés del análisis del retraso de decodificación, es cuando el factor de carga $\rho = \lambda/\mu$, con $\lambda < \mu$, $\rho \rightarrow 1$. En primer lugar, se analiza el caso en que existen dos receptores. El transmisor ocupa un esquema de codificación propuesto en la literatura para calcular las combinaciones lineales de paquetes que se van a enviar. Se demuestra que el tiempo esperado del retraso de decodificación es $O\left( \frac{1}{1-\rho} \right)$, siendo una cota asintóticamente óptima. Se introduce el uso de funcionales de Lyapunov sobre cadenas de Markov, que permiten estudiar y acotar esperanzas que dependen del funcional. Posteriormente, se estudia si es posible para el caso de dos receptores realizar transmisiones, en períodos específicos, que den prioridad al receptor que ha recibido menos paquetes, con el objetivo de acotar el retraso de decodificación de los paquetes que le falta por decodificar a tal receptor. Aquí, se introduce la técnica de coupling de cadenas de Markov en el contexto de network coding. Por último, se avanza en el análisis de un esquema de codificación para el caso de tres receptores propuesto en la literatura. Se generalizan resultados que permiten obtener cotas para el caso de dos receptores utilizando funcionales de Lyapunov, adecuando las hipótesis a las que se tienen en el esquema de codificación en consideración.