Reducción de tasa proporcional: algoritmo de recuperación de pérdida de TCP

TCP CUBIC se está convirtiendo en el predeterminado en Linux Kernel y la técnica Rate Halving para evitar la congestión se está convirtiendo en la predeterminada en Linux Kernel. Entonces, hubo un desajuste entre estos dos. Porque Rate Halving fue bueno para TCP Reno, Tahoe y NewReno. Es bueno solo para aquellos TCP que reducen el cwnd a la mitad cuando se produce una pérdida de paquetes. Pero TCP Cubic reduce el cwnd en un 30 %, a diferencia de otros TCP. Por lo tanto, Rate Halving y CUBIC no podían encajar de forma predeterminada en el kernel de Linux. Esta fue la motivación de Google e inventaron un nuevo algoritmo conocido como Reducción de Tasa Proporcional. Esto está cubierto en RFC 6937.

Reducción de Tasa Proporcional:

PRR calcula la cantidad de paquetes nuevos que se enviarán cuando llega un ACK usando algunas ecuaciones. Se acuñan algunos términos nuevos para estas ecuaciones, las nuevas terminologías son las siguientes:

1. sndcnt (leído como ‘recuento de envíos’) : la cantidad de datos que se enviarán a la llegada de un DupACK. Este es el número de nuevos paquetes que el remitente envía a la llegada de un nuevo ACK. A diferencia de Fast Recovery, no es igual a 2 y, a diferencia de Rate Halving, no envía 1 paquete nuevo a la llegada de dos DUP-ACK. Puede enviar cualquier número de paquetes nuevos que se calcula mediante una fórmula.

2. RecoverFS: el valor de la tubería al comienzo de la fase de recuperación

3. prr_delivered: la cantidad de datos entregados ‘durante’ la fase de recuperación. Este es el recuento de datos acumulados entregados hasta el momento al receptor desde que comenzó la fase de recuperación. Esto es igual al número de DUP-ACK recibidos durante la fase de recuperación. ¿Cuántos paquetes se entregan antes de que la fase de recuperación no sea importante? Solo cuenta los paquetes entregados después de la pérdida de paquetes.

4. prr_out: la cantidad de datos transmitidos ‘durante’ la fase de recuperación. Este cuenta el número acumulado de nuevos paquetes enviados por el remitente una vez que ha entrado en la fase de recuperación.

5. Datos entregados : la cantidad de datos entregados según lo indicado por un paquete ACK (observe los números de secuencia). No confunda esto con «prr_delivered». DeliveredData indica el número de paquetes entregados por este DUP_ACK. Puede ser 1 o más si los ACK llegan desordenados.

6. límite: límite de envío de datos (calculado en el algoritmo PRR). Esto puede ser considerado como el umbral. Se utiliza dentro de la ecuación y se calcula en pasos intermedios.

7. MSS: Tamaño máximo de segmento . Este es el tamaño típico de un segmento. Dado que utilizaremos la granularidad de todos los términos como segmentos, MSS se convierte en 1.

Modo de Reducción de Tasa Proporcional:

La Reducción de Tasa Proporcional (PRR) tiene dos modos, que son los siguientes:

1. Límite de reducción conservador (CRB)
2. Límite de reducción de inicio lento (SSRB) [este está habilitado de forma predeterminada en Linux]

Solo podemos usar un modo a la vez, ambos modos no se pueden usar simultáneamente.

Funcionamiento de PRR:

Cuando comienza la fase de recuperación, el valor de tubería es mayor que cwnd. Pero puede darse el caso de que los bloques SACK confirmen la pérdida del paquete y el valor de la canalización sea menor que cwnd. Todos estos casos son manejados de manera diferente por el algoritmo PRR.

CASO 1: PRR (Caso: tubería > ssthresh)

Cuando el remitente entra en la fase de recuperación:

pipe = 10 segments, 
RecoverFS = 10 segments
ssthresh = 7 segments,

cwnd se calcula mediante PRR:

cwnd = pipe + sndcnt
sndcnt = CEIL(p_d * ssthresh / RecoverFS) - p_o, {p_d=prr_delivered, p_o=prr_out}

Paso 1 : viene un DupACK, pipe=10-1=9, p_d=1, p_o=0, (Pipe se reduce en uno) . DupACK dice que se entregó 1 paquete. Por lo tanto,   p_d=1 , no se ha enviado ningún paquete nuevo todavía, por lo que p_o=0

sndcnt= CEIL(1*7/10)-0 = CEIL(0.7)-0 = 1
sender sends one new packet and pipe becomes =9+1=10 again.

Paso 2 : viene un DupACK, pipe=10-1=9, p_d=2, p_o=1, (Pipe se reduce en uno). DupACK dice que se entregó un paquete, por lo que p_d=2 (acumulativo). Todavía se ha enviado un nuevo paquete, por lo tanto, p_o=1.

