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 artículo 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 difusió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 (que se analiza a continuación) que ilustra cómo la codificación de red lineal puede superar al 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 su transmisión. Esto se puede utilizar 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 alcanzar 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, multisink con demandas arbitrarias), incluso para versiones más generales de linealidad como codificación convolucional y 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.
Codificación y decodificación
En un problema de codificación de red lineal, un grupo de nodos están involucrados en mover los datos de nodos de origen a sumideros de nodos. 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 indegree ,, genera un mensaje de la combinación lineal de mensajes recibidos por la relación:
donde los valores son los coeficientes seleccionados de . Tenga en cuenta que, dado que las operaciones se calculan en un campo finito, el mensaje generado tiene la misma longitud que los mensajes originales. Cada nodo envía el valor calculado junto con los coeficientes, , utilizado en el nivel, .
Los nodos receptores reciben estos mensajes codificados en la red y los recopilan en una matriz. Los mensajes originales se pueden recuperar realizando una eliminación gaussiana en la matriz. [5] En forma escalonada de fila reducida, los paquetes decodificados corresponden a las filas del formulario.
Una breve historia
Una red está representada por un gráfico dirigido . es el conjunto de nodos o vértices, es el conjunto de enlaces dirigidos (o bordes), y da la capacidad de cada enlace de . Dejar ser el máximo rendimiento posible del nodo al nodo . Según el teorema de corte mínimo de flujo máximo ,es superior delimitado por la capacidad mínima de todos los cortes , que es la suma de las capacidades de los bordes en un corte, entre estos dos nodos.
Karl Menger demostró que siempre hay un conjunto de caminos disjuntos de bordes que alcanzan el límite superior en un escenario de unidifusión , conocido como el teorema de corte mínimo de flujo máximo . Posteriormente, se propuso el algoritmo de Ford-Fulkerson para encontrar tales caminos en tiempo polinomial. Luego, Edmonds demostró en el artículo "Derivaciones de bordes disjuntos" que el límite superior en el escenario de transmisión también es alcanzable, y propuso un algoritmo de tiempo polinomial.
Sin embargo, la situación en el escenario de multidifusión es más complicada y, de hecho, no se puede alcanzar ese límite superior utilizando ideas de enrutamiento tradicionales . Ahlswede y col. demostró que se puede lograr si se pueden realizar tareas informáticas adicionales (los paquetes entrantes se combinan en uno o varios paquetes salientes) en los nodos intermedios. [2]
El ejemplo de la red de mariposas
La red mariposa [2] se utiliza a menudo para ilustrar cómo la codificación de red lineal puede superar al enrutamiento . Dos nodos de origen (en la parte superior de la imagen) tienen información A y B que debe transmitirse a los dos nodos de destino (en la parte inferior). Cada nodo de destino quiere conocer tanto A como B. Cada borde puede llevar solo un valor (podemos pensar en un borde que transmite un bit en cada intervalo de tiempo).
Si solo se permitiera el enrutamiento, entonces el enlace central solo podría transportar A o B, pero no ambos. Supongamos que enviamos A a través del centro; entonces el destino de la izquierda recibiría A dos veces y no conocería B en absoluto. Enviar B plantea un problema similar para el destino correcto. Decimos que el enrutamiento es insuficiente porque ningún esquema de enrutamiento puede transmitir tanto A como B simultáneamente a ambos destinos. Mientras tanto, se necesitan cuatro intervalos de tiempo en total para que ambos nodos de destino conozcan A y B.
Usando un código simple, como se muestra, A y B se pueden transmitir a ambos destinos simultáneamente enviando la suma de los símbolos a través de los dos nodos de retransmisión; en otras palabras, codificamos A y B usando la fórmula "A + B". El destino de la izquierda recibe A y A + B, y puede calcular B restando los dos valores. De manera similar, el destino correcto recibirá B y A + B, y también podrá determinar tanto A como B. Por lo tanto, con la codificación de red, solo se necesitan tres intervalos de tiempo y mejora el rendimiento.
Codificación de red lineal aleatoria
La codificación de red lineal aleatoria [6] es un esquema de codificación simple pero poderoso, que en esquemas de transmisión de radiodifusión permite un rendimiento cercano al óptimo utilizando un algoritmo descentralizado. Los nodos transmiten combinaciones lineales aleatorias de los paquetes que reciben, con coeficientes elegidos de un campo de Galois. Si el tamaño del campo es suficientemente grande, la probabilidad de que el receptor o los receptores obtengan combinaciones linealmente independientes (y por lo tanto obtengan información innovadora) se aproxima a 1. Sin embargo, debe tenerse en cuenta que, aunque la codificación de red lineal aleatoria tiene un excelente rendimiento de rendimiento, si un receptor obtiene un número insuficiente de paquetes, es extremadamente improbable que puedan recuperar alguno de los paquetes originales. Esto se puede solucionar enviando combinaciones lineales aleatorias adicionales hasta que el receptor obtenga el número apropiado de paquetes.
Problemas abiertos
La codificación de redes lineales es todavía un tema relativamente nuevo. Según estudios anteriores, hay tres cuestiones abiertas importantes en RLNC:
- Alta complejidad computacional de decodificación debido al uso del método de eliminación de Gauss-Jordan
- Alta sobrecarga de transmisión debido a la conexión de vectores de coeficientes grandes a bloques codificados
- Dependencia lineal entre vectores de coeficientes que pueden reducir el número de bloques codificados innovadores
Codificación de red inalámbrica
La naturaleza de la transmisión inalámbrica (junto con la topología de la red) determina la naturaleza de la interferencia . Las transmisiones simultáneas en una red inalámbrica generalmente dan como resultado la pérdida de todos los paquetes (es decir, colisión, consulte Acceso múltiple con prevención de colisiones para redes inalámbricas ). Por lo tanto, una red inalámbrica requiere un programador (como parte de la funcionalidad MAC ) para minimizar dicha interferencia. Por lo tanto, cualquier ganancia de la codificación de red se ve fuertemente afectada por el programador subyacente y se desviará de las ganancias observadas en las redes cableadas. Además, los enlaces inalámbricos suelen ser semidúplex debido a limitaciones de hardware; es decir, un nodo no puede transmitir y recibir simultáneamente debido a la falta de suficiente aislamiento entre las dos rutas.
Aunque originalmente se propuso utilizar la codificación de red en la capa de red (ver modelo OSI ), en las redes inalámbricas, la codificación de red se ha utilizado ampliamente en la capa MAC o en la capa PHY . [7] Se ha demostrado que la codificación de red, cuando se utiliza en redes de malla inalámbricas, necesita un diseño y una reflexión atentos para aprovechar las ventajas de la mezcla de paquetes, de lo contrario, las ventajas no se pueden realizar. También hay una variedad de factores que influyen en el rendimiento, como el protocolo de la capa de acceso a los medios, los algoritmos de control de la congestión, etc. No es evidente cómo la codificación de la red puede coexistir y no poner en peligro lo que los algoritmos de control de flujo y congestión existentes están haciendo para nuestra Internet . [8]
Aplicaciones
Dado que la codificación de redes lineales es un tema relativamente nuevo, su adopción en las industrias aún está pendiente. A diferencia de otras codificaciones, la codificación de red lineal no es completamente aplicable en un sistema debido a su escenario de uso específico estrecho. Los teóricos están intentando conectarse a aplicaciones del mundo real. [9] De hecho, se encontró que el enfoque de BitTorrent es muy superior a la codificación de red. [ vago ] [ cita requerida ]
Se prevé que la codificación de red sea útil en las siguientes áreas:
- Debido a la naturaleza de entrega de contenido de múltiples fuentes y multidifusión de las redes centradas en la información en general y de las redes de datos con nombre en particular, la codificación lineal puede mejorar la eficiencia de la red en general. [10]
- Alternativa a la corrección de errores de reenvío y ARQ en redes tradicionales e inalámbricas con pérdida de paquetes. por ejemplo: TCP codificado , [11] ARQ multiusuario [12]
- Robusto y resistente a los ataques de red, como ataques de espionaje, escuchas clandestinas, reproducción o corrupción de datos. [13] [14]
- Distribución de archivos digitales e intercambio de archivos P2P. por ejemplo: Avalanche de Microsoft
- Almacenamiento distribuido. [15] [16] [17]
- Aumento del rendimiento en redes de malla inalámbricas. por ejemplo: COPE , [18] CORE , [19] Enrutamiento con reconocimiento de codificación , [20] [21] BATMAN [22]
- Reducción de búfer y retardo en redes de sensores espaciales: multiplexación de búfer espacial [23]
- Reduzca el número de retransmisiones de paquetes para una transmisión de multidifusión inalámbrica de un solo salto y, por lo tanto, mejore el ancho de banda de la red. [24]
- Intercambio de archivos distribuido [25]
- Transmisión de video de baja complejidad a dispositivos móviles [26]
- Extensiones de dispositivo a dispositivo (D2D) [27] [28] [29] [30] [31]
Están surgiendo nuevos métodos para utilizar la codificación de red en sistemas de accesos múltiples para desarrollar redes de área de cableado definidas por software (SD-WAN) que pueden ofrecer menor retardo, fluctuación y alta solidez. [32] La propuesta menciona que el método es independiente de tecnologías subyacentes como LTE, Ethernet, 5G. [33]
Madurez y problemas
Dado que esta área es relativamente nueva y el tratamiento matemático de este tema se limita actualmente a un puñado de personas, la codificación de redes aún ha encontrado su camino hacia la comercialización de productos y servicios. No está claro en esta etapa si este tema prevalecerá o cesará como un buen ejercicio matemático. [34]
Los investigadores han señalado claramente que se necesita especial cuidado para explorar cómo la codificación de red puede coexistir con el enrutamiento existente, el acceso a los medios, la congestión, los algoritmos de control de flujo y el protocolo TCP. De lo contrario, la codificación de red puede no ofrecer muchas ventajas y puede aumentar la complejidad del cálculo y los requisitos de memoria. [35]
Ver también
- Protocolo de intercambio secreto
- Firmas homomórficas para codificación de red
- Codificación de red triangular
Referencias
- ^ Celebiler, M .; G. Stette (1978). "Sobre el aumento de la capacidad de enlace descendente de un repetidor de satélite regenerativo en comunicaciones punto a punto". Actas del IEEE . 66 (1): 98–100. doi : 10.1109 / PROC.1978.10848 .
- ^ a b c Ahlswede, Rudolf ; N. Cai; S.-YR Li; RW Yeung (2000). "Flujo de información de la red". Transacciones IEEE sobre teoría de la información . 46 (4): 1204-1216. CiteSeerX 10.1.1.722.1409 . doi : 10.1109 / 18.850663 .
- ^ S. Li, R. Yeung y N. Cai, "Codificación de red lineal" ( PDF ), en IEEE Transactions on Information Theory, Vol 49, No. 2, págs. 371–381, 2003
- ^ R. Dougherty, C. Freiling y K. Zeger, "Insuficiencia de codificación lineal en el flujo de información de la red" ( PDF ), en IEEE Transactions on Information Theory, vol. 51, núm. 8, págs. 2745-2759, agosto de 2005 ( errata )
- ^ Chou, Philip A .; Wu, Yunnan; Jain, Kamal (octubre de 2003), "Codificación de red práctica", Conferencia de Allerton sobre comunicación, control y computación .
Cualquier receptor puede recuperar los vectores de origen utilizando la eliminación gaussiana de los vectores en sus paquetes h (o más) recibidos.
. - ^ T. Ho, R. Koetter, M. Médard , DR Karger y M. Effros, "Los beneficios de la codificación sobre el enrutamiento en un entorno aleatorizado" Archivado el 31 de octubre de 2017 en la Wayback Machine en 2003 Simposio internacional IEEE sobre teoría de la información . doi : 10.1109 / ISIT.2003.1228459
- ^ MHFirooz, Z. Chen, S. Roy y H. Liu, ( Codificación de red inalámbrica a través de MAC / PHY 802.11 modificada: Diseño e implementación en SDR ) en IEEE Journal on Selected Areas in Communications, 2013.
- ^ XOR en el aire: codificación práctica de redes inalámbricas
- ^ "¿Qué tan práctica es la codificación en red? Por Mea Wang, Baochun Li". CiteSeerX 10.1.1.77.6402 . Cite journal requiere
|journal=
( ayuda ) - ^ Bilal, Muhammad; et al. (2019). "Enfoque de codificación de red para redes centradas en la información". Revista de sistemas IEEE . 13 (2): 1376-1385. arXiv : 1808.00348 . Código bibliográfico : 2019ISysJ..13.1376B . doi : 10.1109 / JSYST.2018.2862913 .
- ^ Kim, Minji (2012). "TCP codificado en red (CTCP)". arXiv : 1212,2291 [ cs.NI ].
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 8 de noviembre de 2007 . Consultado el 16 de junio de 2007 .CS1 maint: copia archivada como título ( enlace )
- ^ "Bienvenido a Network Coding Security - Secure Network Coding" .
- ^ http://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf [ enlace muerto permanente ]
- ^ Bilal, Muhammad; et al. (2019). "Enfoque de codificación de red para redes centradas en la información". Revista de sistemas IEEE . 13 (2): 1376-1385. arXiv : 1808.00348 . Código bibliográfico : 2019ISysJ..13.1376B . doi : 10.1109 / JSYST.2018.2862913 .
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 19 de septiembre de 2013 . Consultado el 18 de abril de 2013 .CS1 maint: copia archivada como título ( enlace )
- ^ Dimakis, Alexandros (2007). "Codificación de red para sistemas de almacenamiento distribuidos". arXiv : cs / 0702015 .
- ^ http://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf
- ^ Krigslund, Jeppe; Hansen, Jonas; Hundeboll, Martin; Lucani, Daniel E .; Fitzek, Frank HP (2013). NÚCLEO: COPE con MÁS en redes inalámbricas de malla . 2013 IEEE 77th Vehicular Technology Conference (VTC Spring) . págs. 1–6. doi : 10.1109 / VTCSpring.2013.6692495 . ISBN 978-1-4673-6337-2.
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 11 de octubre de 2008 . Consultado el 10 de mayo de 2007 .CS1 maint: copia archivada como título ( enlace )
- ^ http://www.cs.wisc.edu/~shravan/infocom-07-2.pdf
- ^ "NetworkCoding - batman-adv - malla abierta" . www.open-mesh.org . Consultado el 28 de octubre de 2015 .
- ^ Bienvenido a IEEE Xplore 2.0: Análisis de redes grandes: codificación frente a colas
- ^ Dong Nguyen; Tuan Tran; Thinh Nguyen; Bose, B. (2009). "Transmisión inalámbrica mediante codificación de red". Transacciones IEEE sobre tecnología vehicular . 58 (2): 914–925. CiteSeerX 10.1.1.321.1962 . doi : 10.1109 / TVT.2008.927729 .
- ^ Difusión de datos en redes inalámbricas con codificación de red
- ^ Códigos de banda para codificación de redes energéticamente eficientes con aplicación a transmisión móvil P2P
- ^ Wu, Y., Liu, W., Wang, S., Guo, W. y Chu, X. (junio de 2015). Codificación de red en comunicaciones de dispositivo a dispositivo (D2D) subyacentes a las redes celulares . En 2015 IEEE International Conference on Communications (ICC) (págs. 2072-2077). IEEE.
- ^ Zhao, Y., Li, Y. y Ge, N. (diciembre de 2015). La codificación de red de capa física ayudó a la comunicación bidireccional de dispositivo a dispositivo subyacente a las redes celulares . En 2015 IEEE Global Communications Conference (GLOBECOM) (págs. 1-6). IEEE.
- ^ Abrardo, A., Fodor, G. y Tola, B. (junio de 2015). Esquemas de codificación de red para la retransmisión basada en comunicaciones de dispositivo a dispositivo para la extensión de la cobertura celular . En 2015, 16º Taller Internacional de IEEE sobre avances en el procesamiento de señales en las comunicaciones inalámbricas (SPAWC) (págs. 670-674). IEEE.
- ^ Gao, C., Li, Y., Zhao, Y. y Chen, S. (2017). Un enfoque de teoría de juegos de dos niveles para la selección conjunta de relevos y la asignación de recursos en comunicaciones D2D asistidas por codificación de red . Transacciones IEEE sobre informática móvil, 16 (10), 2697-2711.
- ^ Zhou, T., Xu, B., Xu, T., Hu, H. y Xiong, L. (2015). Esquema de adaptación de enlace específico del usuario para multidifusión de codificación de red de dispositivo a dispositivo. Comunicaciones IET, 9 (3), 367-374.
- ^ SD-WAN codificada en red en sistemas de acceso múltiple para control de retardo
- ^ Un controlador SD-WAN para minimizar la fluctuación de retardo en sistemas codificados de acceso múltiple
- ^ "¿Qué tan práctica es la codificación de red?". CiteSeerX 10.1.1.77.6402 . Cite journal requiere
|journal=
( ayuda ) - ^ "XOR en el aire" (PDF) .
- Fragouli, C .; Le Boudec, J. & Widmer, J. "Network coding: An instant primer" en Computer Communication Review , 2006.
Ali Farzamnia, Sharifah K. Syed-Yusof, Norsheila Fisa "Codificación de descripción múltiple de multidifusión mediante codificación de red de ciclo p", Transacciones de KSII en Internet y sistemas de información, Vol 7, No 12, 2013.
enlaces externos
- Página de inicio de codificación de red
- Una bibliografía de codificación en red
- Raymond W. Yeung, Teoría de la información y codificación de redes, Springer 2008, http://iest2.ie.cuhk.edu.hk/~whyeung/book2/
- Raymond W. Yeung et al., Network Coding Theory, ahora Publishers, 2005, http://iest2.ie.cuhk.edu.hk/~whyeung/netcode/monograph.html
- Christina Fragouli et al., Network Coding: An Instant Primer, ACM SIGCOMM 2006, http://infoscience.epfl.ch/getfile.py?mode=best&recid=58339 .
- Sistema de archivos Avalanche, http://research.microsoft.com/en-us/projects/avalanche/default.aspx
- Codificación de red aleatoria, https://web.archive.org/web/20060618083034/http://www.mit.edu/~medard/coding1.htm
- Códigos de fuentes digitales, http://www.icsi.berkeley.edu/~luby/
- Enrutamiento con reconocimiento de codificación, https://web.archive.org/web/20081011124616/http://arena.cse.sc.edu/papers/rocx.secon06.pdf
- MIT ofrece un curso: Introducción a la codificación de redes
- Codificación de redes: ¿la próxima revolución de las redes?
- Diseño de protocolos de codificación para redes inalámbricas: http://scholarcommons.sc.edu/etd/230/