Кратко

  • Обычный пакетный round robin поровну раздаёт возможности передачи, но не байты. В DRR Шридхара и Varghese каждой очереди начисляется quantum, из счётчика дефицита оплачиваются целые пакеты, а неиспользованный остаток переносится дальше, пока очередь сохраняет backlog.
  • DRR создавался для ограниченного отклонения долгосрочной пропускной способности при малой работе на пакет. Справедливость относится к настроенным очередям и весам; базовый DRR не ограничивает задержку пакета, не классифицирует пользователей, не формирует трафик, не выполняет AQM или контроль перегрузки и не доказывает сквозное качество.

Равное число пакетов — это ответ не на тот вопрос

Round robin легко проверить взглядом: указатель посетил каждую активную очередь, никого не пропустил и начал новый круг. Если все задания одинакового размера, симметрия расписания переходит в симметрию ресурса. IP-пакеты имеют разную длину. Один ход может занять линию на время передачи 500 байт, другой — 1 500. Одинаковое число ходов не означает одинаковую долю полосы.

Панель с packets per second способна показывать идеальный баланс именно тогда, когда байтовый сервис устойчиво перекошен. Ошибка не в неисправном указателе: неправильно выбрана единица учёта. Дефицитным ресурсом является время передачи битов, а пакет — лишь неделимый контейнер переменного размера.

Точные схемы fair queuing могут вообразить текучий сервер, который одновременно обслуживает потоки, и вычислять виртуальные моменты завершения неделимых пакетов. Это даёт сильный эталон, но требует вычислений и упорядочивания в быстром тракте. Задача Shreedhar и Varghese состояла в том, чтобы удержать ошибку относительно идеальной байтовой доли в границах, не поддерживая дорогую глобальную сортировку для каждого пакета.

Недостающий остаток не сгорает

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

Главный шаг — не обнулять остаток у всё ещё занятой очереди. В следующем круге к нему прибавится новый квант. Поэтому пакет, который крупнее одного кванта, через несколько кругов накопит достаточно права на передачу. Когда очередь опустела, счётчик сбрасывается: будущий трафик не должен наследовать кредит, накопленный прежним backlog.

Слово «дефицит» здесь не означает долг клиента, штраф или цену перегрузки. Это локальное бухгалтерское состояние — уже выделенный сервис, который нельзя было потратить из-за неделимости головного пакета. Число не имеет самостоятельного договорного смысла. Его можно интерпретировать только вместе с квантом, длиной головного пакета и состоянием очереди.

Пусть две всегда занятые очереди имеют одинаковые кванты. Очередь мелких пакетов за одно посещение отправит несколько штук; очередь крупных в отдельном круге может не отправить ни одного. Короткий снимок выглядит неровно. Но остаток второй очереди накапливается, и на длинном интервале объём отправленных байтов приближается к заданной доле. Разность остаётся связанной с максимальным размером пакета, а не растёт с каждым оборотом без предела.

Quantum — это политика, записанная числом

Равные кванты задают равные целевые доли байтов. Соотношение квантов два к одному при постоянном backlog задаёт примерно такое же соотношение долгосрочного сервиса. Вес не возникает из свойств пакетов. Его выбрал оператор, поэтому quantum нельзя спрятать в приложении к отчёту как малозначительный параметр.

Размер кванта влияет и на гранулярность. Если он мал относительно ожидаемого максимального пакета, крупный пакет ждёт накопления несколько кругов, а активный список обходится чаще. Большой квант позволяет выпустить больше байтов за один визит и способен усилить сервисные всплески. Записи «используется DRR» недостаточно: воспроизводимость требует квантов по очередям, предположений о размерах, правила сброса и версии конфигурации.

Технический отчёт 1994 года и последующая статья Shreedhar и Varghese в SIGCOMM сформулировали цель как почти идеальную справедливость пропускной способности, сложность O(1) и простую аппаратную реализацию. O(1) относится к операциям планирования, а не обещает постоянную цену классификации любого числа потоков, хранения очередей или наблюдения всей сети. Экономия возникает потому, что выбор не требует заново поддерживать глобальную приоритетную последовательность для каждого пакета.

