Справедливая очередь — это семейство алгоритмов планирования, используемых в некоторых планировщиках процессов и сетей . Алгоритм предназначен для достижения справедливости при совместном использовании ограниченного ресурса, например, для предотвращения того, чтобы потоки с большими пакетами или процессы, генерирующие небольшие задания, потребляли больше пропускной способности или процессорного времени, чем другие потоки или процессы.
Справедливая организация очередей реализована в некоторых современных сетевых коммутаторах и маршрутизаторах .
Термин «справедливая очередь» был введен Джоном Нэглом в 1985 году, когда он предложил циклическое планирование на шлюзе между локальной сетью и Интернетом для уменьшения сбоев в работе сети из-за плохо работающих хостов. [1] [2] [3]
Версия с байтовым весом была предложена Аланом Демерсом, Шринивасаном Кешавом и Скоттом Шенкером в 1989 году и была основана на более раннем алгоритме справедливой организации очередей Нейгла. [4] [5] Алгоритм справедливой организации очередей с байтовым весом призван имитировать мультиплексирование побитно путем вычисления теоретической даты отправления для каждого пакета.
Эта концепция получила дальнейшее развитие в виде взвешенной справедливой очередности и более общей концепции формирования трафика , в которой приоритеты очередей динамически контролируются для достижения желаемого качества обслуживания потока или ускорения некоторых потоков.
Справедливая организация очередей использует одну очередь на поток пакетов и обслуживает их поочередно, так что каждый поток может «получить равную долю ресурсов». [1] [2]
Преимущество по сравнению с традиционным принципом « первым пришел — первым обслужен » (FIFO) или приоритетной очередностью заключается в том, что поток данных с высокой скоростью, состоящий из больших пакетов или множества пакетов данных, не может занять больше своей справедливой доли пропускной способности канала.
Справедливая очередь используется в маршрутизаторах, коммутаторах и статистических мультиплексорах , которые пересылают пакеты из буфера . Буфер работает как система очередей, где пакеты данных временно хранятся до тех пор, пока они не будут переданы.
При скорости передачи данных по каналу R в любой момент времени N активных потоков данных (с непустыми очередями) обслуживаются каждый со средней скоростью передачи данных R/N . В течение короткого промежутка времени скорость передачи данных может колебаться вокруг этого значения, поскольку пакеты доставляются последовательно по очереди.
В контексте сетевого планирования справедливость имеет несколько определений. Статья Нагеля использует циклическое планирование пакетов [2], которое справедливо с точки зрения количества пакетов, но не использования полосы пропускания, когда пакеты имеют разный размер. Было определено несколько формальных понятий меры справедливости, включая максимально -минимальную справедливость , справедливость в худшем случае [6] и индекс справедливости [7] .
Первоначальная идея дает каждому потоку одинаковую скорость. Естественное расширение состоит в том, чтобы позволить пользователю указать часть полосы пропускания, выделенную каждому потоку, что приводит к взвешенной справедливой очередности и обобщенному разделению процессора .
Этот алгоритм пытается эмулировать справедливость побитового циклического распределения ресурсов связи между конкурирующими потоками. Однако пакетные потоки должны передаваться пакетно и последовательно. Алгоритм справедливой очереди с байтовым весом выбирает порядок передачи пакетов, моделируя время окончания для каждого пакета, как если бы они могли передаваться побитовым циклическим методом. Пакет с самым ранним временем окончания в соответствии с этим моделированием выбирается следующим для передачи.
Сложность алгоритма составляет O(log(n)) , где n — количество очередей/потоков.
Моделирование фактического времени завершения, хотя и осуществимо, требует больших вычислительных затрат. Модель необходимо существенно пересчитывать каждый раз, когда пакет выбирается для передачи и каждый раз, когда новый пакет поступает в любую очередь.
Для снижения вычислительной нагрузки вводится понятие виртуального времени . Время окончания для каждого пакета вычисляется на этой альтернативной монотонно увеличивающейся виртуальной шкале времени. Хотя виртуальное время не точно моделирует время завершения передач пакетов, оно точно моделирует порядок, в котором передачи должны происходить для достижения целей полнофункциональной модели. Используя виртуальное время, нет необходимости пересчитывать время окончания для ранее поставленных в очередь пакетов. Хотя время окончания в абсолютном выражении для существующих пакетов потенциально зависит от новых поступлений, время окончания на виртуальной временной шкале остается неизменным — виртуальная временная шкала деформируется относительно реального времени, чтобы вместить любую новую передачу.
Виртуальное время окончания для вновь поставленного в очередь пакета определяется суммой виртуального времени начала плюс размер пакета. Виртуальное время начала — это максимум между предыдущим виртуальным временем окончания той же очереди и текущим моментом.
С вычисленным виртуальным временем завершения всех пакетов-кандидатов (т. е. пакетов в начале всех непустых очередей потока) справедливая очередь сравнивает виртуальное время завершения и выбирает минимальное. Пакет с минимальным виртуальным временем завершения передается.
Функция receive () выполняется каждый раз при получении пакета, а send () выполняется каждый раз, когда необходимо выбрать пакет для отправки, т. е. когда соединение неактивно и очереди не пусты. Этот псевдокод предполагает, что есть функция now (), которая возвращает текущее виртуальное время, и функция chooseQueue (), которая выбирает очередь, в которую помещен пакет.
Функция selectQueue () выбирает очередь с минимальным виртуальным временем завершения. Для удобства чтения представленный здесь псевдокод выполняет линейный поиск. Но поддержание отсортированного списка может быть реализовано за логарифмическое время, что приводит к сложности O(log(n)) , но с более сложным кодом.
Нагл представил свою схему «справедливой очередности», в которой шлюзы поддерживают отдельные очереди для каждого отправляющего хоста. Таким образом, хосты с патологическими реализациями не могут узурпировать больше, чем их справедливая доля ресурсов шлюза. Это вызвало оживленное и заинтересованное обсуждение.