SC: Control de congestión

Transp. 1

Introducción
Se llama congestión al exceso de tráfico en alguna parte de una
red, que da lugar al exceso de demanda de algún recurso (ancho
de banda, memoria, capacidad de procesamiento...)
Síntomas: Aumentan los retardos y las pérdidas.

F1
100 Mbps

C 10 Mbps
D
100 Mbps
F2

Una propiedad típica de la congestión es la realimentación, que

hace que la situación empeore con el paso del tiempo, pues un
nodo congestionado provocará con el tiempo la saturación de los
que envían tráfico hacia él. La consecuencia final de la congestión,
si ésta no es resuelta, es que los nodos entran en una situación
de bloqueo.
Ideal

Capacidad máxima
de la subred
Tráfico entregado

Asintótico

Real

Zona de Zona de
Zona de trabajo Bloqueo o Deadlock
riesgo congestión

Tráfico ofrecido
 SC: Control de congestión
Transp. 2

Consecuencias de la congestión
Retardos: Trabajar cerca de la capacidad de los enlaces es
ideal desde el punto de vista de la productividad, pero no lo
es respecto al retardo. Se experimentan grandes retardos en
una cola según la tasa de llegadas de paquetes se acerca a la
capacidad del enlace.
Pérdidas: Como los búferes no son de tamaño infinito el emi-
sor debe realizar retransmisiones para compensar los paquetes
perdidos debido al desbordamiento de los búferes.
Desperdicio de recursos:
• Las retransmisiones innecesarias realizadas por el emisor
en presencia de grandes retardos, que provocan que venzan
los temporizadores de retransmisión antes de que lleguen
los asentimientos, hacen que el ancho de banda de los en-
laces se utilice para encaminar copias innecesarias de los
paquetes.
• Cuando un paquete es desechado a lo largo de un camino,
la capacidad de almacenamiento, procesamiento y trans-
misión que fue utilizada en cada uno de los nodos y enlaces
anteriores, para encaminar ese paquete hasta el punto en
el que es desechado, está siendo desperdiciada.
 SC: Control de congestión
Transp. 3

Dinámica del control de la congestión

Básicamente se distinguen dos tipos de mecanismos de control
de congestión, atendiendo al momento en el que actúan:
Preventivos: Mecanismos que pretenden prevenir la conges-
tión, denominados de lazo abierto.
• Control de admisión: Se limita el número de usuarios o
flujos.
• Monitotización: Se vigila que un flujo no exceda su cuota
de tráfico.
• Regulación de tráfico: Se modifica el patrón de tráfico a la
entrada de forma que sea más predicible.
Ejemplo: Servicio CBR (Constant Bit Rate) en ATM.
Reactivos: Mecanismos que intentan resolver el problema de
la congestión cuando ésta aparece, denominados de lazo ce-
rrado o con realimentación.
• Realimentación directa: Los nodos de conmutación avisan
a los extremos cuando están congestionados o en peligro
de congestión (envían paquetes especiales o marcan los
paquetes de datos si no los van a descartar). Ejemplo: Ser-
vicio ABR (Available Bit Rate) en ATM.
• Realimentación indirecta: Los extremos infieren la presen-
cia de congestión en la red basándose en las pérdidas o en
los retardos. Ejemplo: Control de congestión en TCP.
 SC: Control de congestión
Transp. 4

Regulación del tráfico

Dado que una de las principales causas de la congestión es que el tráfico
es a ráfagas, los mecanimos de regulación de tráfico fuerzan a las fuentes a
transmitir de forma más predecible. En realidad, lo que se pretende es regular
la tasa media y la variabilidad del tráfico de entrada a la red. Aunque esta
regulación es más fácil de implementar con circuitos virtuales, puede aplicarse
igualmente a redes de datagramas.
A continuación se explican dos algoritmos para regular el tráfico de entra-
da: Leaky Bucket y Token Bucket.

Algoritmo Leaky Bucket

Cada fuente se conecta a la red a través de una interfaz que contiene un

