Алгоритм предотвращения переполнения

Медленный старт, который мы описали в разделе "Медленный старт" главы 20, это способ первоначально установить поток данных по соединению. Однако, в это же самое время мы достигнем предела у промежуточного маршрутизатора, при котором пакеты будут отбрасываться. Предотвращение переполнения это способ, позволяющий предотвратить потерю пакетов. Подробности можно найти в [Jacobson 1988].

Предположение, на котором строится этот алгоритм, заключается в том, что из-за различных повреждений теряется очень малое число пакетов (значительно меньше чем 1%), поэтому потеря пакетов сигнализирует о том, что в каком-либо месте сети между источником и назначением появилось переполнение. Существуют два признака, по которым можно определить, что пакеты теряются: появление тайм-аутов и получение дублированных ACK. (Мы видели последнее в разделе "Пример переполнения" этой главы. Если же использовать тайм-аут как показатель возникновения переполнения, то нам потребуется хороший алгоритм расчета RTT, примерно такой, как описан в разделе "Определение времени возврата".)

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

Предотвращение переполнения и медленный старт требуют, чтобы для каждого соединения были определены две переменные: окно переполнения, cwnd, и размер порога медленного старта, ssthresh. Вместе алгоритмы работают следующим образом:

Инициализация заданного соединения устанавливает cwnd в один сегмент, а ssthresh в 65535 байт. Подпрограмма вывода TCP определит, какое из значений меньше: cwnd или окно, объявленное получателем и никогда не пошлет больше минимального значения. Предотвращение переполнения это способ контролировать поток данных, со стороны отправителя, тогда как объявление окна это способ контролировать поток данных, со стороны получателя. Первый основан на оценке отправителем того, насколько переполнена сеть, тогда как последний связан с величиной доступного буферного пространства у получателя для данного соединения. Когда возникает переполнение (на что указывает тайм-аут или получение дублированных ACK), одна половина текущего размера окна (меньшее значение из величин cwnd и размера окна, объявленного получателем, но по меньшей мере два сегмента) сохраняется в ssthresh. Более того, если мы узнали о переполнении с помощью тайм-аута, cwnd устанавливается в один сегмент (то есть осуществляется медленный старт). Когда новые данные подтверждены удаленным концом, cwnd увеличивается, однако способ этого увеличения зависит от того, работает ли алгоритм медленного старта или предотвращения переполнения. Если cwnd меньше или равно ssthresh, используется медленный старт; иначе используется предотвращение переполнения. Медленный старт продолжается до тех пор, пока мы не достигнем половины пути до того момента где были, когда возникло переполнение (то есть, до того момента пока мы не запишем половину размера окна, которое доставило нам проблемы в шаге 2), после чего используется алгоритм предотвращения переполнения. Медленный старт требует, чтобы cwnd начиналась с одного сегмента и увеличивалась на один сегмент каждый раз при приеме ACK. Как указано в разделе "Медленный старт" главы 20, это открывает окно экспотенциально: посылается один сегмент, затем два, затем четыре и так далее. Предотвращение переполнения требует, чтобы cwnd увеличивалась на 1/cwnd плюс меньшая дробная часть размера сегмента (размер сегмента, поделенный на 8) каждый раз, когда прибывает ACK. (Это ошибка реализации, которая присутствовала во всех релизах 4.3BSD и даже в 4.4BSD. Но этой ошибки нет в будущих реализациях [Floyd 1994]. Обратите внимание на то, что в примерах ниже в главе используется этот термин, потому что примеры исполнялись на реализации с ошибкой [см. рисунок 21.9 и рисунок 21.11]). Это увеличение посредством сложения, по сравнению с экспотенциальным увеличением при медленном старте. Мы хотим увеличивать cwnd по крайней мере на один сегмент за каждый промежуток времени равный времени возврата (вне зависимости от того, сколько ACK было принято за этот RTT), тогда как медленный старт увеличивает cwnd на количество ACK принятых за время возврата. Прибавление меньшей дробной части размера сегмента позволяет быстрее открывать большие окна.

Релиз 4.3BSD Tahoe, описанный в [Leffler et al. 1989], осуществляет медленный старт, только если удаленный конец находится в другой сети. Это было изменено в релизе 4.3BSD Reno таким образом, что медленный старт осуществляется всегда.

На рисунке 21.8 приведено описание медленного старта и предотвращения переполнения. Мы показали размер cwnd и ssthresh в блоках сегментов, тогда как в действительности их размер измеряется в байтах.

Содержание раздела