Перевантаження і черги

Навіщо це

Ви копіюєте великий файл на сервер, і відео-дзвінок у сусідній вкладці перетворюється на слайд-шоу. ping до роутера, який хвилину тому показував 3 мс, тепер показує 800. Канал тим часом заповнений «на сто відсотків», нічого не губиться, усе працює, просто повільно й із затримкою. Провайдер каже, що з його боку все гаразд, і формально він має рацію.

Ніякого збою тут немає: так разом поводяться TCP, який сам підбирає швидкість, і черга в маршрутизаторі, яка ховає ознаки перевантаження замість того, щоб про нього повідомити. Модуль пояснює, як вони взаємодіють, як це виглядає в Linux і як зіпсувати мережу навмисно, щоб перевіряти на ній власні програми.

Передумови. Вікно, RTT, повторні передачі й стани (модуль 11), добуток пропускної здатності на затримку (BDP, модуль 2).

Керування потоком і керування перевантаженням

У модулі 11 відправника стримувало вікно отримувача: не слати більше, ніж співрозмовник устигає прийняти. Це керування потоком, і воно розв’язує проблему двох кінців. Проте між кінцями лежить мережа, яка теж має межу, і про неї отримувач нічого не знає: його буфер може бути порожнім, а маршрутизатор посередині уже тоне.

Для мережі відправник тримає ще одне число, вікно перевантаження (congestion window, cwnd): скільки даних можна мати в польоті, щоб не переповнити шлях. Воно живе лише на відправнику, у заголовку його нема, і відправник оцінює його сам за побічними ознаками. Діє менше з двох вікон:

у польоті ≤ min(вікно отримувача, cwnd)

У середині 1980-х мережа, з якої виріс інтернет, пережила колапс перевантаження: відправники, не отримавши підтвердження, повторювали сегменти, повтори перевантажували мережу ще більше, і корисна пропускна здатність падала майже до нуля. У 1988 році Ван Джекобсон (Van Jacobson) у статті Congestion Avoidance and Control запропонував тримати cwnd і змінювати його за правилами, описаними нижче. Із цього вийшов сучасний TCP. Без такого керування мережа з мільярдами відправників не працювала б, бо ніхто, окрім самих відправників, швидкості не обмежує.

Повільний старт

Відправник не знає, скільки витримає шлях, тому починає з малого й швидко збільшує. Початковий cwnd у Linux становить 10 сегментів (у виводі ss -ti свіжого з’єднання ви побачите cwnd:10). Далі за кожен отриманий ACK cwnd зростає на один сегмент, а це означає подвоєння за кожен RTT: 10, 20, 40, 80…

Назва «повільний старт» історична й заплутує, бо зростання тут експоненційне. Повільним його назвали порівняно з первісною поведінкою, коли відправник одразу виплескував у мережу все вікно отримувача.

Експонента триває, доки cwnd не дійде до порога ssthresh (тоді TCP переходить на обережніше зростання) або не станеться втрата (тоді повернутися назад доведеться різко).

Для короткого з’єднання це важливо: відповідь розміром у кілька десятків кілобайтів може закінчитися, не вийшовши з повільного старту. Швидкість такого завантаження визначають RTT і початкове вікно, а не пропускна здатність каналу, тож для малих запитів затримка важить більше за «швидкість інтернету».

Уникнення перевантаження: AIMD

Після порога cwnd росте лінійно: приблизно на один сегмент за RTT. Коли відправник вирішує, що сталася втрата, він різко зменшує вікно, у класичному алгоритмі вдвічі. Це правило називають AIMD (additive increase, multiplicative decrease): адитивне збільшення (додаванням) і мультиплікативне зменшення (множенням на дріб).

Повільний старт, далі пилка: лінійне зростання й ділення навпіл після кожної втрати. Схема без чисел, лише форма. Штрихова лінія — рівень, на якому черга на вузькому місці переповнюється й починає відкидати пакети.

Збільшувати повільно, а зменшувати швидко вигідно, бо помилки в різні боки коштують по-різному. Занадто швидкий розгін обходиться дорого: переповнена черга губить пакети всіх, хто ділить з вами канал, і запускає повтори. Помилка в бік «занадто повільно» лише марнує трохи смуги. Асиметрія ще й забезпечує збіжність до справедливого розподілу: два потоки на одному каналі з часом вирівнюються, бо той, у кого вікно більше, втрачає за кожного зменшення більше.

