Различные алгоритмы управления перегрузкой TCP

TCP/IP

предисловие

С тех пор как была предложена концепция управления перегрузкой TCP, алгоритм управления перегрузкой TCP претерпел ряд изменений. Вот общее резюме каждого алгоритма управления перегрузкой TCP, основанное на информации в Интернете.

TCP Tahoe/Reno

Первоначальная реализация включает две части: медленный старт и предотвращение перегрузки. Определяет, происходит ли потеря пакетов на основе времени ожидания повторной передачи (RTO) и повторного подтверждения в качестве условий. Разница между ними заключается в следующем: в алгоритме Тахо, если получены три повторных подтверждения, он перейдет к быстрой повторной передаче и немедленно повторно передаст потерянные пакеты данных.В то же время установите порог медленного запуска на половину текущего окна перегрузки, установите окно перегрузки на 1MSS и войдите в состояние Slow-start; а алгоритм Reno входит в быструю повторную передачу, если он получает три повторных подтверждения, но не входит в состояние медленного запуска, а прямо вдвое сокращает окно перегрузки и входит в стадию управления перегрузкой , что называется "быстрое восстановление".

Алгоритмы Tahoe и Reno принимают одинаковые меры при возникновении RTO: они оба уменьшают окно перегрузки до 1 MSS, а затем переходят в стадию медленного старта.

TCP Vegas

Алгоритм TCP Vegas был предложен Лоуренсом Бракмо и Ларри Л. Петерсоном в 1994 году. Разница между ним и другими алгоритмами управления перегрузкой заключается в том, что алгоритм Vegas не стремится терять пакеты, чтобы судить о том, произошла ли перегрузка, а судит по пакету. задерживать. Vegas использует RTT (время приема-передачи), чтобы принять решение об увеличении или уменьшении окна перегрузки. Это может предотвратить перегрузку, когда она вот-вот должна произойти, вместо того, чтобы ждать, пока не произойдет перегрузка, а затем снижать скорость передачи, что может снизить вероятность повторной передачи. и тайм-аут. Когда алгоритм Vegas сосуществует с другими алгоритмами (такими как Reno), возникают проблемы со справедливостью из-за снижения скорости передачи раньше, чем другие алгоритмы.

TCP New Reno

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

При быстром восстановлении Reno после 3 повторных подтверждений отправитель TCP повторно отправит пакет данных и установит таймер для ожидания подтверждения повторно переданного пакета данных. Когда повторно переданный пакет данных подтвержден, он немедленно выходит из фазы быстрого восстановления и переходит в фазу управления перегрузкой. Однако, если в одной перегрузке произойдет несколько потерь пакетов, Reno ошибочно подумает, что произошло несколько перегрузок, и многократно уменьшит окно перегрузки, что приведет к снижению скорости отправки.

При быстром восстановлении New Reno после 3 повторных подтверждений будет записан максимальный порядковый номер неподтвержденного пакета данных при повторном подтверждении, а затем повторный пакет подтверждения будет отправлен повторно. Если потеряно несколько пакетов данных, продолжайте повторно отправлять потерянные пакеты данных до тех пор, пока пакет данных с наибольшим порядковым номером не будет подтвержден перед запуском фазы быстрого восстановления.

Новый Reno работает так же эффективно, как выборочное подтверждение (SACK) при низкой частоте ошибок, и все же лучше, чем Reno, при высокой частоте ошибок.

TCP BIC/CUBIC

TCP BIC (управление бинарным увеличением перегрузки) предназначен для оптимизации контроля перегрузки в высокоскоростных сетях с высокой задержкой (т. е. в «длинных толстых сетях» (LFN)). Его алгоритм окна перегрузки использует алгоритм двоичного поиска, чтобы попытаться найти Окно перегрузки, которое может сохраняться длительное время Значение максимального значения. Ядро Linux использует этот алгоритм в качестве алгоритма перегрузки TCP по умолчанию с 2.6.8 по 2.6.18.

Алгоритм BIC использует бинарный поиск для определения максимального размера окна: если размер окна равен W1, когда происходит потеря пакета, то максимальное окно Wmax должно быть меньше, чем W1; тогда окно уменьшается до W2 (умножается на коэффициент, т.е. , сокращение умножения ), то можно ожидать, что W1>Wmax>W2; затем установить размер окна равным (W1+W2)2 (то есть бинарный поиск), то есть установить размер окна на середину две границы каждый раз при получении ACK.

Если размер окна приблизился к W1 бесконечно, это означает, что состояние сети снова улучшилось (увеличилась доступная пропускная способность), тогда BIC попытается найти большее Wmax. При поиске вверх БИК будет использовать путь, приближающийся к текущему Wmax, для поиска в зеркальном отображении, то есть как приближаться к текущему Wmax быстро, так и медленно спереди, а затем медленно, а затем быстро расти.