До счётчика кто-то уже провёл границы

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

Внутри одной FIFO счётчик также ничего не разделяет. Большая передача способна задерживать интерактивный поток, если классификатор сложил их вместе. Ошибочная метка может отправить пакеты в привилегированный класс. Неизвестный трафик может попасть в default с неожиданным весом. Планировщик исполняет такие границы, но не проверяет их смысл.

Поэтому фраза «у нас DRR» должна сопровождаться картой: какие поля выбирают очередь; обозначает ли она пользователя, поток, туннель или класс; куда идёт несовпавший трафик; кто установил кванты; когда очередь входит в активный список; как состояние переживает failover и изменение конфигурации. Эти решения определяют население, внутри которого вообще верно слово «справедливость».

Аудит должен связать карту с результатом. Сумма по порту скрывает внутренние доли. Число пакетов повторяет исходную ошибку. Нужны версия классификатора, состав очередей, кванты, интервалы активности, размеры пакетов, выгруженные байты и перенесённые остатки. Иначе точный счётчик лишь аккуратно выполняет неизвестную политику.

Справедливая полоса не назначает срок каждому пакету

Базовый DRR ограничивает долгосрочную разницу сервиса относительно весов, но сам по себе не устанавливает жёсткий предел ожидания отдельного пакета. Очередь ждёт обхода других активных очередей, а пакет — тех, что стоят перед ним внутри собственной FIFO. Задержку меняют число конкурентов, квант, максимальная длина и характер прихода. Исходная работа явно отличает throughput fairness от latency bounds и рассматривает расширения для требований задержки; свойства расширения нельзя приписывать основе.

DRR не определяет темп входящего трафика, сам не выбирает drop или ECN mark и не меняет congestion window отправителя. Shaper управляет поступлением, AQM — сигналами и сбросом в очереди, congestion control — поведением конечного узла, маршрутизация — путём. RFC 7567 обсуждает scheduling рядом с AQM, но как отдельный механизм. Совместное размещение на интерфейсе не объединяет их функции.

Различие важно при расследовании. Если байтовые доли соответствуют весам, а хвост задержки вырос, DRR может быть исправен, а проблема — реальна. Следует изучить backlog, общую FIFO, AQM и другие сегменты пути. Если суммарное предложение постоянно выше пропускной способности, DRR способен предсказуемо поделить нехватку, но не создаёт ёмкость и не устраняет перегрузку.

George Varghese и алгоритмика быстрого тракта

Официальная страница UCLA называет George Varghese Distinguished Professor of Computer Science и Jonathan B. Postel Chair. Среди его направлений — network algorithmics, верификация, кибербезопасность и будущий Интернет. Он получил докторскую степень в MIT, преподавал в Washington University in St. Louis и UC San Diego, работал в Microsoft Research и пришёл в UCLA в 2016 году.

Биография не доказывает границу ошибки, но помогает увидеть метод: найти дорогую операцию в datapath, изменить представление состояния и сделать теоретическую цель исполнимой на скорости линии. ACM SIGCOMM присудила Varghese награду SIGCOMM Award в 2014 году. Internet Hall of Fame, включая его в 2021 году, отдельно отметил изобретение DRR совместно с M. Shreedhar и историческое использование схемы в оборудовании, включая Cisco GSR.

Награда и внедрение свидетельствуют о влиянии; техническое утверждение всё равно опирается на модель и допущения исходной статьи. Разделение важно: премия не заменяет доказательство, но и строгий алгоритм не обязательно остаётся бумажной конструкцией. Малый счётчик оказался достаточно дешёвым для маршрутизатора и достаточно содержательным для ограниченного обещания о справедливости.

Последнее значение не объясняет свою историю

Остаток мог измениться из-за нового кванта, иной длины пакетов, появления активных очередей, реклассификации или временного опустошения. Один snapshot не различит причины. Нужна история нескольких раундов, совмещённая по времени с изменениями конфигурации.

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

Источники