Calcular la capacidad total de una red de datos es un problema notoriamente difícil, pero los teóricos de la información están comenzando a hacer algo de progreso.
Larry Hardesty, MIT News Office. Original (en inglés).
En sus primeros años, la teoría de la información – que nació de un artículo histórico en 1948 por alumno del MIT (Massachusetts Institute of Technology – Instituto Tecnológico de Massachusetts) y futuro profesor Claude Shannon – estuvo dominado por investigación de códigos de corrección de errores: ¿Cómo codificas la información para garantizar su transmisión fiel, aún en presencia de influencias corruptoras que los ingenieros llaman “ruido”?
Recientemente, uno de los desarrollos más intrigantes en la teoría de la información ha sido una tipo diferente de codificación, llamado codificación de red, en el que la pregunta es cómo codificar información para maximizar la capacidad de una red como conjunto. Para los teóricos de la información, era natural preguntar cómo estos dos tipos de codificación podían ser combinados: Si quieres a la vez minimizar los errores y maximizar la capacidad, ¿Qué tipo de codificación aplicas dónde, y cuándo haces la decodificación?
Lo que hace la pregunta particularmente difícil de responder es que nadie sabe cómo calcular la capacidad de datos de una red como un todo – o incluso si puede ser calculada. No obstante, en la primera mitad de un artículo de dos partes, que fue publicado recientemente en Transacciones de Teoría de la Información del IEEE, Muriel Médard del MIT, Michelle Effros del Instituto de Tecnología de California y el fallecido Ralf Koetter de la Universidad de Tecnología en Munich muientras que en una red cableada, la codificación de red y la codificación de corrección de errores pueden ser manejadas separadamente, sin reducción en la capacidad de la red. En la próxima segunda mitad del artículo, los mismos investigadores demuestran algunos límites en las capacidades de las redes inalámbricas, que podría ayudar a guiar investigación futura tanto en la industria como en la academia.
Una red de datos típica consiste de un arreglo de nodos – que podrían ser ruteadores en el Internet, estaciones base inalámbricas e incluso unidades de procesamiento en un solo chip – cada uno de los cuales puede comunicarse directamente con un algunos de sus vecinos. Cuando un paquete de datos llega a un nodo, el nodo inspecciona su información de direccionamiento y decide por cual de los varios caminos enviarlo.
Confusión calculada
Con la codificación de redes, por otro lado, un nodo revuelve los paquetes que recibe y envía los paquetes híbridos por caminos múltiples; en cada nodo subsecuente ellos son revueltos de nuevo en diferentes formas. Contraintuitivamente, esto puede incrementar significativamente la capacidad de la red entera: Paquetes híbridos llegan a su destino por caminos múltiples. Si uno de estos caminos está congestionado, o si uno o más de sus vínculos falla completamente, los paquetes que llegan por los otros caminos probablemente contendrán suficiente información para que el recipiente pueda armar el mensaje original.
Pero cada vínculo entre los nodos podría ser ruidoso, así que la información en los paquetes también necesita ser codificada para corregir errores. “Supón que soy un nodo en una red, y veo una comunicación entrando, y está corrupta por ruido”, dice Médard, una profesora de ingeniería eléctrica y ciencia computacional”. Podría tratar de remover el ruido, pero al hacer eso, estoy en efecto tomando una decisión justo ahora que quizá habría sido mejor tomada por alguien que podría tener más observaciones de la misma fuente.
Por otro lado, dice Médard, si un nodo simplemente reenvia los datos que recibe sin realizar ninguna correción de errores, podría terminar despilfarrando ancho de banda. Si el nodo toma toda la señal y no reduce su representación, entonces podría estar usando mucha energía para transitar ruido”, dice ella. “La pregunta es, ¿cuánto del ruido remuevo, y cuánto dejo?”.
En su primer artículo, Médard y sus colegas analizan el caso en el que el ruido en un vínculo dado no está relacionado a las señales viajando sobre otros vínculos, como sucede con la mayoría de las redes cableadas. En ese caso, mostraron los investigadores, los problemas de corrección de error y la codificación de red pueden ser separados sin limitar la capacidad de la red entera.
Vecinos ruidosos
En el segundo artículo, los investigadores abordan un caso en el que el ruido en un vínculo dado está relacionado a las señales en los otros vínculos, como es el caso de la mayoría de las redes inalámbricas, ya que las transmisiones de estaciones base vecinas pueden interferir una con la otra. Esto complica las cosas enormemente: En efecto, Médard apunta, los teóricos de la información aún no saben como cuantificar la capacidad de una simple red inalámbrica de tres nodos, en la que dos nodos se envían mensajes uno al otro por medio de un tercer nodo.
No obstante, Médard y sus colegas muestran ahora cómo calcular los límites superior e inferior en la capacidad de una red inalámbrica dada. Mientras que la brecha entre los límites puede ser muy grande en la práctica, conocer los límites todavía podría ayudar a los operadores de redes a evaluar los beneficios de investigación futura sobre codificación de red. Si la tasa de transferencia observada en una red en el mundo real está por debajo del límite inferior, el operador conoce la mínima mejora que el código ideal proveería; si la tasa de transferencia observada está por encima del límite inferior y por debajo del límite superior, entonces el operador conoce la máxima mejora que el código ideal podría proveer. Incluso si la máxima mejora solo traería un pequeño ahorro en los gastos operacionales, el operador podría decidir que investigación adicional en codificación mejorada no vale el dinero.
“El teorema de separación que ellos probaron es de interés fundamental”, dice Raymond Yeung, un profesor de ingeniería de información y co-director del Instituto de Codificación de Red en la Universidad China de Hong Kong. “Mientras que el resultado en sí mismo no es sorprendente, es algo inesperado que pudieron probar el resultado en un ajuste tan general”.
Yeung advierte, sin embargo, que mientras que los investigadores han “descompuesto un problema muy difícil en dos”, uno de esos problemas “sigue siendo muy difícil. … El límite en términos de la solución a otro problema que es difícil de resolver”, dice. “No está claro que tan ajustado es este límite; eso necesita investigación adicional”.
Reimpreso con permiso de MIT News.
Fuente
http://web.mit.edu/ (en inglés)