En este apartado trataremos el tema de la congestión de las redes. Comenzaremos haciendo una distinción entre control de flujo y control de congestión:

Control de flujo.

Es una técnica que permite sincronizar el envío de información entre dos entidades que producen/procesan la misma a distintas velocidades. Por ejemplo, supongamos el caso representado en la siguiente figura:

Figura 10 Conexión entre nodo de alta capacidad y PC

nodo conectado con PC

En este caso, dada la gran velocidad a la que produce y envía información, el nodo desborda al PC, por lo que éste debe enviar información de control (control de flujo) para que el nodo reduzca su tasa de envío de datos. De esta forma , parando a la fuente cada cierto tiempo, el PC puede procesar el tráfico que le envía el nodo.

Control de congestión.

Es un concepto más amplio que el control de flujo. Comprende todo un conjunto de técnicas para detectar y corregir los problemas que surgen cuando no todo el tráfico ofrecido a una red puede ser cursado, con los requerimientos de retardo, u otros, necesarios desde el punto de vista de la calidad del servicio. Por tanto, es un concepto global, que involucra a toda la red, y no sólo a un remitente y un destinatario de información, como es el caso del control de flujo.

Figura 11 Congestión en un nodo

congestión en un nodo

El control de flujo es una más de las técnicas para combatir la congestión. Se consigue con ella parar a aquellas fuentes que vierten a la red un tráfico excesivo. Sin embargo, como veremos, hay otros mecanismos. Una vez hecha esta distinción, en los sucesivos apartados veremos características del retardo y del caudal, veremos distintas causas de aparición de congestión, analizaremos las soluciones que se proponen para este problema y acabaremos viendo distintos algoritmos de control de congestión.

Características del retardo y caudal.

El caudal depende del tipo de red y tiene un valor nominal máximo, que no podremos superar en ningún caso. Pero además, la red no ofrece el mismo caudal real si se le ofrece poco tráfico o si se le ofrece mucho. Veamos la siguiente figura:

Figura 12 Caudal en función del tráfico ofrecido

La curva (1) representa el comportamiento ideal de la red: hay linealidad hasta llegar a la capacidad nominal de la red, momento en el que el tráfico cursado se satura. La curva (2) representa el comportamiento real típìco de una red. Como puede observarse, al llegar a la zona de saturación, cuanto más tráfico se ofrece menos tráfico se cursa. Esto es debido, por ejemplo, a que los paquetes tardarán mucho tiempo en llega r a su destino, y mientras tanto serán retransmitidos por la fuente, pensando que se han perdido por el camino. Esto, a su vez, origina una explosión de tráfico, ya que cada paquete es retransmitido varias veces, hasta que consigue llegar a tiempo al destino.

Para evitar esa degradación, se introduce el control de congestión que trata de aproximar el comportamiento de la red al dado por la curva (3), evitando así entrar en una zona de degradación.

El retardo de tránsito en la red sigue la siguiente curva:

Figura 13 Retardo de tránsito en función del tráfico ofrecido

Vemos que el retardo no aumenta linealmente, sino que el aumento de éste es mayor que el aumento de tráfico ofrecido.

Causas de la congestión.

Hay varias causas de congestión. Enumeraremos aquí las más importantes:

Memoria insuficiente de los conmutadores. Por ejemplo, veamos la siguiente figura:

Figura 14 Saturación del buffer de un nodo

En ella se tiene un conmutador en el que tres líneas de entrada mandan paquetes a una de salida. Así puede llenarse el buffer (cola) de la línea de salida.

Además, si hay congestión en otros nodos, las colas no liberan la información de los paquetes transmitidos (que se guarda por si hay que retransmitir), con lo que la situación empeora aún más.

Insuficiente CPU en los nodos. Puede que el nodo sea incapaz de procesar toda la información que le llega, con lo que hará que se saturen las colas.

Velocidad insuficiente de las líneas. Se tiene el mismo problema que en el caso anterior.

Soluciones. Mecanismos de control de congestión.

El problema del control de congestión puede enfocarse matemáticamente desde el punto de vista de la teoría de control de procesos, y según esto pueden proponerse soluciones en bucle abierto y en bucle cerrado.

Soluciones en bucle abierto.

