TEO03 - Apuntes Congestión PDF

Preview

Summary

Apuntes Congestión...

Description

Mecanismos de control de congestión (control de flujo) de red Cuando se definió e implementó TCP, las redes existentes presentaban como problema principal una baja fiabilidad, es decir, la presencia de errores era la característica limitante del comportamiento eficiente de la red. Las situaciones de congestión de la red, causa principal del deterioro del comportamiento de las redes actuales, no fueron tenidas en cuenta de inicio, y por ello, no se especificó mecanismo alguno para su control. Posteriormente aparecieron nuevas versiones del TCP, por ejemplo, el TCP Tahoe (1988) y el TCP Reno (1990) con sus algoritmos de control de congestión, así como otras versiones posteriores menos utilizadas. Los algoritmos de control de congestión pretenden llegar a transmitir usando al completo la capacidad (desconocida) del canal extremo a extremo de ese momento, esto se consigue cuando: de forma ininterrumpida se inyectan paquetes en la red con la tasa a la que llegan los reconocimientos (ack clock)". Lo cual supone transmitir sin interrupción a la velocidad del canal. Esto es así porque la tasa/cadencia de llegada de los reconocimientos la impone el enlace más lento, que es el que define la capacidad del canal, ver figura de más abajo. El RTT depende de la capacidad del canal, y de otros factores como distancia extremo a extremo.

Estos algoritmos imponen una tasa de transmisión mediante la fijación de un tamaño de ventana de transmisión (de congestión). El tamaño de ventana ideal es igual a la velocidad de transmisión en paquetes/segundo del enlace más lento (ack clock) x RTT. El problema está en que la velocidad de transmisión del enlace más lento es desconocida por variante en el tiempo. Visto al revés, si el tamaño de la ventana impuesto en bytes es cwnd y el tiempo de ida y vuelta es RTT, la tasa de transmisión lograda es: cwnd/RTT. Así, al variar cwnd se consigue variar la tasa de transmisión. Pero en verdad el motivo de encontrar el tamaño adecuado de cwnd es conseguir el propósito enunciado antes, llegar a transmitir de forma ininterrumpida al ritmo marcado por la llegada de ACKs, o lo que es lo mismo, encontrar cuantos segmentos de datos caben en un RTT, espaciados según la cadencia de llegada de ACKs. Cualquier algoritmo de control de congestión debe ser rápido para converger ante cambios en la carga de la red (en la capacidad del canal), así se llegó a la conclusión de que debía tener un comportamiento: AIMD (Additive Increase Multiplicative Decrease):

La señal de congestión usada para reducir el tamaño de cwnd de los algoritmos del TCP es la pérdida de un paquete, pero se podrían utilizar otras señales: variación del RTT, la señal ECN (Explicit Congestion Notification) puesta en el paquete IP por el router congestionado para ser recogida por el receptor para que éste, en el segmento ACK de vuelta ponga la señal: ECE (ECN-Echo) y que el emisor a su vez indique que ha recibido la señal poniendo en su segmento: CWR (Congestion Window Reduced).

Finalmente, ¿cómo encontrar la capacidad desconocida del canal?, o lo que es lo mismo, ¿cómo deducir el valor de cwnd?. La estrategia es la siguiente: partiendo de un cwnd mínimo inicial (1 ó 4 segmentos) se amplía el tamaño de cwnd cada RTT, mejor dicho, por cada ACK recibido, por ejemplo, slow-start envía dos segmentos de datos juntos por cada ACK recibido, se inyectan datos por parejas para que se vayan incrementado y espaciando las llegadas de ACKs hasta conseguir un continuo durante un RTT completo, situación para la cual se consigue el punto de equilibrio descrito antes. Existe la tentación de inyectar todavía más segmentos de datos, sobrepasando el punto de equilibrio. En tal caso se producirá la congestión. Para incrementar la cwnd de forma relativamente rápida, y no perder un tiempo inicial de transmisión, de inicio se aplica crecimiento exponencial; y después lineal (que es lo que toca según AIMD) y se usará la pérdida de un segmento de datos como señal de congestión para reducir el tamaño de cwnd de forma multiplicativa (a la mitad). Nota: en la práctica, la velocidad de transmisión viene impuesta por la ventana más restrictiva de entre: la ventana de control de flujo del receptor y la ventana de congestión.

