Планировщик сети
Планировщик сети (англ. network scheduler, также планировщик пакетов, очередь дисциплины (англ. queueing discipline, qdisc), или алгоритм управления очередями) — это арбитр на узле в сети с коммутацией пакетов. Он управляет порядком передачи сетевых пакетов в очередях отправки и приёма стека протоколов и сетевого интерфейсного контроллера. Существуют различные реализации планировщиков сети для операционных систем, использующих многочисленные существующие алгоритмы управления очередями.
Логика планировщика сети определяет, какой сетевой пакет будет передан следующим. Планировщик работает в связке с системой очередей, временно хранящих пакеты до их передачи. В системах может быть как одна очередь, так и несколько, в последнем случае каждая из них может содержать пакеты определённого потока, классификации или приоритета.
В некоторых случаях выполнение всех передач не укладывается в ограничения системы. Тогда задача планировщика — определить, какой трафик передать, а какой подвергнуть сбросу.
Терминология и задачи
Планировщик сети также участвует в реализации механизмов управления сетевым трафиком. Управление трафиком охватывает все меры по снижению перегрузки сети, задержек и потерь пакетов. В частности, активное управление очередями (AQM) предполагает выборочный сброс пакетов для предотвращения чрезмерной перегрузки. Планировщик выбирает, какие пакеты сбросить. Формирование трафика (traffic shaping) сглаживает требования к пропускной способности путём задержки пакетов при пакетировании их в очереди. Планировщик определяет момент передачи каждого пакета. Качество обслуживания (QoS) означает приоритезацию трафика по классу услуги (англ. Differentiated services) или по выделенному соединению (англ. Integrated services).
Алгоритмы
С течением времени было разработано множество дисциплин обслуживания очередей в сети. Каждая из них определяет определённые правила переупорядочивания или сброса пакетов в буферах передачи и приёма[1]. Дисциплины управления очередями обычно применяются для компенсации различных сетевых условий, например, для снижения задержки определённых классов трафика, и часто используются в реализации мер QoS.[2][3][4]
Классовые (classful) дисциплины управления очередями позволяют создавать «классы», подобно ветвям дерева, и настраивать правила, направляющие пакеты в определённые подклассы. В каждом классе могут быть определены и другие классовые или бесклассовые (classless) дисциплины. Бесклассовые дисциплины не позволяют включать внутри себя дополнительные дисциплины[5].
Примеры алгоритмов, применяемых для управления трафиком:
| Алгоритм | Аббревиатура | Тип | Аппаратная поддержка |
|---|---|---|---|
| Алгоритм регулирования скорости ячеек | GCRA | ||
| Choose and Kill for unresponsive flows | CHOKe | Бесклассовый | |
| Управление задержкой | CoDel | Бесклассовый | |
| Усовершенствованный для прикладных задач | CAKE | ||
| Earliest TxTime First | ETF | Бесклассовый | Да |
| Первым пришёл — первым обслужен | FIFO | Бесклассовый | |
| Справедливая очередь | FQ | Бесклассовый | |
| Справедливая очередь с управлением задержкой | FQ-CoDel | Бесклассовый | |
| Flow Queuing with Proportional Integral controller Enhanced | FQ-PIE | Бесклассовый | |
| Генерализованный ранний случайный сброс | GRED | Бесклассовый | |
| Heavy-Hitter Filter[6] | HHF | Бесклассовый | |
| Multiqueue Priority | MQ-PRIO | Бесклассовый | Да |
| Multiqueue | MULTIQ | Бесклассовый | Да |
| Эмулятор сети[7] | NETEM | Бесклассовый | |
| Усовершенствованный пропорционально-интегральный контроллер[8] | PIE | Бесклассовый | |
| Случайный ранний сброс | RED | Бесклассовый | |
| Стохастический справедливый Blue | SFB | Бесклассовый | |
| Стохастическое справедливое обслуживание очереди | SFQ | Бесклассовый | |
| Фильтр пакетной ёмкости | TBF | Бесклассовый | |
| Основанное на классах управление очередью | CBQ | Классовый | |
| Справедливая очередь на основе кредита | CBS | Классовый | Да |
| Дефицитный круговой перебор[9] | DRR | Классовый | |
| Усиленный выбор передачи | ETS | Классовый | |
| Иерархическая справедливая кривая обслуживания | HFSC | Классовый | |
| Иерархический фильтр пакетной ёмкости[10] | HTB | Классовый | |
| Приоритет | PRIO | Классовый | |
| Быстрая справедливая очередь[11] | QFQ | Классовый | |
| Time Aware Priority Shaper | TAPRIO | Классовый | Да |
Некоторые из перечисленных алгоритмов реализованы как модули ядра Linux[12][13] и доступны свободно с открытым исходным кодом.
Проблема избыточного буферизации (Bufferbloat)
Bufferbloat — явление в сетях с коммутацией пакетов, при котором чрезмерная буферизация пакетов приводит к высоким задержкам и высокой вариативности задержки. Данной проблеме противодействует планировщик, осуществляющий стратегический сброс пакетов для предотвращения накопления избыточного числа пакетов в буфере. Примеры соответствующих алгоритмов — CoDel, FQ-CoDel и случайный ранний сброс.
Реализации
Ядро Linux
Планировщик пакетов в ядре Linux — неотъемлемая часть сетевого стека ядра Linux, управляющая буферами передачи и приёма всех сетевых интерфейсов.
Планировщик настраивается утилитой tc (сокр. от traffic control). По умолчанию используется дисциплина управления очередями FIFO под названием pfifo_fast[14], однако начиная с версии 217 systemd меняет дисциплину по умолчанию на fq_codel[15].
Утилиты ifconfig и ip позволяют администраторам настраивать размер буферов через параметры txqueuelen и rxqueuelen для каждого устройства по числу кадров Ethernet; размер фрейма значения не имеет. При этом в сетевом стеке ядра присутствуют и другие буферы, которые не подчиняются планировщику сети.
Классификаторам планировщика могут быть присоединены фильтры Berkeley Packet Filter. Функциональность eBPF, появившаяся в версии 4.1 ядра Linux (2015 год), расширяет классические классификаторы BPF до eBPF[16]. Они могут быть скомпилированы через компилятор LLVM (bpf backend) и загружены в работающее ядро с помощью tc[17].
BSD и OpenBSD
ALTQ — реализация планировщика сети в системах семейства BSD. В OpenBSD, начиная с версии 5.5, ALTQ заменён на HFSC-планировщик.
Планирование в беспроводных сетях с разделяемыми ресурсами (Cell-Free Network Scheduling)
Планировщики в системах связи управляют распределением ресурсов, включая приоритезацию пакетов, временные интервалы передачи и распределение каналов. В современных реализациях для решения сложных задач всё чаще применяются методы искусственного интеллекта. Так, для беспроводных сетей c архитектурой распределённых радиоузлов (cell-free) предложены планировщики на основе нейронных сетей, что позволяет эффективно организовывать взаимодействие между несколькими радиобазовыми точками (RU) и абонентскими устройствами (UE). Такой подход снижает вычислительную сложность при одновременной оптимизации задержки, пропускной способности и распределения ресурсов, что делает его перспективным для сетей стандарта «за пределами 5G».