Честная очередь
Справедливая организация очередей — это семейство алгоритмов планирования, используемых в некоторых планировщиках процессов и сетей . Алгоритм предназначен для достижения справедливости при совместном использовании ограниченного ресурса, например, чтобы предотвратить потребление потоков с большими пакетами или процессами, генерирующими небольшие задания, большей пропускной способности или процессорного времени, чем другие потоки или процессы.
Справедливая организация очередей реализована в некоторых современных сетевых коммутаторах и маршрутизаторах .
История [ править ]
Термин «справедливая организация очереди» был придуман Джоном Нэглом в 1985 году, когда он предлагал циклическое планирование на шлюзе между локальной сетью и Интернетом , чтобы уменьшить сбои в работе сети из-за плохо ведущих себя хостов. [1] [2] [3]
Байто-взвешенная версия была предложена Аланом Демерсом, Сринивасаном Кешавом и Скоттом Шенкером в 1989 году и была основана на более раннем алгоритме справедливой организации очереди Нэгла. [4] [5] Алгоритм справедливой организации очередей с взвешиванием по байтам направлен на имитацию побитового мультиплексирования путем вычисления теоретической даты отправления для каждого пакета.
Эта концепция получила дальнейшее развитие в взвешенной справедливой организации очередей и в более общей концепции формирования трафика , в которой приоритеты очередей динамически контролируются для достижения желаемого качества потока для целей обслуживания или ускорения некоторых потоков.
Принцип [ править ]
Справедливая организация очередей использует одну очередь для каждого потока пакетов и обслуживает их поочередно, так что каждый поток может «получить равную долю ресурсов». [1] [2]
Преимущество по сравнению с традиционной организацией очереди «первым пришел — первым обслужен » (FIFO) или приоритетной организацией очереди заключается в том, что поток данных с высокой скоростью, состоящий из больших пакетов или множества пакетов данных, не может занять больше, чем справедливая доля пропускной способности канала.
Справедливая организация очередей используется в маршрутизаторах, коммутаторах и статистических мультиплексорах , которые пересылают пакеты из буфера . Буфер работает как система очередей, в которой пакеты данных временно сохраняются до момента их передачи.
При скорости передачи данных по каналу R в любой момент времени N активных потоков данных (те, которые имеют непустые очереди) обслуживаются каждый со средней скоростью передачи данных R/N . За короткий промежуток времени скорость передачи данных может колебаться около этого значения, поскольку пакеты доставляются последовательно по очереди.
Справедливость [ править ]
В контексте сетевого планирования справедливость имеет несколько определений. В статье Нагеля используется циклическое планирование пакетов. [2] это справедливо с точки зрения количества пакетов, но не с точки зрения использования полосы пропускания, когда пакеты имеют разный размер. несколько формальных понятий меры справедливости, Было определено включая максимальную и минимальную справедливость , справедливость в наихудшем случае , [6] и индекс справедливости . [7]
Обобщение для взвешенного распределения [ править ]
Первоначальная идея придает каждому потоку одинаковую скорость. Естественным расширением является предоставление пользователю возможности указать часть полосы пропускания, выделяемую каждому потоку, что приводит к взвешенной справедливой организации очередей и обобщенному совместному использованию процессоров .
Алгоритм справедливой организации очереди по байтам [ править ]
Этот алгоритм пытается эмулировать справедливость побитового циклического разделения ресурсов каналов между конкурирующими потоками. Однако пакетные потоки должны передаваться пакетно и последовательно. Алгоритм справедливой организации очереди по байтам выбирает порядок передачи пакетов, моделируя время окончания для каждого пакета, как если бы они могли передаваться побитовым циклическим методом. Пакет с самым ранним временем завершения в соответствии с этим моделированием выбирается следующим для передачи.
Сложность алгоритма составляет O(log(n)) , где n — количество очередей/потоков.
Детали алгоритма [ править ]
Моделирование фактического времени окончания, хотя и осуществимо, требует больших вычислительных ресурсов. Модель необходимо существенно пересчитывать каждый раз, когда пакет выбирается для передачи, и каждый раз, когда новый пакет поступает в какую-либо очередь.
понятие виртуального времени Для снижения вычислительной нагрузки вводится . Время окончания для каждого пакета вычисляется в этой альтернативной монотонно возрастающей виртуальной шкале времени. Хотя виртуальное время неточно моделирует время завершения передачи пакетов, оно точно моделирует порядок, в котором должна происходить передача, чтобы достичь целей полнофункциональной модели. При использовании виртуального времени нет необходимости пересчитывать время окончания для ранее поставленных в очередь пакетов. Хотя на время окончания в абсолютном выражении для существующих пакетов потенциально влияют новые поступления, время окончания на виртуальной временной шкале не меняется — виртуальная временная шкала искажается по отношению к реальному времени, чтобы приспособиться к любой новой передаче.
Время виртуального окончания для нового пакета, поставленного в очередь, определяется как сумма виртуального времени начала и размера пакета. Время виртуального начала — это максимальное время между предыдущим виртуальным временем окончания той же очереди и текущим моментом.
После вычисления виртуального времени завершения всех пакетов-кандидатов (т. е. пакетов в начале всех непустых очередей потока), справедливая организация очереди сравнивает виртуальное время завершения и выбирает минимальное. Передается пакет с минимальным виртуальным временем завершения.
Псевдокод [ править ]
Общие переменные const N // Кол-во очередей очереди[1..N] // очереди LastVirFinish[1..N] // последний момент виртуального завершения | |
получить (пакет) lengthNum := selectQueue(пакет) очереди[queueNum].enqueue(пакет) updateTime (пакет, QueueNum) | updateTime (пакет, lengthNum) // virStart — виртуальный запуск сервиса virStart := max(now(), LastVirFinish[queueNum]) package.virFinish := package.size + virStart LastVirFinish[queueNum] := package.virFinish |
отправлять() очередьNum := selectQueue() пакет:= очереди[queueNum].dequeue() обратный пакет | выберитеОчередь() это := 1 минВирФиниш = пока оно ≤ N, делайте очередь := очереди[оно] если не очередь.пустая и очередь.head.virFinish < minVirFinish , тогда minVirFinish = очередь.head.virFinish очередьNum := это это := это + 1 возврат очередиNum |
Функция получения () выполняется каждый раз при получении пакета, а функция send () выполняется каждый раз, когда необходимо выбрать пакет для отправки, т.е. когда канал простаивает и очереди не пусты. В этом псевдокоде предполагается, что существует функция now (), которая возвращает текущее виртуальное время, и функция ChooseQueue (), которая выбирает очередь, в которой пакет поставлен в очередь.
Функция selectQueue () выбирает очередь с минимальным виртуальным временем завершения. Для удобства чтения представленный здесь псевдокод выполняет линейный поиск. Но поддержание отсортированного списка может быть реализовано за логарифмическое время, что приведет к сложности O(log(n)) , но с более сложным кодом.
См. также [ править ]
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Джон Нэгл: «О коммутаторах пакетов с бесконечным хранилищем», RFC 970, IETF , декабрь 1985 г.
- ↑ Перейти обратно: Перейти обратно: а б с Нэгл, Дж. Б. (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 .