Laboratorio. Mecanismos de control de congestión

Para esta entrega se nos pidió buscar un artículo académico sobre mecanismos de control de congestión en TCP/IP, video streaming, VoIP o algún otro protocolo. Yo encontré este artículo: Congestion Control and Traffic Management in ATM Networks: Recent Advances and A Survey, realizado por Raj Jain.

Para comprender un poco mejor el Modo de Transferencia Asíncrona o Asynchronous Transfer Mode (ATM) es una tecnología de telecomunicación desarrollada para hacer frente a la gran demanda de capacidad de transmisión para servicios y aplicaciones.[Wikipedia].

Este artículo fue realizado en 1996 por lo que mucho de lo que voy a mencionar puede que ya esté realizado o implementado pero es interesante conocer como las personas ya preveían un mundo como el que tenemos ahora.

Se esperaba que las futuras redes de alta velocidad para utilizar el modo de transferencia asíncrono ATM en el que se transmite la información a través de celdas de tamaño corto las cuales constan de 48 bytes de carga útil y 5 bytes de cabecera. El tamaño fijo de las celdas reduce la varianza de retardo haciendo las redes adecuadas para el tráfico integrado que consta de voz, vídeo y datos. La gestión adecuada del tráfico ayuda a garantizar un funcionamiento eficiente y equitativo de las redes, a pesar de la constante demanda variable. Esto es particularmente importante para el tráfico de datos que tiene muy poca previsibilidad y, por lo tanto, no se puede reservar recursos de antemano como en el caso de las redes de telecomunicaciones de voz.

La gestión del tráfico se ocupa de garantizar que los usuarios obtienen la calidad de servicio que desean. El problema es especialmente difícil durante los períodos de carga pesada sobre todo si las demandas de tráfico no se puede predecir de antemano.

Control de congestión es fundamental tanto en redes no ATM y ATM. Cuando dos ráfagas de tráfico llegan simultáneamente en un nodo, la cola llega a crecer muy rápido lo que resulta en un desbordamiento del búfer.

Las redes ATM son orientadas a la conexión, en el sentido de que antes de que dos sistemas puedan comunicarse, deben informar a todos los switches intermedios acerca de sus necesidades de servicio y parámetros del tráfico. Las conexiones permiten a la red garantizar calidad del servicio al limitar el número de circuitos virtuales (por donde viajará la información). Por lo general, el usuario declara requisitos de servicio clave en el momento que se establece la conexión, declara los parámetros de tráfico y puede estar de acuerdo con el control de estos parámetros de forma dinámica a medida tal como lo pide la red.

Para una conexión en redes ATM, los usuarios pueden especificar los siguientes parámetros relacionados con las características de tráfico de entrada y de la calidad de servicio que desean:

• Peak Cell Rate (PCR): La velocidad máxima instantánea en la que el usuario se transmitir.
• Sustained Cell Rate (SCR): velocidad promedio durante un largo intervalo.
• Cell lost rate (CLR): El porcentaje de celdas que se pierden en la red debido a un error y la congestión y no se entrega al destino. Cada celda tiene un bit en su cabecera el cual dice la prioridad de pérdida de celda (CLP). Durante una congestión, la red pierde primero las células que tienen el bit CLP.
• Cell Transfer Delay (CTD):  es el retraso experimentado por una celda entre la entrada de la red y los puntos de salida.
• Cell Delay Variation (CDV): Alta variación implica búfer mayor para el tráfico sensible al retardo, como voz y vídeo.
• Cell Delay Variation Tolerance (CDVT) and Burst Tolerance (BT): para las fuentes de transmisión, de cualquier velocidad, se permite una ligera variación en el tiempo entre las celdas.
• Maximum Burst Size (MBS): El número máximo de celdas de respaldo que se pueden enviar cuando hay un pico de velocidad, pero sin violar la velocidad de celdas promedio.
• Minimum Cell Rate (MCR) : Es la velocidad mínima deseada por el usuario.

Métodos de control de congestión.

Una congestión sucede siempre que la velocidad de entrada es mayor que la capacidad de enlace disponible. La mayoría de los sistemas de control de la congestión consisten en ajustar las tasas de entrada para que coincida con la capacidad del enlace.

El mejor método para las redes que están casi siempre congestionadas es instalar conexiones de mayor velocidad y rediseñar la topología para que coincida con el patrón de la demanda.

Para redes con congestión esporádica, un método consiste en enrutar por nivel de carga de enlaces y en rechazar nuevas conexiones si todos los caminos están altamente cargados. Esto se conoce como conexión de control de admisión "CAC".

Para redes donde la congestión tiene una duración menor que la conexión, un esquema punto a punto puede ser utilizado.

GCRA.

Uno de los algoritmos utilizados para ajustar la velocidad de entrada es el GCRA (Generalized Cell Rate Algorithm). Lo que hace este algoritmo es poner en un "cubo"y lo va vaciando a una velocidad establecida. Las celdas que no caben o no son admitidas en este cubo y cuando con admitidas el bit CLP es cambiado para que en caso de que se llene el cubo, éstas serán las primeras en ser retiradas.

