Управление перегрузкой TCP

Алгоритм аддитивного увеличения/мультипликативного уменьшения (AIMD, англ. additive increase/multiplicative decrease) представляет собой замкнутую систему управления, сочетающую линейный рост окна перегрузки с экспоненциальным уменьшением при возникновении перегрузки. Если несколько потоков используют AIMD, их потребление полосы пропускания постепенно выравнивается.

Этот алгоритм рекомендуется для фазы «предотвращения перегрузки» в стандарте^[2].

В TCP окно перегрузки (CWND, англ. congestion window) определяет, сколько байт данных может быть отправлено в каждый момент времени. Данный параметр поддерживается на стороне отправителя и используется для предотвращения перегрузки канала данных между отправителем и получателем. Окно перегрузки не стоит путать со скользящим окном, которое обеспечивает контроль потока относительно возможностей приёмника. Размер окна перегрузки определяется на основании оценки текущего уровня загруженности канала.

При установлении соединения CWND изначально устанавливается как небольшое кратное максимального размера сегмента (MSS, англ. max segment size). Дальнейшее изменение CWND происходит согласно принципу AIMD: если все сегменты доставляются без потерь и подтверждения приходят вовремя, к размеру окна прибавляется константа. Точный алгоритм может разниться.

Системный администратор может настроить максимальный размер окна или величину постоянной при аддитивном увеличении в рамках оптимизации TCP.

Передача данных также ограничивается размером окна приёма (receive window), который рекламируется приёмником. Таким образом, число передаваемых данных ограничивается минимумом между CWND и окном приёма.

Медленный старт (англ. slow start), описанный в RFC 5681^[3], — часть стратегии управления перегрузкой в TCP, направленная на предотвращение превышения пропускной способности сети.

Алгоритм медленного старта начинается с малого значения CWND — 1, 2, 4 или 10 MSS^[4]. С каждым подтверждением (ACK) размер окна увеличивается на 1 MSS, что фактически удваивает CWND за каждый круговой обход (RTT).

Передача ускоряется за счёт медленного старта, пока не случится потеря пакета, не достигнуто ограничение рекламируемого окна приёма (rwnd), либо не будет достигнут порог медленного старта (ssthresh), определяющий переключение на фазу предотвращения перегрузки.

Когда CWND доходит до ssthresh, TCP переключается на алгоритм предотвращения перегрузки — окно увеличивается не быстрее, чем на 1 MSS за RTT. Часто используется формула, по которой каждое новое подтверждение увеличивает CWND на MSS*MSS/CWND, что обеспечивает почти линейный рост.

При обнаружении потери TCP предполагает перегрузку и сокращает нагрузку на сеть. Конкретные меры зависят от используемого алгоритма.

Если потеря обнаружена по таймауту, ssthresh устанавливается не более половины объёма неподтверждённых данных или 2*MSS — выбирается большее значение.

TCP Tahoe

При потере — повторная передача, половина текущего CWND сохраняется как ssthresh, и медленный старт начинается заново с начального CWND.

TCP Reno

Выполняется быстрая повторная передача, половина CWND сохраняется как ssthresh и в качестве нового CWND, то есть медленный старт пропускается, сразу переходя к фазе предотвращения перегрузки (эта схема называется быстрое восстановление).

Медленный старт исходит из предположения, что все неподтверждённые сегменты — из-за перегруженности сети, что не всегда так (например, при неустойчивой связи на канальном уровне, как в беспроводных сетях).

Механизм медленного старта также неэффективен для коротких соединений: старые веб-браузеры открывали множество последовательных коротких TCP-соединений, каждое из которых начиналось с медленного старта, снижая производительность. Современные браузеры используют параллельные или постоянные соединения.

Быстрая повторная передача (англ. fast retransmit) — усовершенствование TCP, позволяющее сократить задержку, связанную с ожиданием таймаута при потере сегмента. В обычном TCP потери распознаются по истечении таймера, но при получении трёх (и более) дубликатов подтверждений считается, что определённый сегмент утерян, и осуществляется немедленная повторная отправка.

Названия Reno и Tahoe — имена выпусков ОС BSD UNIX, в которых впервые были реализованы соответствующие алгоритмы управления перегрузкой (CCA, англ. congestion control algorithm). Классификация алгоритмов может строиться по:

1. Типу и объёму обратной связи с сетью
2. Возможности внедрения в существующем интернете
3. Ориентированию на определённые характеристики (широкополосность, потери, справедливость, короткие потоки, переменность скоростей, скорость сходимости)
4. Принципу справедливости

Некоторые известные алгоритмы:

