Управление перегрузкой TCP - быстрое восстановление в графике

Ответ 1

ОБНОВЛЕНИЕ. Мой первоначальный ответ был согласован с решением, но после тщательного анализа я считаю, что решение неверно. Этот ответ был переписан с нуля; прочитайте его внимательно. Я показываю, почему быстрое восстановление вводится в момент времени T = 16 и почему протокол остается там до T = 22. Данные на графике подтверждают мою теорию, поэтому я почти уверен, что решение просто неправильно.

Давайте начнем с установки чего-то прямого: медленный старт растет экспоненциально; уклонение от перегрузки растет линейно, а быстрое восстановление растет линейно, хотя оно использует ту же формулу, что и медленный запуск, чтобы обновить значение cwnd.

Позвольте мне уточнить.

Почему мы говорим, что медленный старт растет cwnd экспоненциально?

Обратите внимание, что cwnd увеличивается на MSS байт для каждого полученного ACK.

Посмотрим на пример. Предположим, что cwnd инициализируется 1 MSS (значение MSS обычно составляет 1460 байт, поэтому на практике это означает, что cwnd инициализируется до 1460). На этом этапе, поскольку размер окна перегрузки может содержать только один пакет, TCP не будет отправлять новые данные до тех пор, пока этот пакет не будет подтвержден. Предполагая, что ACK не теряются, это означает, что каждый RTT-секунда передается приблизительно по одному новому пакету (напомним, что RTT - это время в оба конца), так как нам нужно (1/2) * RTT отправить пакет и ( 1/2) * RTT для ACK.

Таким образом, это приводит к скорости отправки приблизительно MSS/RTT бит. Теперь помните, что для каждого ACK, cwnd увеличивается на MSS. Таким образом, как только будет получен первый ACK, cwnd станет 2*MSS, теперь мы можем отправить 2 пакета. Когда эти два пакета подтверждены, мы увеличиваем cwnd дважды, так что теперь cwnd есть 4*MSS. Большой! Мы можем отправить 4 пакета. Эти 4 пакета подтверждены, поэтому мы увеличиваем cwnd 4 раза! Итак, мы имеем cwnd = 8*MSS. И тогда мы получаем cwnd = 16*MSS. Мы по существу удваиваем cwnd каждые RTT секунд (это также объясняет, почему cwnd = cwnd+MSS*(MSS/cwnd) в предотвращении перегрузок приводит к линейному росту)

Да, это сложно, формула cwnd = cwnd+MSS легко заставляет нас считать ее линейной - распространенное заблуждение, потому что люди часто забывают, что это применяется для каждого подтвержденного пакета.

Обратите внимание, что в реальном мире передача 4 пакетов не обязательно генерирует 4 ACK. Он может генерировать только 1 ACK, но поскольку TCP использует кумулятивные ACK, этот единственный ACK все еще подтверждает 4 пакета.

Почему быстрое восстановление линейно?

Формула cwnd = cwnd+MSS применяется как при медленном запуске, так и при предотвращении перегрузки. Можно было бы подумать, что это заставляет оба государства индуцировать экспоненциальный рост. Однако быстрое восстановление применяет эту формулу в другом контексте: при получении дубликата ACK. В этом заключается разница: при медленном запуске один RTT признал целую кучу сегментов, и каждый подтвержденный сегмент предоставил + 1MSS новому значению cwnd, тогда как при быстром восстановлении дублирующий ACK тратит RTT, чтобы признать потеря одного сегмента, поэтому вместо обновления cwnd N раз каждые RTT секунд (где N - количество переданных сегментов), мы обновляем cwnd один раз для сегмента, который был LOST. Таким образом, мы "потратили впустую" одно путешествие в оба конца с одним сегментом, поэтому мы увеличиваем cwnd на 1.

О предотвращении переполнения - это я объясню ниже при анализе графика.

Анализ графика

Хорошо, так что посмотрим, что именно происходит на этом графике, круг за раундом. Ваша фотография верна до некоторой степени. Сначала дайте мне понять некоторые вещи:

Когда мы говорим, что медленный старт и быстрое восстановление растут экспоненциально, это означает, что он растет экспоненциально по кругу, как показано на картинке. Итак, это правильно. Вы правильно идентифицировали раунды с синими кругами: обратите внимание, как значения cwnd экспоненциально растут из одного круга в следующий - 1, 2, 4, 8, 16,...
Ваша фотография, кажется, говорит, что после медленного старта протокол переходит в Fast Recovery. Это не то, что происходит. Если бы он перешел к Fast Recovery из Slow Start, мы увидели бы, что cwnd будет уменьшено вдвое. Это не то, что показывает график: значение cwnd не уменьшается до половины от T = 6 до T = 7.

Хорошо, теперь давайте посмотрим, что именно происходит в каждом раунде. Обратите внимание, что единица времени на графике является раундом. Итак, если в момент времени T = X мы передаем N сегментов, то предполагается, что в момент времени T = X + 1 эти N сегментов были ACKed (при условии, что они не были потеряны, конечно).

Также обратите внимание, как мы можем узнать значение ssthresh, просто посмотрев на график. При T = 6, cwnd перестает расти экспоненциально и начинает расти линейно, а его значение не уменьшается. Единственный возможный переход от медленного старта к другому состоянию, не связанный с уменьшением cwnd, - это переход к предотвращению перегрузки, который происходит, когда размер окна перегруженности равен ssthresh. На графике видно, что это происходит, когда cwnd равно 32. Итак, мы сразу знаем, что ssthresh инициализируется 32 MSS. В книге показан очень похожий график на стр. 276 (рис. 3.53), где авторы делают аналогичный вывод:

В нормальных условиях это происходит - когда TCP впервые переключается с экспоненциального роста до линейного роста, не уменьшая размер окна, он всегда потому, что он достиг порога и переключается на предотвращение перегрузки.

Наконец, предположим, что MSS составляет не менее 1460 байт (обычно это 1460 байт, поскольку Ethernet имеет MTU = 1500 байт, и нам нужно учитывать размер заголовков TCP + IP, которые вместе нуждаются в 40 байтах). Это важно, когда cwnd превышает ssthresh, так как cwnd единица MSS и ssthresh выражается в байтах.

Итак, идем:

T = 1:

cwnd = 1 MSS; ssthresh = 32 kB

Передача 1 сегмента

T = 2

1 признанный сегмент

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 2

Передача 2 сегментов

T = 3

2 сегмента признаны

cwnd + = 2; ssthresh = 32 kB

Новое значение cwnd: 4

Передача 4 сегментов

T = 4

Подтверждено 4 сегмента

cwnd + = 4; ssthresh = 32 kB

Новое значение cwnd: 8

Передача 8 сегментов

T = 5

Подтверждено 8 сегментов

cwnd + = 8; ssthresh = 32 kB

Новое значение cwnd: 16

Передача 16 сегментов

T = 6

Подтверждено 16 сегментов

cwnd + = 16; ssthresh = 32 kB

Новое значение cwnd: 32

Передача 32 сегментов

Хорошо, посмотрим, что происходит сейчас. cwnd достигло ssthresh (32 * 1460 = 46720 байт, что больше 32000). Пришло время переключиться на предотвращение перегрузки. Обратите внимание, как значения cwnd растут экспоненциально по раундам, поскольку каждый подтвержденный пакет вносит 1 MSS в новое значение cwnd, и каждый отправленный пакет подтверждается в следующем раунде.

Переключение на предотвращение перегрузки

Теперь cwnd не будет увеличиваться экспоненциально, потому что каждый ACK больше не будет вносить свой вклад в 1 MSS. Вместо этого каждый ACK вносит вклад MSS*(MSS/cwnd). Так, например, если MSS составляет 1460 байт, а cwnd - 14600 байт (поэтому в начале каждого раунда мы отправляем 10 сегментов), то каждый ACK (при условии, что один ACK на сегмент) будет увеличиваться cwnd на 1/10 MSS (146 байт). Поскольку мы отправляем 10 сегментов, и в конце раунда мы предполагаем, что каждый сегмент был признан, то в конце раунда мы увеличили cwnd на 10 * 1/10 = 1. Другими словами, каждый сегмент вносит небольшую долю в cwnd, так что мы просто увеличиваем cwnd на 1 MSS каждый раунд. Итак, теперь каждый раунд увеличивает cwnd на 1, а не на количество сегментов, которые были переданы/подтверждены.