Retroalimentación.

La tarjeta de interfaz de red que utilizaban en este tipo de redes permite dos tipos de retroalimentación:

• GFC (Generalized Flow Control)
• EFCT (Explicit Forward Congestion Indication)

Cabecera de una celda ATM

Los switches utilizan el bit que indica el tipo de payload para convertir la información a una forma binaria. Cuando el primer bit de este campo es 0, el segundo bit es tratado como una indicación de que podrá ocurrir una congestión. Los destinos pueden monitorear los bits EFCT y avisar a las fuentes de aumentar o reducir su velocidad de envío.

Escalabilidad.

Como las redes ATM fueron creadas para cubrir grandes cantidades de nodos y distintos tipos de velocidad, es necesesario que utilizen un esquema que no se encuentre limitado a solo un rango de velocidad, número de switches o a un número de switches. Esto para asegurar que estas redes puedan utilizarse tanto para WAN's como para LAN's.

Optimización.

En un ambiente donde se comparte este tipo de red el throughput de una fuente depende de de lo que demanden otras fuentes. El criterio más común para compartir correctamente el ancho de banda se utiliza el método conocido como "max-min allocation", lo que hace este método es asignar el mayor ancho de banda posible a la fuente que está recibiendo la menor cantidad de banda.

Robustez.

El esquema que utiliza este tipo de redes no es sensible a desviaciones, por ejemplo algún cambio o mal parámetro o pérdida de paquetes no provocaría que la red se cayera.

Delay Based Rate Control.

Este método requiere que las fuentes monitoreen el retardo de ida y vuelta, enviando periódicamente celdas de gestión de recursos (RM) que contienen una marca de tiempo (timestamp). Las celdas son devueltas por  el destinatario y la fuente utiliza la marca de tiempo para medir el retardo de ida y vuelta y con esto deducir el nivel de congestión.

Backward Explicit Congestion Notification (BECN).

Este método consiste en switches monitoreando la longitud de su cola y envían una celda RM de vuelta a la fuente si está congestionado. Las fuentes reducen sus tasas de velocidad por la mitad si al recibir la celda está muestra que está congestionado. Si no se reciben celdas BECN dentro de un período de recuperación, la tasa de circuitos virtuales se duplica una vez cada período hasta que se alcanza la tasa máxima.

Fair queueing.

Cada switch implementa espera equitativa en su cola que consiste en el mantenimiento de una cola separada para cada circuito virtual y calculando el tiempo en el que la celda termine su transmisión si las colas fueran atendidas por un algoritmo round-robin de un bit a la vez. Las celdas están programadas para transmitir en este orden el tiempo calculado.

OSU Time-based Congestion Avoidance.

Uno de los esquemas para prevenir la congestión en las redes ATM fue el que desarrollaron Jain, Kalyanaraman y Viswanathan en la Universidad Estatal de Ohio (OSU). Este esquema se componía de switches que medían su ritmo de entrada obteniendo un promedio de velocidad de entrada y se comparaba con una tasa o velocidad  objetivo para calcular el factor de carga actual z:

Esto es,  si el factor de carga (z) es cerca de 1, todos los circuitos virtuales dividen su velocidad de carga por este factor z. Por ejemplo, si el factor de carga es 0,5, todos los circuitos virtuales su tasa en un factor de 0,5, es decir, el doble de sus tasas. En cambio, si el factor de carga es 2, todos los circuitos virtuales reducen a la mitad su tasa de velocidad.

Si el factor de carga es cercano a uno el switch da diferente retroalimentación a la carga insuficiente de fuentes y la sobrecarga fuentes. Para compartir justamente el ancho de banda se hace lo siguiente:

Todas aquellas fuentes cuyas velocidades sean mayores que este factor dividían sus velocidades por:

En cambio, si su velocidad era menor se dividía por:

Ese algoritmo se conoce como Target Utilization Band (TUB).

Este esquema y algoritmo fue el último utilizado en este tipo de redes, de este esquema se derivaron muchas variantes pero todas con la misma base.

Fuente virtual y destino virtual.

Uno de los problemas de la tasa de control de extremo a extremo es que el retardo de ida y vuelta puede ser muy grande. Este problema se resuelve mediante la segmentación de la red en trozos pequeños y dejar que los interruptores actúan como "fuente virtual" yo "destino virtual".

Fuente virtual/Destino virtual

En la imagen el switch A en segmento medio actúa como un destino virtual y devuelve todas las celdas RM recibidas de la fuente como si el switch fuera el destino. El switch B en el mismo segmento actúa como una fuente virtual y genera celdas RM como si se tratara de una fuente.

La segmentación utilizando fuentes virtuales y destinos virtuales reduce el tamaño de los ciclos de retroalimentación. Además, los segmentos intermedios pueden utilizar cualquier esquema de control de la congestión.