Алгоритмы TCP Tahoe и Reno получили названия по версиям ОС 4.3BSD, где они впервые появились (Tahoe для поддержки миникомпьютера CCI Power 6/32 «Tahoe», Reno — для очередного релиза). Алгоритм Tahoe стал широко распространяться с выпуском 4.3BSD Networking Release 1, а улучшения Reno были опубликованы в Networking Release 2 и 4.4BSD-Lite.

Оба алгоритма рассматривают как потерю пакетных данных истечение таймаута (RTO) и дублирующиеся ACK, но различаются реакцией на дубликаты ACK:

• Tahoe: при получении трёх дубликатов ACK — выполняется быстрая повторная передача, порог медленного старта устанавливается в половину текущего CWND, CWND уменьшается до 1 MSS, режим медленного старта активируется заново^[9].
• Reno: при трёх дубликатах ACK выполняется быстрая повторная передача и сразу переход к фазе быстрого восстановления — CWND делится на два, ssthresh приравнивается к новому CWND, медленный старт опускается^[10].

При истечении таймаута ACK оба алгоритма переходят в режим медленного старта с установкой CWND = 1 MSS.

Алгоритм TCP New Reno, описанный в, улучшает процесс повторной передачи на фазе быстрого восстановления Reno. В отличие от Reno, New Reno не делит ssthresh сразу, а ждёт подтверждения всех промежуточных сегментов, а также различает полные и частичные подтверждения, соответствующим образом регулируя окно.

Если ACK подтверждает только часть данных, означает возможную повторную потерю — тогда повторной передаче подвергается первый неподтверждённый сегмент. После таймаута New Reno записывает максимальный переданный порядковый номер и выходит из быстрого восстановления.

При нарушении порядка доставки более чем на 3 сегмента New Reno ошибочно начинает быструю передачу и добавляет лишние повторы.

New Reno показывает сопоставимую с SACK производительность при малых вероятностях ошибок и заметно превосходит Reno в условиях большого числа потерь^[11].

Алгоритм TCP Vegas, предложенный Ларри Петерсоном и Лоренсом Брэкмо из Университета Аризоны, использует измерения задержки и таймауты отдельно для каждого пакета, а не только для последнего. Кроме того, Vegas применяет аддитивный рост окна перегрузки. В сравнительных тестах Vegas отличается самой равномерной работой окна перегрузки^[12].

Vegas не получил широкого распространения, но использовался по умолчанию в альтернативной прошивке DD-WRT v24 SP2^[13].

TCP Hybla^[14][15] устраняет недостатки TCP на соединениях с высокой задержкой, например спутниковых.

BIC (Binary Increase Congestion control) — CCA, оптимизированный для высокоскоростных сетей с большой задержкой (LFN). Использовался по умолчанию в ядрах Linux с 2.6.8 по 2.6.18.

Алгоритм CUBIC — модификация BIC: размер окна задаётся кубической функцией времени, прошедшего с последней перегрузки, точка перегиба соответствует предыдущему размеру окна. CUBIC включён по умолчанию в ядро Linux с версии 2.6.19.

Agile-SD — CCA для Linux, оптимизированный для сетей с малым BDP (локальные и волоконно-оптические сети), особенно при малом размере буфера^[16].

Westwood+ — модификация TCP Reno для большего пропускания в беспроводных и проводных сетях, основана на оценке полосы пропускания через анализ частоты приходящих ACK.

Compound TCP — реализация корпорации Microsoft, использующая два окна перегрузки для оптимальной работы как на LFN, так и с сохранением справедливости; применяется в Windows Vista, Server 2008 и новее, а также портирован на Linux.

TCP Proportional Rate Reduction (PRR)^[17] — алгоритм для точного восстановления окна после перегрузки. В тестах Google PRR снижает среднюю задержку на 3-10 % и количество таймаутов на 5 %. Входит в ядро Linux с версии 3.2^[18].

Bottleneck Bandwidth and Round-trip propagation time (BBR) — алгоритм контроля перегрузки, разработанный в Google (2016). В отличие от большинства CCA, полагающихся на потери, BBR строит модель сети, оценивая максимальную пропускную способность и минимальную задержку^[19]. Внедрение в YouTube увеличило пропускную способность на 4 % в среднем. BBR применяется в Linux TCP c версии 4.9, а также реализован для QUIC^[20].

Отмечаются проблемы с несправедливым распределением полосы между BBR и другими потоками, такими как CUBIC^[21].

BBRv2 и BBRv3 корректируют эти недостатки, внося данные о потерях пакетов и ECN (explicit congestion notification), а также реализуют дополнительную оптимизацию для дата-центров^[22].

