Алгоритм перегрузки tcp android

TCP Congestion Control или Почему скорость прыгает

Бывало ли у вас такое, что ставите файл на закачку, и скорость медленно, но верно возрастает, затем, в какой-то момент, резко снижается, затем опять возрастает? Закачка файла в один поток не обеспечивает полную скорость канала? Запускаете торрент-клиент, и пинг в игре сильно прыгает? Используете 3G-модем (или другую линию с относительно большой потерей пакетов) и не можете это терпеть?
Наверняка вы винили во всем ваш роутер, либо обвиняли своего провайдера в кривой настройке шейпера? Это влияет, но виноваты не они.
Итак, встречайте:

TCP Congestion Control, или TCP Congestion Avoidance Algorithm.

Что это такое?

Вкратце ­— алгоритмы, которые пытается сделать все возможное, чтобы обеспечить наиболее быструю скорость передачи данных между двумя узлами, передающими данные через TCP. Они управляют размером TCP-окна и могут ориентироваться на RTT (Round Trip Time — время от отправки запроса до получения ответа), потерю пакетов, время ожидания отправки пакета из очереди и т.д. Каждый алгоритм по разному ведет себя в той или иной ситуации и нет какого-то универсального.

Долгое время, в ходу были алгоритмы Reno, разработанный в 1990 году, и BIC. Первый применялся во всех ОС Windows до XP, а второй — в Linux до 2.6.18. Затем, в Windows Vista появился новый алгоритм Compound TCP, а в Linux сменили BIC на Cubic.

Какие есть алгоритмы?

Их достаточно много. В ядре Linux 3.7 имеются:

• BIC TCP
• CUBIC TCP
• Highspeed TCP
• H-TCP
• TCP Hybla
• TCP-Illinois
• TCP Low Priority
• TCP Vegas
• TCP NewReno
• TCP Veno
• TCP Westwood+
• YeAH-TCP

BIC, CUBIC, Highspeed, H-TCP, NewReno, Illinois — эти алгоритмы созданы для так называемых long fat networks ­— длинных (а значит, с высоким RTT) и быстрых сетей. TCP Hybla здорово ведет себя на спутниковых линках, а Veno создан для беспроводных сетей с высокой потерей пакетов. TCP Low Priority вообще сложно назвать congestion алгоритмом, т.к. он мало что делает, а просто пытается отправить пакет без очереди, TCP Vegas иногда применяют на серверах с большим количеством подключений, т.к. он обеспечивает почти постоянную скорость, хоть и далеко не идеальную. Westwood+ — комбинированный алгоритм, YeAH-TCP самый младший из них, но самый интересный, т.к. ведет себя более-менее во всех случаях.
Более подробно о самих алгоритмах можно прочитать в постеcasperrr

Тест 3G

К сожалению, CUBIC, который используется по умолчанию во всех дистрибутивах, совершенно не подходит, например, для 3G-соединений. Ниже представлен график сравнения 4 алгоритмов congestion avoidance для HSDPA сетей за конец 2012 года из TCP Congestion Control over HSDPA: an Experimental Evaluation:

Как видите, CUBIC в отстающих. Он значительно повысил RTT на полной утилизации 3G канала, в то время как Westwood+ и NewReno более-менее справляются с этой проблемой.
Давайте взглянем на количество ретрансмиссий:

Как видно из графика, у CUBIC относительно большое количество ретрансмиссий

В то же время, он лидирует в скорости передачи данных за единицу времени.

Что это значит? Это значит, что с использованием Westwood+ или NewReno вы сможете комфортней серфить интернет, пока у вас скачивается большой файл.

Тест WiMAX и WiFi каналов

Тест взят из Comparative Performance Evaluation of TCP Variants in WiMAX (and WLANs) Network Configurations — еще одного интересного сравнения алгоритмов для беспроводных сетей.

В тесте №1 используется соединение компьютер-wimax.роутер-wimax.клиент с пропускной способностью между компьютером и роутером в 100 мбит/с и RTT в 45 мс и соотношением DL:UL 1:1 между wimax роутером и клиентом.
Зависимость эффективной передачи данных от потери пакетов:

Чуть изменим тест. В тесте №2 используется схема компьютер-роутер1-роутер2-wimax.роутер-wimax.клиент, где RTT 10 мс. между компьютером и первым роутером, далее используется 10 мбит/с канал с 25 мс. RTT, между вторым и wimax роутером канал опять 100 мбит/с c RTT в 10 мс.

Как видно из графиков, лидерство держит Westwood.
Картина для WiFi схожа с WiMAX:

Тест высокоскоростного канала

Этот тест взят из технического отчета алгоритма YeAH-TCP за 2006 год. Теоретически, YeAH является самым продвинутым алгоритмом и нацелен работать как можно лучше на высокоскоростных линиях, на линиях с высокой задержкой или высокими потерями пакетов.
Тесты делались с импользованием канала пропускной способностью в 500 mbit/s

В эффективной передаче данных в зависимости от RTT лидирует YeAH

Зависимость эффективной передачи данных и потери пакетов, опять YeAH занимает первое место

К сожалению, с YeAH на ядре 3.7 какие-то проблемы, через некоторое время он весит систему software interrupt’ами. Такого поведения не наблюдается на 3.6.

Как поменять?

Сменить Congestion Algorithm достаточно просто, всего одна строка:
sysctl -w net.ipv4.tcp_congestion_control=westwood
Где вместо westwood можно вставить названия из /lib/modules/. /kernel/net/ipv4/tcp_. ko без префикса tcp_.

Вместо заключения

На каналах вроде домашнего вайфая, рекомендую использовать Westwood или H-TCP. Для проводных каналов хорошим выбором может быть YeAH (если у вас не наблюдается с ним проблем), H-TCP или Illinois.

Источник

Русские Блоги

Контроль перегрузки TCP (Tahoe Reno Newreno Sack)

Контроль перегрузки TCP (Tahoe Reno Newreno Sack)

вступление

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

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

В целях предотвращения явления заторов сети TCP предлагает серию механизмов контроля заложений. Контроль перегрузки TCP, предложенный В. Якобсон в 1988 году в 1988 годуМедленное начало (медленное начало)с участиемПредотвращение перегрузкиКомпозиция, позже версия TCP Reno добавленаБыстрое повторное передачу、Быстрое выздоровлениеАлгоритм, потом позжеTCP NewRenoБыстрый алгоритм восстановления был улучшен, и он появился в последние годы.Выборочный ответ (селективное подтверждение, мешок)Алгоритм, есть и другие аспекты великих и небольших улучшений, чтобы стать горячей точкой для сетевых исследований.

Основной принцип контроля заторов TCP зависит от одногоОкно застой CWND (окно перегрузки)Для контроля, TCP имеет уведомление о сверткеПолучить окно (приема окна, RWND)Для управления движением. Размер значения окна представляет собой максимальный сегмент отчета о данных, который можно отправить, но не получил ACK. Чем больше окно, тем быстрее отправленные данные, но это может сделать сетевую заторы, если значение окна равно 1. Так Упрощение подобного стопом протокола, каждый из которых отправляет данные и т. Д. И т. Д., Подтверждение другой стороны может отправлять второй пакет, ясно, что эффективность передачи данных низкая. Алгоритм управления перегрузкой для TCP состоит в том, чтобы весить между собой, выберите лучшее значение CWND, что приводит к максимизации пропускной способности сети без заложенности.

Поскольку должно быть рассмотрено содержание контроля заложений и контроля трафика,TCP истинное отправку окна = мин (RWND, CWND)Принимающее окно слишком мало, чтобы стать потолком CWND. Однако RWND определяется Peer, сетевая среда не влияет на него, поэтому мы, как правило, независимо от стоимости RWND при рассмотрении застой, мы временно обсудим, как определить размер значения CWND. Что касается единицы CWND, с точки зрения байтов, мы предполагаем, что TCP отправляет данные в соответствии с размером MSS, поэтому вы можете думать, что CWND можно понять в соответствии с количеством пакетов. Так что иногда мы говорим, что CWND увеличивается 1 эквивалентно добавить 1 размер MSS.

