Algoritmos para el control de la congestión

 

La congestión se refiere a la presencia en demasía de paquetes en una parte de una subred.

En casos de extrema congestión, los routers comienzan a "rechazar" paquetes, disminuyendo de esta forma el rendimiento del sistema.

Las razones de la congestión son muchas, entre ellas están:

1. Por ejemplo, si por 4 líneas le llega información a un router y todas necesitan la misma línea de salida -> competencia.

2. Insuficiente cantidad de memoria en los routers. Pero añadir más memoria ayuda hasta cierto punto solamente, ya que si tiene demasiada memoria, el tiempo para llegar al primero de la cola puede ser demasiado.

3. Procesadores lentos en los routers. El proceso de "analizar" los paquetes es caro, así que procesadores lentos pueden provocar congestión.

La congestión se propaga a los demás routers…

El control de flujo y el control de la congestión no son lo mismo:

Control de Flujo: se preocupa de que un emisor rápido no sature a un receptor lento.

Control de Congestión: su función es tratar de evitar que se sobrecargue la red.

Las soluciones para el problema de la congestión se pueden dividir en dos clases:

Open Loop: Tratan de resolver el problema con un buen diseño.

Usan algoritmos para decidir cuando aceptar más paquetes, cuando descartarlos, etc. Pero no utilizan el actual estado de la red.

Closed Loop: La solución en este caso se basa en la retroalimentación de la línea.

Por lo general tienen tres partes:

1. Monitorean el sistema para detectar cuándo y dónde ocurre la congestión.

2. Se pasa esta información hacia donde se puedan tomar acciones.

3. Se ajustan los parámetros de operación del sistema para corregir los problemas.

Varias medidas del rendimiento pueden ser usadas para medir la congestión. Las principales medidas que se utilizan son:

* % de paquetes descartados.

* Largo de las colas.

* Número de paquetes que hace "timed out" y/o retransmitidos.

* El promedio del retardo de los paquetes.


La forma en que las "redes" trabajan afectan a la congestión de la red.

 

 

 


Traffic Shaping

Una de las razones principales de la congestión son las ráfagas de paquetes que llegan a la red.

La idea del traffic shaping es hacer que los hosts transmitan la información a una tasa constante.

A continuación se verán algunos algoritmos:

Algoritmo del cubo agujereado

Un cubo agujereado entrega su agua a una tasa constante, la idea de este algoritmo es usar este concepto en las redes.
En este caso cada host es conectado a la red por una interfaz que contiene un cubo agujereado, es decir, una cola finita.
Si un frame llega al cubo cuando está lleno (cola llena) se le descarta.
En este caso, el host sólo puede poner un paquete en la red en cada interalo, formando así un flujo uniforme.
Este algoritmo es bueno para redes que trafican paquetes de tamaño fijo.
En caso de redes con tamaño de paquetes variable, se forman paquetes de tamaño fijo con varios de ellos.


 

 

 


The Token Bucket Algoritm

El anterior algoritmo no permite que ocurran ráfagas en la red, pero a veces ellas son necesarias.
En estos casos se puede cambiar la forma de transmitir a una en la cual los permisos para transmitir se obtienen en base a tokens que se dejan en el cubo.

.


 

 


Especificaciones de Flujo

La idea de esta técnica de control de congestión es que el emisor y la red se ponen de acuerdo acerca de cuáles serán las características del input.

Por ejemplo, algunas medidas que se pueden especificar:

– Máximo tamaño del paquete
– Máxima tasa de transición

Control de la congestión en Redes con circuitos virtuales

Cuando ocurre congestión en una red con circuito virtual se pueden tomar las siguientes acciones para tratar de mejorar el problema:

1. No admitir que más equipos transmitan.

La idea es simple, cuando la congestión ocurre, no se setean más circuitos virtuales. Esto, con el objetivo de evitar interferencias.


2. Eliminar como posibles caminos las áreas donde existe congestión.

.

 

 

3. Negociar algunas medidas del rendimiento de la red.

Esto se puede hacer sólo cuando hay congestión o en todo momento (al inicio de la transmisión).

Choke Packets

Para el funcionamiento de este algoritmo, se supone que cada router puede monitorear la utilización de sus líneas.

Por ejemplo, U puede obtenerse de :

a: variable de tiempo, sirve para determinar cuan rápido se olvida la historia.
f: utilización instantánea de la línea.

Cuando U sube de algún límite predefinido, la línea de salida es marcada como "warning".
Si un paquete nuevo llega para esa línea, se envía un choke packet al host emisor. Este paquete de bloqueo le indica al host que la línea de comunicación hacia ese destino está copada.
Después de recibir esta información, el host disminuye su tráfico en un x % hacia ese destino. Si llegan más paquetes de aviso, lo vuelve a disminuir.
Un problema de este algoritmo es que cada host modifica su comportamiento voluntariamente. Con lo cual host "inescrupulosos" pueden aprovecharse de otros que lo bajen.


Una solución a este problema es agrupar algunas colas (algoritmo con colas justas).
En este caso, el router tiene una cola para cada línea de entrada (se supone que todas compiten por la misma línea). El router, en este caso, transmite un paquete por cola en turno.
Un problema de este algoritmo es que todas las colas tienen la misma prioridad, una solución a esto es agregarle prioridades a las colas.
Un problema de este algoritmo es la demora en la propagación del paquete de bloqueo, como solución se puede pedir que los routers intermedios bajen su carga (lo cual involucra un gasto en buffers).

 


