Справедливая очередь - Википедия - Fair queuing

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

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

История

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

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

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

Принцип

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

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

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

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

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

В контексте сетевого планирования справедливость имеет несколько определений. В статье Нагеля используется циклическое планирование пакетов,[2] что справедливо с точки зрения количества пакетов, но не с точки зрения использования полосы пропускания, когда пакеты имеют разный размер. Несколько формальных представлений о мера справедливости были определены в том числе макс-мин честность, наихудший случай справедливости,[6] и индекс справедливости.[7]

Обобщение на взвешенное совместное использование

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

Байтовый алгоритм справедливой организации очередей

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

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

Детали алгоритма

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

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

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

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

Псевдокод

Общие переменные    const N // Nb очередей queues [1..N] // очереди lastVirFinish [1..N] // момент последнего виртуального финиша
получить(пакет) queueNum: = выбратьQueue (пакет) очереди [queueNum] .enqueue (пакет) updateTime (пакет, queueNum)
Время обновления(packet, queueNum) // virStart - виртуальный запуск службы virStart: = max (now (), lastVirFinish [queueNum]) packet.virFinish: = packet.size + virStart lastVirFinish [queueNum]: = packet.virFinish
Отправить()     queueNum: = selectQueue () пакет: = queues [queueNum] .dequeue () возвращаться пакет
selectQueue ()     it: = 1 минVirFinish =      пока это ≤ N делать         queue: = queues [it] если нет queue.empty и queue.head.virFinish тогда             minVirFinish = queue.head.virFinish queueNum: = it it: = it + 1 возвращаться queueNum

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

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

Смотрите также

Рекомендации

  1. ^ а б Джон Нэгл: «На коммутаторах пакетов с бесконечным хранилищем» RFC 970, IETF, Декабрь 1985 г.
  2. ^ а б c Нэгл, Дж. Б. (1987). «На пакетных коммутаторах с бесконечным хранилищем». Транзакции IEEE по коммуникациям. 35 (4): 435–438. CiteSeerX  10.1.1.649.5380. Дои:10.1109 / TCOM.1987.1096782.
  3. ^ Филипп Гросс (январь 1986 г.), Материалы рабочей группы по алгоритмам шлюза DARPA и структурам данных 16-17 января 1986 г. (PDF), IETF, стр.5, 98, получено 2015-03-04, Нэгл представил свою схему «справедливой организации очереди», в которой шлюзы поддерживают отдельные очереди для каждого отправляющего хоста. Таким образом, хосты с патологическими реализациями не могут узурпировать больше, чем их справедливая доля ресурсов шлюза. Это вызвало оживленную и заинтересованную дискуссию.
  4. ^ Демерс, Алан; Кешав, Шринивасан; Шенкер, Скотт (1989). «Анализ и моделирование алгоритма справедливой организации очередей». Обзор компьютерных коммуникаций ACM SIGCOMM. 19 (4): 1–12. Дои: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. Дои: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. Дои:10.1109 / IPCCC.2002.995147. ISBN  978-0-7803-7371-6.