Медленное начало и заторы

Отправитель поддерживает имя под названиемЗаголовок окна CWNDПеременная состояния. Размер окна застой зависит от степени заторов сети и динамически изменяется. Отправитель делает свое собственное окно отправки, равное окну застой, а также учитывает возможность приема, окно отправки может быть меньше, чем окно застой.

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

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

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

Чтобы предотвратить слишком большое рост CWND, чтобы вызвать застой сетевой заторы, также необходимо настроить медленно начальную порогу Ssthresh. Использование Ssthresh заключается в следующем:

• Когда CWND Ssthresh, алгоритм избегания заторов изменен.
• Когда CWND = Ssthresh, медленное начало с алгоритмом предотвращения заторов.

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

Медленный процесс запуска:Когда создается новое соединение, CWND инициализируется до 1 размера максимальной сегменты отчета (MSS), и отправитель начинает отправлять данные по размеру, когда сегмент сообщения подтверждается, CWND добавляет 1 размер MSS. Таким образом значение CWND с сетьюВремя поездки вокруг, RTT)Экспоненциально расти,На самом деле скорость медленного запуска не медленная.Это чуть ниже в начальной точке. Мы можем просто рассчитать:

• Start -> CWND = 1
• После 1 RTT -> CWND = 2 * 1 = 2
• После 2 RTTS -> CWND = 2 * 2 = 4
• Выдвижение класса, если полоса пропускания W, то время RTT * Log2W может объяснить полную пропускную способность.

Предотвращение перегрузкиАлгоритм позволяет окно перегрузки медленно расти, то есть плюс окно застой отправителя CWND Plus 1, а не двойной. Такое окно перегрузки медленно растет на линейных законах.

Будь то на этапе медленного запуска или в фазе избегания заторов, до тех пор, пока суждения отправителя сеть появляется в заторах (что не получено, она может быть потеряна, но потому что подтверждение может быть потерей группы, но потому что это не Возможно, это процедура застой), установите медленный порог начала до половины размера окна отправки при заторых. Затем установите окно застой до 1, выполните алгоритм медленного запуска. Как показано ниже:

Напомните это здесь, чтобы обсудить количество единиц, которые делают размер окна застой к количеству отчетов о данных, он должен быть байтом.

Зачем использовать заторы, чтобы избежать: От медленного запуска CWND может быстро расти, таким образом использование ресурсов пропускной способности сети, но CWND не может работать бесконечно, должен быть предел.

Основные шаги предотвращения перегрузки: TCP использует имяМедленный начальный порог (Ssthresh)Переменные, когда медленно активированный CWND превышает это значение, процесс медленного запуска заканчивается и входит в фазу избегания перегрузки. Для большинства реализаций TCP значение Ssthresh составляет 65536 (одинаково байт). Основное мышление скопления состоит в том, чтобы увеличить, то есть значение CWND больше не является уровнем индекса, а добавление увеличивается. В это время, когда все сегменты отчета в окне подтверждены, размер CWND PLUS 1, значение CWND увеличит увеличение линейности в виде RTT, поэтому он может избежать роста застой сетевой загрузки, медленное увеличение до сети , Лучшее значение.

Два механизма, обсуждаемые выше, не обнаружили поведение застой, то как CWND был скорректирован, когда он найден?

Быстрая передача и быстрое восстановление

В целом, принцип изменения в окне контроля заторов TCPПринцип призма, то есть повышение добавления, умножениеОтказ Видно, что принцип TCP может лучше гарантировать справедливость между потоками, потому что, как только пакет потерян, то немедленноВложительноТем не менее, у вас может быть достаточно места для хранения других вновь построенных, тем самым обеспечивая всю справедливость.

