ОБНОВЛЕНИЕ: мой первоначальный ответ согласился с решением, но после тщательного обдумывания я считаю, что решение неверное. Этот ответ был переписан заново; пожалуйста, прочтите внимательно. Я показываю, почему быстрое восстановление вводится в момент времени T = 16 и почему протокол остается там до T = 22. Данные на графике подтверждают мою теорию, поэтому я почти уверен, что решение совершенно неверное.
Давайте начнем с того, что кое-что проясним: медленный старт растет экспоненциально; Предотвращение перегрузки растет линейно, а быстрое восстановление растет линейно, даже если для обновления значения cwnd используется та же формула, что и при медленном запуске.
Позвольте мне уточнить.
Почему мы говорим, что "Медленный старт" растет cwnd экспоненциально?
Обратите внимание, что cwnd увеличивается на MSS байта для каждого полученного ACK.
Посмотрим на пример. Предположим, что cwnd инициализируется значением 1 MSS (значение MSS обычно составляет 1460 байт, поэтому на практике это означает, что cwnd инициализируется значением 1460). На этом этапе, поскольку размер окна перегрузки может содержать только 1 пакет, 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 один раз для сегмента, который был ПОТЕРЯН. Таким образом, мы «потратили» один круговой обход всего на один сегмент, поэтому мы увеличиваем cwnd только на 1.
О предотвращении перегрузки - об этом я объясню ниже, анализируя график.
Анализ графика
Хорошо, давайте посмотрим, что именно происходит на этом графике, шаг за шагом. Ваша картина в какой-то степени верна. Позвольте мне сначала прояснить некоторые вещи:
- Когда мы говорим, что медленный старт и быстрое восстановление растут экспоненциально, это означает, что он растет экспоненциально раунд за раундом, как показано на картинке. Итак, это правильно. Вы правильно определили раунды с синими кружками: обратите внимание, как значения
cwnd экспоненциально растут от одного кружка к другому - 1, 2, 4, 8, 16, ...
- На вашем изображении, кажется, написано, что после медленного старта протокол переходит в быстрое восстановление. Это не то, что происходит. Если бы он перешел на быстрое восстановление из медленного старта, мы бы увидели, что
cwnd уменьшится вдвое. Это не то, что показывает график: значение cwnd не уменьшается вдвое с T = 6 до T = 7.
Хорошо, теперь давайте посмотрим, что именно происходит в каждом раунде. Обратите внимание, что единица времени на графике - раунд. Итак, если в момент времени T = X мы передаем N сегментов, то предполагается, что в момент времени T = X + 1 эти N сегментов были подтверждены (конечно, при условии, что они не были потеряны).
Также обратите внимание, как мы можем определить значение 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 КБ
Передать 1 сегмент
T = 2
1 сегмент подтвержден
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 2
Передать 2 сегмента
T = 3
2 сегмента подтверждены
cwnd + = 2; ssthresh = 32 КБ
Новое значение cwnd: 4
Передать 4 сегмента
T = 4
4 сегмента подтверждены
cwnd + = 4; ssthresh = 32 КБ
Новое значение cwnd: 8
Передача 8 сегментов
T = 5
8 сегментов подтверждены
cwnd + = 8; ssthresh = 32 КБ
Новое значение cwnd: 16
Передача 16 сегментов
T = 6
16 сегментов подтверждены
cwnd + = 16; ssthresh = 32 КБ
Новое значение 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, а не на количество сегментов, которые были переданы / подтверждены.
Мы будем избегать перегрузки до тех пор, пока не будет обнаружена какая-либо потеря (либо 3 повторяющихся ACK, либо тайм-аут).
А теперь позвольте часам возобновить работу ...
T = 7
32 сегмента подтверждены
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 33
Передать 33 сегмента
Обратите внимание, как cwnd перешел с 32 на 33, хотя было подтверждено 32 сегмента (каждый ACK, таким образом, составляет 1/32). Если бы мы были в медленном старте, как в T = 6, у нас было бы cwnd += 32. Это новое значение cwnd также согласуется с тем, что мы видим на графике в момент времени T = 7.
T = 8
33 сегмента признаны
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 34
Передать 34 сегмента
T = 9
34 сегмента признаны
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 35
Передача 35 сегментов
Обратите внимание, что это согласуется с графиком: при T = 9 у нас есть cwnd = 35. Это продолжается до Т = 16 ...
T = 10
35 сегментов признаны
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 36
Передать 36 сегментов
T = 11
36 сегментов признаны
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 37
Передать 37 сегментов
T = 12
37 сегментов признаны
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 38
Передать 38 сегментов
T = 13
38 сегментов признаны
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 39
Передать 39 сегментов
T = 14
39 сегментов признаны
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 40
Передача 40 сегментов
T = 15
40 сегментов подтверждены
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 41
Передать 41 сегмент
T = 16
41 сегмент признан
cwnd + = 1; ssthresh = 32 КБ
Новое значение cwnd: 42
Передать 42 сегмента
ПАУЗА
Что происходит сейчас? График показывает, что размер окна перегрузки уменьшается примерно до половины своего размера, а затем снова увеличивается линейно по циклам. Единственная возможность состоит в том, что было 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
cwnd + = 1; ssthresh = 30660 байт
Новое значение cwnd: 25
T = 19
Получен дубликат ACK
cwnd + = 1; ssthresh = 30660 байт
Новое значение cwnd: 26
T = 20
Получен дубликат ACK
cwnd + = 1; ssthresh = 30660 байт
Новое значение cwnd: 27
T = 21
Получен дубликат ACK
cwnd + = 1; ssthresh = 30660 байт
Новое значение cwnd: 28
T = 22
Получен дубликат ACK
cwnd + = 1; ssthresh = 30660 байт
Новое значение cwnd: 29
** ПАУЗА **
Мы все еще находимся в режиме быстрого восстановления, и теперь внезапно cwnd падает до 1. Это показывает, что он снова входит в режим медленного запуска. Новое значение ssthresh будет 29*1460/2 = 21170 и cwnd = 1. Это также означает, что, несмотря на наши усилия по ретрансляции сегмента, был тайм-аут.
T = 23
cwnd = 1; ssthresh = 21170 байт
Передать 1 сегмент
T = 24
1 сегмент подтвержден
cwnd + = 1; ssthresh = 21170 байт
Новое значение cwnd: 2
Передать 2 сегмента
T = 25
2 сегмента подтверждены
cwnd + = 2; ssthresh = 21170 байт
Новое значение cwnd: 4
Передать 4 сегмента
T = 26
4 сегмента подтверждены
cwnd + = 4; ssthresh = 21170 байт
Новое значение cwnd: 8
Передача 8 сегментов
...
Надеюсь, это проясняет.
person
Filipe Gonçalves
schedule
13.06.2015
Почему cwnd экспоненциально растет в состоянии быстрого восстановления? (на картинке я случайно написал целесообразно, а не экспоненциально)