Середня швидкість потоку тут виходить приблизно cwnd × MSS / RTT, і з цієї формули видно, звідки береться половина скарг на «повільний інтернет»:

За однакового cwnd швидкість обернено пропорційна RTT: потік до сервера за океаном розганяється й відновлюється повільніше за локальний.
Щоб заповнити канал, потрібне вікно хоча б розміром BDP. Для каналу 10 Мбіт/с із RTT 100 мс це 125 000 байтів, приблизно 86 сегментів по 1448 байтів. Поки cwnd менше, канал недозавантажено.

Про втрату відправник дізнається через ті самі механізми, що в модулі 11: три дублікати ACK (швидка повторна передача, cwnd ділиться навпіл і зростання лінійне далі) або спрацювання RTO (значно гірше: cwnd падає до мінімуму і починається новий повільний старт).

Від Reno до CUBIC і BBR

Алгоритм керування перевантаженням у Linux змінний: кожен сокет може мати свій. Найвідоміші з них зручно порівнювати за тим, що кожен вважає сигналом.

Reno (і його родичі) сприймає за сигнал втрату пакета. Поводиться за AIMD, як на схемі. Проста й справедлива, але на швидких каналах із великою затримкою надто повільно зростає: відновлення після однієї втрати займає безліч RTT.

CUBIC теж реагує на втрату, але зростання після неї будує не лінійно, а за кубічною функцією часу від останньої втрати: спершу швидко повертається до колишнього рівня, біля нього сповільнюється (обережно пробує), а далі знову прискорюється. Так на довгих швидких каналах він відновлюється швидше за Reno, і не залежить від RTT так жорстко. CUBIC — типовий вибір у Linux уже давно.

BBR (Google, 2016) відмовляється вважати втрату головним сигналом. Він безперервно оцінює дві величини: максимальну швидкість доставки (смугу вузького місця) і мінімальний RTT (затримку без черги). Їхній добуток і є BDP, і BBR намагається тримати в польоті саме стільки: канал заповнений, а черга порожня. Тому він не розганяє чергу до переповнення, як Reno і CUBIC. Водночас його поведінка поряд із іншими алгоритмами на спільному вузькому місці — предмет досліджень і суперечок, і варіантів BBR існує кілька.

	Що сприймає за сигнал	Що робить із чергою на вузькому місці
Reno	втрату	доводить до переповнення, потім ділить `cwnd` навпіл
CUBIC	втрату	те саме, але відновлюється швидше на довгих каналах
BBR	модель: смуга й мінімальний RTT	намагається її не заповнювати

Жоден із них не «найкращий». Reno і CUBIC реагують на те, що вже сталося, BBR будує модель і може помилятися в моделі. Вибір залежить від шляху й сусідів по каналу.

Черги, а з ними bufferbloat

Досі сигналом була втрата, а береться вона з черги. Маршрутизатор із швидкою вхідною і повільною вихідною ланкою мусить десь тримати пакети, що не встигли піти: це буфер. Коли буфер повний, нові пакети відкидаються, і відправники бачать втрату. Така черга називається drop-tail: відкидає з хвоста, коли місця нема.

Інженери історично виходили з того, що більший буфер кращий, бо пам’ять дешевшала, а відкинутий пакет — це марна робота. Результат назвали bufferbloat (роздуття буферів). Великий буфер, заповнений відправником, що ігнорує затримку, перетворює втрату на очікування:

час у черзі = байти в черзі ÷ швидкість вихідної ланки

Мегабайт у черзі перед ланкою 10 Мбіт/с — це 0,8 секунди затримки для кожного пакета, що стане в кінець, і для дзвінка, і для ping, і для DNS-запиту. Пакети нічого не гублять, завантаження показує повну швидкість, а інтерактивним програмам неможливо працювати.

Швидка ланка перед повільною з глибокою чергою. Пакет ping стає в хвіст і чекає за всіма великими пакетами: затримка в черзі лягає на кожен пакет, хоч би який малий.

