Optimización del rendimiento de redes inalámbricas multi-salto mediante balanceo de carga considerando interferencias

Resum

Las redes inalámbricas multi-salto (RIMs) son colecciones de nodos autónomos capaces de establecer una red inalámbrica de forma dinámica sin necesidad de una infraestructura previa. Estas redes se caracterizan por el uso de comunicaciones multi-salto en las que, en general, un paquete de datos necesita recorrer múltiples enlaces inalámbricos (saltos) para alcanzar su destino. Las RIMs pueden admitir una topología dinámica y tienen restricciones significativas de recursos, como por ejemplo un canal inalámbrico compartido. Una de las características más interesantes de las RIMs es que permiten desplegar una red de forma sencilla y rápida en un área relativamente extensa. Recientemente, una clase especial de RIMs llamadas Redes Malladas Inalámbricas (RMIs) han atraído mucha atención. En ellas, un subconjunto de nodos llamados enrutadores mesh son estacionarios y pueden formar una red troncal inalámbrica de alta velocidad. Estos nodos pueden equiparse con múltiples interfaces radio para permitir más transmisiones simultáneas usando varios canales de frecuencia no solapados. Se espera que las RMIs sean en un futuro una forma de desplegar una red de área extensa con bajo coste capaz de ofrecer servicios como conectividad a Internet. Uno de los escenarios de aplicación más relevantes para RMIs es por tanto el escenario de acceso a puertas de enlace (gateways en inglés) que pueden estar a varios saltos de un enrutador. En este escenario, la mayoría del tráfico se intercambia entre los enrutadores mesh y las puertas de enlace. En RIMs, los nodos transmiten de forma inalámbrica y comparten el acceso al medio. Enlaces en el mismo dominio de colisiones no pueden transmitir de forma simultánea. La interferencia inalámbrica entre enlaces del mismo dominio de colisiones puede limitar drásticamente la capacidad de la red y ser especialmente devastador para el rendimiento de flujos multi-salto. En estas redes, se pueden distinguir dos tipos fundamentales de interferencia: (i) interferencia intra-flujo, la cual es el resultado de interferencia entre enlaces del mismo camino seguido por un flujo de tráfico, y (ii) interferencia inter-flujo, que se refiere a transmisiones que interfieren de flujos que usan caminos diferentes. Debido a la capacidad limitada de las RIMs, la utilización eficaz de esta capacidad es esencial. El balanceo de carga es una técnica apropiada para optimizar la utilización de recursos, y consiste en distribuir una carga de trabajo a través de múltiples recursos. En una red, esta técnica puede contribuir a un aumento del rendimiento e igualdad de los flujos de tráfico. Para balancear carga en una RIM, es necesario distribuir la carga a través de diferentes dominios de colisiones, reduciendo de esta forma el número de transmisiones en un mismo dominio. Esto se consigue evitando interferencia intra-flujo e inter-flujo. En otras palabras, para balancear carga de forma eficaz son necesarias estrategias que consideran interferencias. Además, ya que el tráfico en una RIM varía con frecuencia y de forma impredecible, es necesario balancear la carga instantánea de la red para obtener un rendimiento óptimo. El balanceo de carga mediante enrutamiento se puede conseguir distribuyendo el tráfico a través de caminos que no interfieren. Si se consideran redes multi-canal, el enrutamiento también debe seleccionar caminos con baja interferencia intra-flujo. La asignación de canales implica asignar canales de transmisión a interfaces radio, lo cual determina el canal usado por un enlace para transmitir. Dos enlaces transmitiendo en canales ortogonales no interfieren. Como el conjunto de radios y canales es finito, la interferencia no puede ser eliminada de forma completa, y una decisión de asignación de canales debe elegir con cuidado qué canales asignar a qué interfaces. La asignación de canales se puede usar para balancear carga, mitigando la interferencia intra-flujo e inter-flujo en regiones sobrecargadas, reduciendo de esta forma las transmisiones simultáneas en dominios de colisión. Esta tesis doctoral propone mecanismos de balanceo de carga considerando interferencias, basados en enrutamiento y, cuando se trate de redes multi-canal, asignación de canales. El diseño de protocolos de red y soluciones sensibles a la carga conlleva un reto importante, debido al problema de evitar inestabilidad de la red. La carga puede variar con frecuencia, y esto puede llevar a diversos problemas como sobrecarga alta para comunicar actualizaciones del estado de carga a través de la red, comportamiento no-convergente del protocolo, o inestabilidad de la solución. Si un protocolo no puede converger a tiempo bajo cambios frecuentes de tráfico, puede perturbar la operación de la red. Desde la perspectiva del enrutamiento, la sensibilidad a la carga puede llevar a inestabilidad de las rutas (oscilaciones frecuentes de rutas), no-convergencia o convergencia lenta, y sobrecarga alta para comunicar actualizaciones de rutas en la red. De forma similar, un protocolo de asignación de canales debe garantizar una asignación estable. Si las condiciones de tráfico no varían o lo hacen de forma mínima, el protocolo debe mantener una asignación estable. Además, debe garantizar un tiempo bajo de convergencia, reducir la sobrecarga necesaria para la coordinación entre nodos, y evitar reajustes de canal frecuentes e innecesarios que introducen latencia. En redes de un solo canal, es posible balancear la carga usando enrutamiento que evite o mitigue la interferencia inter-flujo. Medir interferencia entre enlaces, sin embargo, no es trivial, y una alternativa más fácil consiste en estimar interferencia basándose en la distancia entre nodos. Este trabajo desarrolla la métrica Path Spatial Distance (PSD) que mide la separación espacial entre un camino y un conjunto de nodos. Uno de los objetivos principales de PSD es ayudar a una solución de enrutamiento a seleccionar caminos que no interfieren. Una ventaja importante de la métrica es que no requiere información de localización de nodos (como coordenadas geográficas) sino que sólo necesita conocer la distancia en saltos entre nodos. Se demuestra que esta distancia tiene una fuerte correlación con la distancia Euclídea en muchos escenarios de red, con lo que proporciona una estimación buena de la distancia entre nodos en el espacio. Basándose en la métrica PSD, este trabajo propone un algoritmo heurístico, llamado Spatially Disjoint Path Calculation algorithm (SD-PCA), para encontrar dos caminos con máxima separación espacial que conectan a dos nodos de un grafo. Un nodo de la red con conocimiento del grafo topológico usa SD-PCA para encontrar caminos separados espacialmente hacia un destino. Basado en lo anterior, se desarrolla un protocolo multi-camino reactivo para RIMs, llamado Spatially Disjoint Multipath Routing (SDMR), que permite a un nodo descubrir el grafo topológico bajo demanda (es decir, sólo cuando las rutas son necesarias) y, usando el algoritmo SD-PCA, calcular un par de caminos separados espacialmente hacia un destino. El uso de caminos separados espacialmente puede proporcionar otros beneficios adicionales en RIMs además de la reducción de interferencia, incluyendo tolerancia a fallos en situaciones de fallo regional, y seguridad adicional mediante la distribución de una transmisión a través de caminos separados espacialmente para evitar intercepción. Resultados de simulaciones muestran que SDMR puede descubrir la topología bajo demanda de forma eficaz, requiriendo menos sobrecarga de control en comparación con OLSR. Además, los resultados muestran que, usando la métrica PSD y el algoritmo SD-PCA, el protocolo descubre caminos con alta separación espacial, a diferencia de otros protocolos multi-camino como AOMDV. En el escenario de acceso a puertas de enlace en RMIs, la mayoría del tráfico va dirigido a/desde las puertas de enlace. El conjunto de nodos (o alternativamente flujos) al que sirve una puerta de enlace se conoce como su dominio. En redes de un solo canal, no es posible balancear la carga de forma adecuada dentro del dominio de una puerta de enlace, porque cada flujo del dominio compite por acceso en la zona que rodea la puerta de enlace. Esta región representa un cuello de botella inevitable. Si la red tiene múltiples puertas de enlace, es sin embargo posible balancear la carga entre ellas. En otras palabras, la carga de la red se puede balancear asignando tráfico dinámicamente a puertas de enlace. Es importante balancear carga entre puertas de enlace para evitar regiones sobre-utilizadas y regiones infra-utilizadas. Se puede dar fácilmente un desbalanceo de carga debido a numerosos factores, incluyendo demandas de tráfico heterogéneas, tráfico variable en el tiempo, y un número desigual de nodos servidos por las puertas de enlace. Esto puede llevar al uso ineficiente de la capacidad de la red, degradación del rendimiento y desigualdad entre flujos de diferentes dominios. Por otro lado, un balanceo de carga arbitrario puede perjudicar el rendimiento. La asociación de nodos a puertas de enlaces se debe elegir con cuidado, para evitar interferencia grave intra-flujo e inter-flujo. Este trabajo propone un sistema de selección de puertas de enlace centralizado para RMIs llamado Gateway Load-Balancing (GWLB) que, dadas las condiciones actuales de la red, selecciona puertas de enlace de forma eficiente para cada nodo o flujo. GWLB es un algoritmo en-línea que balancea la carga instantánea y al mismo tiempo evita la inestabilidad de la red. La solución no sufre problemas de convergencia ya que se calcula de forma centralizada. La inestabilidad de la selección de puertas de enlace no ocurre, porque es fácil impedir que un nodo cambie de puerta de enlace hasta que transcurra un tiempo. GWLB no introduce ninguna sobrecarga para determinar la carga actual y responde con prontitud, gracias al hecho de que la solución se puede recalcular de forma periódica con una frecuencia muy alta. Para impedir balanceo de carga perjudicial debido a interferencias graves, GWLB tiene en cuenta la interferencia potencial generada por la selección de puertas de enlace usando la métrica PSD, basándose en conocimiento de la topología de red. Otra ventaja importante de GWLB es que balancea tráfico a nivel de flujos TCP, y por tanto mejora el rendimiento e igualdad de los flujos. Por todas estas razones, es válido para implementación en escenarios de RMI prácticos y dinámicos. Hemos demostrado mediante numerosos experimentos que GWLB puede balancear carga eficazmente entre puertas de enlace mientras evita el uso de caminos perjudiciales. Las simulaciones llevadas a cabo en ns-3 demuestran la eficacia de GWLB, y su ventaja sobre propuestas anteriores. En particular, puede alcanzar un incremento en la tasa media de datos de un 128% sobre la estrategia de la puerta de enlace más cercana. GWLB se distancia de otras soluciones de manera notable cuando la congestión o desbalanceo entre dominios aumenta. En RMIs multi-radio multi-canal, los nodos disponen de múltiples interfaces radio, cada una de las cuales se puede sintonizar a uno de varios canales de frecuencia no solapados. Esto proporciona un aumento sustancial en las opciones de balanceo en el escenario de acceso a puertas de enlace. La asignación de canales permite eliminar o mitigar interferencia en la región que rodea a una puerta de enlace, haciendo posible balancear carga dentro de su dominio. En este escenario, se puede balancear carga mediante enrutamiento dentro del dominio a través de la selección de caminos con baja interferencia intra-flujo e inter-flujo. Por otro lado, la asignación de canales se puede usar para dar más capacidad a los enlaces que llevan más tráfico. Lo anterior determina que haya una interdependencia entre enrutamiento y asignación de canales y, cuando son optimizados de forma conjunta, es posible mejorar de forma notable la utilización de la red y el rendimiento e igualdad de los flujos. Este trabajo propone el sistema Load-Balancing and Channel Assignment (LBCA) para RMIs multi-radio multi-canal. LBCA realiza enrutamiento y asignación de canales para optimizar el rendimiento de un conjunto de flujos TCP servidos por una puerta de enlace, dentro de la RMI. LBCA es un sistema centralizado que, dadas las condiciones de red y tráfico actuales, asigna canales a interfaces radio y asigna una ruta a cada flujo. El sistema es capaz de adaptarse rápidamente a condiciones cambiantes, y evitar inestabilidad de la red. La solución de LBCA converge, y lo hace rápidamente, gracias a la baja complejidad temporal de los algoritmos propuestos de enrutamiento y asignación de canales. La inestabilidad de rutas no ocurre porque es fácil impedir que un flujo cambie de rutas hasta que transcurra un tiempo determinado. De forma similar, para impedir el reajuste frecuente de canales, el algoritmo propuesto tiene en cuenta explícitamente la asignación previa de canales para calcular una nueva, de tal forma que limita el número de reajustes de canal. Este trabajo muestra que la re-asignación de canales con un periodo de pocos segundos es posible en escenarios de acceso a puerta de enlace. Para difundir la asignación de canales, LBCA implementa un protocolo novedoso que rápidamente distribuye mensajes de cambio de canal a través de la red con baja sobrecarga. Este protocolo de distribución no requiere una interfaz de cada nodo sintonizada a un canal común, a diferencia de otros protocolos existentes. Hemos mostrado mediante abundantes evaluaciones la eficacia de LBCA. Hemos llevado a cabo simulaciones en ns-3 con un periodo de adaptación de un segundo, mostrando que el protocolo puede adaptarse con frecuencia muy alta. Los experimentos muestran que la re-asignación de canales sólo afecta a entre el 25% y 50% de los enlaces. Esto significa que adaptarse a condiciones de tráfico variables sólo requiere re-ajustar el canal de un número limitado de enlaces. Cuando se realiza enrutamiento y asignación de canales conjunto, los resultados en escenarios estáticos muestran un aumento de la tasa mínima de los flujos de hasta un 84% y tasa media de hasta un 37% en comparación con una estrategia de camino más corto y una asignación de canales que no tiene en cuenta el tráfico. LBCA es por tanto eficaz impidiendo la inanición de los flujos y aumentando la igualdad. En escenarios dinámicos, la ventaja de LBCA es aún mayor. Se muestra que la frecuencia de adaptación es un factor determinante en escenarios altamente dinámicos. Con un periodo de adaptación de un segundo, los resultados muestran un aumento de la tasa mínima de los flujos de hasta 175% comparado con LBCA con un periodo de adaptación de treinta segundos, y un aumento de la tasa media de hasta 63%. La duración de los flujos con un periodo de treinta segundos es hasta 164% mayor.