Этот алгоритм называется медленным стартом (slow start), однако на самом деле он совсем не медленный — это метод экспоненциального роста (особенно в сравнении с предыдущим алгоритмом, который позволяет отправлять целое окно управления потоком за один раз). Медленный старт показан на илл. 6.44. Во время первого RTT отправитель передает в сеть один пакет (и адресат получает один пакет). На втором RTT передается два пакета, на третьем — четыре.
Медленный старт хорошо работает для широкого диапазона значений скорости и RTT. Чтобы регулировать скорость отправки в зависимости от сетевого пути, он использует скорость прихода подтверждений. Посмотрим, как подтверждения возвращаются от отправителя к получателю (илл. 6.44). Когда отправитель получает подтверждение, он увеличивает окно перегрузки на единицу и сразу же передает в сеть два пакета. (Один из них соответствует увеличению окна на единицу, а второй передается взамен пакета, доставленного получателю и, таким образом, покинувшего сеть. В каждый момент времени число неподтвержденных пакетов определяется окном перегрузки.) Однако эти два пакета не обязательно придут на хост-получатель с тем же интервалом, с каким они были отправлены. Допустим, отправитель подключен к сети Ethernet мощностью 100 Мбит/с. На отправку каждого 1250-байтного пакета уходит 100 мкс. Поэтому интервал между пакетами может быть небольшим, от 100 мкс. Ситуация меняется, если путь проходит через ADSL-линию мощностью 1 Мбит/с. Теперь для отправки такого же пакета требуется 10 мс. Таким образом, минимальный интервал между пакетами возрастает по меньшей мере в 100 раз. Он так и останется большим, если только в какой-то момент пакеты не окажутся все вместе в одном буфере.
Илл. 6.44. Медленный старт с начальным окном перегрузки в один сегмент
На илл. 6.44 описанный эффект можно увидеть на примере интервала прибытия пакетов к получателю. Он сохраняется при отправке подтверждений и, следовательно, при их получении отправителем. Если сетевой путь медленный, подтверждения приходят медленно, если быстрый — быстро. В обоих случаях они прибывают через один RTT. Отправитель должен просто учитывать скорость прихода подтверждений при отправке новых пакетов, — это и делает алгоритм медленного старта.
Поскольку алгоритм медленного старта приводит к экспоненциальному росту, в какой-то момент (скорее рано, чем поздно) в сеть будет слишком быстро отправлено чрезвычайно много пакетов. В результате на маршрутизаторах выстроятся очереди. Когда очереди переполняются, происходит потеря пакетов. В этом случае подтверждение для пакета не приходит вовремя и время ожидания TCP-отправителя истекает. На илл. 6.44 можно увидеть слишком быстрый рост алгоритма медленного старта. Через три RTT в сети находится четыре пакета. Чтобы добраться до получателя, им требуется время, равное целому RTT. Это значит, что для данного соединения подходит окно перегрузки размером в четыре пакета. Но поскольку получение пакетов подтверждается, алгоритм медленного старта продолжает увеличивать окно перегрузки, достигнув восьми пакетов за один RTT. Независимо от того, сколько пакетов отправлено, только четыре из них успевают дойти до места назначения за один RTT. Это значит, что сетевая шина заполнена. Новые пакеты, попадая в сеть, будут застревать в очередях на маршрутизаторах, так как сеть не может достаточно быстро доставлять их получателю. Вскоре возникнет перегрузка и потеря пакетов.
Чтобы контролировать медленный старт, отправитель хранит в памяти пороговое значение для каждого соединения — порог медленного старта (slow start threshold). Изначально устанавливается произвольное высокое значение, не превышающее размер окна управления потоком, чтобы не ограничивать возможности соединения. Используя алгоритм медленного старта, TCP продолжает увеличивать окно перегрузки, пока не произойдет тайм-аут или размер окна не превысит порог (либо пока не заполнится окно получателя).
При обнаружении потери пакета (например, при тайм-ауте) порог медленного старта устанавливается в половину окна перегрузки, и весь процесс начинается заново. Дело в том, что текущее окно слишком велико и вызвало перегрузку, которую удалось зафиксировать с опозданием. Вдвое меньший размер окна, успешно применявшийся ранее, дает лучший результат: пропускная способность используется довольно эффективно, а потерь нет. В нашем примере на илл. 6.44 увеличение окна до восьми пакетов может вызвать потери, а окно, равное четырем пакетам, подходит хорошо. В итоге устанавливается исходное значение окна перегрузки, и алгоритм медленного старта выполняется с начала.
При превышении порога медленного старта TCP переключается на аддитивное увеличение. В этом режиме окно перегрузки возрастает на один сегмент через интервалы времени, равные RTT. Как и при медленном старте, увеличение происходит по мере получения подтверждений о доставке, а не на один сегмент на каждом круге. Пусть cwnd — окно перегрузки, а MSS — максимальный размер сегмента. Обычно увеличение окна производится с коэффициентом (MSS × MSS)/cwnd для каждого из cwnd/MSS пакетов, которые можно подтвердить. Этот рост не должен быть быстрым. Вся идея в том, чтобы TCP-соединение максимально долго работало с размером окна, близким к оптимальному, — не слишком маленьким, чтобы пропускная способность не была низкой, и не слишком большим, чтобы не было перегрузок.
Аддитивное увеличение показано на илл. 6.45. Ситуация та же, что и для медленного старта. В конце каждого круга окно перегрузки отправителя увеличивается настолько, что в сеть может быть передан один дополнительный пакет. По сравнению с медленным стартом линейная скорость роста очень низкая. Для маленьких окон разница не слишком существенна, но она станет ощутимой, если, к примеру, понадобится увеличить окно на 100 сегментов.
Для улучшения производительности можно сделать еще кое-что. Недостаток этой схемы — ожидание тайм-аута. Тайм-ауты могут быть относительно долгими, так что они должны быть минимальными. При потере пакета получатель не подтверждает его, так что номер подтверждения не меняется, а у отправителя нет возможности передавать в сеть новые пакеты, так как его окно перегрузки все еще заполнено. В таком состоянии хост может пробыть довольно долго, пока не сработает таймер и не произойдет повторная передача пакета. На этом этапе медленный старт начинается заново.
Отправитель может быстро выяснить, что один из его пакетов потерян. Новые пакеты, следующие за потерянным, приходят к получателю и вызывают отправку подтверждений, которые имеют один и тот же номер и называются дубликатами подтверждений (duplicate acknowledgements). Каждый раз, когда отправитель получает дубликат подтверждения, есть вероятность, что другой пакет уже пришел к адресату, а потерянный — нет.
Илл. 6.45. Аддитивное увеличение при начальном размере окна в один сегмент
Пакеты могут идти разными путями, поэтому они часто приходят в неправильном порядке. В этом случае дубликаты подтверждений не означают потерю пакетов. Однако в интернете такое случается достаточно редко. Следование пакетов разными маршрутами не слишком нарушает порядок их получения. Поэтому в 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 (в которой, кстати, имеются хорошие таймеры повторной передачи) реализует работающий алгоритм контроля перегрузки, который решает проблему отказа сети из-за перегрузки. Однако Джейкобсон придумал, как добиться большего. Во время быстрой повторной передачи соединение работает с окном слишком большого размера, но скорость прихода подтверждений продолжает учитываться. Каждый раз, когда приходит дубликат подтверждения, велика вероятность того, что еще один пакет покинул сеть. Это позволяет подсчитывать общее количество пакетов в сети и продолжать отправку нового пакета при получении каждого дополнительного дубликата подтверждения.