Пропорциональное снижение скорости — алгоритм восстановления потерь TCP

Опубликовано: 17 Сентября, 2022

TCP CUBIC становится стандартом в ядре Linux, а метод халвинга скорости для предотвращения перегрузки становится стандартом в ядре Linux. Значит, между этими двумя была нестыковка. Потому что халвинг скорости был хорош для TCP Reno, Tahoe и NewReno. Это хорошо только для тех TCP, которые уменьшают cwnd наполовину при потере пакетов. Но TCP Cubic уменьшает cwnd на 30%, в отличие от других TCP. Таким образом, Rate Halving и CUBIC не могут быть установлены по умолчанию в ядре Linux. Это было мотивацией Google, и они изобрели новый алгоритм, известный как пропорциональное снижение ставок. Это описано в RFC 6937.

Пропорциональное снижение ставки:

PRR вычисляет количество новых пакетов, которые должны быть отправлены, когда приходит ACK, используя некоторые уравнения. Для этих уравнений введены некоторые новые термины, новые термины заключаются в следующем:

1. sndcnt (читается как «счетчик отправлений») : количество данных, которые должны быть отправлены при получении DupACK. Это количество новых пакетов, которые отправитель отправляет при получении нового ACK. В отличие от Fast Recovery, он не равен 2 и, в отличие от Rate Halving, не отправляет 1 новый пакет при поступлении двух DUP-ACK. Он может отправлять любое количество новых пакетов, которое рассчитывается по формуле.

2. RecoverFS: значение пайпа в начале фазы восстановления

3. prr_delivered: объем данных, доставленных «во время» фазы восстановления. Это количество накопленных данных, доставленных получателю с момента начала фазы восстановления. Это равно количеству DUP-ACK, полученных на этапе восстановления. Сколько пакетов доставлено перед фазой восстановления не важно? Он подсчитывает только пакеты, доставленные после потери пакетов.

4. prr_out: количество данных, переданных «во время» фазы восстановления. Это подсчитывает накопленное количество новых пакетов, отправленных отправителем после того, как он вошел в фазу восстановления.

5. DeliveredData: объем данных, доставленных в соответствии с пакетом ACK (см. порядковые номера). Не путайте это с «prr_delivered». DeliveredData указывает количество пакетов, доставленных этим DUP_ACK. Это может быть 1 или более, если ACK приходят не по порядку.

6. limit: лимит на отправку данных (рассчитывается в алгоритме PRR). Это можно считать порогом. Он используется внутри уравнения и рассчитывается на промежуточных этапах.

7. MSS: максимальный размер сегмента. Это типичный размер одного сегмента. Поскольку мы будем использовать детализацию всех терминов как сегментов, MSS становится равным 1.

Режим пропорционального снижения скорости:

Пропорциональное снижение скорости (PRR) имеет два режима:

  1. Граница консервативного сокращения (CRB)
  2. Slow Start Reduction Bound (SSRB) [этот параметр включен по умолчанию в Linux]

Мы можем использовать только один режим за раз, оба режима нельзя использовать одновременно.

Работа ПРР:

Когда начинается фаза восстановления, значение канала больше, чем cwnd. Но возможен случай, когда блоки SACK подтверждают потерю пакета и значение канала становится меньше cwnd. Все эти случаи по-разному обрабатываются алгоритмом PRR.

СЛУЧАЙ 1: PRR (случай: pipe > ssthresh)

Когда отправитель переходит на этап восстановления:

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

cwnd вычисляется по PRR:

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

Шаг 1 : приходит один DupACK, pipe=10-1=9, p_d=1, p_o=0, (Pipe уменьшается на единицу) . DupACK сообщает, что был доставлен 1 пакет. Итак, p_d=1 , новый пакет еще не отправлен, поэтому 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.

Шаг 2 : приходит один DupACK, pipe=10-1=9, p_d=2, p_o=1, (Pipe уменьшается на единицу). DupACK сообщает, что был доставлен один пакет, поэтому p_d=2 (кумулятивно). Еще один новый пакет был отправлен, поэтому 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.

Вот как это продолжается.

Implementation:

Below is the code implementation for Case 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 << " ";
        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);
}

Output
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
CASE 2: PRR (Case: pipe ≤ ssthresh, with SSRB)
When recovery phase begins:
pipe = 4 segments
RecoverFS = 10 segments
ssthresh = 5 segments
cwnd is calculated by PRR:
cwnd = pipe + sndcnt
sndcnt = MIN (ssthresh - pipe, limit) and 
limit = MAX (p_d - p_o, DeliveredData) + MSS
Step 1: One DupACK comes, pipe reduces by 1, pipe=4-1=3, DupACK confirms that 1 packet got delivered, so p_d=1, no new packet is sent yet, so 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
Step 2: One DupACK comes, pipe reduces by 1, pipe=5-1=4, DupACK confirms that 1 packet got delivered, so p_d=2 (cumulative) one new packet is sent yet, so 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
This is how it continues.
Implementation:
Below is the code implementation for CASE 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 << "
";
        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);
}
Output
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
CASE 3: PRR (Case: pipe ≤ ssthresh, with CRB)
Initially when sender enters recovery phase:
pipe = 4 segments
RecoverFS = 10 segments
ssthresh = 5 segments
cwnd is calculated by PRR:
cwnd = pipe + sndcnt
sndcnt = MIN (ssthresh - pipe, limit), and 
limit = p_d - p_o
Step 1: One DupACK arrives, pipe reduces by 1, pipe=4-1=3, DupACK confirms that one packet got delivered, so p_d=1, no new packet is sent yet, so 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
Step 2: One DupACK arrives, pipe reduces by 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
This is how it continues.
Implementation:
Below is the code implementation for CASE 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 << "
";
        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);
}
Output
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


            

                            

                    
                                            Компьютеры
                                            Продвинутая компьютерная тематика
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ

                

                                            

                            
Оборудование MikroTik: что это такое и зачем оно нужно?

                            
5 Апреля, 2023

                        

                                            

                            
Сеть сортировки Bitonic с использованием параллельных вычислений

                            
27 Февраля, 2023

                        

                                            

                            
Что такое график Петерсона?

                            
26 Февраля, 2023

                        

                                            

                            
Коллекция на основе трассировки

                            
23 Февраля, 2023

                        

                                            

                            
Аппаратное обеспечение ввода-вывода в операционной системе

                            
23 Февраля, 2023

                        

                                            

                            
Аппаратное обеспечение ввода-вывода в операционной системе

                            
23 Февраля, 2023

                        

                                            

                            
Контекстно-независимый межпроцедурный анализ

                            
23 Февраля, 2023

                        

                                            

                            
Портативная операционная система

                            
23 Февраля, 2023