Введение
Алгоритм планирования для совместного использования ограниченных ресурсов. Справедливое распределение (или справедливая очередь) — это семейство алгоритмов планирования, используемых в некоторых планировщиках процессов и сетевых устройствах. Алгоритм разработан для обеспечения справедливости при совместном использовании ограниченного ресурса, например, для предотвращения ситуации, когда потоки с большими пакетами или процессы, генерирующие небольшие задания, потребляют большую пропускную способность или время процессора, чем другие потоки или процессы. Справедливое распределение (или справедливая очередь) реализовано в некоторых современных сетевых коммутаторах и маршрутизаторах.
Fair queuing is a family of scheduling algorithms used in some process and network schedulers. The algorithm is designed to achieve fairness when a limited resource is shared, for example to prevent flows with large packets or processes that generate small jobs from consuming more throughput or CPU time than other flows or processes. Fair queuing is implemented in some advanced network switches and routers.
История
Термин "справедливое распределение пропускной способности" был введен Джоном Наглом в 1985 году при предложении алгоритма обслуживания методом "круговой очереди" в шлюзе между локальной сетью и Интернетом для снижения влияния некорректно работающих хостов на работу сети. В 1989 году Алан Демерс, Шринивасан Кешав и Скотт Шенкер предложили версию с учетом веса байтов, основанную на более раннем алгоритме справедливого распределения пропускной способности Нагла. Алгоритм справедливого распределения пропускной способности с учетом веса байтов предназначен для имитации мультиплексирования побитово путем вычисления теоретического времени отправки для каждого пакета. Эта концепция была далее развита в алгоритм взвешенного справедливого распределения пропускной способности и более общую концепцию управления трафиком, где приоритеты очередей динамически регулируются для достижения требуемых целей по качеству обслуживания потоков или ускорения определенных потоков.
Принцип
Справедливое распределение ресурсов использует одну очередь для каждого потока пакетов и обслуживает их поочередно, обеспечивая каждому потоку "равную долю ресурсов", а также использует индекс справедливости.
Обобщение в весовое распределение
Первоначальная идея предполагает одинаковую скорость для каждого потока. Естественным расширением является предоставление пользователю возможности указывать долю полосы пропускания, выделяемую каждому потоку, что приводит к взвешенной справедливой очередной обработке и обобщенному разделению ресурсов процессора.
Алгоритм справедливой очереди с байтовым весом
Этот алгоритм стремится эмулировать справедливость поочередного распределения ресурсов канала связи между конкурирующими потоками, как если бы осуществлялось побитовое циклическое обслуживание. Однако потоки, основанные на пакетах, должны передаваться пакетами и последовательно. Алгоритм справедливого обслуживания с учетом веса байтов определяет порядок передачи пакетов, моделируя время завершения каждого пакета так, как если бы они могли быть переданы побитово по циклическому принципу. Пакет с наименьшим временем завершения, рассчитанным по этой модели, выбирается следующим для передачи. Временная сложность алгоритма составляет O(log(n)), где n – количество очередей/потоков.
Детали алгоритма
Моделирование фактического времени завершения, хотя и возможно, требует значительных вычислительных ресурсов. Модель необходимо существенно пересчитывать каждый раз, когда пакет выбирается для передачи и каждый раз, когда новый пакет поступает в любую очередь. Для снижения вычислительной нагрузки вводится понятие виртуального времени. Время завершения каждого пакета вычисляется на этой альтернативной монотонно возрастающей виртуальной шкале времени. Хотя виртуальное время неточно моделирует время, в течение которого пакеты завершают передачу, оно точно моделирует порядок, в котором передачи должны происходить для достижения целей полнофункциональной модели. При использовании виртуального времени нет необходимости пересчитывать время завершения для пакетов, уже находящихся в очереди. Хотя фактическое время завершения существующих пакетов может потенциально измениться из-за новых поступлений, время завершения на виртуальной шкале времени остается неизменным – виртуальная шкала времени адаптируется к реальному времени, чтобы учесть любую новую передачу. Виртуальное время завершения для вновь поступившего в очередь пакета определяется как сумма виртуального времени начала и размера пакета. Виртуальное время начала – это максимум между предыдущим виртуальным временем завершения той же очереди и текущим моментом времени. После вычисления виртуального времени завершения для всех кандидатов (то есть пакетов в начале всех непустых очередей потока), алгоритм справедливого обслуживания сравнивает виртуальное время завершения и выбирает минимальное. Пакет с минимальным виртуальным временем завершения передается.