networking - tahoe - Control de congestión TCP-Recuperación rápida en gráfico

tcp wikipedia (1)

He estado leyendo el libro "Redes informáticas: un enfoque de arriba hacia abajo" y encontré una pregunta que no entiendo.

A medida que leo, TCP Congestion Control tiene tres estados: inicio lento, evitación de la congestión y recuperación rápida. Entiendo Slow Start y Congestion Avoidance bien, pero Fast Recovery es bastante vago. El libro afirma que TCP se comporta de esta manera: (cwnd = Ventana de congestión)
Veamos el siguiente gráfico:

Como podemos ver, en la ronda 16 el emisor envía 42 segmentos, y debido a que el tamaño de la ventana de congestión se ha reducido a la mitad (+3), podemos inferir que ha habido 3 ACK duplicados. La respuesta a esta pregunta afirma que las rondas entre 16 y 22 están en estado de Evitación de congestión . Pero, ¿por qué no una recuperación rápida ? Quiero decir, después de tres ACK duplicados, TCP ingresa a Recuperación rápida y todos los demás ACK duplicados, ya que debería aumentar la ventana de congestión. ¿Por qué el gráfico no tiene representación de eso? La única explicación razonable que se me ocurre es que en este gráfico, solo había tres ACK duplicados, y los ACK que se habían recibido desde entonces no eran duplicados.

Incluso si ese es el caso, ¿cómo se vería el gráfico si hubiera habido más de 3 ACK duplicados? **

¿Hay alguna representación de Fast Recovery en el gráfico de arriba? Por qué no / si?

** He estado luchando por responder esa pregunta durante mucho tiempo. Estaré muy contento por cualquier respuesta, ¡Gracias!

ACTUALIZAR aquí está la imagen. Creo que una ronda se define como cuando todos los segmentos en la ventana están siendo ACKed. En la foto, una ronda se muestra con un círculo. ¿Por qué cwnd crece exponencialmente cuando está en estado de recuperación rápida? (en la imagen que accidentalmente escribí de manera conveniente en lugar de exponencial)

ACTUALIZACIÓN : mi respuesta original estuvo de acuerdo con la solución, pero después de pensarlo detenidamente, creo que la solución es incorrecta. Esta respuesta fue reescrita desde cero; por favor léelo cuidadosamente. Muestro por qué se ingresa Recuperación rápida en el momento T = 16 y por qué el protocolo permanece allí hasta T = 22. Los datos en el gráfico respaldan mi teoría, por lo que estoy bastante seguro de que la solución es completamente incorrecta.

Comencemos por establecer algo correcto: Slow Start crece exponencialmente; la evitación de la congestión crece de forma lineal, y la recuperación rápida crece de forma lineal a pesar de que utiliza la misma fórmula que el inicio lento para actualizar el valor de cwnd .

Permíteme aclarar.

¿Por qué decimos que Slow Start crece cwnd exponencialmente?

Tenga en cuenta que cwnd se incrementa en bytes de MSS para cada ACK recibido .

Veamos un ejemplo. Supongamos que cwnd se inicializa a 1 MSS (el valor de MSS es típicamente 1460 bytes, por lo que en la práctica esto significa que cwnd se inicializa a 1460). En este punto, dado que el tamaño de la ventana de congestión solo puede contener 1 paquete, TCP no enviará nuevos datos hasta que se reconozca este paquete. Suponiendo que los ACK no se pierden, esto implica que se transfiere aproximadamente un nuevo paquete cada RTT segundos (recuerde que RTT es el tiempo de ida y vuelta), ya que necesitamos (1/2) * RTT para enviar el paquete, y ( 1/2) * RTT para que llegue el ACK.

Por lo tanto, esto da como resultado una tasa de envío de aproximadamente MSS / RTT bps. Ahora, recuerde que para cada ACK , cwnd se incrementa por MSS . Por lo tanto, una vez que llega el primer ACK , cwnd convierte en 2*MSS , por lo que ahora podemos enviar 2 paquetes. Cuando se reconocen estos dos paquetes, incrementamos cwnd dos veces , por lo que ahora cwnd es 4*MSS . ¡Estupendo! Podemos enviar 4 paquetes. Estos 4 paquetes son reconocidos, ¡así que aumentamos cwnd 4 veces! Entonces tenemos cwnd = 8*MSS . Y luego obtenemos cwnd = 16*MSS . Estamos esencialmente doblando cada segundo de RTT (esto también explica por qué cwnd = cwnd+MSS*(MSS/cwnd) en Evitación de congestión lleva a un crecimiento lineal)

Sí, es complicado, la fórmula cwnd = cwnd+MSS nos lleva fácilmente a creer que es lineal, una idea errónea común, porque a menudo la gente olvida que esto se aplica a cada paquete reconocido.

