[Перевод] Система BBR: регулирование заторов непосредственно по заторам23.02.2017 15:18

Измерение пропускной способности узких мест по времени двойного прохода пакета


По всем параметрам, сегодняшний интернет не может перемещать данные так быстро, как должен. Большинство пользователей сотовой связи в мире испытывают задержки от нескольких секунд до нескольких минут: публичные точки WiFi в аэропортах и на конференциях ещё хуже. Физикам и климатологам нужно обмениваться петабайтами данных с коллегами по всему миру, но они сталкиваются с тем, что их тщательно продуманная многогигабитная инфраструктура часто выдаёт всего несколько мегабит в секунду на трансконтинентальных линиях. [6]

Эти проблемы возникли из-за выбора архитектуры, который был сделан при создании системы регулирования заторов TCP в 80-е годы — тогда потерю пакетов решили интерпретировать как «затор». [13] Эквивалентность этих понятий была справедливой для того времени, но только из-за ограничений технологии, а не по определению. Когда NIC (контроллеры сетевых интерфейсов) модернизировали с мегабитных до гигабитных скоростей, а микросхемы памяти — с килобайт до гигабайт, до связь между потерей пакетов и заторами стала менее очевидной.

В современном TCP регулирование заторов по потере пакетов — даже в наиболее совершенной технологии такого рода CUBIC [11] — основная причина этих проблем. Если буферы узких мест слишком большие, то система регулирования заторов по потере пакетов держит их полными, вызывая излишнюю сетевую буферизацию. Если буферы слишком маленькие, то система регулирования заторов по потере пакетов неверно интерпретирует потерю пакета как сигнал затора, что ведёт к снижению пропускной способности. Решение этих проблем требует альтернативы регулированию заторов по потере пакетов. Для нахождения этой альтернативы следует разобраться, где и как возникают заторы.

Затор и узкое место
В любой момент времени в (полнодуплексное) соединении TCP есть только одно самое медленное звено или узкое место в каждом направлении. Узкое место важно по следующим причинам:
  • Оно определяет максимальную скорость передачи данных по соединению. Это главное свойство несжатого потока данных (например, представьте шестиполосное шоссе в час пик, если из-за ДТП один небольшой отрезок дороги ограничен всего одной полосой. Трафик перед местом ДТП будет двигаться не быстрее, чем трафик через эту полосу.
  • Это то место, где постоянно образуются очереди. Они уменьшаются только в том случае, если интенсивность исходящего потока из «бутылочного горлышка» превысит интенсивность входящего потока. Для соединений, работающих на максимальной скорости передачи все исходящие потоки к узкому месту всегда имеют более высокую интенсивность исходящего потока, так что очереди перемещаются к «бутылочному горлышку».

Независимо от того, сколько линков в соединении и какие у них скорости по отдельности, с точки зрения TCP сколь угодно сложный маршрут представляется как единое соединение с одинаковым RTT (время двойного прохода пакета, то есть время прохождения в оба конца) и пропускной способностью узкого места. Два физических ограничения, RTprop (round-trip propagation time, время двойного прохода пакета) и BtlBw (bottleneck bandwidth, пропускная способность узкого места), влияют на производительность передачи. (Если бы сетевой путь был материальной трубой, RTprop был бы длиной трубы, а BtlBw — её диаметром).

На иллюстрации 1 показаны разнообразные сочетания RTT и скорости передачи с объёмом данных в полёте, то есть inflight (данные отправлены, но без подтверждения доставки). Синие линии показывают ограничение RTprop, зелёные линии — ограничение BtlBw, а красные линии — буфер узкого места. Операции в серых областях невозможны, поскольку противоречат хотя бы одному ограничению. Переходы между ограничениями привели к образованию трёх районов (app-limited, bandwidth-limited и buffer-limited) с качественно разным поведением.

4651414c01034662067e3e902c75830c.png
Рисунок 1

Когда в полёте недостаточно данных, чтобы заполнить трубу, RTprop определяет поведение; в противном случае доминирует BtlBw. Линии ограничения пересекаются в точке $inflight = BtlBw × RTprop$, она же BDP трубы (bandwidth-delay product, производное пропускной способности и задержки). Поскольку труба полная после этой точки, то излишек $inflight - BDP$ создаёт очередь к узкому месту, что приводит к линейной зависимости RTT от данных inflight, показанной на верхнем графике. Пакеты отбрасываются, когда излишек превышает вместимость буфера. Затор — это просто непрерывное нахождение справа от линии BDP, а регулирование заторов — некая схема для установления ограничения, как далеко справа от линии BDP, в среднем, происходит передача данных.

Регулирование заторов по потерям работает на правой границе района, ограниченного пропускной способностью канала (bandwidth-limited), обеспечивая полную пропускную способность узкого места за счёт больших задержек и частой потери пакетов. В те времена, когда память была дорога, размеры буфера лишь немного превышали BDP, что минимизировало избыточную задержку регулирования заторов по потерям. Последующие снижения цен на память привели к увеличению излишней сетевой буферизации и росту RTT до секунд вместо миллисекунд. [9]

На левом краю района, ограниченного пропускной способностью канала, есть рабочая точка с лучшими условиями, чем справа. В 1979 году Леонард Клейнрок [16] показал, что данная рабочая точка оптимальна, она максимизирует фактическую пропускную способность с минимизацией задержек и потерь, как для отдельных соединений, так и для сети в целом [8]. К сожалению, примерно в то же время Джеффри Яффе доказал, что невозможно создать распределённый алгоритм, который сходится в этой рабочей точке. Этот вывод изменил направление исследований. Вместо поиска распределённого алгоритма, который стремится к оптимальной рабочей точки Клейнрока, исследователи начали изучать альтернативные подходы к регулированию заторов.

Наша группа в компании Google каждый день тратит часы на изучение логов с перехватами заголовков пакетов TCP со всего мира, осмысляя аномалии и патологии поведения. Обычно мы первым делом ищем ключевые характеристики маршрута, RTprop и BtlBw. То, что их можно вывести из сетевых трейсов, позволяет предположить, что вывод Яффе мог быть не таким однозначным, как когда-то казалось. Его вывод полагается на фундаментальную неопределённость измерения (например, будь измеренное увеличение RTT вызвано изменением длины пути, уменьшением пропускной способности узкого места или увеличением задержки в очереди из-за трафика от другого соединения). Хотя невозможно устранить неопределённость каждого конкретного измерения, но поведение соединения во времени даёт более ясную картину, подсказывая возможность применения стратегий измерений, созданных для устранения неопределённости.

Совместив эти измерения с надёжным следящим контуром, применив последние достижения в системах управления [12], можно надеяться на разработку распределённого протокола регулирования заторов, который реагирует на действительный затор, а не на потерю пакетов или кратковременную задержку в очереди. И он будет с высокой вероятностью сходиться в оптимальной рабочей точке Клейнрока. Так начался наш трёхлетний проект по разработке системы управления заторами на основе измерения двух параметров, которые характеризуют маршрут: пропускной способности узкого места и времени двойного прохода пакета, или BBR.

Характеристика узкого места
Соединение работает с максимальной пропускной способностью и минимальной задержкой, когда (баланс скорости) скорость прибытия пакетов к узкому месту равняется BtlBw и (полный канал) общее количество данных в полёте равняется BDP ($= BtlBw × RTprop$).

Первое условие гарантирует, что узкое место используется на 100%. Второе гарантирует, что у нас достаточно данных, чтобы предотвратить простой узкого места, но не переполнить канал. Условие баланса скорости само по себе не гарантирует отсутствия очереди, только её неизменный размер (например, если соединение начинается с отправки 10-пакетного Initial Window в пятипакетный BDP, затем работает в точности на одинаковой скорости узкого места, то пять из десяти начальных пакетов заполнят канал, а излишек сформирует стоячую очередь в узком месте, которая не сможет рассосаться). Точно так же, условие полного канала не гарантирует отсутствия очереди (например, соединение отправляет BDP всплесками по BDP/2 и полностью использует узкое место, но, но средняя очередь составляет BDP/4). Единственный способ минимизировать очередь в узком месте и по всему каналу — это соответствовать обоим условиям одновременно.

Значения BtlBw и RTprop изменяются в течение срока жизни соединения, так что их следует постоянно оценивать. В настоящее время TCP отслеживает RTT (интервал времени между отправкой пакета данных до сообщения о его доставке), потому что это требуется для определения потерь. В любой момент времени $t$,

$RTT_t = RTprop_t + \eta_t$


где $\eta \ge 0$ представляет собой «шум» от очередей вдоль маршрута, стратегию получателя с задержкой подтверждений, скопление подтверждений и т.д. RTprop — это физическая характеристика соединения, и она изменяется только при изменении самого канала. Поскольку изменения канала происходят во временном масштабе ≥ RTprop, то беспристрастной и эффективной оценкой времени $T$ будет

$\widehat{RTprop} = RTprop +min(\eta_t) = min (RTT_t)\;\;\;\;\forall t \in [T - W_R, T]$


то есть запуск $min$ во временном окне $W_R$ (которое обычно составляет от десятков секунд до минут).

В отличие от RTT, ничто в спецификациях TCP не требует реализации для отслеживания пропускной способности узкого места, но хорошую оценку этого можно получить из отслеживания скорости доставки. Когда подтверждение о доставке какого-то пакета возвращается к отправителю, оно показывает RTT пакета и анонсирует доставку данных в полёте, когда пакет отбывает. Средняя скорость доставки между отправкой пакета и получением подтверждения — это отношение доставленных данных к прошедшему времени: $deliveryRate = \Delta delivered/\Delta t$. Эта скорость должна быть меньше или равна пропускной способности узкого места (количество по прибытию точно известно, так что вся неопределённость заключается в $\Delta t$, которая должна быть больше или равна настоящему интервалу прибытия; поэтому отношение должно быть меньше или равно настоящей скорости доставки, которое, в свою очередь, ограничено сверху ёмкостью узкого места). Следовательно, максимальное окно скорости доставки — это эффективная, беспристранстная оценка BtlBw:

$\widehat{BtlBw} = max(deliveryRate_t)\;\;\;\;\forall t \in [T - W_B, T]$


где окно времени $W_B$ обычно составляет от шести до десяти RTT.

TCP должен записать время отправки каждого пакета, чтобы вычислить RTT. BBR дополняет эти записи общим количеством доставленных данных, так что прибытие каждого подтверждения сообщает одновременно и RTT, и результат измерения скорости доставки, которую фильтры преобразуют в оценки RTprop и BtlBw.

Заметьте, что эти значения полностью независимы: RTprop может изменяться (например, при изменении маршрута), но обладает тем же узким местом, или BtlBw может изменяться (например, когда меняется пропускная способность беспроводного канала) без изменения маршрута. (Независимость обеих сдерживающих факторов — там причина, почему они должны быть известны, чтобы связать поведение при отправке с маршрутом доставки). Поскольку RTprop виден только с левой стороны BDP, а BtlBw — только с правой стороны на рисунке 1, то они подчиняются принципу неопределённости: всякий раз, когда одно из двух можно измерить, второе измерить невозможно. Интуитивно это можно понять следующим образом: чтобы определить ёмкость канала, его нужно переполнить, что создаёт очередь, которая не даёт возможность измерить длину канала. Например, приложение с протоколом запросов/ответов может никогда не отправить достаточно данных для заполнения канала и наблюдения BtlBw. Многочасовая передача большого массива данных может всё своё время потратить в районе с ограниченной пропускной способностью и получить только единственный образец RTprop от RTT у первого пакета. Присущий принцип неопределённости означает, что вдобавок к оценкам для восстановления двух параметров маршрута, должны быть такие состояния, которые отслеживают одновременно и что можно узнать в текущей рабочей точке и, по мере того как информация теряет свежесть, как перейти в рабочую точку, где можно получить более свежие данные.

Сопоставление потока пакетов с путём доставки
Основной алгоритм BBR состоит из двух частей:

Когда получаем подтверждение (ack)

Каждое подтверждение предоставляет новый RTT и измерения средней скорости доставки, которая обновляет оценки RTprop и BtlBw: 

function onAck(packet) 
  rtt = now - packet.sendtime 
  update_min_filter(RTpropFilter, rtt) 
  delivered += packet.size 
  delivered_time = now 
  deliveryRate = (delivered - packet.delivered) / (delivered_time - packet.delivered_time) 
  if (deliveryRate > BtlBwFilter.currentMax || ! packet.app_limited) 
     update_max_filter(BtlBwFilter, deliveryRate) 
  if (app_limited_until > 0) 
     app_limited_until = app_limited_until — packet.size

Проверка if нужна из-за проблемы неопределённости, о которой говорилось в последнем параграфе: отправители могут быть ограничены приложением, то есть у приложения могут закончиться данные для заполнения сети. Это довольно типичная ситуация из-за трафика запрос/ответ. Когда есть возможность для отправки, но никакие данные не отправляются, BBR помечает соответствующие образцы пропускной способности как «ограниченные приложением», то есть app_limited (см. псевдокод send()). Этот код определяет, какие образцы включать в модель пропускной способности, так что он отражает именно сетевые ограничения, а не лимиты приложения. BtlBw является твёрдым верхним ограничением скорости доставки, так что полученная по результатам измерения скорость доставки большая, чем текущая оценка BtlBw, должна означать заниженную оценку BtlBw, независимо от того, был ли образец ограничен приложением или нет. В противном случае образцы с ограничением приложения отбрасываются. (Рисунок 1 показывает, что в регионе с ограничением приложения deliveryRate параметр BtlBw занижен). Такие проверки предотвращают заполнение фильтра BtlBw заниженными значениями, из-за которых отправка данных может замедлиться.

Когда данные отправляются

Для соотнесения скорости прибытия пакетов со скоростью вылета из узкого места BBR отслеживает каждый пакет данных. (BBR должен соответствовать rate узкого места: это значит, что отслеживание является неотъемлемой частью архитектуры и фундаментальной частью работы — поэтому pacing_rate является основным контрольным параметром. Вспомогательный параметр cwnd_gain связывает inflight с небольшим множеством BDP для обработки типичных патологий сети и получателя (см. ниже главу по задержанным и растянутым подтверждениям). Концептуально, процедура send в TCP выглядит как следующий код. (В Linux отправка данных использует эффективную процедуру массового обслуживания FQ/pacing [4], которая обеспечивает BBR линейную производительность одиночного соединения на мультигигабитных каналах и обрабатывает тысячи соединений с более низкой скоростью с незначительным оверхедом CPU).

function send(packet) 
  bdp = BtlBwFilter.currentMax × RTpropFilter.currentMin 
  if (inflight >= cwnd_gain × bdp) 
     // wait for ack or retransmission timeout 
     return 
  if (now >= nextSendTime) 
     packet = nextPacketToSend() 
     if (! packet) 
        app_limited_until = inflight 
        return 
     packet.app_limited = (app_limited_until > 0) 
     packet.sendtime = now 
     packet.delivered = delivered 
     packet.delivered_time = delivered_time 
     ship(packet) 
     nextSendTime = now + packet.size / (pacing_gain × BtlBwFilter.currentMax) 
  timerCallbackAt(send, nextSendTime)

Поведение в устойчивом состоянии

Скорость и количество данных, отправляемых по BBR, зависит только от BtlBw и RTprop, так что фильтры контролируют не только оценки ограничений узкого места, но и их применение. Это создаёт нестандартный контур управления, изображённый на рисунке 2, на котором показаны RTT (синим), inflight (зелёным) и скорость доставки (красным) на протяжении 700 миллисекунд для 10-мегабитного 40-миллисекундного потока. Жирная серая линия над скоростью доставки — это состояние фильтра BtlBw max. Треугольные формы получаются от цикличного применения коэффициента pacing_gain в BBR для определения увеличения BtlBw. Коэффициент передачи в каждой части цикла показан выровненным по времени с данными, на которые он повлиял. Этот коэффициент сработал на RTT раньше, когда данные отправлялись. Это показано горизонтальными неровностями в описании последовательности событий с левой стороны.

0d52cdb5d319240c894572ac49b9bbd2.png
Рисунок 2

BBR сводит к минимум задержку, потому что основная часть времени проходит с одной и той же BDP в действии. За счёт этого узкое место передвигается к отправителю, так что увеличение BtlBw становится незаметным. Следовательно, BBR периодически тратит интервал RTprop на значении pacing_gain > 1, которое увеличивает скорость отправки и объём отправленных данных без подтверждения доставки (inflight). Если BtlBw не меняется, то очередь создаётся перед узким местом, увеличивая RTT, что сохраняет неизменным показатель deliveryRate. (Очередь можно устранить, отправляя данные с компенсирующим значением pacing_gain < 1 для следующего RTprop). Если BtlBw увеличивается, то скорость deliveryRate тоже увеличивается, а новое максимальное значение фильтра немедленно увеличивает базовую скорость отслеживания (pacing_rate). По этой причине BBR приспосабливается к новому размеру узкого места экспоненциально быстро. Рисунок 3 показывает этот эффект на 10-мегабитном 40-миллисекундном потоке, который BtlBw внезапно увеличивает до 20 Мбит/с после 20 секунд устойчивой работы (в левой части графика), затем сбрасывает до 10 Мбит/с после ещё 20 секунд устойчивой работы на 20 Мбит/с (правая часть графика).

782dc2df0ea26284cda4bcd194e7507d.png
Рисунок 3

(По сути, BBR — это простой пример управляющей системы «макс-плюс», нового подхода к системам управления, основанном на нестандартной макс-плюс алгебре [12]. Этот подход позволяет адаптировать скорость [управляется коэффициентом передачи max] независимо от роста очереди [управляется коэффициентом передачи average]. В применении к нашей задаче это сводится к простому, безусловному контуру управления, где адаптация к изменениям физических ограничений автоматически осуществляется изменением фильтров, выражающих эти ограничения. Традиционная система потребовала бы создания множества контуров управления, объединённых в сложный конечный автомат, чтобы добиться такого результата).

Поведение при запуске одиночного потока BBR
Современные реализации обрабатывают события вроде запуска (startup), закрытия (shutdown) и возмещения потерь (loss recovery) с помощью алгоритмов, реагирующих на «события», с большим количеством строк кода. В BBR используется код, приведённый выше (в предыдущей главе «Сопоставление потока пакетов с путём доставки»), для всего. Обработка событий происходит путём прохода через последовательность «состояний». Сами «состояния» определены таблицей с одним или несколькими фиксированными значениями коэффициентов и критериев выхода. Основное время тратится в состоянии ProbeBW, которое описано в главе «Поведение в устойчивом состоянии». Состояния Startup и Drain используются при запуске соединения (рисунок 4). Чтобы обрабатывать соединение, где пропускная способность увеличивается на 12 порядков, в состоянии Startup реализован алгоритм двоичного поиска для BtlBw, где используется коэффициент передачи $2/ln2$ для двукратного увеличения скорости передачи, когда увеличивается скорость доставки. Так определяется BtlBw в $log_2BDP$ RTT, но в то же время создаёт излишнюю очередь до $2BDP$. Как только Startup находит BtlBw, система BBR переходит в состояние Drain, которое использует обратные коэффициенты передачи Startup, чтобы избавиться от излишней очереди, а затем — в состояние ProbeBW, как только inflight опускается до линии BDP.

2faac84009e59e0332173d560ceafcab.png
Рисунок 4

Рисунок 4 показывает первую секунду 10-мегабитного 40-миллисекундного потока BBR. На верхнем графике отложено время и последовательность событий, а также прогресс отправителя (зелёным) и получателя (синим): объём переданных и полученных данных. Красная линия показывает показатели отправителя по технологии CUBIC при тех же условиях. Вертикальные серые линии означают моменты перехода между состояниями BBR. На нижнем графике — изменение времени двойного прохода пакетов (RTT) обоих соединений. Обратите внимание, что шкала времени для этого графика соответствует времени получения подтверждения о прибытии (ack). Поэтому может показаться, что графики будто смещены во времени, но на самом деле события внизу соответствуют тем моментам, когда система BBR узнаёт об этих событиях и реагирует.

Нижний график на рисунке 4 сравнивает BBR и CUBIC. Сначала их поведение почти одинаково, но BBR полностью опустошает образовавшуюся при запуске соединения очередь, а CUBIC не может этого сделать. У неё нет модели трассы, которая сообщила бы, сколько отправленных данных являются излишними. Поэтому CUBIC менее агрессивно наращивает передачу данных без подтверждения доставки, но этот рост продолжается до тех пор, пока буфер узкого места не переполнится и не начнёт отбрасывать пакеты, или до достижения лимита у получателя на отправленные данные без подтверждения (окно приёма TCP).

Рисунок 5 показывает поведение RTT в первые восемь секунд соединения, изображённого на предыдущем рисунке 4. Технология CUBIC (красным) заполняет весь доступный буфер, затем крутится между 70% и 100% заполнения каждые несколько секунд. После запуска соединения BBR (зелёным) работает практически без создания очереди.

ba54cce323dbd38e54462ea8bbf3cb67.png
Рисунок 5

Поведение, когда несколько потоков BBR встречаются в узком месте
Рисунок 6 показывает, как пропускная способность нескольких потоков BBR сходится в честном разделе канала с узким местом на 100 мегабит/10 миллисекунд. Смотрящие вниз треугольные структуры — состояния соединений ProbeRTT, в которых самосинхронизация ускоряет окончательную конвергенцию.

4912d0f00580c8523040ee59b7a39df9.png
Рисунок 6

Циклы изменения коэффициентов усиления ProbeBW (рисунок 2) стимулируют бóльшие потоки уступать полосу меньшим потокам, в результате чего каждый поток понимает своё честное состояние. Это происходит довольно быстро (несколько циклов ProbeBW), хотя несправедливость может сохраняться, если опоздавшие к началу передела потоки переоценивают RTprop из-за того, что начавшие ранее потоки (временно) создают очередь.

Чтобы выяснить настоящий RTProp, поток перемещается налево от линии BDP, используя состояние ProbeRTT: если оценка RTProp не обновляется (то есть путём замера меньшего RTT) в течение многих секунд, то BBR входит в состояние ProbeRTT, уменьшая количество отправляемых данных (inflight) до четырёх пакетов по крайней мере для одного двойного прохода, а затем возвращается в предыдущее состояние. Когда большие потоки входят в состояние ProbeRTT, то из очереди изымается много пакетов, так что сразу несколько потоков видят новое значение RTprop (новое минимальное RTT). Благодаря этому их оценки RTprop обнуляются одновременно, так что они все вместе входят в состояние ProbeRTT — и очередь уменьшается ещё сильнее, в результате чего ещё больше потоков видят новое значение RTprop, и так далее. Такая распределённая координация — ключевой фактор одновременно для честного распределения полосы и стабильности.

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

Опыт внедрения B4 WAN в Google
Сеть B4 в компании Google — это высокоскоростная сеть WAN (wide-area network), построенная на обычных дешёвых коммутаторах [15]. Потери на этих коммутаторах с мелкими буферами происходят в основном из-за случайного наплыва небольших всплесков трафика. В 2015 году Google начала переводить рабочий трафик с CUBIC на BBR. Не было зафиксировано никаких проблем или регрессий, а с 2016 года весь трафик B4 TCP использует BBR. Рисунок 7 иллюстрирует одну причину, по которой это было сделано: пропускная способность BBR неизменно в 2–25 раз выше, чем у CUBIC. Мы видели даже большее улучшение, но обнаружили, что 75% соединений BBR ограничены буфером приёма TCP в ядре, который сотрудники отдела эксплуатации сети сознательно установили на низкое значение (8 МБ), чтобы не дать CUBIC заполонить сеть мегабайтами избыточного трафика без подтверждения доставки (если разделить 8 МБ на 200 мс межконтинентального RTT, то получится 335 Мбит/с максимум). Ручное увеличение буфера приёма на на одном маршруте США−Европа мгновенно повысило скорость передачи данных BBR до 2 Гбит/с, в то время как CUBIC остался на 15 Мбитах/с — это 133-кратное относительное увеличение пропускной способности было предсказано Мэтисом с коллегами в научной работе 1997 года. [17]

d02a04ce75499aacc753dacd72d15c56.png
Рисунок 7

Рисунок 7 показывает относительное улучшение BBR по сравнению с CUBIC; на врезке — интегральные функции распределения (cumulative distribution functions, CDF) для пропускной способности. Замеры произведены с помощью службы активного зондирования, которая открывает постоянные соединения BBR и CUBIC к удалённым дата-центрам, затем каждую минуту передаёт по 8 МБ данных. Зонды исследуют много маршрутов B4 между Северной Америкой, Европой и Азией.

Огромное улучшение — прямое следствие того, что BBR не использует потерю пакетов как индикатор затора. Для достижения полной пропускной способности существующим методам регулирования заторов по потере пакетов нужно, чтобы уровень потерь был меньше, чем обратный квадрат BDP [17] (например, менее одной потери на 30 миллионов пакетов для соединения 10 Гбит/с и 100 мс). На рисунке 8 сравнивается измеренная полезная пропускная способность на различных уровнях потерь пакетов. В алгоритме CUBIC допуск на потерю пакетов является структурным свойством алгоритма, а в BBR это параметр конфигурации. По мере того, как уровень потерь в BBR приближается к максимальному коэффициенту усиления ProbeBW, вероятность измерения скорости доставки реального BtlBw резко падает, что приводит к недооценке со стороны фильтра max.

e314ab029416ab03f7a80c8d882db8cd.png
Рисунок 8

Рисунок 8 сравнивает полезную пропускную способность BBR и CUBIC в 60-секундном потоке на соединении 100 Мбит/c и 100 мс со случайными потерями от 0,001% до 50%. Пропускная способность CUBIC уменьшается в 10 раз при потерях 0,1% и полностью глохнет при более 1%. Максимальной пропускной способностью считается доля полосы за минусом потерь пакетов ($= 1 - lossRate$). BBR держится на этом уровне до уровня потерь 5% и близко к нему до 15%.

Опыт внедрения YouTube Edge
BBR развёртывается на видеосерверах YouTube и Google.com. Google проводит небольшой эксперимент, в рамках которого малый процент пользователей случайно переводят на BBR или CUBIC. Воспроизведение видео по BBR показывает значительно улучшение всех оценок пользователями качества услуги. Возможно, потому что поведение BBR более последовательное и предсказуемое. BBR лишь немного улучшает пропускную способность соединения, потому что YouTube и так адаптирует скорость потоковой передачи до уровня гораздо ниже BtlBw, чтобы свести к минимуму излишнюю сетевую буферизацию и повторную буферизацию. Но даже здесь BBR уменьшает среднее медианное RTT на 53% в целом по миру и более чем на 80% в развивающихся странах.

Рисунок 9 показывает медианное улучшение RTT в сравнении BBR и CUBIC по статистике более 200 млн просмотров видео на YouTube, измеренных на пяти континентах в течение недели. Более половины из всех 7 млрд мобильных соединений в мире подключаются по 2.5G на скорости от 8 до 114 Кбит/с [5], испытывая хорошо задокументированные проблемы из-за того, что методы регулирования заторов по потере пакетов склонны переполнять буферы [3]. Узкое место в этих системах обычно находится между SGSN (обслуживающий узел поддержки GPRS) [18] и мобильным устройством. Программное обеспечение SGSN работает, а стандартной платформе ПК с обильным количеством ОЗУ, где часто имеются мегабайты буфера между интернетом и мобильным устройством. Рисунок 10 сравнивает (эмулированную) задержку SGSN между интернетом и мобильным устройством для BBR и CUBIC. Горизонтальные линии отмечают одни из наиболее серьёзных последствий: TCP адаптируется к длительным задержкам RTT за исключением пакета SYN, инициирующего соединение, у которого фиксированный таймаут, в зависимости от операционной системы. Когда мобильное устройство получает большой массив данных (например, от автоматического обновления программного обеспечения) через SGSN с большим буфером, устройство не может установить никакое соединение в интернете, пока очередь не освободится (подтверждающий пакет SYN ACK задерживается на большее время, чем фиксированный таймаут SYN).

8038d13ff6ae9a5538a9170196b2b61b.png
Рисунок 9

Рисунок 10 показывает медианные изменения RTT в устойчивом состоянии соединения и зависимость от размера буфера на соединении 128 Кбит/с и 40 мс с восемью потоками BBR (зелёным) или CUBIC (красным). BBR удерживает очередь у минимальных значений, независимо от размера буфера узкого места и количества активных потоков. Потоки CUBIC всегда заполняют буфер, так что задержка увеличивается линейно с размером буфера.

4f3e349eea51398a085dba9875819aed.png
Рисунок 10

Адаптивная полоса в мобильной сотовой связи
Сотовые системы адаптируют полосу пропускания для каждого пользователя частично в зависимости от прогноза запросов, в котором учитывается очередь пакетов, предназначенная для этого пользователя. Ранние версии BBR были настроены таким образом, чтобы создавать очень маленькие очереди, из-за чего соединения стопорились на низких скоростях. Увеличение пикового значения pacing_gain для ProbeBW и увеличение очередей привело к уменьшению заглохших соединений. Это показывает возможность великолепной адаптации для некоторых сетей. С текущим значением пикового коэффициента усиления $1,25 × BtlBw$ не проявляется никакой деградации ни в какой сети, по сравнению с CUBIC.Задержанные и растянутые пакеты ack
Сети сотовой связи, WiFi и широкополосные сети часто задерживают и скапливают пакеты ack [1]. Когда inflight ограничивается одним BDP, это приводит к срывам, снижающим пропускную способность. Увеличение коэффициента cwnd_gain ProbeBW до двух позволило продолжить ровную передачу на прогнозируемой скорости доставки, даже когда пакеты ack задерживались до значения в один RTT. Это в значительной степени предотвращает срывы.Ограничители текущего ведра
Первоначальное развёртывание BBR на YouTube показал, что большинство интернет-провайдеров в мире искажают трафик с помощью ограничителей скорости по алгоритму текущего ведра [7]. Ведро обычно полно в начале соединения, так что BBR узнаёт параметр BtlBw для лежащей в основе сети. Но как только ведро опустошается, то все пакеты, отправленные быстрее, чем (намного меньшая, чем BtlBw) скорость наполнения ведра, отбрасываются. BBR в конце концов узнаёт эту новую скорость доставки, но цикличное изменение коэффициента усиления ProbeBW приводит к постоянным умеренным потерям. Чтобы минимизировать потери полосы восходящего потока и увеличение задержек приложения от этих потерь, мы добавили специальный детектор ограничителей и явную модель ограничителей в BBR. Мы также активно изучаем лучшие способы устранить вред от работы ограничителей скорости.Конкуренция с методами регулирования заторов по потерям пакетов
BBR сводится к честному разделению полосы пропускания узкого места, будь то в конкуренции с другими потоками BBR или с потоками под управлением методов регулирования заторов по потерям пакетов. Даже когда последние заполняют доступный буфер, ProbeBW всё ещё надёжно сдвигает оценку BtlBw в сторону честного разделения потоков, а ProbeRTT считает оценку RTProp достаточно высокой для сходимости «око за око» к честному разделению. Однако неуправляемые буферы маршрутизаторов, превышающие некоторые BDP, заставляют устаревших конкурентов с регулированием заторов по потерям пакетов раздувать очередь и захватывать больше, чем им причитается по-честному. Устранение этого — ещё одна область активных исследований.Заключение
Переосмысление методов регулирования заторов приносит огромную пользу. Вместо использования событий, таких как потери или занятие буфера, которые лишь слабо коррелируют с заторами, BBR начинает с формальной модели заторов Клейнрока и связанной с ней оптимальной рабочей точки. Досадный вывод о «невозможности» одновременного определения критически важных параметров задержки и полосы пропускания обходитс

© Habrahabr.ru