Cellular Controlled Delay TCP (C2TCP) — плагин, работающий поверх loss-based TCP (Reno, NewReno, CUBIC, BIC и др.), позволяющий серверам удовлетворять требованиям к крайне малой задержке для приложений вроде VR, видеозвонков, многопользовательских игр в высокодинамичных сотовых сетях (LTE, 5G).

В испытаниях NYU C2TCP демонстрирует в несколько раз меньшую задержку, чем BBR, CUBIC и Westwood.

Elastic-TCP — Linux-алгоритм для облачной среды, повышающий использование полосы на сетях с высоким BDP. Он использует взвешенную функцию, учёт потерь и задержки и не требует ручной настройки параметров^[23].

NATCP (Network-Assisted TCP) — проект S. Abbasloo и др., нацеленный на максимальное использование возможностей сетей с мультидоступом (MEC). NATCP строит работу TCP с учётом заранее известных характеристик сети, используя внешнюю обратную связь о пропускной способности и минимальной задержке^[24].

• FAST TCP
• Генерализованный FAST TCP
• H-TCP
• Data Center TCP
• High Speed TCP
• HSTCP-LP^[25]
• TCP-Illinois
• TCP-LP
• TCP SACK
• Scalable TCP
• TCP Veno^[26]
• Westwood
• XCP^[27]
• YeAH-TCP^[28]
• TCP-FIT^[29]
• CANIT (Congestion Avoidance with Normalized Interval of Time)^[30]
• Неклассические регуляторы на базе нейросетей и генетических алгоритмов^[31]
• D-TCP^[32]
• NexGen D-TCP^[33]
• Copa^[34]

До середины 2010-х годов наиболее распространён был алгоритм New Reno; поддержка SACK реализована почти во всех актуальных ОС и TCP-стеках. Большинство других — альтернативные предложения, находящиеся на стадии апробации. Ядро Linux использует по умолчанию: New Reno (до 2.6.8), BIC (2.6.8-2.6.18), CUBIC (с 2.6.19). FreeBSD переключилась на CUBIC с версии 14.X (ранее применялся New Reno)^[35]. Возможен выбор других реализаций^[36].

С ростом произведения полосы и задержки на соединение TCP становится менее эффективным и устойчивым, что особенно важно для высокоскоростных оптических линий.

Пример «активной» схемы — TCP Interactive (iTCP), позволяющий приложениям реагировать на TCP-события и динамически менять поведение передачи^[37]. Zeta-TCP оценивает перегрузку по потерям и задержке, применяет гибкое масштабирование окна и дополнительные методы для сокращения таймаутов и ускорения загрузки^[38].

Контроллеры TCP можно классифицировать по степени осведомлённости о состоянии сети:^[39]

• Black box — алгоритмы, работающие только на бинарной обратной связи и не учитывающие параметры сети.
• Grey box — используют, кроме признаков потерь, ещё и измерения RTT, контенцию потоков и т. д.
• Green box — алгоритмы с прямым вычислением «честной доли» пропускной способности для каждого потока.

• Highspeed-TCP^[40]
• BIC TCP
• CUBIC TCP
• AIMD-FC (улучшение AIMD с быстрой сходимостью)^[41]
• Binomial Mechanisms
• SIMD Protocol
• GAIMD

• TCP Vegas — использует оценку задержки в буфере, линейно увеличивает/уменьшает CWND.
• FAST TCP — достигает т. ж. равновесия, но применяет пропорциональный контроль.
• TCP BBR — оценивает задержку, использует экспоненциальное наращивание, периодически замедляется ради справедливости.
• TCP Westwood
• C2TCP
• TFRC^[42]
• TCP-Real
• TCP-Jersey

• Bimodal Mechanism — механизм двукратного управления.
• Сигнальные методы на маршрутизаторах
  • Random Early Detection (RED)
  • Explicit Congestion Notification (ECN)
• Network-Assisted Congestion Control
  • NATCP^[5]
  • VCP с двубитовой ECN и собственным протоколом на стороне узла

Следующие алгоритмы требуют введения новых полей в заголовок TCP:

• Explicit Control Protocol (XCP) — пакеты содержат заголовок с полем обратной связи.
• MaxNet — использует информацию о максимальной загруженности одного из маршрутизаторов^[43].
• JetMax

• BIC применялся по умолчанию в ядрах с 2.6.8 по 2.6.18 (2004—2006)
• CUBIC — с версии 2.6.19 (с ноября 2006)^[44]
• PRR используется для восстановления после потерь с версии 3.2 (2012)
• BBRv1 доступен в Linux начиная с версии 4.9 (2016)^[45]