Tenga en cuenta que en el mundo real, la transmisión de 4 paquetes no necesariamente genera 4 ACK. Puede generar 1 ACK solamente, pero dado que TCP usa ACK acumulativos, ese ACK solo sigue reconociendo 4 paquetes.

¿Por qué es Fast Recovery lineal?

La fórmula cwnd = cwnd+MSS se aplica tanto en inicio lento como en evitación de congestión. Uno podría pensar que esto causa que ambos estados induzcan un crecimiento exponencial. Sin embargo, la recuperación rápida aplica esa fórmula en un contexto diferente: cuando se recibe un ACK duplicado. Aquí radica la diferencia: en el arranque lento, un RTT reconoció un montón de segmentos, y cada segmento reconocido contribuyó con + 1MSS al nuevo valor de cwnd , mientras que en recuperación rápida, un ACK duplicado está desperdiciando un RTT para reconocer la pérdida de un solo segmento, por lo que en lugar de actualizar cwnd N veces cada RTT segundos (donde N es el número de segmentos transmitidos), estamos actualizando cwnd una vez para un segmento que se PERDIÓ. Así que "desperdiciamos" un viaje de ida y vuelta con solo un segmento, por lo que solo incrementamos cwnd en 1.

Acerca de la prevención de la congestión : esta será la siguiente explicación al analizar el gráfico.

Analizando el gráfico

Ok, entonces veamos exactamente lo que sucede en ese gráfico, ronda por ronda. Tu imagen es correcta hasta cierto punto. Déjame aclarar algunas cosas primero:

Cuando decimos que Slow Start y Fast Recovery crecen exponencialmente, significa que crece exponencialmente ronda por ronda , como se muestra en la imagen. Entonces, eso es correcto. Identificó correctamente las rondas con círculos azules: observe cómo los valores de cwnd crecen exponencialmente de un círculo al siguiente: 1, 2, 4, 8, 16, ...
La imagen parece indicar que, después del inicio lento, el protocolo ingresa en Recuperación rápida. Esto no es lo que sucede Si fuera Fast Recovery de Slow Start, veríamos que cwnd se redujera a la mitad. Eso no es lo que muestra el gráfico: el valor de cwnd no disminuye a la mitad de T = 6 a T = 7.

Ok, ahora veamos exactamente qué sucede en cada ronda. Tenga en cuenta que la unidad de tiempo en el gráfico es una ronda. Entonces, si en el tiempo T = X transmitimos N segmentos, entonces se supone que en el momento T = X + 1 estos N segmentos han sido ACK (asumiendo que no se perdieron, por supuesto).

También tenga en cuenta cómo podemos decir el valor de ssthresh solo mirar el gráfico. En T = 6, cwnd deja de crecer exponencialmente y comienza a crecer linealmente, y su valor no disminuye. La única transición posible desde el inicio lento a otro estado que no implica la disminución de cwnd es la transición a la evitación de la congestión, que ocurre cuando el tamaño de la ventana de congestión es igual a ssthresh . Podemos ver en el gráfico que esto sucede cuando cwnd es 32. Entonces, inmediatamente sabemos que ssthresh se inicializa a 32 MSS. El libro muestra un gráfico muy similar en la página 276 (Figura 3.53), donde los autores sacan una conclusión similar:

En condiciones normales, esto es lo que sucede: cuando TCP cambia por primera vez de un crecimiento exponencial a un crecimiento lineal sin disminuir el tamaño de la ventana, siempre es porque llega al umbral y se cambia a la prevención de la congestión.

Finalmente, suponga que MSS tiene al menos 1460 bytes (comúnmente es 1460 bytes porque Ethernet tiene MTU = 1500 bytes y necesitamos tener en cuenta el tamaño de los encabezados TCP + IP, que en conjunto necesitan 40 bytes). Esto es importante para ver cuando cwnd excede ssthresh , ya que la unidad de cwnd es MSS y ssthresh se expresa en bytes.

Así que, aquí vamos:

T = 1 :

cwnd = 1 MSS; ssthresh = 32 kB

Transmitir 1 segmento

T = 2

1 segmento reconocido

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 2

Transmitir 2 segmentos

T = 3

2 segmentos reconocidos

cwnd + = 2; ssthresh = 32 kB

Nuevo valor de cwnd: 4

Transmita 4 segmentos

T = 4

4 segmentos reconocidos

cwnd + = 4; ssthresh = 32 kB

Nuevo valor de cwnd: 8

Transmita 8 segmentos

T = 5

8 segmentos reconocidos

cwnd + = 8; ssthresh = 32 kB

Nuevo valor de cwnd: 16

Transmita 16 segmentos

T = 6

16 segmentos reconocidos

cwnd + = 16; ssthresh = 32 kB

Nuevo valor de cwnd: 32

Transmita 32 segmentos

