Циклический рост дефицита
-
Основы циклического анализа дефицита (DRR)
- DRR — это алгоритм планирования для сетевого планировщика, предложенный в 1995 году.
- Он представляет собой пакетную реализацию идеальной политики общего доступа к процессорам (GPS) и имеет сложность O(1).
-
Принцип работы DRR
- Каждый поток может отправить не более своего квантового значения Qi байт, а оставшаяся информация передается на следующий раунд.
- Минимальная скорость потока позволяет достичь в долгосрочной перспективе скорости, равной Qi/(Q1 + Q2 + … + QN)R, где R — скорость соединения.
-
Алгоритм DRR
- Программа DRR последовательно сканирует очереди, увеличивая счетчик дефицита на квантовое значение при выборе параметра.
- Если счетчик дефицита превышает размер пакета в начале очереди, пакет может быть отправлен.
- Очередь считается пустой, когда счетчик дефицита достигает нуля.
-
Производительность DRR
- DRR обеспечивает минимальную скорость для каждого потока независимо от размера пакетов.
- Сложность DRR равна O(1), если квантовое значение больше максимального размера пакета потока.
- Задержка DRR больше, чем у WFQ, но задержка в худшем случае может быть уменьшена путем модификации алгоритма.
-
Реализации и модификации
- Патрик Макхарди написал реализацию DRR для ядра Linux с лицензией GNU GPL.
- Cisco и Juniper модифицировали DRR для повышения приоритета некоторых очередей над другими.
-
Дополнительные ресурсы
- Ссылки на лекции и внешние ресурсы по теме справедливых очередей и DRR предоставлены в статье.
Полный текст статьи: