Лекция 4. Управление перегрузкой TCP (Лекции)

Современные алгоритмыуправления перегрузкой TCPЧемерицкий Евгений Викторовичк.ф.-м.н.Перегрузки в сети100 Mbps10 Mbps10 MbpsОбъём данных, поступающих накоммутатор, превышает объёмданных, которые он может передатьКоммутаторы буферизируют проходящий через них трафик:• При кратковременной перегрузке увеличивается задержка• При достаточно долгой перегрузке пакеты сбрасываютсяУправление перегрузкой TCP: задачи• Соединения должны адаптироваться ккачеству предоставленной линии связи истремиться использовать предоставленныересурсы максимально эффективно• Соединения должны автоматическираспределять пропускную способностьразделяемой ими линии связисправедливым образомБазовое устройство TCPАлгоритм скользящего окна (sliding window)• Позволяет восстанавливать порядок пакетов приотправке множества пакетов с использованиембуфера фиксированного размераCumulative ACK• Получатель сообщает о последнем успешнополученном пакете – пакеты с меньшиминомерами считаются полученнымиавтоматически• NACK (negative ACK) – получатель явноперечисляет пакеты, которые он не получил• SACK (selective ACK) – получатель сообщаетдиапазоны успешно полученных пакетовУправление TCP трафикомдругие виды “окон”• Rate control (traffic policing)• Receiver-side flow control– Цель: избежать перегрузки получателя– Параметр: RWND – окно получателя– Получатель отправляет свой RWND отправителю• Network congestion control– Цель – избежать перегрузки сети– Параметр: CWND – окно перегрузки– Отправитель вычисляет свой CWND с помощьюалгоритма управления перегрузкойЛитератураЗачем нужны протоколы управленияперегрузкой и какие принципы лежат воснове современных сетей?TCP design principles:• Van Jacobson "Congestion avoidance andcontrol“ // Proceedings of SIGCOMM ’88,Stanford, CA.