leaky bucket, es decir una cola finita, capaz de almacenar un máximo de C
paquetes, de forma que cualquier paquete que llegue estando la cola llena será
descartado. De esa cola se envían los paquetes a la red a una tasa constante
de ρ pkt/s, independientemente de cuál sea la tasa de llegada al leaky bucket.

Fuente

flujo no regulado

Bucket

flujo regulado

Red
 SC: Control de congestión
Transp. 5

Regulación del tráfico

Algoritmo Token Bucket

El algoritmo Leaky Bucket fuerza a una tasa constante, independiente-

mente de lo variable que sea el tráfico. Para muchas aplicaciones se prefiere,
sin embargo, que para ráfagas cortas esa tasa pueda ser incrementada. Se
necesita un algoritmo más flexible.
En el algoritmo Token Bucket, se añade un bucket que contiene testigos
(tokens), que son generados a una tasa de ρ testigos/s, hasta un máximo de C
testigos, de forma que cada testigo da derecho a transmitir un paquete. Así,
este algoritmo permite ahorrar testigos cuando no hay datos que transmitir,
comportándose de la misma manera que Leaky Bucket cuando siempre hay
datos para transmitir.
Para una ráfaga de longitud S segundos, y si la tasa máxima de salida per-
mitida es de M pkt/s, una ráfaga de salida contendrá como mucho C + ρ · S
paquetes. Por otro lado, el número de paquetes en una ráfaga a velocidad de
salida máxima es M · S.
Por tanto, la duración máxima Smáx de una ráfaga de salida será:

C
C + ρ · Smáx = M · Smáx =⇒ Smáx =
M−ρ

Para suavizar el tráfico de entrada a la red se puede combinar un Leaky

Bucket (de tasa ρ(l) ) tras un Token Bucket (de tasa ρ(t) ), de forma que
ρ(t) < ρ(l) < M.
Regulación del tráfico

Leaky Bucket

Fuente 1 MB cada segundo

25 MBps

C = 1 MB

ρ = 2 MBps

Red

flujo de entrada a la red no regulado

25 MBps

t (ms)
40 ms

flujo de entrada a la red regulado

2 MBps

t (ms)
500 ms
 Regulación del tráfico

Token Bucket

Fuente 1 MB cada segundo

25 MBps

C = 250 KB

M = 25 MBps
ρ = 2 MBps

Red

S= C
M− ρ

10.86 ms − 25 MBps − 271.5 KB

364 ms − 2 MBps − 728.5 KB

flujo de entrada a la red regulado

25 MBps

2 MBps

t (ms)
10.86 ms 375 ms
Regulación del tráfico

Token Bucket + Leaky Bucket

Fuente 1 MB cada segundo

25 MBps

C(t) = 500 KB Token Bucket

ρ (t) = 2 MBps

Leaky Bucket

ρ (l) = 10 MBps

Red

S= C(t)
ρ(l) − ρ(t)

62.5 ms − 10 MBps − 625 KB

187.5 ms − 2 MBps − 375 KB

flujo de entrada a la red regulado

10 MBps

2 MBps

t (ms)
62.5 ms 250 ms
 Control de flujo en TCP
Emisor Receptor

TCP TCP

LastByteWritten LastByteRead

LastByteAck LastByteRcv

LastByteSent NextByteExpected

El emisor mantiene el tamaño de la ventana de recepción,

RcvWindow, que determina la cantidad de paquetes pendientes
de asentimiento que pueden circular por la red.
Siendo RcvBuffer el tamaño del búfer de recepción, LastByteRead
el último byte leído por la aplicación receptora y LastByteRcv el
último byte que ha llegado al búfer del receptor, debe cumplirse:
LastByteRcv − LastByteRead ≤ RcvBuffer
El tamaño de la ventana de recepción se hace igual a la cantidad
de espacio libre en el búfer del receptor:
RcvWindow = RcvBuffer − (LastByteRcv − LastByteRead)
El receptor envía el tamaño de la ventana al emisor cada cierto
tiempo.
Siendo LastByteSent el último byte enviado por el emisor y
LastByteAck el último byte asentido, el emisor debe garantizar:
LastByteSent − LastByteAcked ≤ RcvWindow
 SC: Control de congestión