И CUBIC является более умеренной и систематической версией ветвления, чем BIC, которая использует кубическую функцию вместо алгоритма деления пополам в качестве алгоритма окна перегрузки (поскольку на самом деле кривая поиска BIC выглядит как кубическая функция, поэтому просто напишите кубическую функцию для имитации кривой) , и использовать точку перегиба функции в качестве значения настройки окна перегрузки. Ядро Linux использует этот алгоритм в качестве алгоритма перегрузки TCP по умолчанию, начиная с версии 2.6.19.

TCP Westwood/Westwood+

TCP Westwood улучшен от New Reno.В отличие от других алгоритмов управления перегрузкой в ​​прошлом, которые использовали потери для измерения, он определяет «правильную скорость отправки» путем измерения пакетов подтверждения и соответствующим образом регулирует окно перегрузки и порог медленного запуска. Вествуд улучшила алгоритм фазы медленного старта как «Agile Probing» и разработала метод непрерывного обнаружения окна перегрузки для управления входом «Agile Probing», чтобы соединение использовало максимально возможную полосу пропускания. Westwood+ использует более длительный интервал оценки пропускной способности и оптимизированные фильтры, чтобы скорректировать переоценку пропускной способности Westwood для сценариев сжатия ACK. Благодаря вышеупомянутым усовершенствованиям серия алгоритмов TCP Westwood достигает баланса в управлении перегрузкой проводных и беспроводных сетей, особенно в сетях беспроводной связи.

Compound TCP

Составной TCP — это алгоритм управления перегрузкой TCP, реализованный самой Microsoft.Поддерживая два окна перегрузки одновременно, он может повысить производительность в сети Changfei без потери справедливости. CTCP поддерживает два окна перегрузки: обычное окно AIMD (на английском языке: аддитивное увеличение / мультипликативное уменьшение) и окно на основе задержки, а фактический размер используемого скользящего окна представляет собой сумму этих двух окон. Окно AIMD увеличивается так же, как Reno; если задержка небольшая, окно, основанное на задержке, будет быстро увеличиваться, чтобы улучшить использование сети. После возникновения очереди окно задержки будет постепенно уменьшаться, чтобы компенсировать увеличение окна AIMD. Цель этого состоит в том, чтобы поддерживать сумму двух приблизительно постоянной, позволяя алгоритму оценить путь произведения пропускной способности-задержки.

TCP PRR

TCP PRR (TCP Proportional Rate Reduction) предназначен для повышения точности отправляемых данных во время восстановления. Алгоритм гарантирует, что восстановленный размер окна перегрузки будет как можно ближе к порогу медленного запуска.

TCP BBR

TCP BBR (Bttleneck Bandwidth and Round-trip Propagation Time) — это алгоритм перегрузки, разработанный Google и выпущенный в 2016 году. В прошлом большинство алгоритмов перегрузки основывались на потере пакетов в качестве сигнала для снижения скорости передачи, в то время как BBR основывался на активном обнаружении на основе моделей. Алгоритм строит явную модель сети, используя текущую максимальную пропускную способность и время приема-передачи самых последних исходящих сетевых пакетов данных. Каждое кумулятивное или выборочное подтверждение передачи пакета используется для генерации частоты дискретизации, которая регистрирует объем данных, переданных в течение времени между процессом передачи пакета и возвратом подтверждения. Алгоритм утверждает, что потеря пакетов не должна считаться основным определяющим фактором для определения перегрузки, поскольку контроллеры сетевых интерфейсов постепенно переходят на гигабитные скорости, поэтому алгоритмы управления перегрузкой на основе моделей могут иметь более высокую пропускную способность и меньшую задержку, BBR можно использовать для замены других популярных перегрузок. алгоритмы, такие как CUBIC.

Суммировать

Можно видеть, что управление перегрузкой TCP в основном: 1. Обнаружение перегрузки 2. Реагирование на перегрузку.

Исходный алгоритм основан на потере пакетов, чтобы определить, возникает ли перегрузка, и как только возникает перегрузка, скорость передачи снижается, чтобы избежать перегрузки. Позже появится алгоритм для оценки перегрузки на основе RTT, но этот алгоритм заранее уменьшит скорость отправки (откажется от пропускной способности), потому что он слишком «джентльменский», который может быть дополнительно сжат другими сосуществующими алгоритмами, что приведет к проблемам справедливости. . CTCP от Microsoft позволяет избежать этой проблемы справедливости, поддерживая два окна: окно AIMD, чтобы гарантировать, что оно не будет сжато другими, и окно, основанное на задержке, чтобы гарантировать, что пропускная способность может быть быстро увеличена для улучшения использования пропускной способности. BBR напрямую использует активное обнаружение, чтобы определить, возникает ли перегрузка.

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