Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья посвящена планированию в сети. Для общего планирования вычислений см. Планирование (вычисления) .
Очередь пакетов в структуре данных FIFO (first in, first out).

Сетевой планировщик , называемый также планировщик пакетов , очередей дисциплины , Qdisc или алгоритм организации очереди , является арбитром на узле в пакетной коммутации сети связи. Он управляет последовательностью сетевых пакетов в передающем и приемную очереди на контроллере сетевого интерфейса . Для разных операционных систем доступно несколько сетевых планировщиков , которые реализуют многие из существующих алгоритмов сетевого планирования .

Логика сетевого планировщика решает, какой сетевой пакет пересылать следующим. Сетевой планировщик связан с системой очередей, временно сохраняя сетевые пакеты, пока они не будут переданы. Системы могут иметь одну или несколько очередей, и в этом случае каждая может содержать пакеты одного потока , классификации или приоритета.

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

Терминология и обязанности [ править ]

Сетевой планировщик может нести ответственность за реализацию конкретных инициатив по управлению сетевым трафиком . Контроль сетевого трафика - это общий термин для всех мер, направленных на уменьшение перегрузки, задержки и потери пакетов. В частности, активное управление очередью (AQM) - это выборочное отбрасывание сетевых пакетов в очереди для достижения более широкой цели предотвращения чрезмерной перегрузки сети. Планировщик должен выбрать, какие пакеты отбрасывать. Формирование трафика сглаживает требования к пропускной способности потоков трафика, задерживая пакеты передачи, когда они помещаются в очередь пакетами. Планировщик определяет время для передаваемых пакетов. качество обслуживания (QoS) - это приоритезация трафика на основе класса обслуживания (Дифференцированные услуги ) или зарезервированное соединение ( Интегрированные услуги ).

Алгоритмы [ править ]

С течением времени было разработано множество дисциплин сетевого очередей. Каждый из них обеспечивает конкретное переупорядочивание или отбрасывание сетевых пакетов внутри различных буферов передачи или приема . [1] [2] Дисциплины организации очередей обычно используются в качестве попыток компенсировать различные сетевые условия, такие как уменьшение задержки для определенных классов сетевых пакетов, и обычно используются как часть мер QoS. [3] [4] [5]

Примеры алгоритмов, подходящих для управления сетевым трафиком, включают:

  • Справедливая организация очереди на основе кредита
  • DRR ( циклический перебор дефицита ) и DWRR, реализация, например, написанная Патриком МакХарди для ядра Linux [8] и опубликованная под Стандартной общественной лицензией GNU .
  • FaQ (FavourQueue) [9]
  • FQ-PIE (Расширенный пропорциональный интегральный контроллер очереди потока)
  • GCRA ( общий алгоритм скорости передачи ячеек )
  • HFF ( фильтр с сильным напором ) [10]
  • HFSC ( иерархическая кривая справедливого обслуживания )
  • HTB ( иерархическая корзина токенов ) [11]
  • QFQ ( быстрая справедливая организация очереди ) [12]
  • FQ ( справедливая организация очереди ) и WFQ ( справедливая организация взвешенных очередей )
  • FIFO ( первый пришел , первый ушел )
  • pkt_sched: fq: планировщик пакетов справедливой очереди [13]
  • Сетевой эмулятор NETEM [14]
  • PIE ( улучшенный пропорциональный интегральный контроллер ) [15]
  • КРАСНЫЙ ( случайное раннее обнаружение )
    • ARED ( расширенное случайное раннее обнаружение )
    • GRED ( обобщенное случайное раннее обнаружение )
    • RRED ( надежное случайное раннее обнаружение )
    • WRED ( взвешенное случайное раннее обнаружение )
  • RR ( циклический ) и WRR ( взвешенный циклический алгоритм )
  • SFB ( стохастический светлый синий ), а также RSFB (устойчивый SFB)
  • SFQ (организация очередей стохастической справедливости) [16]
  • TBF ( фильтр корзины токенов ) [17]
  • TEQL ( тривиальный эквалайзер ссылок )

Некоторые из вышеперечисленных реализованы в виде модулей ядра Linux [18] и находятся в свободном доступе .

Bufferbloat [ править ]

Bufferbloat - это явление в сетях с коммутацией пакетов, в котором избыточная буферизация пакетов вызывает большие задержки и вариации задержки пакетов . Bufferbloat может быть адресован сетевому планировщику, который стратегически отбрасывает пакеты, чтобы избежать излишне большого объема невыполненной буферизации. Примеры включают CoDel и раннее обнаружение Random .

Реализации [ править ]

Ядро Linux [ править ]

Планировщик пакетов ядра Linux является частью сетевого стека вместе с netfilter , nftables и Berkeley Packet Filter .