También llamadas soluciones pasivas. Combaten la congestión de las redes mediante un adecuado diseño de las mismas. Existen múltiples variables con l as que el diseñador puede jugar a la hora de diseñar la red. Estas variables influirán en el comportamiento de la red frente a la congestión. Las resumiremos en función del nivel del modelo OSI al que hacen referencia:

Nivel	Variable de diseño
Enlace	Diseño de temporizadores y política de retransmisiones: Cuando los temporizadores agotan su cuenta, los paquetes afectados serán retransmitidos por la fuente. Si este tiempo es muy pequeño, habrá gran cantidad de retransmisiones. Por el contrario, si es grande, habrá menos congestión, pero el retardo medio aumentará. Además, podemos controlar lo que se retransmite cuando el temporizador se agota (por ejemplo, cuando un paquete es sólo una porción de un mensaje , puede retransmitirse el mensaje entero o sólo el paquete afectado). Política de descartes y almacenamiento de paquetes que llegan fuera de orden: El rechazo puede ser simple, que origina más retransmisiones, o bien selectivo, obligando a un almacenamiento temporal de los paquetes que llegan fuera de orden y mejorando la congestión. Política de asentimientos: El piggybacking, o utilización de parte de un paquete de datos para enviar asentimientos de paquetes anteriormente recibidos, reduce, en principio, el tráfico, pero puede dar lugar a retransmisiones que contribuyan a la congestión. Política de control de flujo: Parando a una fuente que vierte mucho tráfico podemos reducir el riesgo de congestión.
Red	Circuitos Virtuales frente a datagramas: Muchos algoritmos de control de congestión funcionan sólo en modo circuito virtual. Política de colas y de servicio: Los router pueden diseñarse con una cola por línea de entrada, una cola por línea de salida, o ambos. Además, puede jugarse con el orden en que los paquetes son procesados, dan do más prioridad a los paquetes de control, que contienen información útil desde el punto de vista de la congestión. Política de descarte de paquetes: De nuevo, la correcta elección de los paquetes que se descartan puede disminuir el riesgo de congestión. Algoritmo de enrutamiento: Es bueno desde el punto de vista de la congestión el balanceo del tráfico entre todas las líneas de la red. Tiempo de vida de los paquetes: La correcta elección de esta variable permite reducir el número de retransmisiones, mejorando así el comportamiento de la red desde el punto de vista de la congestión.
Transporte	Análogo al nivel de enlace, pero entre sistemas finales.

Soluciones en bucle cerrado.

También llamadas soluciones activas. Actúan cuando se detectan problemas. Tienen tres fases:

Monitorización de parámetros.

Reacción: envío de información a los puntos necesarios.

Ajuste del sistema.

El mecanismo que permite la reacción del sistema frente a estos problemas puede ser:

Realimentación explícita.

Los nodos próximos a saturarse envían información hacia atrás comunicando esta situación.

Realimentación implícita.

La permiten los mecanismos de asentimiento de la red. Por ejemplo, IP realiza realimentación implícita midiendo el tiempo que tarda en llegar el paquete de asentimiento a una transmisión.

Algoritmos de control de congestión.

Veremos un algoritmo en bucle abierto llamado mecanismo de Traffic Shaping y dos algoritmos en bucle cerrado llamados algoritmo de paquetes regulador es y algoritmo de descarte de paquetes.

Mecanismo de Traffic Shaping.

