Справедливая организация очередей - это семейство алгоритмов планирования, используемых в некоторых планировщиках процессов и сетей . Алгоритм разработан для достижения справедливости при совместном использовании ограниченного ресурса, например, для предотвращения потоков с большими пакетами или процессов, которые создают небольшие задания, от использования большей пропускной способности или времени ЦП, чем другие потоки или процессы.
Справедливая организация очереди реализована в некоторых усовершенствованных сетевых коммутаторах и маршрутизаторах .
История
Термин « честная организация очереди» был введен Джоном Нэглом в 1985 году, когда он предлагал циклическое планирование на шлюзе между локальной сетью и Интернетом для уменьшения сбоев сети из-за плохо работающих хостов. [1] [2] [3]
Версия с байтовым взвешиванием была предложена Аланом Демерсом, Сринивасаном Кешавом и Скоттом Шенкером в 1989 году и была основана на более раннем алгоритме справедливой организации очередей Нэгла. [4] [5] Алгоритм справедливой организации очереди с байтовым взвешиванием нацелен на имитацию побитового мультиплексирования путем вычисления теоретической даты отправления для каждого пакета.
Эта концепция была далее развита до взвешенной справедливой организации очередей и более общей концепции формирования трафика , в которой приоритеты очередей динамически управляются для достижения желаемого качества потока для целей обслуживания или ускорения некоторых потоков.
Принцип
Справедливая организация очередей использует одну очередь для каждого потока пакетов и обслуживает их по очереди , так что каждый поток может «получить равную долю ресурсов». [1] [2]
Преимущество перед обычным порядком очереди по принципу « первым пришел - первым обслужен» (FIFO) или приоритетом состоит в том, что поток с высокой скоростью передачи данных, состоящий из больших пакетов или множества пакетов данных, не может занимать больше, чем справедливую долю пропускной способности канала.
Справедливая организация очередей используется в маршрутизаторах, коммутаторах и статистических мультиплексорах, которые пересылают пакеты из буфера . Буфер работает как система очередей, где пакеты данных временно хранятся, пока они не будут переданы.
При ссылке скорости передачи данных из R , в любой данный момент времени N потоки данных , активные (те , с непустыми очередями) обслуживаются каждый со средней скоростью передачи данных R / N . За короткий промежуток времени скорость передачи данных может колебаться около этого значения, поскольку пакеты доставляются последовательно по очереди.
Справедливость
В контексте сетевого планирования справедливость имеет несколько определений. В статье Нагеля используется циклическое планирование пакетов [2], которое справедливо с точки зрения количества пакетов, но не с точки зрения использования полосы пропускания, когда пакеты имеют разный размер. Несколько формальных представления о справедливости мер были определены в том числе макс-мин справедливости , в худшем случае справедливости , [6] и индекс справедливости . [7]
Обобщение на взвешенное совместное использование
Первоначальная идея дает каждому потоку одинаковую скорость. Естественное расширение состоит в том, чтобы позволить пользователю указать часть полосы пропускания, выделенную для каждого потока, что приводит к взвешенной справедливой организации очередей и обобщенному совместному использованию процессора .
Алгоритм справедливой организации очереди с байтовым взвешиванием
Этот алгоритм пытается имитировать справедливость побитового циклического разделения ресурсов канала между конкурирующими потоками. Однако потоки на основе пакетов должны передаваться последовательно и пакетно. Алгоритм справедливой организации очереди с байтовым взвешиванием выбирает порядок передачи для пакетов, моделируя время окончания для каждого пакета, как если бы они могли быть переданы побитовым циклическим перебором. Пакет с самым ранним временем окончания в соответствии с этим моделированием является следующим, выбранным для передачи.
Сложность алгоритма составляет O (log (n)) , где n - количество очередей / потоков.
Детали алгоритма
Моделирование фактического времени окончания работ, хотя и возможно, требует больших вычислительных ресурсов. Модель необходимо пересчитывать каждый раз, когда пакет выбирается для передачи и каждый раз, когда новый пакет поступает в любую очередь.
Для снижения вычислительной нагрузки вводится понятие виртуального времени . Время окончания для каждого пакета вычисляется на этой альтернативной монотонно увеличивающейся виртуальной шкале времени. Хотя виртуальное время не точно моделирует время, в течение которого пакеты завершают свою передачу, оно точно моделирует порядок, в котором должны происходить передачи, чтобы соответствовать целям полнофункциональной модели. Используя виртуальное время, нет необходимости повторно вычислять время окончания для ранее поставленных в очередь пакетов. Хотя время окончания в абсолютном выражении для существующих пакетов потенциально зависит от новых поступлений, время окончания на виртуальной временной шкале не изменяется - виртуальная временная шкала деформируется относительно реального времени, чтобы приспособиться к любой новой передаче.
Виртуальное время окончания для вновь поставленного в очередь пакета определяется суммой виртуального времени начала плюс размер пакета. Виртуальное время начала - это максимальное время между предыдущим виртуальным временем окончания той же очереди и текущим моментом.
После вычисления виртуального времени завершения всех пакетов-кандидатов (т. Е. Пакетов в начале всех непустых потоковых очередей) функция справедливой организации очереди сравнивает виртуальное время завершения и выбирает минимальный из них. Передается пакет с минимальным виртуальным временем окончания.
Псевдокод
Общие переменные const N // Кол-во очередей queues [1..N] // очереди lastVirFinish [1..N] // последний момент виртуального финиша | |
получить (пакет) queueNum: = chooseQueue (пакет) очереди [queueNum] .enqueue (пакет) updateTime (пакет, queueNum) | updateTime (пакет, queueNum) // virStart - виртуальный запуск службы virStart: = max (сейчас (), lastVirFinish [queueNum]) packet.virFinish: = packet.size + virStart lastVirFinish [queueNum]: = packet.virFinish |
Отправить() queueNum: = selectQueue () пакет: = очереди [queueNum] .dequeue () возвратный пакет | selectQueue () это: = 1 minVirFinish = пока это ≤ N делать queue: = queues [it] если не queue.empty и queue.head.virFinish |
Функция receive () выполняется каждый раз при получении пакета, а send () выполняется каждый раз, когда должен быть выбран пакет для отправки, то есть когда ссылка неактивна и очереди не пусты. Этот псевдокод предполагает, что существует функция now (), которая возвращает текущее виртуальное время, и функция chooseQueue (), которая выбирает очередь , в которую помещается пакет.
Функция selectQueue () выбирает очередь с минимальным виртуальным временем завершения. Для удобства чтения представленный здесь псевдокод выполняет линейный поиск. Но поддержание отсортированного списка может быть реализовано за логарифмическое время, что приведет к сложности O (log (n)) , но с более сложным кодом.
Смотрите также
Рекомендации
- ^ a b Джон Нэгл: «О пакетных коммутаторах с бесконечной памятью», RFC 970, IETF , декабрь 1985 г.
- ^ a b c Нэгл, JB (1987). «На пакетных коммутаторах с неограниченным объемом памяти». Транзакции IEEE по коммуникациям . 35 (4): 435–438. CiteSeerX 10.1.1.649.5380 . DOI : 10.1109 / TCOM.1987.1096782 .
- ^ Филип Гросс (январь 1986 г.), Протоколы рабочей группы по алгоритмам шлюза DARPA и структурам данных 16-17 января 1986 г. (PDF) , IETF , стр. 5, 98 , извлечено 4 марта 2015 г. ,
Нэгл представил свою схему «справедливой организации очередей» , в котором шлюзы поддерживают отдельные очереди для каждого отправляющего хоста. Таким образом, хосты с патологическими реализациями не могут узурпировать больше, чем их справедливая доля ресурсов шлюза. Это вызвало оживленную и заинтересованную дискуссию.
- ^ Демерс, Алан; Кешав, Шринивасан; Шенкер, Скотт (1989). «Анализ и моделирование алгоритма справедливой организации очередей». Обзор компьютерных коммуникаций ACM SIGCOMM . 19 (4): 1–12. DOI : 10.1145 / 75247.75248 .
- ^ Демерс, Алан; Кешав, Шринивасан; Шенкер, Скотт (1990). "Анализ и моделирование алгоритма справедливой организации очередей" (PDF) . Межсетевое взаимодействие: исследования и опыт . 1 : 3–26.
- ^ Беннетт, JCR; Хуэй Чжан (1996). «WF / sup 2 / Q: Справедливая организация очередей со справедливым взвешиванием в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . 1 . п. 120. DOI : 10,1109 / INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.
- ^ Ито, Й .; 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.