Справедливая организация очереди

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

Справедливая организация очередей реализована в некоторых усовершенствованных сетевых коммутаторах и маршрутизаторах.

• 1 История
• 2 Принцип
  • 2.1 Справедливость
  • 2.2 Обобщение до взвешенного разделения
• 3 Алгоритм справедливой организации очередей с байтовым взвешиванием
  • 3.1 Подробности алгоритма
  • 3.2 Псевдокод
• 4 См. также
• 5 Ссылки

Термин справедливая организация очереди был придуман Джоном Нэглом в 1985 году, когда он предлагал циклическое планирование на шлюзе между локальной сетью и Интернетом для уменьшения сбоев сети из-за плохого поведения хосты.

Версия с байтовым взвешиванием была предложена Аланом Демерсом, Шринивасаном Кешавом и Скоттом Шенкером в 1989 году и была основана на более раннем алгоритме справедливой организации очередей Нэгла. Алгоритм справедливой организации очереди с побайтовым взвешиванием нацелен на имитацию побитового мультиплексирования путем вычисления теоретической даты отправления для каждого пакета.

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

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

Преимущество перед традиционным первым пришел - первым вышел (FIFO) или очередью с приоритетом состоит в том, что поток с высокой скоростью передачи данных, состоящий из больших пакетов или множества пакетов данных, не может брать больше, чем справедливая доля пропускной способности канала.

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

При скорости передачи данных линии R в любой момент времени обслуживаются N активных потоков данных (с непустыми очередями), каждый со средней скоростью передачи данных R / N. За короткий промежуток времени скорость передачи данных может колебаться около этого значения, поскольку пакеты доставляются последовательно по очереди.

Справедливость

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

Обобщение на взвешенное распределение

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

Этот алгоритм пытается имитировать справедливость побитового циклического разделения ресурсов канала между конкурирующими потоками. Однако потоки на основе пакетов должны передаваться последовательно и пакетно. Алгоритм справедливой организации очереди с байтовым взвешиванием выбирает порядок передачи пакетов, моделируя время окончания для каждого пакета, как если бы они могли быть переданы побитовым циклическим перебором. Пакет с самым ранним временем окончания в соответствии с этим моделированием является следующим, выбранным для передачи.

Сложность алгоритма составляет O (log (n)), где n - количество очередей / потоков.

Подробности алгоритма

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

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

Виртуальное время окончания для вновь поставленного в очередь пакета дается суммой виртуального времени начала плюс размер пакета. Виртуальное время начала - это максимальное время между предыдущим виртуальным временем окончания той же очереди и текущим моментом.

С вычисленным виртуальным временем завершения всех пакетов-кандидатов (то есть пакетов в начале всех непустых потоковых очередей) справедливая организация очереди сравнивает виртуальное время завершения и выбирает минимальное. Передается пакет с минимальным виртуальным временем окончания.

Псевдокод

Общие переменные const N // Nb очередей queues [1..N] // очередей lastVirFinish [1..N] // последний момент виртуального финиша

receive (пакет) queueNum: = chooseQueue (пакет) очереди [queueNum].enqueue (пакет) updateTime (packet, queueNum)

updateTime (packet, queueNum) // virStart - виртуальный запуск службы virStart: = max (now (), lastVirFinish [queueNum]) packet.virFinish: = packet.size + virStart lastVirFinish [queueNum]: = packet.virFinish

send () queueNum: = selectQueue () packet: = queues [queueNum].dequeue () return packet

selectQueue () it: = 1 minVirFinish = $\infty \; \{\backslash \; displaystyle\; \backslash \; infty\}$пока it ≤ N do queue: = queues [it] ifnot queue.empty и queue.head.virFinish 

Функция receive () выполняется каждый раз при получении пакета, а send () выполняется каждый раз, когда pac Кет для отправки должен быть выбран, т.е. когда ссылка неактивна и очереди не пусты. Этот псевдокод предполагает, что существует функция now (), которая возвращает текущее виртуальное время, и функция chooseQueue (), которая выбирает очередь, в которую помещается пакет.

Функция selectQueue () выбирает очередь с минимальным виртуальным временем завершения. Для удобства чтения представленный здесь псевдокод выполняет линейный поиск. Но поддержание отсортированного списка может быть реализовано за логарифмическое время, что приведет к сложности O (log (n)), но с более сложным кодом.

• Сетевой планировщик
• Взвешенная справедливая организация очередей
• Взвешенный циклический перебор
• Обобщенное совместное использование процессора
• Круговой алгоритм дефицита
• Bufferbloat
• Показатель справедливости
• Макс. -min справедливость
• Статистическое мультиплексирование
• Активное управление очередью

1. ^ Джон Нэгл: «На пакетных коммутаторах с бесконечной памятью» RFC 970, IETF, декабрь 1985 г.
2. ^ Nagle, JB (1987). «На пакетных коммутаторах с бесконечным хранилищем». Транзакции IEEE по коммуникациям. 35(4): 435–438. CiteSeerX 10.1.1.649.5380. doi : 10.1109 / TCOM.1987.1096782.
3. ^Филип Гросс (январь 1986 г.), Материалы рабочей группы DARPA по алгоритмам шлюза и структурам данных 16-17 января 1986 г. (PDF), IETF, стр. 5, 98, получено 4 марта 2015 г., Нэгл представил свою схему «справедливой организации очередей», в которой шлюзы поддерживают отдельные очереди для каждого отправляющего хоста. Таким образом, хосты с патологическими реализациями не могут узурпировать больше, чем их справедливая доля ресурсов шлюза. Это вызвало оживленную и заинтересованную дискуссию.
4. ^Демерс, Алан; Кешав, Шринивасан; Шенкер, Скотт (1989). «Анализ и моделирование алгоритма справедливой организации очередей». Обзор компьютерных коммуникаций ACM SIGCOMM. 19 (4): 1–12. doi : 10.1145 / 75247.75248.
5. ^Демерс, Алан; Кешав, Шринивасан; Шенкер, Скотт (1990). «Анализ и моделирование алгоритма справедливой организации очередей» (PDF). Межсетевое взаимодействие: исследования и опыт. 1 : 3–26.
6. ^Bennett, J.C.R.; Хуэй Чжан (1996). «WF / sup 2 / Q: справедливая организация очередей со справедливым взвешиванием в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям. 1 . п. 120. doi : 10.1109 / INFCOM.1996.497885. ISBN 978-0-8186-7293-4.
7. ^Ито, Й.; Tasaka, S.; Ишибаши Ю. (2002). «Круговая очередь с переменным весом для основных IP-маршрутизаторов». Материалы конференции IEEE International Performance, Computing and Communications Conference (Cat. No. 02CH37326). п. 159. doi : 10.1109 / IPCCC.2002.995147. ISBN 978-0-7803-7371-6.