Проблема особливо помітна там, де вузьке місце фіксоване: домашній роутер, стільникова мережа, Wi-Fi. Якраз вихідна ланка домашнього роутера (вихідна швидкість у кілька разів менша за вхідну) зазвичай і страждає першою. Це явище виявили не в лабораторії, а як регулярну скаргу «інтернет повільний, коли хтось вивантажує»; назву закріпив Джим Геттіс (Jim Gettys).

Ось воно в лабораторному масштабі. У просторі імен srv вузьке місце зроблено фільтром tbf (token bucket filter, він є в типовому ядрі): швидкість 10 Мбіт/с, черга дозволена глибока. Паралельно з iperf3 запущено ping:

ip netns exec srv tc qdisc replace dev v1 root tbf rate 10mbit burst 16kbit latency 1000ms
ip netns exec srv iperf3 -c 10.0.0.2 -t 8 &
ip netns exec srv ping -c5 -i0.5 10.0.0.2

# без навантаження
rtt min/avg/max/mdev = 0.031/0.034/0.037/0.002 ms
# під навантаженням, глибока черга (latency 1000ms), 0 повторних передач
rtt min/avg/max/mdev = 74.486/88.521/105.345/11.280 ms
[  5]   0.00-8.00   sec  9.75 MBytes  10.2 Mbits/sec    0    sender

Затримка зросла в тисячі разів, хоча швидкість потоку та сама, а повторних передач нуль. Тепер та сама перевірка з короткою чергою (latency 20ms):

# під навантаженням, коротка черга (latency 20ms)
rtt min/avg/max/mdev = 8.515/12.564/17.462/3.114 ms        (cubic)
[  5]   0.00-8.00   sec  9.00 MBytes  9.44 Mbits/sec   32   sender

Затримка лишається приблизно десятком мілісекунд, швидкість майже та сама, зате з’явилися повтори: 32 за вісім секунд у CUBIC. Саме ці втрати змушують відправника відступити, і це ціна чесної, коротшої черги.

ECN: сигнал без втрати

Втрата як сигнал має недолік: щоб про перевантаження дізналися, пакет мусить загинути. Явне сповіщення про перевантаження (explicit congestion notification, ECN) дозволяє маршрутизатору позначити пакет замість того, щоб відкидати.

Під час рукостискання обидва кінці TCP домовляються, що підтримують ECN, а відправник ставить у заголовку IP позначку «ECN-capable».
Маршрутизатор із заповненою чергою замість відкидання ставить у пакеті позначку «congestion experienced» (CE, два біти в заголовку IP).
Отримувач, побачивши CE, повертає відправнику в ACK прапорець ECE.
Відправник зменшує cwnd, як після втрати, і ставить прапорець CWR, щоб отримувач припинив повторювати ECE.

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

У Linux поведінку задає net.ipv4.tcp_ecn: 0 — вимкнено, 1 — просити ECN на вихідних і приймати на вхідних, 2 — приймати, коли просить співрозмовник, а самому не просити (типове значення в Linux — 2). Тому вдома ECN часто не задіяний, навіть коли підтримується з обох боків.

Активне керування чергою й qdisc у Linux

Черга в Linux живе в qdisc (queueing discipline), дисципліні черги, що прив’язана до кожного мережевого інтерфейсу. Вона вирішує, у якому порядку випускати пакети на ланку і кого відкидати, коли місця мало. Побачити її просто:

tc qdisc show dev eth0
tc -s qdisc show dev eth0      # зі статистикою: скільки відправлено, відкинуто

Найпоширеніші дисципліни:

pfifo_fast — класична проста черга з трьома пріоритетними смугами й одним правилом усередині кожної: першим прийшов, першим пішов. Глибина фіксована (у пакетах), розумної боротьби з bufferbloat нема.
fq — «чесна черга» (fair queueing): кожному потоку свій рядок, потоки обслуговуються по черзі, і один важкий не зайде в хвіст усім. Вміє також витримувати темп відправлення (pacing), який задає сам сокет, тобто не випускати пакети пачками.
fq_codel — чесна черга, у кожній підчерзі якої працює CoDel (controlled delay): вона керується не довжиною черги, а часом, який пакет у ній простояв. Якщо мінімальний час простою довго перевищує невелику ціль, CoDel починає відкидати (або позначати за ECN) пакети, щоб відправники відступили раніше, ніж черга роздується. Для малих потоків, як-от дзвінок чи DNS, це означає, що вони не чекають за великим завантаженням.