sndcnt= CEIL(2*7/10)-1 = CEIL(1.4)-1= 1
sender sends one new packet and pipe becomes 9 + 1 = 10 again.

Así sigue.

Implementación:

A continuación se muestra la implementación del código para el Caso 1:

C++

// pipe>cwnd, PRR // PRR, case-1 #include <bits/stdc++.h> using namespace std;    // utility function void prr(float pipe, float cwnd, float recoverFS,          float ssthresh) {     int i;     float prr_delivered = 0, prr_out = 0, snd_cnt;        for (i = 1;; i++) {         // one DUP-ACK arrived         pipe -= 1;            // terminating condition.         if (pipe < ssthresh)             break;            // Calculation         cout << "Iteration " << i << " => "              << "pipe= " << pipe;         prr_delivered = i;         cout << " p_d= " << prr_delivered;         snd_cnt = ceil(prr_delivered * ssthresh / recoverFS)                   - prr_out;         cout << " snd_cnt= " << snd_cnt;         cout << " p_o= " << prr_out << "\n";         prr_out += snd_cnt;         cwnd = pipe + snd_cnt;         pipe = cwnd;     } }    // main function int main() {     float pipe, cwnd, recoverFS, ssthresh;     pipe = 10;     ssthresh = 7;     cwnd = pipe;     recoverFS = pipe;     prr(pipe, cwnd, recoverFS, ssthresh); }

Producción

Iteration 1 => pipe= 9 p_d= 1 snd_cnt= 1 p_o= 0
Iteration 2 => pipe= 9 p_d= 2 snd_cnt= 1 p_o= 1
Iteration 3 => pipe= 9 p_d= 3 snd_cnt= 1 p_o= 2
Iteration 4 => pipe= 9 p_d= 4 snd_cnt= 0 p_o= 3
Iteration 5 => pipe= 8 p_d= 5 snd_cnt= 1 p_o= 3
Iteration 6 => pipe= 8 p_d= 6 snd_cnt= 1 p_o= 4
Iteration 7 => pipe= 8 p_d= 7 snd_cnt= 0 p_o= 5
Iteration 8 => pipe= 7 p_d= 8 snd_cnt= 1 p_o= 5
Iteration 9 => pipe= 7 p_d= 9 snd_cnt= 1 p_o= 6
Iteration 10 => pipe= 7 p_d= 10 snd_cnt= 0 p_o= 7

CASO 2: PRR (Caso: tubería ≤ ssthresh, con SSRB)

Cuando comienza la fase de recuperación:

pipe = 4 segments
RecoverFS = 10 segments
ssthresh = 5 segments

cwnd se calcula mediante PRR:

cwnd = pipe + sndcnt
sndcnt = MIN (ssthresh - pipe, limit) and 
limit = MAX (p_d - p_o, DeliveredData) + MSS

Paso 1: llega un DupACK, la tubería se reduce en 1, pipe=4-1=3 , DupACK confirma que se entregó 1 paquete, por lo que p_d=1 , aún no se envió ningún paquete nuevo, por lo que p_o=0

limit = MAX(1-0, 1)+1 = 1+1 = 2
sndcnt= MIN(5-3, 2) = MIN(2, 2) = 2
So, the sender sends 2 new packets. Thus, pipe=3+2=5

Paso 2: llega un DupACK, la tubería se reduce en 1, tubería = 5-1 = 4 , DupACK confirma que se entregó 1 paquete, por lo que p_d = 2 (acumulativo) todavía se envió un paquete nuevo, por lo que p_o = 1

limit = MAX(2-1, 1)+1 = 1+1 = 2
sndcnt= MIN(5-4, 2) = MIN(1, 2) = 1
So, the sender sends 1 new packet. Thus, pipe=4+1=5

Así sigue.

Implementación:

A continuación se muestra la implementación del código para el CASO 2:

C++

// pipe<cwnd with Slow Start Reduction Bound, PRR    #include <bits/stdc++.h> using namespace std;    // utility function void prr_ssrb(float pipe, float cwnd, float recoverFS,               float ssthresh) {     int i;     float prr_delivered = 0, prr_out = 0, limit, snd_cnt;        for (i = 1; i < 10; i++) {         // one DUP-ACK arrived         pipe -= 1;            // Calculation         cout << "Iteration " << i << " => pipe= " << pipe;         prr_delivered = i;         cout << " p_d= " << prr_delivered;         cout << " p_o= " << prr_out;         limit = max(prr_delivered - prr_out, float(1)) + 1;         cout << " limit= " << limit;         snd_cnt = min(ssthresh - pipe, limit);         cout << " snd_cnt= " << snd_cnt << "\n";         prr_out += snd_cnt;            cwnd = pipe + snd_cnt;         pipe = cwnd;            // terminating condition.         if (pipe > ssthresh)             break;     } }    // main function int main() {     float pipe, cwnd, recoverFS, ssthresh;     pipe = 4, recoverFS = 10, ssthresh = 5;     prr_ssrb(pipe, cwnd, recoverFS, ssthresh); }

