Перегрузка сети

Теоретические основы заложил Фрэнк Келли (англ. Frank Kelly), впервые применивший микроэкономику и методы выпуклой оптимизации для описания оптимального распределения пропускной способности между автономными пользователями сети. К примеру, такими являются максимин-справедливое распределение и пропорционально-справедливое распределение, хотя их может быть и больше.

Пусть ${\displaystyle x_{i}}$ — скорость потока ${\displaystyle i}$, ${\displaystyle c_{l}}$ — пропускная способность канала ${\displaystyle l}$, ${\displaystyle r_{li}}$ = 1, если поток использует канал, и = 0 иначе. Пусть ${\displaystyle U(x)}$ — возрастающая строго вогнутая функция, отражающая пользу пользователя от передачи с темпом ${\displaystyle x}$. Оптимальное распределение достигается решением задачи:

${\displaystyle \max \limits _{x}\sum _{i}U(x_{i})}$

при условии ${\displaystyle Rx\leq c}$

Двойственная задача Лагранжа раскладывается так, чтобы каждый поток мог определить свою скорость, основываясь лишь на цене — суммарной нагрузке на сети, определяемой множителями Лагранжа ${\displaystyle p_{l}}$; итоговая цена для потока — ${\displaystyle y_{i}=\sum _{l}p_{l}r_{li}}$.

Управление перегрузкой в этом случае становится распределённым алгоритмом оптимизации. Многие современные реализации вписываются в эту схему, где ${\displaystyle p_{l}}$ отражает вероятность потерь или задержки в очереди. К недостаткам относится равенство цены для всех потоков, тогда как скользящее окно вносит вариативность в потери и задержки.

Классифицировать алгоритмы управления перегрузкой можно по следующим признакам:

• по виду и объёму обратной связи от сети: потери; задержки; явные сигналы одним или несколькими битами;
• по степени внедрения: требуется модификация только на отправителе; и на отправителе, и на приёмнике; только на маршрутизаторе; на всех элементах;
• по критериям эффективности: работа в сетях с высоким произведением полоса-задержка; в условиях потерь; справедливость; преимущество коротких потоков; переменная скорость;
• по критерию справедливости: максимин, пропорционально-справедливо, по задержке.

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

Алгоритм управления перегрузкой TCP лежит в основе борьбы с перегрузкой в Интернете^{[8][9][10][11][12]}. Проблемы возникают при одновременных потоках, когда сброс «по хвосту» в условиях избыточных буферов вызывает задержку потерь, приводя к глобальной синхронизации TCP.

Активное управление очередью (AQM) — перестановка или удаление пакетов в исходящем буфере сетевого интерфейса под управлением планировщика.

Одним из решений является случайное раннее обнаружение (RED) на выходной очереди^[13][14]. На оборудовании с несколькими выходными очередями используется взвешенное RED.

RED даёт косвенные сигналы TCP, удаляя часть пакетов — например, при переполнении очереди выше определённого порога (50 %), выполняя удаление по линейному либо кубическому закону^[15].

Устойчивое случайное раннее обнаружение (англ. robust random early detection, RRED) предназначено для увеличения пропускной способности TCP при LDoS-атаках. Эксперименты показывают уязвимость RED-подобных алгоритмов в таких условиях из-за периодического роста и падения очередей^[16].

Некоторые сетевые устройства позволяют измерять каждый поток и сигнализировать о превышении лимита, что даёт возможность раздельного распределения полосы пропускания по определённым критериям^[17].

Ещё один подход — использование ECN (англ. Explicit Congestion Notification)^[18]. ECN применяется, если оба хоста согласовали его поддержку. При этом бит протокола служит явным сигналом перегрузки, что предпочтительнее неявного, реализуемого через потерю пакетов в RED/WRED, но требует поддержки на обоих концах^[19][13].

При получении ECN-отмеченного пакета и наличии угрозы перегрузки маршрутизатор устанавливает ECN-флаг, уведомляя отправителя, который, соответственно, уменьшает скорость передачи (например, снижая размер окна TCP).

Протокол L4S является модификацией ECN и допускает совместное управление перегрузкой между отправителем и сетевыми устройствами^[20].

Снижение перегрузки достигается и ограничением размера окна передачи. При запросе больших файлов/страниц приложение обычно выставляет окно в 32-64 КБайт. Сервер при этом передаёт максимально возможные данные по окну. Если множество клиентов одновременно загружают большие файлы, это приводит к перегрузке на вышестоящем провайдере. Сокращая объём окна, можно снизить объём трафика и нагрузку^[21][22].

Обратное ECN (англ. Backward ECN, BECN) — механизм, использующий ICMP source quench для передачи сигналов о перегрузке на уровне IP без согласования между конечными узлами^[23].

Многие алгоритмы борьбы с коллапсом подразумевают, что потери пакетов обусловлены исключительно перегрузкой. Для проводных сетей это справедливо, но в Wi-Fi, 3G и других радиосетях потери могут вызываться помехами, а TCP будет ошибочно трактовать их как перегрузку, приводя к ненужному снижению скорости.

Медленный старт неэффективен для коротких соединений. Старые веб-браузеры для каждой загрузки открывали отдельное TCP-соединение, что удерживало соединения в режиме медленного старта, увеличивая задержки. Современные браузеры либо открывают несколько соединений, либо используют постоянные HTTP-соединения.