Справедливая очередь

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

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

История [ править ]

Термин « честная организация очереди» был введен Джоном Нэглом в 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 делать ${\ displaystyle \ infty}$   queue: = queues [it] если  не queue.empty и queue.head.virFinish <minVirFinish, тогда minVirFinish = queue.head.virFinish queueNum: = это  it: = it + 1 return queueNum

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

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

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

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

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

^ 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 , извлечено 04 марта 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.

[RFC970-1] Джон Нэгл: «О пакетных коммутаторах с бесконечной памятью», RFC 970, IETF , декабрь 1985 г.

[Nagle87-2] Нэгл, 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 , извлечено 04 марта 2015 г. , Нэгл представил свою «справедливую организацию очереди» схема, в которой шлюзы поддерживают отдельные очереди для каждого отправляющего хоста. Таким образом, хосты с патологическими реализациями не могут узурпировать больше, чем их справедливая доля ресурсов шлюза. Это вызвало оживленную и заинтересованную дискуссию.

[4] Демерс, Алан; Кешав, Шринивасан; Шенкер, Скотт (1989). «Анализ и моделирование алгоритма справедливой организации очередей». Обзор компьютерных коммуникаций ACM SIGCOMM . 19 (4): 1–12. DOI : 10.1145 / 75247.75248 .

[5] Демерс, Алан; Кешав, Шринивасан; Шенкер, Скотт (1990). "Анализ и моделирование алгоритма справедливой организации очередей" (PDF) . Межсетевое взаимодействие: исследования и опыт . 1 : 3–26.

[6] Беннетт, JCR; Хуэй Чжан (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.

[1]