Mecanismo de Inicio Lento o Slow Start El algoritmo opera de la siguiente forma: x

Al inicio: cwnd=1;

x

Por cada ACK recibido se incrementa en una unidad cwnd: cwnd++;

x

Si expira un temporizador de segmento de datos: cwnd = 1;

El emisor enviará el primer segmento; al recibir el ack, cwnd pasa a valer 2. Ahora se envían dos segmentos, y otra vez, por cada ack recibido se añade uno más, así: cwnd = 2 + 1 + 1 = 4. Esto provoca un incremento exponencial de la ventana.

Mecanismo de Prevención de la Congestión (Congestion Avoidance) El algoritmo opera de la siguiente manera:

x

Al inicio: cwnd = cwnd_init; (tamaño inicial de cwnd).

x

Por cada ACK recibido se incrementa cwnd en 1/cwnd (es decir, se incrementa 1 segmento por ventana completa transmitida), por ejemplo: cwnd = 5, entonces cwnd = 5 + 1/5, es decir, hasta que no se reciben 5 ACKs no incrementas cwnd a 6: cwnd= cwnd + 1/cwnd;

x

Si expira un temporizador: cwnd = cwnd / 2;

Combinación de Slow Start y Congestion Avoidance Inicio Lento y Prevención de la Congestión son algoritmos totalmente independientes, no obstante, en la práctica, se implementan de manera conjunta. El algoritmo combinado mantiene dos variables para el control de la congestión: una ventana de congestión (cwnd) y un valor umbral del slow-start (ssthresh) que permite conmutar entre los dos algoritmos. Su funcionamiento es el siguiente:

x

Al inicio: cwnd = 1; ssthresh = ssthresh_init; (umbral inicial de conmutación de slow-start a congestion avoidance).

x

La llegada de un ACK, incrementa el valor de cwnd según el siguiente procedimiento: o Si cwnd < ssthresh -> cwnd++. o Si cwnd t ssthresh -> cwnd= cwnd + 1/cwnd;

x

Si expira un temporizador, la mitad del tamaño actual de la ventana pasa a ser el umbral del slow-start, la mitad porque durante el slow-start se ha ido doblando cada RTT por tanto, lo lógico es volver al tamaño anterior sin pérdidas: ssthresh = cwnd / 2; cwnd = 1; (comienzo de nuevo de Inicio Lento).

Crecimiento de la ventana de congestión (segmentos)

cwnd = 37 no llega a ser nunca

Retransmisión

Tiempo (RTT)

x

En este ejemplo, ssthresh = 32 segmentos (línea discontinua), a partir del cual se pasa de Inicio Lento a Prevención de la Congestión.

x

También puede apreciarse como tras una retransmisión, ssthresh se reduce a la mitad de cwnd = 36 del momento; así: ssthresh = 18; y cwnd = 1.

x

En la gráfica hay un pequeño fallo, el paso a cwnd = 1 no es en el momento 10*RTT; es un poco después porque el timeout no puede ser igual a 1 RTT, se supone que en 10*RTT, cwnd sería = 37, pero no llega a ser 37 porque un ACK no llega (el del paquete de datos perdido), entonces, pasado el timeout, en un instante 10*RTT + algo, se hace cwnd = 1 y ssthresh = 36/2.

