Algoritmo AIMD

AIMD es un algoritmo de control de retroalimentación, lo utilizan los protocolos TCP en la capa de transporte de la pila TCP/IP. La fase de IA es responsable del crecimiento lineal de la ventana de congestión del remitente donde no se detecta congestión. La fase MD es responsable de la reducción exponencial de la ventana de congestión del remitente cuando se detecta congestión. Pueden existir múltiples combinaciones de estas dos fases: aditiva y multiplicativa.

AIAD, MIAD y MIMD son tres combinaciones adicionales. Pero no garantizan la equidad. AIMD, por el contrario, garantiza la equidad mientras compite con otros flujos TCP por el ancho de banda de la red. MIMD aumenta la ventana de congestión exponencialmente cuando no hay congestión en la red, como resultado, las posibilidades de congestión aumentan y una gran parte del ancho de banda es consumida por este flujo en particular, lo que perjudica el rendimiento de otros flujos. Debido a su crecimiento exponencial, la congestión se produce con mucha más frecuencia. MIMD y AIMD no alcanzan la estabilidad, todos los flujos de TCP no convergen en el uso del ancho de banda de la red.

Incremento aditivo Disminución multiplicativa (AIMD):

Se conoce como el algoritmo para evitar la congestión (pero este es un nombre inapropiado). No evita la congestión en el verdadero sentido. De hecho, no existe un algoritmo para evitar la congestión. Controla el crecimiento de la ventana de congestión con extremo cuidado, de modo que las posibilidades de una mayor congestión son mínimas. La ventana de congestión (cwnd) aumenta en ‘un’ segmento ‘por’ RTT, esta es la fase de IA. A diferencia de Slow Start, donde cwnd aumenta en ‘un’ segmento por ‘ACK’ recibido. El cwnd se reduce a la ‘mitad’ al detectar una pérdida de paquete, esta es la fase MD. 

Ejemplo: Consulte ‘Tiempo restante’ mientras descarga/carga un archivo. Inicialmente, la velocidad aumentaría exponencialmente y el tiempo restante sería menor. Entonces ocurre una pérdida de paquetes y la velocidad disminuye a la mitad y el tiempo restante se vuelve aproximadamente el doble. Si se produce una mayor pérdida de paquetes, la velocidad disminuye aún más y el tiempo vuelve a duplicarse.

Objetivo principal de AIMD:

AIMD sondea ‘lentamente’ en comparación con la fase de ‘Inicio lento’. El inicio lento aumenta exponencialmente el tamaño de la ventana de congestión (el doble por RTT) mientras que AIMD aumenta cwnd linealmente (en 1 por RTT). Cuando se introdujo TCP, no había ningún mecanismo de control de congestión. El remitente TCP solía enviar el valor total de cwnd de los paquetes a la vez sin preocuparse por la pérdida de paquetes en los dispositivos intermediarios. Los enrutadores no pudieron tolerar esa ráfaga de paquetes y, por lo tanto, los perdieron. Luego, se diseñó el inicio lento para superar esta situación y, por lo tanto, se denominó inicio lento. Comienza lentamente en comparación con la tasa y los criterios de envío de TCP originales, que no tuvo en cuenta el estado de congestión. 

El segundo objetivo de AIMD es garantizar la equidad entre los flujos que compiten por el ancho de banda. Si hay un estado de congestión en la red, reducir cwnd a la mitad reduce el uso de la red a la mitad o menos y permite que los otros flujos TCP (clientes) los usen. Cuando todos los flujos obtienen una parte igual del ancho de banda, el sistema se llama equitativo. El 50% cwnd de 1000 segmentos es 500 segmentos, y el de 100 segmentos es 50 segmentos, por lo tanto, el flujo TCP congestionado brinda la parte adecuada de la red a otros clientes TCP y garantiza una conexión justa.

Algoritmo:

A la llegada de cada ACK, incremente el cwnd en (1 ÷ cwnd) y envíe 1 nuevo segmento en la red

1. cwnd = cwnd + (1 ÷ cwnd)
2. inflight = inflight – 1 + 1 // -1 porque recibimos un ACK, +1 porque enviamos 1 nuevo segmento

Ejemplo: Supongamos que el cwnd = 10 cuando recibimos un ACK