Transp. 6

Control de congestión en Internet

En Internet, gran parte del peso de control de congestión recae
en TCP. Internet inicialmente no tenía control de congestión en
TCP, los paquetes eran enviados a máxima velocidad y en caso
de pérdida por congestión volvían a ser retransmitidos al vencer
la correspondiente temporización, produciendo más congestión.
El control de congestión fue introducido a finales de los 90 por
Van Jacobson. La idea es que cada fuente determine de cuánta
capacidad dispone en la red, de forma que sepa cuántos paquetes
puede transmitir en cada momento.
Para ello se añade a la ventana de control de flujo, RcvWindow,
la ventana de control de congestión, CongWindow, de forma que
el número de paquetes pendientes de asentimiento en el emisor
no puede exceder el mínimo de las dos ventanas, esto es:
LastByteSend − LastByteAcked ≤ mín [CongWindow, RcvWindow]
Considerando una conexión para la que los retardos y las pérdi-
das sean despreciables, y siendo el tamaño del búfer del receptor
suficientemente grande, se puede ver como que al principio de
cada RTT el emisor puede enviar CongWindow bytes, al final del
RTT ha recibido los asentimientos, y la tasa de envío del emisor
es aproximadamente CongWindow
RTT bytes/s. Ajustando CongWindow
se ajusta la tasa de transmisión.
Para ver cómo un emisor percibe que el camino hasta el destino
está congestionado, se define un evento de pérdida en el emisor
como la ocurrencia de un fin de temporización sin llegada de
asentimiento, o la recepción de tres asentimientos duplicados.
 SC: Control de congestión
Transp. 7

Control de congestión en Internet

La ventana de congestión, y por tanto la tasa de transmisión,
se ajusta cuando se reciben los asentimientos, se incrementa, o
cuando el emisor detecta un evento de pérdida, se decrementa.
Al aumentar los retardos, debido a que se está ofreciendo ca-
da vez más tráfico a la red, la tasa de incremento disminuye,
produciéndose de esta forma el efecto deseado.
El algoritmo de control de congestión de TCP consta de tres
componentes principales: (1) crecimiento aditivo/decrecimiento
multiplicativo, (2) arranque lento y (3) reacción a los eventos de
pérdidas.
Crecimiento aditivo/decrecimiento multiplicativo.
Se aumenta la ventana de congestión en el tamaño de un seg-
mento cada RTT. Para ello, con cada asentimiento recibido,
ha de incrementarse en la cantidad:
MSS
MSS
CongWindow
siendo MSS el máximo tamaño de un segmento.
Cuando se detecta un evento de pérdida se reduce (a MSS o
a la mitad).
Con este mecanismo, el valor de CongWindow pasa por ciclos
en los que se va incrementando linealmente, y de repente se
decrementa, dando lugar a la conocida forma de diente de
sierra para conexiones TCP de larga duración.
 SC: Control de congestión
Transp. 8

Control de congestión en Internet

Arranque lento
Surge para acelerar el crecimiento de la ventana de congestión
cuando su tamaño es muy pequeño, como al principio de una
conexión, en donde se le da típicamente el valor de MSS.
Con este mecanismo, se incrementa la ventana de congestión
en el tamaño de un segmento por cada asentimiento recibido,
lo que da lugar a que doble su valor con cada RTT (creci-
miento exponencial). Se continúa así hasta que se alcanza un
valor objetivo, o se detecta un evento de pérdida.
También se utiliza arranque lento en algunos casos cuando se
detecta un evento de pérdidas.
La denominación de arranque lento, cuando supone un creci-
miento exponencial, es debida a la comparación con TCP sin
control de congestión.
Reacción ante los eventos de pérdidas
Eventos de fin de temporización
Cuando la pérdida se detecta por fin de temporización, se
pone el valor objetivo a la mitad del valor que tiene la ventana
de congestión en ese momento, la ventana de congestión se
inicializa a MSS y se entra en la fase de arranque lento.
 SC: Control de congestión
