Честная очередь

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

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

История

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

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

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

Принцип

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

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

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

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

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

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

Обобщение для взвешенного обмена

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

Побайтно-взвешенный алгоритм справедливой организации очереди

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

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

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

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

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

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

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

Псевдокод

Shared variables
    const N             // Nb of queues 
    queues[1..N]        // queues
    lastVirFinish[1..N] // last virtual finish instant

receive(packet)
     queueNum := chooseQueue(packet)
     queues[queueNum].enqueue(packet)
     updateTime(packet, queueNum)

updateTime(packet, queueNum)
    // virStart is the virtual start of service
    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$ 
     while it ≤ N do
         queue := queues[it]
         if not queue.empty and queue.head.virFinish < minVirFinish then
             minVirFinish = queue.head.virFinish
             queueNum := it 
         it := it + 1
     return queueNum

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

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

См. также

Ссылки

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

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

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

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

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

[6] Беннетт, JCR; Хуэй Чжан (1996). «WF/sup 2/Q: справедливо взвешенная справедливая очередь в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . Том. 1. п. 120. дои : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 . S2CID 17558577 .

[7] Ито, Ю.; Тасака, С.; Ишибаси, Ю. (2002). «Кадровая очередь с переменным взвешиванием для основных IP-маршрутизаторов». Материалы конференции Международной конференции IEEE по производительности, вычислениям и коммуникациям (кат. № 02CH37326) . п. 159. дои : 10.1109/IPCCC.2002.995147 . ISBN 978-0-7803-7371-6 . S2CID 60787008 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]