Во-первых, посмотрите, как TCP определяет, что сеть ввела состояние застой.TCP считает, что основой для застой сетевых заложений является то, что она повторно передает раздел сообщения.Отказ Вышеупомянутое выше, что TCP имеет таймер для каждого раздела отчета, называемыйТаймер восстановления (RTO)Когда TIMEOUT RTO TIMEOUT TIMEOUT, TCP будет повторно передавать сегмент отчета. Когда возникает время ожидания, возможна возможность заложенности, очень большая, а сегмент отчета может быть где-то в сети. Утерянные, а последующие газеты не имеют новостей.В случае этого RTO Ret Timeout Reepmission ответ TCP более «сильна» (TCP считает, что произошло тяжелое заложенность)：

1. Уменьшить Ssthresh до половины значения CWND
2. Сброс CWND до 1
3. Введите процесс медленного запуска.

TCP определяет другую основу для застой сетевых заложений в быстром повторном трансмиссии: 30 идентичных ACK входит в состояние быстрого повторного передачиОтказ TCP сразу же отправит ACK при получении диаграммы, и TCP использует три идентичных ACK для определения потери пакета. В это время быстро повторная передачаВ случае, когда происходит быстрое ретрансляцию, ответ TCP «умеренный» (TCP думает также может получить ACK, должен быть частичным заложением)：

1. Установите Ssthresh до половины CWND
2. Установите значение CWND в Ssthresh (некоторые из Ssthresh + 3)
3. Повторно введите фазу избегания заторов.

Алгоритм быстрого Backbread появился в версии Tahoe Of 4.bsd, быстро восстановился в первый раз в версии 4.bsd Reno, также называемую версию Reno Algorith Control Control Controlse.。

Видно, что быстрый двоичный алгоритм Reno представляет собой повторную передачу пакета, однако, на практике, время ожидания повторной передачи может привести к ряду повторной передачи пакетов, поэтому, когда несколько пакетов теряются из одного окна данных, когда быстрая повторная передача и быстрое восстановление Алгоритм срабатывает, проблема генерируется. Итак, появился NewReno, и он немного изменен на основе быстрого восстановления Reno быстро, что может восстановить несколько пакетов нескольких пакетов в окне. В частности, это:Reno выходит из статуса быстрого восстановления при получении новых данных, и Newreno необходимо получить подтверждение всех пакетов в этом окне, чтобы выйти быстрое восстановление, чтобы пропускную способность улучшено.

Rapid Retransmission требует, чтобы получатель немедленно выдает подтверждение повторения после получения последовательного сегмента отчета (для отправителя знает, что нет раздела новостей, не достигает другой стороны) вместо подтверждения ремня при отправке данных. Алгоритм быстрой передачи предусматривает, что отправитель должен немедленно повторно передавать количество сегментов отчетов, которые не были немедленно, без необходимости продолжать ждать время истечения времени таймера повторной передачи (эффективность ожидания тайм-аута является самым низким. Из). Как показано ниже:

Также есть быстрый переводВосстановление (быстрое восстановление быстрого восстановления)Алгоритм, есть два основных момента:

1. Когда отправитель получает три повторяющихся подтверждения, выполняется алгоритм «уменьшение умножения», а порог Ssthresh уменьшен. Тем не менее, алгоритм медленного запуска не выполняется.
2. Учитывая, что если есть застой, будет несколько подтверждений повторения, поэтому отправитель теперь считает, что сеть может не задержать. Так что не выполняйте алгоритм медленного запуска в это время, но установите CWND в SSthresh, затем выполните алгоритм избегания заторов. Как показано ниже:

Последнее «быстрое восстановление» алгоритм добавляется после того, как алгоритм «Rapid Retransmission», описанного выше, при получении 3 повторения ACK TCP, наконец, ввел фазу избегания перегрузки, но быстрое фазу восстановления. Быстрое повторная передача и алгоритмы быстрого восстановления обычно используются одновременно. Быстрое восстановление — принцип «Пакет данных», то есть количество пакетов в сети в сети является постоянным, только когда «старый» пакет покидает сеть, может отправить «новые» данные в сеть. Пакет, Если отправитель получает дубликат ACK, то в соответствии с механизмом TCP ACK есть пакет для выхода из сети, поэтому CWND Plus 1. Если вы можете строго соблюдать этот принцип, вы редко возникаете в сети, и целью того факта, что контроль заложений также пересмотрен в нарушение принципов. В частности, основные шаги быстрого восстановления:

1. Когда вы получаете 3 повторяющихся ACK, установите SSthresh в половину, установите CWND в SSthresh + 3, затем Retransmit потерянные сегменты отчета и 3 причина из-за 30 повторяющихся ACK, указывающих на то, что есть 3 «старые» пакеты.
2. Когда вы получаете повторяющийся ACK, окно затора увеличивается 1.
3. При получении ACK нового пакета установите CWND в значение Ssthresh на первом шаге. Причина в том, что ACK подтверждает новые данные, указывающие на то, что данные повторяются, были получены. Процесс восстановления закончился, и его можно вернуть в восстановление, и он снова ввел избегание перегрузки.

SACKТо есть изменение механизма подтверждения для TCP, начальный TCP подтверждает, что в настоящее время полученные в настоящее время данные в настоящее время получены, и SACK рассказывает другую сторону, тем самым уменьшая слепоту повторной передачи отправителя данных. Например, данные о серийном номере 1, 2, 3, 5 и 7 получают. Обычный ACK будет подтвердить только серийный номер 4, а мешок будет сообщить Peer в варианте мешка в варианте мешка. Тем самым улучшится Производительность, при использовании мешка, алгоритм NewReno не может быть использован, потому что информация, перенесенная самим мешком, может заставить отправителя иметь достаточную информацию, чтобы узнать, какие пакеты должны быть повторно переданы без необходимости повторной передачи.

Раннее обнаружение красного

Вышеуказанные алгоритмы предотвращения заторов не связаны с сетевым слоем, и тот факт, что стратегия сети сетевого уровня является наиболее затронутой. Алгоритм предотвращения заторов — это стратегия отбрасывания маршрутизатора. В простом случае маршрутизатор обычно обрабатывает пакеты из первой первой форвардной политики. Когда маршрутизатор кэшируется, он упадет в группу, которая называетсяСтратегия сброса хвостаОтказ Это приведет к потере пакетов, и отправитель считает, что сеть генерирует заторы. Более серьезным является то, что в сети есть много TCP-соединений, и отчеты в этих соединениях обычно являются мультиплексированными путями.Если маршрутизатор отбрасывается, может быть много TCP-соединений, результатом заключается в том, что многие TCP-соединения входят в медленное начало одновременно, которое называется глобальной синхронизацией.Глобальная синхронизация сделает сетевое движение внезапно упало, и после того, как сеть возвращается к нормальному, его трафик внезапно увеличивается.

Чтобы избежать глобальной синхронизации в сети, маршрутизатор принятСлучайное раннее обнаружение (красное, случайное раннее обнаружение)Отказ Точки алгоритма следующие:

• Сделайте очередь маршрутизатора до двух параметров, то есть, то есть минимальный порог командной длины очереди min и максимальный порог макс. Всякий раз, когда приходит пакет, красный вычисляет среднюю длину очереди. Затем группа лечила Группа:
  1. Средняя длина очереди меньше минимального порога — поставьте вновь прибывший пакет в очередь очереди.
  2. Средняя длина очереди между минимальным порогом и максимальным порогом — затем выключите пакет в соответствии с определенной вероятностью.
  3. Средняя длина очереди превышает максимальный порог — выбросьте вновь прибывающую группу.

Красный случайно откажитесь от пакета в вероятности P, позволяя контролировать заторы только на отдельных соединениях TCP, что позволяет избежать глобального контроля заторов.
Ключ состоит в том, чтобы выбрать три параметра Минимальный порог, максимальный порог, вероятность сброса вероятности и средняя длина очереди. Средняя длина очереди использует средневзвешенный средний метод для расчета длины средней очереди, которыйВремя отключения кругов (RTT)Стратегия расчета одинакова.

Источник