Producción

Iteration 1 => pipe= 3 p_d= 1 p_o= 0 limit= 2 snd_cnt= 2
Iteration 2 => pipe= 4 p_d= 2 p_o= 2 limit= 2 snd_cnt= 1
Iteration 3 => pipe= 4 p_d= 3 p_o= 3 limit= 2 snd_cnt= 1
Iteration 4 => pipe= 4 p_d= 4 p_o= 4 limit= 2 snd_cnt= 1
Iteration 5 => pipe= 4 p_d= 5 p_o= 5 limit= 2 snd_cnt= 1
Iteration 6 => pipe= 4 p_d= 6 p_o= 6 limit= 2 snd_cnt= 1
Iteration 7 => pipe= 4 p_d= 7 p_o= 7 limit= 2 snd_cnt= 1
Iteration 8 => pipe= 4 p_d= 8 p_o= 8 limit= 2 snd_cnt= 1
Iteration 9 => pipe= 4 p_d= 9 p_o= 9 limit= 2 snd_cnt= 1

CASO 3: PRR (Caso: tubería ≤ ssthresh, con CRB)

Inicialmente, cuando el remitente entra en la fase de recuperación:

pipe = 4 segments
RecoverFS = 10 segments
ssthresh = 5 segments

cwnd se calcula mediante PRR:

cwnd = pipe + sndcnt
sndcnt = MIN (ssthresh - pipe, limit), and 
limit = p_d - p_o

Paso 1: llega un DupACK, la tubería se reduce en 1, pipe=4-1=3 , DupACK confirma que se entregó un paquete, por lo que p_d=1 , todavía no se envió ningún paquete nuevo, por lo que p_o=0.

limit = 1-0 = 1,
sndcnt = MIN(5-3, 1) = MIN(2, 1) = 1
Sender sends one new packet, thus pipe = 3+1 = 4

Paso 2: llega un DupACK, la tubería se reduce en 1, 

pipe= 4-1=3,
p_d=2, p_o=1
limit = 2-1 = 1
sndcnt = MIN(5-3, 1) = MIN(2, 1) = 1
Sender sends one new packet, thus pipe = 3+1 = 4

Así sigue.

Implementación:

A continuación se muestra la implementación del código para el CASO 3:

C++

// pipe<cwnd with Conservative Reduction Bound, PRR    #include <bits/stdc++.h> using namespace std;    // utility function void prr_crb(float pipe, float cwnd, float recoverFS,              float ssthresh) {     int i;     float prr_delivered = 0, prr_out = 0, limit, snd_cnt;        for (i = 1; i < 10; i++) {         // one DUP-ACK arrived         pipe -= 1;            // Calculation         cout << "Iteration " << i << " => pipe= " << pipe;         prr_delivered = i;         cout << " p_d= " << prr_delivered;         cout << " p_o= " << prr_out;         limit = prr_delivered - prr_out;         cout << " limit= " << limit;         snd_cnt = min(ssthresh - pipe, limit);         cout << " snd_cnt= " << snd_cnt << "\n";         prr_out += snd_cnt;            cwnd = pipe + snd_cnt;         pipe = cwnd;            // terminating condition.         if (pipe > ssthresh)             break;     } }    // main function int main() {     float pipe = 4, cwnd, recoverFS = 10, ssthresh = 5;        prr_crb(pipe, cwnd, recoverFS, ssthresh); }

Producción

Iteration 1 => pipe= 3 p_d= 1 p_o= 0 limit= 1 snd_cnt= 1
Iteration 2 => pipe= 3 p_d= 2 p_o= 1 limit= 1 snd_cnt= 1
Iteration 3 => pipe= 3 p_d= 3 p_o= 2 limit= 1 snd_cnt= 1
Iteration 4 => pipe= 3 p_d= 4 p_o= 3 limit= 1 snd_cnt= 1
Iteration 5 => pipe= 3 p_d= 5 p_o= 4 limit= 1 snd_cnt= 1
Iteration 6 => pipe= 3 p_d= 6 p_o= 5 limit= 1 snd_cnt= 1
Iteration 7 => pipe= 3 p_d= 7 p_o= 6 limit= 1 snd_cnt= 1
Iteration 8 => pipe= 3 p_d= 8 p_o= 7 limit= 1 snd_cnt= 1
Iteration 9 => pipe= 3 p_d= 9 p_o= 8 limit= 1 snd_cnt= 1