Significa conformado de tráfico. Es un mecanismo en bucle abierto. Conforma el tráfico que una fuente puede inyectar a la red. Se usa en redes ATM (Asynchronous Transfer Mode; tecnología de red orientada a conexión; en estas redes, la velocidad de línea es de 155 Mbps y el usuario puede ver una velocidad de unos 10 Mbps.

Si se tiene una ráfaga lista para transmitir, el sistema obliga a no transmitir todo seguido (conforma el tráfico). Requiere un acuerdo entre proveedor y cliente: el proveedor garantiza que se cursa el tráfico si se transmite a una tasa determinada y tira el tráfico si se supera. Esto lo realiza mediante una función policía, que es un nodo que tira los paquetes que superan la tasa contratada a la entrada de la red (no se tiran una vez que ya ha entrado). Esto puede realizarse mediante un algoritmo de Leaky Bucket, cuyo nombre se debe a que es como si tuviéramos un bidón que vamos llenando con un caudal determinado y por el que sale el líquido (Leaky: hace aguas) con otro caudal distinto; si llenamos muy deprisa el bidón acabará llenándose y vertiéndose por arriba, lo que asemeja una pérdida de paquetes en una red. Veamos un ejemplo con un sistema codificador de imágenes:

Figura 15 Ejemplo de mecanismo de Leaky Bucket

Este sistema codifica la señal de video y la envía a ráfagas. Para ser transmitida necesita ser conformada: se almacenan muestras en un buffer y después se transmiten a velocidad constante. Si se sobrepasa el caudal predeterminado, pueden tirarse paquetes en el regulador (por parte del usuario) o en la función policía (por parte del proveedor). Este sistema permite aplanar ráfagas, como puede verse en la siguiente figura, donde la situación de la izquierda representa un sistema con tráfico no conformado y la de la derecha la equivalente si se conforma y se contrata transmisión a 2Mbps (la fuente transmite ráfagas de 1 Mb a 25 Mbps):

Figura 16 Ejemplo de aplanamiento de ráfagas con tráfico conformado

Algoritmo de paquetes reguladores.

En terminología inglesa, al paquete regulador se le llama choke packet. Se hace en bucle cerrado. Asocia un peso u a cada línea que cambia con el tiempo según la ecuación:< P

(8)

donde:

u_n: función de peso, que depende del instante actual a través de f y del anterior a través de u_n-1.

f: tiene un valor "0" si no transmitimos en el instante actual o "1" si transmitimos.

a: constante comprendida entre 0 y 1 y que da más importancia al instante actual o al instante anterior según su valor.

Si _n supera un cierto umbral, se pone la línea en estado de alerta y se considera que puede haber congestión. Si llegan paquetes a esa línea, se envía un aviso hacia atrás con un paquete regulador que indica esta situación. Además, en los paquetes que se envían hacia delante se pone un flag a "1" para indicar al resto de los nodos que no manden paquetes reguladores hacia atrás, ya que el nodo origen está avisado. Al llegar el paquete regulador al origen, se reduce el flujo (por ejemplo, a la mitad).

Si pasa un determinado tiempo sin recibir notificaciones de congestión, se vuelve a subir el flujo que puede cursar el origen. Si por el contrario se supera un umbral mayor, se pasa directamente a hacer descarte de paquetes.

Variaciones:

Pueden mandarse paquetes reguladores con información de estado (grave, muy grave, etc.)

En vez de monitorizar las líneas de salida pueden medirse otros parámetros, tales como el tamaño de las colas en los nodos.

Con el mecanismo descrito se tarda mucho en reaccionar. Entonces, puede hacerse regulación salto a salto, en la que se dice al nodo anterior que mande la información por otro sitio si es posible.

Algoritmo de descarte de paquetes.

Es un algoritmo de control de congestión en bucle cerrado. Se basa en que los nodos descartan (tiran) paquetes cuando su ocupación es alta. Para esto los nodos han de conocer sus recursos (CPU y memoria). Hace una asignación dinámica de los buffers en base a las necesidades de cada línea.

Sin embargo, cada línea necesita al menos una (o más) posiciones de memoria para gestionar información relevante, tal como asentimientos, que permite la liberación de posiciones de memoria ocupadas por paquetes que estaban esperando por si necesitaban retransmitirse. Si a la línea llegan datos (no asentiminentos u otra información relevante) y el buffer de salida de la línea correspondiente está lleno, se descarta el paquete. Hay varias formas de hacer la asignación de buffers:

En base al uso. No es muy eficiente, porque cuando una línea se empieza a cargar acapara todos los recursos.

Asignación fija. Tampoco es muy buena, ya que desaprovecha recursos.

Asignación subóptima (de Irland). Llamando k al número de posiciones del buffer y s al número de líneas de salida, se tiene que el número de posiciones de memoria asociadas a cada línea es:

m=k/(s)^1/2

(9)

Bibliografía

http://selva.dit.upm.es/~cd/apuntes

Tanenbaum, Andrew S., Computer Networks, Prentice-Hall, 1996.

Bertsekas, D. y Gallager, R., Data Networks, 2^a edición, Prentice-Hall, 1992.

Comer, Douglas E., Internetworking with TCP/IP, 3^a edición, Volumen 1: Principles, Potocols and Architectures, Prentice-Hall, 1995.