Aug. 1988.Принцип инвариантностиколичества отправляемых пакетовpacket conserving principleКаждое соединение должно стремиться кустойчивому состоянию, в котором отправкакаждого следующего пакета соединенияпроисходит сразу после того, как завершиласьпередача одного из его предыдущих пакетов:• Каналы не должны простаивать• Передача пакетов должна быть равномерной,а её итоговая скорость должна соответствоватьпропускной способности каналаКак найти состояние равновесия?self-clocking principleСкорость отправки пакетов должна соответствовать пропускнойспособности канала в узком местеSlow startподгонка часов• На отправителе появляется новый параметр– congestion window (CWND)• Значение CWND устанавливается в 1 вначале соединения и при каждой потере• При получении каждого подтверждения одоставке CWND увеличивается на 1• Отправитель передаёт max(CWND, RWND)где RWND – окно получателяМедленный старт совсем не медленный – количествоотправленных пакетов растёт в геометрической прогрессииКак остаться в состоянии равновесия?Retransmit timer• Если пакет теряется, то отправитель долженотправить в сеть новый пакет в нужныймомент времени• Нужен надёжный расчёт для RTT и RTO = + 1 − = Выбор таймера при повторенииошибокПерегруженная система обретаетстабильность, если нагрузка падает поэкспоненциальному закону:• Exponential Backoff• RTO, 2RTO, 4RTO, 8RTO, 16RTO, 32RTOКак остаться в состоянии равновесия?Congestion avoidance• Вероятность потери из-за ошибки нафизическом уровне обычно мала (~10−10 )• Потери возникают из-за перегрузок в сети• Стратегия:– Сеть подаёт сигнал о потере пакета– Отправитель снижает нагрузкуIf packet loss is (almost) always due to congestion and if atimeout is (almost) always due to a lost packet, we have agood candidate for the ‘network is congested’ signal.- Congestion Avoidance and Control+ Не нужно изменять стек протоколов на устройствахКак остаться в состоянии равновесия?Additive Increase Multiple Decrease (AIMD)Политика изменения окна при перегрузке:• Пусть – загрузка очередей на интервале • В состоянии равновесия = • В состоянии перегрузки = + −1• Поскольку загрузка очередей растётэкспоненциально, то размер окнаперегрузки тоже должен меняться поэкспоннете = −1 ( < 1)Как остаться в состоянии равновесия?Additive Increase Multiple Decrease (AIMD)Изменение окна при нормальной работе:• Скорость изменения окна должна бытьменьше, чем при перегрузке, иначе системабудет нестабильной• Можно построить такую смесь трафика, чтоэкспоненциальное увелсичение (умножение)размера окна приведёт к тому, что пакетыбудут отправляться в сеть быстрее, чем онасможет их обрабатывать = + ( ≪ )Алгоритмы управления перегрузкойпротокола TCPVan Jacobson Congestion avoidance and controlProceedings of SIGCOMM ’88 -- Stanford, CAУправления перегрузкой TCP:принципы работы• Взаимодействующие с сетью– Сетевые устройства сигнализируют овозникновении перегрузки (TCP/ECN)• Без взаимодействия с коммутаторами– Перегрузка определяется косвенно (по потерепакета, увеличению задержки и т.д.)• Реактивные (как правило, loss based)– Детектируют возниконовение перегрузок по факту• Проактивные (как правило, delay based)– Ограничивают пропускную способностьсоединения, предчувствуя скорую перегрузкуУправление перегрузкой:скорость реакции• При отсутствии дополнительных сервисныхпакетов отправитель получает информациюиз поступающих к нему ACK-сообщений• ACK-сообщение, соответствующееотправленному пакету, поступает спустяодин Round Trip Time (RTT)• Хосты способны адаптироваться ксостоянию сети не быстрее, чем RTTAdditive IncreaseMultiple Decrease (AIMD)В устойчивом состоянии график зависимостиокна перегрузки (CWND) от времени (t) дляалгоритма TCP Reno имеет вид пилыCWNDWW/2tЗависимость размера congestionwindow от уровня потерь p• Между последовательными потерями:– проходит W/2 раундов алгоритма перегрузки,который увеличивает окно от W/2 до W– передаётся 1/p пакетов• (/2 + )/2 ∗ /2 = 1/• = (8/3)Проблемы TCP Reno:1) cети с большим BDP• BDP = Bandwidth Delay Product• TCP Reno растёт слишком медленно– При использовании канала 10 Gb x 100 ms дляувеличения CWND от W/2 до W потребуется50000 RTT (более часа)– При достаточно частых потерях пакетовалгоритм никогда не сможет добраться домаксимальной пропускной способности каналаПроблемы TCP Reno:2) RTT fairness• Потоки с меньшим RTT адаптируются кпропускной способности канала быстрее,чем потоки с большим RTT• Более “быстрые” соединения получаютпреимущество и используют большееколичество сетевых ресурсовПроблемы TCP Reno:3) TCP friendliness• В теории delay-based алгоритмы управленияперегрузкой, как правило, могут работатьболее эффективно– Алгоритмы могут избегать потерь пакетов– Значение задержки содержит больше информациио сетевом окружении• На практике delay-based соединения имеютплохую производительность, потому чтопередаются вместе с loss-based соединениями– Буферы коммутаторов перегружаются внезависимости от стратегий delay-based соединенийTCP Cubic• Идея – предположить, что потери случаютсячерез равные промежутки времени• Размер окна наращивается таким образом,чтобы он достигал своего максимума вмомент следующей потери– Размер окна не зависит от RTT!• Текущий размер окна определяетсякубической функцией– быстрый рост после перегрузкиTCP Cubic: CWND•••••Изначально CWND растёт быстрее, чем у TCP RenoПри увеличении вероятности потери рост замедляетсяCWND равен предполагаемому оптимуму максимально долгоЕсли потери не происходит – потолок соединения неверенАлгоритм начинает быстрый рост, чтобы найти правильнуюпропускную спсобсность соединенияTCP Compound• Идея – эффективная комбинация delay-based иloss-based алгоритмов– Скорость delay-based соединений– Равная борьба с loss-based соединениями• Окно перегрузки состоит из loss-based b delaybased компонент:– Loss-based изменяется по аналогии с TCP Reno– Delay-based изменяется экспоненциально взависимости от текущей задержки: может какрасти, так и уменьшатьсяTCP CompoundData Center TCP: специализированныйпротокол управления перегрузкой для ЦОДов• Горизонтальное масштабированиесервисов: map-reduce– Поступающие на сервер запросы отправляютсяна вспомогательные сервера– Каждый из серверов выполняет обработкузапроса в своей области и возвращаетрезультат на центральный сервер– Центральный сервер комбинирует результаты иформирует окончательный ответ на запросData Center TCP: специализированныйпротокол управления перегрузкой для ЦОДов• Множество “коротких” соединенийконкурирует с долго живующимисоединения• Частый сброс пакетов коротких соединенийувеличивает латентность системы– В буферах коммутаторов не помещаетсямножесто одновременных ответов– Буферы коммутаторов заполнены пакетамидолго живущих соединенийData Center TCP: специализированныйпротокол управления перегрузкой для ЦОДов• Идея – маркировать пакеты соединений,передающиеся через буферы с высокимуровнем загруженности• При достаточно частом поступлениимаркированных пакетов отправительуменьшает размер CWND• При редком поступлении маркированныхпакетов размер CWND увеличиваетсяСосуществование разных TCP в ЦОД** AC/DC TCP: Virtual Congestion Control Enforcement for Datacenter NetworksKeqiang He, Eric Rozner, Kanak Agarwal, Yu (Jason) Gu, Wes Felter, John Carter, Aditya AkellaРезюме• TCP fairness• TCP friendliness• Разные алгоритмы TCP хороши в разныхобластях применения.