Мы остаемся в избегании перегрузки до тех пор, пока не будет обнаружена какая-либо потеря (либо три дубликата ACK, либо тайм-аут).

Теперь возобновим часы...

T = 7

Зарегистрировано 32 сегмента

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 33

Передача 33 сегментов

Обратите внимание, что cwnd перешло от 32 до 33, хотя было подтверждено 32 сегмента (каждый ACK поэтому вносит вклад 1/32). Если бы мы были в медленном запуске, как и в T = 6, мы имели бы cwnd += 32. Это новое значение cwnd также согласуется с тем, что мы видим на графике в момент времени T = 7.

T = 8

Зарегистрировано 33 сегмента

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 34

Передача 34 сегментов

T = 9

Подтверждено 34 сегмента

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 35

Передача 35 сегментов

Обратите внимание, что это согласуется с графиком: при T = 9 имеем cwnd = 35. Это продолжается до T = 16...

T = 10

Зарегистрировано 35 сегментов

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 36

Передача 36 сегментов

T = 11

Зарегистрировано 36 сегментов

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 37

Передача 37 сегментов

T = 12

Зарегистрировано 37 сегментов

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 38

Передача 38 сегментов

T = 13

Зарегистрировано 38 сегментов

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 39

Передача 39 сегментов

T = 14

подтверждено 39 сегментов

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 40

Передача 40 сегментов

T = 15

Зарегистрировано 40 сегментов

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 41

Передача 41 сегмента

T = 16

Зарегистрировано 41 сегмент

cwnd + = 1; ssthresh = 32 kB

Новое значение cwnd: 42

Передача 42 сегментов

PAUSE

Что происходит сейчас? График показывает, что размер окна скопления уменьшается примерно до половины его размера, а затем он растет линейно по раундам снова. Единственная возможность состоит в том, что было 3 дублирующих ACK, и протокол переключается на быстрое восстановление. График показывает, что он не переключается на медленный старт, потому что это приведет к тому, что cwnd снизится до 1. Таким образом, единственный возможный переход - быстрое восстановление.

Вводя быстрое восстановление, получим ssthresh = cwnd/2. Помните, что cwnd единиц MSS и ssthresh находится в байтах, мы должны быть осторожны с этим. Таким образом, новое значение ssthresh = cwnd*MSS/2 = 42*1460/2 = 30660.

Опять же, это соответствует графику; обратите внимание, что ssthresh будет удалено в ближайшем будущем, когда cwnd будет чуть меньше 30 (напомним, что с MSS = 1460 отношение не соответствует точно 1:1, поэтому мы попадаем в порог, даже если размер окна перегруженности немного ниже 30).

Переключение на предотвращение переполнения также приводит к тому, что новое значение cwnd будет ssthresh+3MSS = 21+3 = 24 (помните, чтобы быть осторожным с единицами, здесь я снова преобразовал ssthresh в MSS, потому что наши значения cwnd учитываются в MSS).

На данный момент мы находимся в избегании перегрузки, с T = 17, ssthresh = 30660 bytes и cwnd = 24.

При входе в T = 18 могут произойти две вещи: либо мы получаем дубликат ACK, либо нет. Если мы этого не сделаем (так это новый ACK), мы перейдем к предотвращению перегрузок. Но это привело бы к cwnd до значения ssthresh, что равно 21. Это не соответствует графику - график показывает, что cwnd продолжает увеличиваться линейно. Кроме того, он не переключается на медленный запуск, потому что это приведет к тому, что cwnd снизится до 1. Это означает, что быстрое восстановление не остается, и мы получаем дубликаты ACK. Это происходит до времени T = 22:

T = 18

Дубликат ACK прибыл