Mejoras a los mecanismos Aprovecha la recepción de reconocimientos (ACKs) duplicados por parte del emisor (se consideran ACKs duplicados aquellos que consecutivamente reconocen el mismo segmento de datos, es decir, contienen el mismo número de secuencia de reconocimiento). La recepción de ACKs duplicados por parte del emisor se debe a que el receptor recibe, de forma ordinaria, la secuencia ordenada de segmentos de datos; y momentáneamente no recibe un segmento de datos dado, aun así, el receptor continua recibiendo segmentos de datos posteriores. Así, el receptor enviará nuevos ACKs por cada segmento de datos o por cada dos segmentos de datos recibidos (caso del TCP), pero en todos ellos indica que espera recibir el mismo segmento de datos, el que le falta. Estos son los denominados reconocimientos duplicados. Mecanismo Fast Retransmit (TCP Tahoe) La idea, como mejora a los mecanismos anteriores, consiste en reaccionar ante la recepción de ACKs duplicados, retransmitiendo (fast retransmit) el segmento solicitado, antes de que expire el temporizador RTO del mismo. El emisor desconoce la razón de recibir ACKs duplicados. Experimentalmente se ha comprobado que no resulta apropiado precipitar la retransmisión ante la recepción del primer o del segundo reconocimiento duplicado en redes que desordenan paquetes. Por esta razón, la mayoría de implementaciones de TCP activan el mecanismo de Retransmisión Rápida al recibir el tercer ACK duplicado. Se retransmite sólo el siguiente segmento esperado según se indica en los ACK duplicados, porque los ACKs duplicados no sólo indican que ha habido un problema en la red con un segmento dado, sino que también confirman que otros paquetes de datos posteriores han sido recibidos correctamente. Esto es así puesto que el receptor sólo puede generar ACKs con la llegada de nuevos segmentos de datos. En definitiva, se pretende no esperar al timeout para reenviar el segmento perdido, pero además se usa como señal de congestión, igual que un segmento retransmitido por RTO, consecuentemente, se hace: ssthresh = cwnd/2 y cwnd = 1 del mecanismo SS+CA.

Fast Retransmit with Fast Recovery (TCP Reno) En el impás de la retransmisión del segmento perdido y la posterior confirmación del mismo, se pretende evitar que la ventana de congestión se consuma, al no recibir ACKs de nuevos segmentos de datos. Para ello se añade el algoritmo de “Fast Recovery”. Dicho algoritmo, de forma similar a la combinación: slow-start + congestion avoidance, en el momento de activar la retransmisión rápida, sitúa el umbral ssthresh en cwnd/2, pero también hace que cwnd = cwnd/2 evitando así el inicio lento.

El algoritmo opera como sigue:

x

Cuando llega el tercer ACK duplicado se retransmite el segmento perdido y se ponen ssthresh y cwnd, los dos, a cwnd/2, así el inicio-lento NO aplica en este caso. En la cuenta de segmentos no reconocidos (viajando en la red) se restan las 3 unidades de los tres duplicados y se hace: ssthresh = cwnd/2; cwnd = cwnd/2;

x

En el tiempo de un RTT, cada nuevo ACK duplicado recibido (porque hace falta que pase un RTT para recibir el ACK del segmento individual que se retransmitió, aunque los ACK

duplicados se siguen recibiendo), se considera como un ack valido y se usa para decrementa el número de segmentos no reconocidos.

x

Cuando se recibe el primer ACK ordinario que reconoce nuevos datos (seguramente habrá un salto en el nº de segmento reconocido en el ACK porque se reconocerán de golpe todos los que se tenían acumulados a la espera del hueco que faltaba), se deja entonces cwnd = ssthresh; es decir, en la mitad de su valor justo antes de la retransmisión del segmento perdido, para así continuar trabajando en la zona de crecimiento lineal de cwnd (congestion avoidance).

Con esta versión del algoritmo de control de congestión en su tramo en forma de sierra se implementa plenamente la técnica AIMD. Pero si expira el RTO se vuelve al slow-start como en el inicio de la transmisión. Otras versiones del TCP usan complementariamente otras opciones para ser más eficaces en la retransmisión rápida, pero el mecanismo ss + ca + fast retransmission + fast recovery opera igual. Otras versiones del TCP usan además el flag ECN junto con la pérdida de segmento como señal de congestión para aplicar fast recovery....