Load Shedding

Aún cuando existen algoritmos de control de congestión, algunas veces es necesario que el router descarte paquetes.

La elección de cuáles paquetes descartar es muy importante:

1. Wine (Vino): Descartar paquetes nuevos.

2. Milk (Leche): Descartar paquetes viejos.

Dependiendo del tipo de aplicación es mejor una o la otra:

Wine -> Transferencia de Archivos

Milk -> Multimedia

Muchas veces, los emisores pueden indicar la importancia de sus paquetes, como por ejemplo ATM.

 

Control de Congestión en Frame Relay

Es posible contratar para cada conexión una calidad de servicio distinta. Dicha calidad está definida mediante ciertos parámetros.

1.      Committed information rate. (CIR) (Tasa de información comprometida). Caudal medio garantizado que la red se compremete a dar en una conexión.

2.      Commited burst size (Bc). (Volumen de información comprometida). Es la máxima cantidad de datos (bits) que la red se compromete a transmitir durante un intervalo de tiempo definido (Tc). Bc = CIR * Tc.

3.      Excess burst size (Be). (Volumen de información en exceso). La máxima cantidad permitida de datos que pueden exceder Bc durante el intervalo de tiempo Tc. La distribución de estos datos (Be),no está garantizada. Aquellos datos que superen Bc+Be se descartan incondicionalmente.

4.      Commited rate measurement interval (Tc). Intervalo de tiempo durante el cual al usuario sólo se le permite transmitir Bc+Be.

El caudal físico (Cf) de la línea de acceso también se contrata. Así el operador dimensiona la red en función de los parámetros contratados por sus abonados.
En el interfaz usuario-red se controla, para cada circuito virtual, que los usuarios se ajusten a los parámetros Bc, y Be que han negociado. Si la red está bien diseñada no debe perder datos que no superen el tráfico comprometido.

Existe un bit en la trama (bit DE) que es activado por la red en tramas que superen Bc (es decir aquellas que pertenezcan a Be) para indicar que esas tramas deberían ser descartadas en preferencia a otras, si es necesario. Un usuario también puede marcar este bit para indicar la importancia relativa de una trama respecto a otras.

En la figura siguiente se puede entender más claramente el significado de los parámetros antes mencionados.

 


FIGURA 4.42 c) Parámetros de transmisión en FR.

 


Se puede observar que el volumen de información (bits) generado por las tramas 1 y 2 se encuentra por debajo del máximo garantizado Be y por tanto se nos garantiza que estas dos tramas serán cursadas por la red sin ningún problema. Con la trama 3, sin embargo, se excede el límite Be, pero sin llegar a la cantidad Be + Bc. La red marca esta trama poniendo su bit DE a '1' lo que indica que si hay que descartar tramas por congestión, esta trama se descartará en preferencia al resto.
Si se diera el caso de transmitir durante todo Tc de forma que con una cuarta trama se sobrepasara Be + Bc, esta trama sería incondicionalmente descartada en el nodo que está conectado al sistema que la ha enviado.

Pregunta:

Ahora nos surge la siguiente pregunta: Manteniendo el CIR, ¿qué le conviene más a un abonado, un Tc grande o pequeño? Al usuario le resulta atractivo que Tc sea muy grande, porque Bc también lo será, y aunque en media se deba mantener la velocidad CIR, está capacitado para enviar ráfagas de datos mayores, pues el límite de datos máximo (Bc) ha aumentado.

Para el operador es conveniente que Tc baje. Con Tc grande, si todos los usuarios deciden mandar simultáneamente ráfagas de tráfico de longitud máxima Bc, podría encontrar problemas para cursar todo el tráfico por la red

Generalmente cuando se envía una trama se desconoce el estado de la red. Tramas por encima de Bc son susceptibles de ser descartadas cuando la congestión de la red aumenta en las rutas que atraviesan dichas tramas. Por ello la red notifica este aumento de la probabilidad de descarte de tramas mediante los bits FECN y BECN. Se requiere que los terminales actúen de forma coherente y reduzcan el tráfico enviado a la red, porque de lo contrario las tramas de usuario que superen Bc están en peligro de ser descartadas en nodos de red congestionados.

Hay que señalar que la congestión es unidireccional, pues puede haber caminos distintos para los dos sentidos de la transmisión y mientras uno puede estar sufriendo problemas de tráfico, el otro puede no tenerlos. Los bits FECN y BECN notifican congestión a los dos extremos de una conexión de la siguiente forma: A una trama que atraviesa una zona congestionada se le pone su bit FECN a '1'. La red identifica las tramas de esa conexión que circulan en sentido contrario y en ellas marca el bit BECN también a '1'.

Pregunta:  ¿ Por qué se notifica al destino la congestión?

Para que sea consciente de que se pueden estar perdiendo tramas que tienen marcado el bit DE a '1', y porque algunos protocolos de niveles superiores tienen capacidad de control de flujo extremo a extremo y pueden tomar medidas al respecto.