Типовим у ядрі лишається pfifo_fast, а багато дистрибутивів із systemd ставлять net.core.default_qdisc = fq_codel. Перевірте у своїй системі: те, що ви бачите на фізичному інтерфейсі, не збігається з віртуальним (veth, lo), де за замовчуванням стоїть noqueue: пакет без черги відразу йде далі.

Удома вузьке місце часто стоїть на чужому пристрої з глибоким буфером (модем, провайдерський роутер). Тоді чергу варто перенести до себе: обмежити власну швидкість трохи нижче реальної швидкості ланки й повісити на цей шейпер fq_codel чи схожу дисципліну. Тоді черга росте там, де нею керуєте ви.

Як це насправді в Linux

Який алгоритм і як його змінити

sysctl net.ipv4.tcp_congestion_control
sysctl net.ipv4.tcp_available_congestion_control

На машині, де знято приклад:

net.ipv4.tcp_congestion_control = bbr
net.ipv4.tcp_available_congestion_control = reno bbr cubic

Список доступних залежить від завантажених модулів ядра, а типове значення — від дистрибутива. У вас, імовірно, cubic. Змінити можна для всієї системи (sysctl -w net.ipv4.tcp_congestion_control=bbr) або для одного сокета: програма викликає setsockopt з TCP_CONGESTION, а iperf3 -C reno робить це за вас. Який алгоритм обрано для конкретного з’єднання, видно в ss -ti (слово bbr, cubic або reno у рядку) разом із cwnd, rtt і, якщо були, retrans.

Погана мережа на замовлення: `tc netem`

Щоб перевіряти програму або налаштування, потрібна мережа з втратами й затримкою, а локально все чисто. netem (network emulator) — qdisc, що вносить затримку, розкид, втрати, дублікати й переставляння. Застосовується до вихідного трафіку інтерфейсу.

# затримка 100 мс з розкидом 10 мс, втрата 1 %
ip netns exec srv tc qdisc add dev v1 root netem delay 100ms 10ms loss 1%
ip netns exec srv tc qdisc show dev v1
# змінити параметри, не видаляючи
ip netns exec srv tc qdisc change dev v1 root netem delay 50ms loss 5%
# прибрати
ip netns exec srv tc qdisc del dev v1 root

qdisc netem 8001: dev v1 root refcnt 2 limit 1000 delay 100ms  10ms loss 1% seed 2073356223798890387

На що натикаються першими:

netem діє лише на вихід інтерфейсу, тому затримка в один бік. Щоб отримати RTT 100 мс, вставте 50 мс на кожному з двох кінців.
Є опція rate, але обмеження швидкості зручніше робити окремим tbf, який ми вже використали, а netem лишати для затримки й втрат.
Втрати в netem незалежні за замовчуванням, а справжні бувають пачками. Для пачкових втрат є окремі моделі, але перш ніж їх шукати, переконайтеся, що вам це справді потрібно.
Будьте обережні на робочій машині: netem на eth0 вплине на весь її трафік, тож використовуйте простори імен.

Поставити `fq_codel` і побачити різницю

На машині, де модуль sch_fq_codel є, експеримент із bufferbloat повторюється так:

# замість глибокої черги — fq_codel під шейпером
tc qdisc replace dev v1 root handle 1: tbf rate 10mbit burst 16kbit latency 1000ms
tc qdisc add dev v1 parent 1:1 fq_codel
tc -s qdisc show dev v1

Якщо у виводі у fq_codel з’являються dropped і ecn_mark, CoDel працює. (Число seed у виводі netem — зерно генератора випадкових утрат; новіші версії tc його показують.) Очікувана картина: ping під навантаженням утримується у десятках мілісекунд чи нижче, а швидкість завантаження майже не змінюється. Саме цю різницю вам пропонує виміряти лабораторна B6.

Типові помилки розуміння

«Керування потоком і керування перевантаженням — одне й те саме». Перше захищає отримувача і працює через вікно, яке він оголошує. Друге захищає мережу і працює через cwnd, який відправник оцінює сам. Швидкість визначає менше з двох.

«Більший буфер — менше втрат, отже краще». Буфер, який ніколи не переповнюється, перетворює втрату на затримку, і відправник не отримує сигналу вчасно. Для інтерактивних програм це гірше за втрату.

