Codificación de red lineal
La codificación de redes es un campo de investigación fundado en una serie de artículos desde finales de la década de 1990 hasta principios de la de 2000. Sin embargo, el concepto de codificación de red, en particular la codificación de red lineal , apareció mucho antes. En un documento de 1978, [1] se propuso un esquema para mejorar el rendimiento de una comunicación bidireccional a través de un satélite. En este esquema, dos usuarios que intentan comunicarse entre sí transmiten sus flujos de datos a un satélite, que combina los dos flujos sumándolos en módulo 2 y luego transmite el flujo combinado. Cada uno de los dos usuarios, al recibir el flujo de transmisión, puede decodificar el otro flujo utilizando la información de su propio flujo.
El documento de 2000 [2] dio el ejemplo de la red mariposa (discutido a continuación) que ilustra cómo la codificación de red lineal puede superar el enrutamiento. Este ejemplo es equivalente al esquema de comunicación por satélite descrito anteriormente. El mismo documento proporcionó un esquema de codificación óptimo para una red con un nodo de origen y tres nodos de destino. Este es el primer ejemplo que ilustra la optimización de la codificación de red convolucional (una forma más general de codificación de red lineal) sobre una red cíclica.
La codificación de red lineal se puede utilizar para mejorar el rendimiento, la eficiencia y la escalabilidad de una red , así como la resistencia a los ataques y las escuchas. En lugar de simplemente transmitir los paquetes de información que reciben, los nodos de una red toman varios paquetes y los combinan para la transmisión. Esto puede utilizarse para lograr el máximo flujo de información posible en una red .
Se ha demostrado matemáticamente que, en teoría, la codificación lineal es suficiente para lograr el límite superior en problemas de multidifusión con una fuente. [3] Sin embargo, la codificación lineal no es suficiente en general (por ejemplo, multifuente, multisumidero con demandas arbitrarias), incluso para versiones más generales de linealidad como la codificación convolucional y la codificación de banco de filtros . [4] Encontrar soluciones de codificación óptimas para problemas generales de red con demandas arbitrarias sigue siendo un problema abierto.
En un problema de codificación de red lineal, un grupo de nodos está involucrado en mover los datos de los nodos de origen a los nodos de destino. Cada nodo genera nuevos paquetes que son combinaciones lineales de paquetes recibidos anteriormente, multiplicándolos por coeficientes elegidos de un campo finito , típicamente de tamaño .
Cada nodo, con grado de entrada , genera un mensaje a partir de la combinación lineal de mensajes recibidos por la relación:
