[REDES DE TELECOMUNICACIONES] Lab 7: Resumen de mecanismos de control de congestión

Hop-by-hop Congestion Control over a Wireless Multi-hop Network

Yung Yi and Sanjay Shakkottai    

Link al paper: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp&arnumber=1354675

Este paper se enfoca en el control de congestión sobre redes multisalto inalámbricas. Una restricción importante en las redes inalámbricas surge debido a la capa de Control de Acceso a Medios (MAC). Muchas MAC's inalámbricas usan una estrategia de división de tiempo para acceso de canal, donde, en cualquier punto del espacio, el canal físico puede accederse por un simple usuario en cada instante.

En el paper se habla del desarrollo de un mecanismo de control de congestión de "salto por salto" con esa restricción de las MAC's siendo impuesta en la forma de una restricción de acceso a canal.

1. Introducción

Se considera el problema de congestión sobre redes multisalto inalámbricas. Los nodos están radio-equipados y se comunican vía broadcasting. Las vías de comunicación entre nodos que no están en el rango de radio están establecidas por nodos intermedios actuando como relevadores para transmitir la información hacia atrás o adelante.

Los años pasados, el problema de control de congestión ha recibido atención, tanto en el contexto de Internet como en redes locales. La mayor parte de esta investigación está enfocada en el modelado, análisis, desarrollo de algoritmo de esquemas extremo-a-extremo y la adaptación de esos esquemas redes ad-hoc.

Los esquemas de salto a salto requieren tener mantenimiento de estado por flujo en nodos intermedios, que son los que general problemas de escalabilidad. Como sea, en una red inalámbrica, el número de flujos por nodo es mas pequeño que en el Internet.Normalmente las redes inalámbricas tienen colas de flujo por nodo.

2. Principales aportes

Los principales aportes en el paper son:

Desarrollo de algoritmos de control de congestión proporcionales (tanto para esquemas salto-a-salto como extremo-a-extremo) aprovechando la restricción MAC siendo impuesta a los canales de acceso.

Se considera la evolución de esos algoritmos en la presencia de propagación de delay. Se demuestra analíticamente el efecto de propagación espacial, derivando explícitamente la reducción de la sobrecarga de buffer bajo el esquema salto-a-salto para un árbol de redes.

3. Modelo del sistema

Se considera una red con un set de "L" links, un set de "V" vértices y "cl" será la capacidad finita de un link "l" para "l" ∈ "L". Cada vértice corresponde a una secuencia ordenada de links "l" ∈ "L", y se denota "R" como un set de posibles sesiones. Así, se modela un link inalámbrico entre cualquiera de 2 nodos en la red para tener una capacidad finita positiva.

En la realidad, los canales inalámbricos son de tiempo variable, cada uno con un promedio de capacidad que dependerá del esquema de la capa física. En el paper se modela con links de capacidad constante, aún así este modelo es muy acertado.

A todo esto, hay 2 tipos de restricciones impuestas, llamadas "Restricción de link" y "Restricción de tiempo".

La restricción de link corresponde al hecho de que la suma de promedios de tiempo de todas las sesiones no es mayor a "cl", la capacidad del link "l".

La restricción de tiempo significa que a cualquier momento de tiempo, solo puede haber una instancia de comunicación en un nodo dado.

Se ilustra un ejemplo de 3 sesiones S1, S2 y S3, cada una de ellas atravesando 2 links. "xi" es el promedio de datos para i = 1,2,3. Se observa que la restricción de tiempo es impuesta en cada nodo en la red.

4. Algoritmo salto-a-salto distribuido

En esta sección se desarrolla un algoritmo para el control de congestión. Primero se observó que el controlador de congestión en la fuente de cada sesión reacciona basado en la suma de la congestión de cada nodo. En lugar de pasar el feedback hacia abajo como en un esquema extremo-a-extremo, se puede prever un esquema donde cada nodo pasa una suma parcial hacia arriba. En otras palabras, cada nodo agrega su costo de congestión recibido de los nodos bajos.

En la siguiente figura es ilustra el algoritmo:

La idea básica es que cada nodo en el camino de la sesión opere su propio algoritmo de congestión. En el algoritmo, se puede sumar todos los costos de congestionamiento sobre la sesión. Así que cada nodo opera (por flujo) un controlador basado en la congestión percibida debido a los nodos bajos, y determinan el radio máximo que pueden transmitir.

Heurísticamente, las pruebas de convergencia son válidas incluso cuando un limite es usado debido al radio de transmisión de datos dentro de la red es gobernado por la fuente.

5. Propagación espacial

Ahora se deriva el tamaño de buffer de pico con el controlador de extremo-a-extremo, así como el controlador salto-a-salto.

Se considera la evolución de estos algoritmos en la presencia de la propagación de delay. Analíticamente se muestra el efecto de la propagación espacial, derivando la reducción de la sobrecarga del buffer pico sobre un esquema salto-a-salto.

Se asume que los links intermedios están bien provisionados, asi que si ocurre un congestionamiento, solo ocurrirá en el punto de acceso común para todos los flujos.

6. Resultados de simulación


Se presentan resultados de simulaciones que comparan el algoritmo salto-a-salto con extremo-a-extremo. Se muestra que hay un pico de carga que decrece con el algoritmo de salto-a-salto.

Se usó una topología de N = 5 y L = 5, osea, una red de 5 saltos y 5 sesiones. Cada nodo con capacidad 40, Por lo que hay un equilibrio de 20 bajo la restricción de tiempo. El delay del salto es de 4 unidades, la propagación de delay es D = 20 unidades.

En la grafica 5 se muestra los radios de control, en la 6 se muestra como el pico decrementa para el esquema de salto-a-salto cuando inician los congestionamientos, a diferencia de el esquema extremo-a-extremo que aumenta.

7. Conclusiones

Por lo visto en el paper, se ve que realmente hay una mejora con respecto a los esquemas extremo-a-extremo, sin embargo estos resultados, aunque positivos, muestran mejoras solo en ambientes inalámbricos, pero puede mejorarse para funcionar en otros ambientes.

Se menciona que se busca la implementación sobre la Internet, pero aún está en fase de experimentación.