|
 |
 | ||||
| ||||||
|
Departamento de Ingeniería en Sistemas de Información | ||||||
|
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.
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.
The Token Bucket Algoritm El anterior algoritmo no permite que
ocurran ráfagas en la red, pero a veces ellas son necesarias. .
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 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.
. 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. Cuando U
sube de algún límite predefinido, la línea de salida es marcada como "warning".
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. 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.
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. 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.
| ||||||