Ok, veamos qué pasa ahora. cwnd alcanzó ssthresh (32 * 1460 = 46720 bytes, que es mayor que 32000). Es hora de pasar a la prevención de la congestión. Observe cómo los valores de cwnd crecen exponencialmente a lo largo de las rondas, ya que cada paquete reconocido contribuye con 1 MSS al nuevo valor de cwnd , y cada paquete enviado se confirma en la siguiente ronda.

El cambio a la evitación de la congestión

Ahora, cwnd no aumentará exponencialmente, porque cada ACK ya no contribuirá con 1 MSS. En cambio, cada ACK contribuye con MSS*(MSS/cwnd) . Entonces, por ejemplo, si MSS es 1460 bytes y cwnd es 14600 bytes (entonces, al comienzo de cada ronda estamos enviando 10 segmentos), entonces cada ACK (suponiendo un ACK por segmento) aumentará cwnd en 1/10 MSS (146 bytes). Dado que enviamos 10 segmentos, y al final de la ronda suponemos que se reconoció cada segmento, al final de la ronda aumentamos cwnd en 10 * 1/10 = 1 . En otras palabras, cada segmento contribuye con una pequeña fracción a cwnd manera que simplemente incrementamos cwnd en 1 MSS cada ronda. Entonces, cada ronda incrementa cwnd en 1 en lugar de la cantidad de segmentos que se transfirieron / reconocieron.

Permaneceremos en la evitación de la congestión hasta que se detecte alguna pérdida (ya sea 3 ACK duplicados o un tiempo de espera excedido).

Ahora, dejen que los relojes se reanuden ...

T = 7

32 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 33

Transmitir 33 segmentos

Observe cómo cwnd pasó de 32 a 33 aunque se reconocieron 32 segmentos (cada ACK por lo tanto contribuye 1/32). Si estuviéramos en un arranque lento, como en T = 6, tendríamos cwnd += 32 . Este nuevo valor de cwnd también es consistente con lo que vemos en el gráfico en el tiempo T = 7.

T = 8

33 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 34

Transmita 34 segmentos

T = 9

34 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 35

Transmitir 35 segmentos

Observe que esto es consistente con el gráfico: en T = 9, tenemos cwnd = 35 . Esto sigue sucediendo hasta T = 16 ...

T = 10

35 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 36

Transmita 36 segmentos

T = 11

36 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 37

Transmitir 37 segmentos

T = 12

37 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 38

Transmita 38 segmentos

T = 13

38 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 39

Transmita 39 segmentos

T = 14

39 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 40

Transmita 40 segmentos

T = 15

40 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 41

Transmita 41 segmentos

T = 16

41 segmentos reconocidos

cwnd + = 1; ssthresh = 32 kB

Nuevo valor de cwnd: 42

Transmita 42 segmentos

PAUSA

¿Que pasa ahora? El gráfico muestra que el tamaño de la ventana de congestión disminuye a aproximadamente la mitad de su tamaño, y luego vuelve a crecer linealmente entre las rondas. La única posibilidad es que haya 3 ACK duplicados y el protocolo cambie a Recuperación rápida. El gráfico muestra que NO cambia a inicio lento porque eso llevaría a cwnd a 1. Por lo tanto, la única transición posible es la recuperación rápida.

Al ingresar a recuperación rápida, obtenemos ssthresh = cwnd/2 . Recuerde que las unidades de cwnd son MSS y ssthresh está en bytes, tenemos que tener cuidado con eso. Por lo tanto, el nuevo valor es ssthresh = cwnd*MSS/2 = 42*1460/2 = 30660 .

De nuevo, esto se alinea con el gráfico; Observe que ssthresh será golpeado en el futuro cercano cuando cwnd sea un poco menor que 30 (recuerde que con MSS = 1460, la relación no es exactamente 1: 1, por eso alcanzamos el umbral aunque el tamaño de la ventana de congestión es ligeramente inferior a 30 )

El cambio a evitar la congestión también provoca que el nuevo valor de cwnd sea ssthresh+3MSS = 21+3 = 24 (recuerde tener cuidado con las unidades, aquí convertí ssthresh en MSS nuevamente porque nuestros valores de cwnd se cuentan en MSS).

A partir de ahora, estamos en la evitación de la congestión, con T = 17, ssthresh = 30660 bytes y cwnd = 24 .

Al ingresar T = 18, pueden suceder dos cosas: o recibimos un ACK duplicado o no lo recibimos. Si no lo hacemos (entonces es un ACK nuevo), haríamos la transición a evitar la congestión. Pero esto reduciría el valor de ssthresh , que es 21. Eso no coincidiría con el gráfico: el gráfico muestra que cwnd sigue aumentando linealmente. Además, no cambia a un inicio lento porque eso llevaría a cwnd a 1. Esto implica que no se puede recuperar rápidamente y estamos recibiendo ACK duplicados. Esto sucede hasta el momento T = 22:

T = 18

Duplicate ACK llegó