cwnd = 10 + (1 ÷ cwnd), since the cwnd increases by 1 per RTT, 
means when all the ACK comes. So, for 1 ACK, cwnd increases by 1/cwnd.

inflight = 10 - 1 = 9 + 1, inflight must be equal to cwnd, 
So, 1 new packet is send to compensate 1 ACK packet.

Por lo tanto, si todos los segmentos se confirman con éxito, cwnd ‘eventualmente’ se incrementará en ‘uno’.

Ejemplo: suponga que cwnd = 10 e inflight = 10. Cuando llega un ACK, el cwnd se convertiría en 10.1, cuando llega el segundo ACK, el cwnd se convertiría en 10.2, …. cuando llega el décimo ACK, el cwnd se convierte en 11. Así que comenzó con 10 segmentos, y cuando llegan todos los ACK de estos 10 segmentos, el cwnd se convierte en 11.

 

Importante:

Cuando el inicio lento alcanza el valor ssthresh, simplemente entrega el control a AIMD.

Cuando se produce una pérdida de paquetes en la fase de inicio lento, ssthresh se establece en la mitad de cwnd y comienza la fase AIMD.

Cuando el inicio lento está inactivo durante 1 segundo, luego se reinicia por cwnd=initcwnd=1 segmento.

Cuando hay una pérdida de paquetes durante la fase AIMD, ssthresh se reduce a la mitad y cwnd se restablece a inticwnd y se reinicia la fase de inicio lento.

Protocolos usando AIMD

Solo el protocolo TCP usa el AIMD además del reinicio lento para detectar congestiones y tomar medidas correctivas.

AIMD es muy compatible con Slow Start Restart. Este combo se usa en conjunto en casi todos los TCP, es decir, Tahoe, Reno, NewReno y Cubic. Cuando el flujo comienza, se usa SSR, cuando SSR alcanza el umbral, comienza AIMD. Cuando se detecta congestión, AIMD cambia a SSR nuevamente. El AIMD es muy efectivo en términos de equidad de red. No daña otros flujos de TCP.

Factor de rendimiento para AIMD

1. Compatibilidad: hoy en día, todos los dispositivos utilizan alguna variante de TCP según la plataforma. AIMD es una parte integral de cada TCP. Es compatible con todas las variantes de TCP. La prevención de la congestión es básicamente el método de retroalimentación para que el remitente sepa que en algún lugar el enlace o el enrutador está congestionado y descartando los paquetes. Se enfoca en ‘cuándo’ en lugar de ‘si’ .
2. Eficacia: AIMD es el algoritmo más eficaz para evitar la congestión. Entra en acción ‘cuando’ hay pérdida de paquetes a través del enlace. Sondea lentamente la red y toma medidas efectivas para evitar más pérdidas de paquetes.
3. Capacidad de respuesta: Es el más sensible en la naturaleza. Tan pronto como se detecta la caída del paquete, el algoritmo que se estaba ejecutando anteriormente se detiene y entrega el control al AIMD. Cuando hay más pérdida de paquetes durante la fase AIMD, inmediatamente entrega el control al reinicio de inicio lento.

Impacto del algoritmo AIMD

Por ejemplo, suponga que cwnd tiene 1000 segmentos. Se produce una pérdida de paquetes y se detiene un inicio lento y comienza la fase AIMD. La disminución multiplicativa reducirá el cwnd a 500 segmentos (la mitad de 1000). Tomará (aproximadamente) 500 RTT para que cwnd vuelva a crecer a 1000 segmentos usando la fase AI (incremento de 1 por RTT). Si un RTT es de 100 ms: ¡500 RTT serán 500 x 100 ms = 50000 ms = 50 segundos! Por lo tanto, AIMD está afectando gravemente el rendimiento del cliente.

Soluciones propuestas

Evolucionó una nueva categoría de algoritmos de control de congestión, llamada alta velocidad. TCP de alta velocidad (cwnd = cwnd + a para AI y cwnd = cwnd xb para MD). TCP escalable (número fijo de RTT necesarios para volver al valor original de cwnd). Control de congestión de aumento binario (BIC) [este fue el precursor de CUBIC]. Otro TCP de alta velocidad más (Sí). CUBIC [diseñado para superar los problemas de equidad con BIC].