Transp. 9

Control de congestión en Internet

Eventos de triple ACK duplicado
TCP Tahoe reacciona en ese caso como ante un evento de fin
de temporización.
TCP Reno, basándose en el hecho de que la recepción de
tres asentimientos repetidos significa que otros datos sí que
han llegado al receptor, utiliza un mecanismo de recuperación
rápida. Se pone el valor objetivo a la mitad del valor que
tenga CongWindow en ese momento, el tamaño de la ventana
de congestión se reduce a la mitad, y se entra en la fase de
crecimiento aditivo/decrecimiento multiplicativo.
En la figura se muestran los cambios más significativos de
CongWindow con TCP Reno.

TRIPLE ASENTIMIENTO DUPLICADO FIN DE TEMPORIZACION

45

40

35
Valor objetivo
30
CongWindow (segmentos)

25
Valor objetivo
20

15 Valor objetivo

10

0 2 4 6 8 10 12 14 16 18 20 22 24 26

RTT
 SC: Control de congestión
Transp. 10

Control de congestión en Internet

TCP Vegas

En TCP Vegas los emisores utilizan el RTT para controlar la

congestión, basándose en que cuanto mayor sea, se puede suponer
que la red tiene mayor peligro de congestión.
Se define BaseRTT como el RTT de un paquete cuando el flujo
no está congestionado, y se inicializa al del primer paquete en-
viado en la conexión. Puede verse como el mínimo de todos los
RTTs.
La tasa esperada es:
CongWindow
ExpectedRate =
BaseRTT
Se calcula la tasa de envío real, ActualRate dividiendo el número
de bytes que se transmiten en el tiempo de un RTT por dicho
tiempo, y se ajusta la ventana en consecuencia.
Para ello se calcula:
Diff = ExpectedRate − ActualRate
que es positiva o 0, dado que ActualRate > ExpectedRate implica
actualizar BaseRTT al último RTT.
Se definen dos límites, α < β, de forma que:
si (Diff < α) se incrementa la ventana de congestión lineal-
mente durante el próximo RTT,
si (Diff > β) se decrementa la ventana de congestion lineal-
mente durante el próximo RTT,
si (α ≤ Diff ≤ β) no se cambia la ventana de congestión.
 SC: Control de congestión
Transp. 11

Control de congestión en Internet

RED (Random Early Detection)

Es un algoritmo de control de congestión propuesto para los

nodos de conmutación en Internet, en el que los nodos monito-
rizan la ocupación media de las colas, y en caso de superar un
umbral señalizan con una determinada probabilidad al extremo
emisor de forma implícita, descartándole un paquete.
Se calcula el tamaño medio de la cola como:
AvgLen = (1 − Weight) × AvgLen + Weight × SampleLen
donde 0 < Weight < 1 y SampleLen es la longitud de la cola cuan-
do se hace una medida.
Se establecen dos límites, MinThreshold y MaxThreshold, y cuan-
do llega un paquete se compara AvgLen con esos límites de esta
forma:
si (AvgLen <= MinThreshol) se encola el paquete,
si (MinThreshold < AvgLen < MaxThreshold) se calcula una
probabilidad P y se descarta el paquete con dicha probabili-
dad,
si (MaxThreshold <= AvgLen) se descarta el paquete.
 SC: Control de congestión
Transp. 12

Control de congestión en Internet

P es una función de AvgLen y del tiempo transcurrido desde el
último descarte, de esta forma:

MaxP × (AvgLen − MinThreshold)

TempP =
MaxThreshold − MinThreshol

TempP
P=
1 − count × TempP

TempP

1.0

MaxP

MinThresh MaxThresh AvgLen

count lleva la cuenta de cuantos paquetes se han encolado (no

descartado) mientras AvgLen ha permanecido entre los dos lí-
mites. De esta forma, se consigue una mejor distribución de la
pérdida de paquetes en el tiempo.