Linux пакет ядра планировщик является составной частью сетевого стека в Linux ядра и управляет приема и передачи кольцевых буферов всех сетевых адаптеров, работая на уровне 2 в модели OSI и обработки кадров Ethernet , например.

Планировщик пакетов настраивается с помощью вызываемой утилиты tc(сокращение от «контроль трафика»). В качестве дисциплины организации очереди по умолчанию планировщик пакетов использует реализацию FIFO под названием pfifo_fast , [19] хотя systemd, начиная с ее версии 217, изменяет дисциплину организации очереди по умолчанию на fq_codel . [20]

ifconfigИ ipутилиты позволяют системным администраторам конфигурировать размеры буферов txqueuelenи rxqueuelenдля каждого устройства в отдельности с точки зрения количества кадров Ethernet , независимо от их размера. Сетевой стек ядра Linux содержит несколько других буферов, которые не управляются сетевым планировщиком. [а]

Фильтры Berkeley Packet Filter могут быть присоединены к классификаторам планировщика пакетов. Функциональность eBPF, представленная в версии 4.1 ядра Linux в 2015 году, расширяет классические программируемые классификаторы BPF на eBPF. [21] Их можно скомпилировать с помощью бэкэнда LLVM eBPF и загрузить в работающее ядро ​​с помощью tcутилиты. [22]

BSD и OpenBSD [ править ]

ALTQ - это реализация сетевого планировщика для BSD . Начиная с версии 5.5 OpenBSD ALTQ был заменен планировщиком HFSC.

См. Также [ править ]

  • Перегрузка сети
  • Очередь (абстрактный тип данных)
  • Теория массового обслуживания
  • Статистическое мультиплексирование с временным разделением
  • Формирование трафика
  • Классификация трафика
  • Тип сервиса

Примечания [ править ]

  1. ^ Общий размер всех буферов был предметом критики со стороныпроекта Bufferbloat , который предоставил частичное решение с CoDel, которое в основном тестировалось в OpenWrt .

Ссылки [ править ]

  1. ^ "Управление трафиком HOWTO: Бесклассовые дисциплины организации очередей (qdiscs)" . tldp.org . Проверено 24 ноября 2013 года .
  2. ^ Saravanan Radhakrishnan (30 сентября 1999). «Поддержка QoS в Linux: правила организации очередей» . qos.ittc.ku.edu . Проверено 18 марта 2014 года .
  3. ^ "Управление трафиком HOWTO: Компоненты управления трафиком Linux" . tldp.org . Проверено 24 ноября 2013 года .
  4. ^ «Управление трафиком HOWTO: традиционные элементы управления движением» . tldp.org . Проверено 24 ноября 2013 года .
  5. ^ «Дисциплины организации очереди: порядок передачи и отбрасывания пакетов» (PDF) . tau.ac.il . 25 октября 2006 . Проверено 18 марта 2014 года .
  6. ^ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.4477&rep=rep1&type=pdf
  7. ^ «Пусть запускают ТОРТ» . LWN.net .
  8. ^ "Модуль сетевого планировщика ядра DRR Linux" . kernel.org . Проверено 7 сентября 2013 .
  9. ^ «FavorQueue: безпараметрическое управление активной очередью для повышения производительности TCP-трафика» (PDF) .
  10. ^ "Фильтр тяжелых ударов qdisc" . kernel.org .
  11. ^ "Модуль сетевого планировщика ядра HTB Linux" . kernel.org . Проверено 7 сентября 2013 .
  12. ^ "Модуль сетевого планировщика ядра QFQ Linux" . kernel.org . Проверено 7 сентября 2013 .
  13. ^ «Планировщик пакетов Fair Queue, предназначенный для ядра Linux 3.12» .
  14. ^ "Модуль сетевого планировщика ядра Linux сетевого эмулятора" . kernel.org . Проверено 7 сентября 2013 .
  15. ^ "Пропорционально-интегральный регулятор Enhanced (PIE)" . kernel.org .
  16. ^ "Модуль сетевого планировщика ядра SFQ Linux" . kernel.org . Проверено 7 сентября 2013 .
  17. ^ "Модуль сетевого планировщика ядра TBF Linux" . kernel.org . Проверено 7 сентября 2013 .
  18. ^ "Сетевой планировщик ядра Linux" . kernel.org . 2012-12-26 . Проверено 7 сентября 2013 .
  19. ^ «Linux Advanced Routing and Traffic Control HOWTO, раздел 9.2.1. Pfifo_fast» . lartc.org . 2012-05-19 . Проверено 19 сентября 2014 .
  20. ^ "systemd System and Service Manager: NEWS file" . freedesktop.org . 2015-05-22 . Проверено 9 июня 2015 .
  21. ^ «Ядро Linux 4.1, раздел 11. Сеть» . kernelnewbies.org . 2015-06-21.
  22. ^ "Справочное руководство по BPF и XDP" . Веб-сайт документации по Cilium .