«Повільний старт — це повільно». Зростання в ньому експоненційне, найшвидше з усіх фаз. Слово «повільний» історичне: так його назвали порівняно з ще давнішою поведінкою, коли відправник одразу випускав у мережу все вікно отримувача.

«Швидкість каналу — це швидкість з’єднання». Окремий TCP-потік не заповнить канал, поки cwnd не сягне BDP, а після кожної втрати знову відкотиться. Для коротких запитів важить RTT, а не смуга.

«BBR кращий за CUBIC в усіх випадках» (або навпаки). Вони спираються на різні сигнали, тож на одному шляху краще працює один, на іншому інший. Вибір залежить від втрат, черг і того, хто ще ділить вузьке місце. Порівнювати треба вимірюванням на своєму шляху.

«tc netem затримує вхідний трафік». Дисципліна застосовується до черги виходу. Для вхідного напрямку її ставлять на іншому кінці ланки або на допоміжному пристрої.

Перевір себе

1. Отримувач оголосив вікно 1 МіБ, але передача йде повільно, а cwnd відправника дорівнює 12 сегментам. Що обмежує швидкість?Вікно отримувача, бо воно більше за cwndКонтрольна сумаРозмір буфера відправного сокетаcwnd: у польоті не може бути більше, ніж мінімум з двох вікон

2. Що відбувається під час повільного старту?cwnd приблизно подвоюється кожен RTT, доки не буде втрати або досягнуто порогаcwnd зростає лінійно на один сегмент за RTTcwnd стоїть на місці, доки не прийде перший ACKcwnd дорівнює вікну отримувача

3. Під час завантаження великого файлу ping до роутера виріс із 3 мс до 800 мс, а пакетів не губиться. Яке пояснення найімовірніше?Втрата пакетів на Wi-FiГлибока черга на вузькому місці: пакети ping чекають за великими пакетами завантаженняПомилка DNSВікно отримувача дорівнює нулю

4. Чим CoDel відрізняється від звичайної drop-tail черги?Він збільшує розмір буфера, коли той повнийВін відкидає лише великі пакетиВін дивиться на час, який пакет простояв у черзі, а не на її довжину, і починає відкидати (чи позначати) пакети, коли цей час довго завеликийВін перевіряє контрольні суми

5. Яка перевага ECN перед втратою як сигналом перевантаження?Вона шифрує трафікВона збільшує cwndВона працює без підтримки маршрутизаторівМаршрутизатор позначає пакет замість відкидання, тож відправник відступає без втрати й повторної передачі

6. Ви виставили tc qdisc add dev eth0 root netem delay 50ms на одній машині й очікуєте RTT на 50 мс більший. Що побачите?RTT зросте на 50 мс, бо затримка діє на вихідні пакети, а відповідь повертається без затримкиRTT зросте на 100 мсRTT не змінитьсяRTT зросте на 25 мс

7. Чим BBR принципово відрізняється від Reno та CUBIC?Працює лише поверх UDPНе вважає втрату головним сигналом: оцінює смугу вузького місця й мінімальний RTT і намагається тримати в польоті їхній добутокЗавжди використовує більше вікноНе має повільного старту

Лабораторна

B6. Продуктивність і черги: iperf3 під tc netem, порівняння CUBIC і BBR, bufferbloat і fq_codel із вимірюванням і поясненням.
A4. Надійна доставка поверх UDP: власне ковзне вікно, яке доведеться перевіряти під втратами й переставлянням. Чекер створює їх власним проксі, а для ручних дослідів підійде netem.

Джерела

Van Jacobson, Congestion Avoidance and Control (SIGCOMM, 1988)
Kurose, Ross, Computer Networking: A Top-Down Approach, розділ про керування перевантаженням
Grigorik, High Performance Browser Networking, розділ про TCP
Cardwell та ін., BBR: Congestion-Based Congestion Control (ACM Queue, 2016)
RFC 5681 (TCP Congestion Control), RFC 3168 (ECN), RFC 8289 (CoDel), RFC 8290 (fq_codel)
man 8 tc, man 8 tc-netem, man 8 tc-tbf, man 8 tc-fq_codel, man 7 tcp, man 8 ss
Документація ядра: Documentation/networking/ip-sysctl.rst