Компьютерные сети. 6-е изд. - Эндрю Таненбаум

порядок их получения. Поэтому в TCP условно считается, что три дубликата подтверждений сигнализируют о потере пакета. Также по номеру подтверждения можно установить, какой именно пакет потерян. Это следующий по порядку пакет. Его повторную передачу можно выполнить сразу, не дожидаясь срабатывания таймера.

Этот эвристический метод получил название быстрого повтора передачи (fast retransmisson). Когда он происходит, порог медленного старта все равно устанавливается в половину текущего окна перегрузки, как и в случае тайм-аута. Медленный старт можно начать заново, взяв окно размером в один сегмент. Новый пакет будет отправлен через один RTT, за который успеет прийти подтверждение для повторно переданного пакета, а также все данные, переданные в сеть до обнаружения потери пакета.

Существующий на данный момент алгоритм контроля перегрузки проиллюстрирован на илл. 6.46. Эта версия называется TCP Tahoe в честь 4.2BSD Tahoe 1988 года, куда она входила. Максимальный размер сегмента в данном примере равен 1 Кбайт. Сначала окно перегрузки было равно 64 Кбайт, но затем произошел тайм-аут, и порог стал равен 32 Кбайт, а окно перегрузки — 1 Кбайт (передача 0). Окна перегрузки удваивается по экспоненте, пока не достигает порога (32 Кбайт).

Илл. 6.46. Медленный старт и последующее аддитивное увеличение в TCP Tahoe

Окно увеличивается каждый раз, когда приходит новое подтверждение, то есть не непрерывно, поэтому мы имеем дискретный ступенчатый график. Однако после превышения порога рост окна приобретает линейный характер. На каждом круге размер окна увеличивается на один сегмент.

Передачи на круге 13 оказываются неудачными (как и положено), и одна из них заканчивается потерей пакета. Отправитель обнаруживает это после получения трех дубликатов подтверждений. Потерянный пакет передается повторно, а пороговое значение устанавливается в половину текущего размера окна (на данный момент это 40 Кбайт, то есть половина составляет 20 Кбайт), и снова запускается медленный старт. Для нового запуска с окном в один сегмент требуется еще один круг. За это время все ранее переданные данные, включая копию потерянного пакета, успевают покинуть сеть. Окно перегрузки снова увеличивается в соответствии с алгоритмом медленного старта до тех пор, пока оно не дойдет до порогового значения в 20 Кбайт. После этого рост окна снова становится линейным. Так будет продолжаться до следующей потери пакета, которая будет выявлена с помощью дубликатов подтверждений или после наступления тайм-аута (или же до заполнения окна получателя).

Версия TCP Tahoe (в которой, кстати, имеются хорошие таймеры повторной передачи) реализует работающий алгоритм контроля перегрузки, который решает проблему отказа сети из-за перегрузки. Однако Джейкобсон придумал, как добиться большего. Во время быстрой повторной передачи соединение работает с окном слишком большого размера, но скорость прихода подтверждений продолжает учитываться. Каждый раз, когда приходит дубликат подтверждения, велика вероятность того, что еще один пакет покинул сеть. Это позволяет подсчитывать общее количество пакетов в сети и продолжать отправку нового пакета при получении каждого дополнительного дубликата подтверждения.

Эвристический метод реализации этой идеи называется быстрым восстановлением (fast recovery). Это временный режим, направленный на поддержание учета скорости прихода подтверждений в тот момент, когда порогом медленного старта становится текущий размер окна или его половина (во время быстрой повторной передачи). Для этого дубликаты подтверждений (включая те три, которые инициировали быструю повторную передачу) подсчитываются до тех пор, пока число пакетов в сети не снизится до нового порогового значения. На это уходит примерно половина RTT. С этого момента на каждый полученный дубликат подтверждения отправитель может передавать в сеть новый пакет. Через один RTT после быстрой повторной передачи получение потерянного пакета подтвердится. В это время поток дубликатов подтверждений прекратится, и алгоритм выйдет из режима быстрого восстановления. Окно перегрузки будет равняться новому порогу медленного старта и начнет увеличиваться линейно.

Этот метод позволяет TCP избегать медленного старта в большинстве ситуаций, за исключением случаев установления нового соединения и возникновения тайм-аутов. Последнее может произойти, если теряется больше одного пакета, а быстрая повторная передача не помогает. Вместо повтора медленного старта окно перегрузки активного соединения перемещается по пилообразным (sawtooth) линиям аддитивного увеличения (на один сегмент за RTT) и мультипликативного уменьшения (в полтора раза за RTT). Это и есть правило AIMD, которое мы с самого начала хотели реализовать.

Такое пилообразное движение показано на илл. 6.47. Данный метод используется в протоколе TCP Reno, названном в честь выпущенного в 1990 году дистрибутива 4.3BSD Reno. По сути, это TCP Tahoe с быстрым восстановлением. После начального медленного старта окно перегрузки растет линейно, пока отправитель не обнаружит потерю пакета, получив нужное количество дубликатов подтверждения. Потерянный пакет передается повторно, и далее алгоритм работает в режиме быстрого восстановления. Этот режим дает возможность продолжать учет скорости прихода подтверждений, пока не придет подтверждение доставки повторно переданного пакета. После этого окно перегрузки принимает значение, равное новому порогу медленного старта, а не единице. Это продолжается неопределенно долго. Почти все время размер окна перегрузки близок к оптимальному значению произведения пропускной способности и времени задержки.

Механизмы выбора размера окна, использующиеся в TCP Reno, составляли основу контроля перегрузки в TCP более двух десятилетий. За это время они претерпели ряд незначительных изменений, например появились новые способы

Илл. 6.47. Быстрое восстановление и пилообразный график TCP Reno

выбора начального окна, были устранены различные примеры неоднозначности. Усовершенствования коснулись и механизмов восстановления после потери двух или более пакетов. Так, версия TCP NewReno использует номера частичных подтверждений, полученных после повторной передачи одного потерянного пакета для восстановления другого (Хо; Hoe, 1996) (см. RFC 3782). С середины 1990-х годов стали появляться варианты описанного выше алгоритма, основанные на других законах управления. К примеру, в системе Linux используется CUBIC TCP (Ха и др.; Ha et al., 2008), а в Windows — Compound TCP (Тань и др.; Tan et al., 2006).

Два более серьезных нововведения касаются реализаций TCP. Во-первых, сложность TCP состоит в том, что по потоку дубликатов подтверждений нужно определить, какие пакеты были потеряны, а какие — нет. Номер накопительного подтверждения не содержит такой информации. Простым решением стало применение выборочных подтверждений SACK, в которых может содержаться до трех диапазонов успешно полученных байтов. Эти сведения позволяют отправителю более точно определять, какие пакеты следует передавать повторно, а также следить за еще не доставленными пакетами.

При установлении соединения отправитель и получатель передают друг другу параметр SACK permitted, сообщая о возможности работы с выборочными подтверждениями. Когда SACK включены, обмен данными происходит, как показано на илл. 6.48. Получатель использует поле Acknowledgement number обычным способом —