Примеры сетевых топологий
TCP-reno
В TCP-reno [] при нормальной ситуации размер окна меняется циклически. Размер окна увеличивается до тех пор, пока не произойдет потеря сегмента. TCP-reno имеет две фазы изменения размера окна: фаза медленного старта и фаза избежания перегрузки. При получении отправителем подтверждения доставки в момент времени t + tA [сек], текущее значение размера окна перегрузки cwnd(t) преобразуется в cwnd(t + tA) согласно (1):
где ssth(t) [пакетов] - значение порога, при котором TCP переходит из фазы медленного старта в фазу исключения перегрузки. Когда в результате таймаута детектируется потеря пакета значения cwnd(t) и ssth(t) обновляются следующим образом:
cwnd(t)=1; ssth(t)=(cwnd(t))/2;
С другой стороны, когда TCP детектирует потерю пакета согласно алгоритму быстрой повторной передачи, cwnd(t) и ssth(t) обновляются иначе:
ssth(t) = (cwnd(t))/2; cwnd(t)= ssth(t);
TCP-reno после этого переходит в фазу быстрого восстановления. В этой фазе размер окна увеличивается на один пакет, когда получается дублированное подтверждение. С другой стороны, cwnd(t) делается равным ssth(t), когда приходит не дублированный отклик для пакета, посланного повторно. В случае таймаута ssth(t)= (cwnd(t))/2; cwnd=1 (смотри описание алгоритма TCP-Tahoe).
Результаты моделирования показывают, что каждое соединение обычно теряет около двух пакетов в каждом эпизоде перегрузки. Потери случаются, когда буфер полон и одно соединение увеличивает размер окна на единицу. Когда ячейки из этого нового пакета приходит в буфер, они обычно вызывают потерю ячеек, принадлежащих двум пакетам (конец пакета, пришедшего из другого соединения, и начала следующего). Итак, в среднем следует ожидать потерю трех пакетов на одно столкновение. В нашем примере двух соединений с RTT 40 мсек и 80 мсек, раз буфер полон и произошло столкновение, эпизод перегрузки длится 40 мсек. За время этого периода 80 мсек соединение увеличивает свое окно грубо 50% времени. То есть среднее число потерянных пакетов из-за этого увеличивается в 1.5 раза.
Следовательно, всего 4.5 пакетов, или 2. 25 пакетов на соединение теряется в среднем на один эпизод перегрузки.
В настоящее время наиболее популярной является модель NewReno, изложенная в документе RFC-3782 (апрель 2004 года), и использующая алгоритм Fast Retransmit & Fast Recovery (быстрая повторная пересылка и быстрое восстановление). В случае, когда доступна опция выборочного подтверждения (SACK), отправитель знает, какие пакеты следует переслать повторно на фазе быстрого восстановления (Fast Recovery). В отсутствии опции SACK нет достаточной информации относительно пакетов, которые нужно послать повторно. При получении трех дублированных подтверждений (DUPACK) отправитель считает пакет потерянным и посылает его повторно. После этого отправитель может получить дополнительные дублированные подтверждения, так как получатель осуществляет подтверждение пакетов, которые находятся в пути, когда отправитель перешел в режим Fast Retransmit. В случае потери нескольких пакетов из одного окна отправитель получает новые данные, когда приходит подтверждение для повторно посланных пакетов. Если потерян один пакет и не было смены порядка пакетов, тогда подтверждение этого пакета будет означать успешную доставку всех предыдущих пакетов до перехода в режим Fast Retransmit. Однако, если потеряно несколько пакетов, тогда потверждение повторно посланного пакета подверждает доставку некоторых но не всех пакетов, посланных до перехода в режим быстрой повторной пересылки (Fast Retransmit). Такие подтверждения называются частичными (смотри также ).
Разработчики назвали алгоритм быстрого восстановления NewReno, так как он значительно отличается от базового алгоритма Reno, описанного в RFC-2581. Предложенный алгоритм дает определенные преимущества по ставнению с каноническим Reno при самых разных сценариях. Однако, при одном сценарии канонический Reno превосходит NewReno - это происходит при изменении порядка следования пакетов.
Алгоритм NewReno использует переменную recover (восстановление), исходное значение которой равно исходному порядкомому номеру пакета.
Рассмотрим узловые этапы реализации алгоритма.
1) Три задублированных ACK:
Когда отправителю приходят три задублированных ACK, а он не находится в состоянии Fast Recovery, проверяется, перекрывает ли поле Cumulative Acknowledgement больший диапазон, чем задано переменной recover. Если это так, то исполняется операция 1A. В противном случае 1B.
1A) Запуск Fast Retransmit:
Если система находится в этом режиме, ssthresh делается равным значению не более, чем задано уравнением 1. (Это уравнение 3 из []).
ssthresh = max (FlightSize / 2, 2*SMSS) (1)
Кроме того, переменная recover делается равной наибольшему порядковуму номеру переданного пакета, и осуществляется переход к пункту 2.
1B) Без быстрой повторной передачи:
Не производится вход в режим быстрой повторной передачи и быстрого восстановления. В частности не изменяется ssthresh, не выполняется переход к пункту 2, чтобы передать потерянный сегмент, и не делается перехода к пункту 3 при последующих задублированных ACK.
2) Вход в режим быстрой повторной передачи:
Передается потерянный сегмент и устанавливается cwnd равным ssthresh плюс 3*SMSS.
Это искуственно увеличивает окно перегрузки на несколько сегментов (три), которые покинули сеть и буферизованы получателем.
3) Быстрое восстановление:
Для каждого нового дублированного ACK, полученного в режиме быстрого восстановления, cwnd увеличивается на SMSS. Это искуственно увеличивает окно перегрузки, для того чтобы учесть сегмент, который покинул сеть.
4) Быстрое восстановление, продолжение:
Сегмент передается, если это разрешено новым значением cwnd и значением window, объявленным получателем.
5) Когда приходит ACK, подтверждающее получение новых данных, это ACK может быть подтверждением, связанным с повторной передачей во время этапа 2 или с более поздней повторной передачей.
Полное подтверждение:
Если ACK подтверждает все данные вплоть до позиции, указанной переменной recover, тогда ACK подтверждает получение промежуточных сегментов, начиная с передачи потерянного сегмента и получения тройного диблированного ACK. cwnd устанавливается либо (1) min (ssthresh, FlightSize + SMSS) либо (2) ssthresh, где ssthresh равно значению, установленному на этапе 1; это называется снижением ("сдутием") значения окна.
Заметим, что FlightSize (FlightSize - объем посланных, но еще неподтвержденных данных) на этапе 1 относится к объему данных не доставленных на этапе 1, когда произошел переход в режим быстрого востстановления, в то время как FlightSize на этапе 5 относится к объему данных недоставленных на этапе 5, когда произошел выход из режима быстрого восстановления. Если выбрана вторая опция, реализации разрешено принять меры, чтобы избежать возможного всплеска информационного потока, в случае, когда объем недоставленных данных в сети много меньше, чем допускает окно перегрузки. Простым механизмом является ограничение числа информационных пакетов, которые могут быть посланы в ответ на одно подтверждение; это называется "maxburst_" в программе моделирования NS. Выход из режима быстрого восстановления.
Частичное подтверждение:
Если это ACK в действительности не подтверждает доставку всех данных вплоть до позции, заданной recover включительно, тогда это частичное ACK. В этом случае передается первый неподтвержденный сегмент. Снижается значение окна перегрузки с учетом объема новых данных, подтвержденных с использованием поля групового подтверждения. Если частичное ACK подтверждает как минимум один SMSS данных, тогда к окну перегрузки добавляется SMSS байт. Так как на этапе 3, это искусственно увеличивает окно перегрузки, для того чтобы учесть сегмент, который покинул сеть. Посылается новый сегмент, если это разрешено новым значением cwnd. Это "частичное сокращение окна" пытается гарантировать то что, когда режим быстрого восстановления в конце концов завершится, объем недоставленных данных будет примерно равен ssthresh. Выхода из режима быстрого восстановления не производится (т.e., если поздее придет какой-либо задублированный ACK, выполняются шаги 3 и 4).
Для первого частичного ACK, который приходит во время реализации быстрого восстановления, сбрасывается таймер повторной передачи.
6) Таймауты повторной передачи:
После RTO в переменную recover записывается наибольший порядковый номер переданного сегмента и производится выход из режима быстрого восстановления, если это возможно.
Этап 1 специфицирует проверку того, что поле кумулятивного подтверждения покрывает больший диапазон, чем это задано переменной recover. Так как поле подтверждения содержит порядковый номер, который получатель ожидает получить, "ack_number" подтверждения покрывает больший диапазон номеров, чем recover когда:
ack_number - 1 > recover;
т.e., получено подтверждение по крайней мере на один байт данных больше, чем наибольший байт из недоставленных данных, с момента последнего входа в режим быстрой повторной отправки.
4. Сброс таймера повторной передачи в ответ на частичное подтверждение. Возможным вариантом реакции на частичные подтверждения может быть сброс таймера повторной передачи после частичного подтверждения. В этом случае, если в пределах окна потеряно большое число пакетов, таймер повторной передачи TCP-отправителя выдает таймаут, а отправитель данных запускает процедуру медленного старта.
Одной из возможностей получения более оптимального алгоритма в случае множественных потерь пакетов является схема, подобная медленному старту, когда осуществляется сброс таймера повторной посылки при каждом частичном подтверждении. Следует заметить, что существует определенное ограничение эффективности в случае отсутствия поддержки опции SACK.
5. Повторные передачи после частичного подтверждения
Возможным вариантом реакции на частичное подтверждение может быть повторная посылка более чем одного пакета, и сброс таймера повторной пересылки после повторной посылки. В случае множественных потерь пакетов повторная посылка двух пакетов при получении частичного подтверждения обеспечивает более быстрое восстановление системы. Такой подход требует меньше времени, чем N RTT в случае потери N пакетов. Однако при отсутствии опции SACK, медленный старт обеспечивает достаточно быстрое восстановление системы без пересылки лишних пакетов.
Этап 5 определяет, что TCP отправитель реагирует на частичные ACK сокращением окна перегрузки на величину, соответствующую объему подтвержденных данных, добавляя назад SMSS байт, если частичное ACK подтверждает по крайней мере SMSS байт новых данных, и, посылая новый сегмент, если это допускается новым значением cwnd.
Таким образом, посылается только один посланный ранее пакет в ответ на каждое частичное подтверждение, но могут быть посланы и новые пакеты, в зависимости от объема подтвержденной частично доставки. Напротив, в варианте NewReno, описанном в (Fall, K. and S. Floyd, "Simulation-based Comparisons of Tahoe, Reno and SACK TCP", Computer Communication Review, July 1996. URL ), в случае частичного подтверждения устанавливается значение окна перегрузки равным ssthresh. Такой подход является более консервативным, и не пытается точно определить число недоставленных пакетов после получения частичного подтверждения.
6. Исключение кратных быстрых повторных передач
В отсутствии опции SACK или временных меток, задублированные подтверждения не несут какой-либо информации, позволяющей идентифицировать информационные пакеты, которые вызвали задублированные подтверждения. В этом случае, отправитель TCP данных не может разделить задублированные подтверждения, вызванные потерей или задержкой пакетов, от задублированных ACK, связанных с повторно посланными информационными пакетами, уже полученными адресатом.
Проблемы оптимальности для алгоритмов быстрого восстановления и быстрой повторной пересылки в Reno TCP, связанные с множественными быстрыми повторными пересылками, относительно меньше по сравнению с аналогичными проблемами в случае алгоритма Tahoe TCP, который не использует быстрого восстановления. Несмотря ни на что ненужные быстрые повторные пересылки могут произойти в Reno TCP, если не использовать дополнительные механизмы связанные с применением переменной recover.
Алгоритм, описанный в RFC-3782, соответствует варианту Careful алгоритма NewReno TCP из RFC 2582, и исключает проблему множественных повторных пересылок. Этот алгоритм использует переменную recover, значение которой соответствует исходному порядковому номеру посланного пакета. После каждого таймаута повторной передачи, наибольший порядковый номер переданного пакета записывается в переменную recover.
Если после таймаута повторной передачи, отправитель TCP повторно пошлет пакеты, уже полученные адресатом, тогда отправитель получит три задублированных отклика, которые перекроют диапазон, заданный переменной recover.
В этом случае задублированные ACK не указывают на случай перегрузки. Они просто сообщают, что отправитель повторно послал по крайней мере три пакета.
Однако, когда повторно посланные пакеты сами теряются, отправитель может получить три задублированные отклика, которые перекрывают меньший диапазон чем определяется переменной recover. Для протокола TCP, который использует рассмотренный здесь алгоритм, отправитель в данном сценарии не предполагает, что потеряннный пакет сопряжен с одним из задублированных подтверждений.
Существует несколько эвристических подходов, основанных на временных метках или на преимуществах поля кумулятивных (групповых) подтверждений, которые отправитель в некоторых случаях использует, чтобы различить случаи с тремя задублированными ACK, следующие за повторно посланным пакетом, который был потерян, и тремя задублированными подтверждениями, сопряженными с откликами на повторно посланные по ошибке сегментами. Отправитель может использовать эвристику, чтобы решить следует ли запускать режим быстрой повторной передачи, даже если задублированные ACK не перекрывают диапазон номеров, определенный переменной recover.
