Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм планирования для сетевого планировщика Deficit Round Robin (DRR), также Deficit Weighted Round Robin (DWRR), — это алгоритм планирования для сетевого планировщика. DRR, как и взвешенная справедливая очередь (WFQ), представляет собой реализацию на основе пакетов идеальной политики обобщенного разделения процессорного времени (GPS). Он был предложен М. Шредхаром и Г. Варгезом в 1995 году как эффективный (со сложностью O(1)) и справедливый алгоритм.
Scheduling algorithm for the network scheduler
Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet based implementation of the ideal Generalized Processor Sharing (GPS) policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with O(1) complexity) and fair algorithm.
Подробности
В DRR планировщик, обрабатывающий N потоков, конфигурируется с одним квантом для каждого потока. Основная идея заключается в том, что в каждом раунде поток может отправить не более байт, а остаток, если он есть, переносится на следующий раунд. Таким образом, минимальная скорость, которую поток достигнет в долгосрочной перспективе, составляет ; где – скорость канала.
In DRR, a scheduler handling N flows is configured with one quantum for each flow. This global idea is that, at each round, the flow can send at most bytes, and the remaining, if any, is reported to the next round. In this way, the minimum rate that flow will achieve over a long term is ; where is the link rate.
Производительность: справедливость, сложность и задержка
Как и другие алгоритмы планирования, подобные GPS, выбор весов остается за администратором сети. Как и WFQ, DRR обеспечивает минимальную скорость для каждого потока, независимо от размера пакетов. В взвешенном циклическом планировании доля используемой полосы пропускания зависит от размера пакетов. По сравнению с планировщиком WFQ, имеющим сложность O(log(n)) (где n – количество активных потоков/очередей), сложность DRR составляет O(1), если квант больше максимального размера пакета для данного потока. Однако эта эффективность достигается ценой: задержка, то есть отклонение от идеального GPS, в DRR больше, чем в WFQ. Более подробную информацию о максимальных задержках можно найти здесь.
Like other GPS like scheduling algorithm, the choice of the weights is left to the network administrator. Like WFQ, DRR offers a minimal rate to each flow whatever the size of the packets is. In weighted round robin scheduling, the fraction of bandwidth used depend on the packet's sizes. Compared with WFQ scheduler that has complexity of O(log(n)) (n is the number of active flows/queues), the complexity of DRR is O(1), if the quantum is larger than the maximum packet size of this flow. Nevertheless, this efficiency has a cost: the latency, i. e., the distance to the ideal GPS, is larger in DRR than in WFQ. More on the worst case latencies can be found here.
Реализация
Реализация алгоритма дефицитного круглого робина была написана Патриком МакХарди для ядра Linux и опубликована под лицензией GNU General Public License. В маршрутизаторах Cisco и Juniper реализованы модифицированные версии DRR: поскольку задержка алгоритма DRR может быть выше для определенных классов трафика, эти модифицированные версии предоставляют более высокий приоритет некоторым очередям, а остальные обслуживаются стандартным алгоритмом DRR.
An implementation of the deficit round robin algorithm was written by Patrick McHardy for the Linux kernel and published under the GNU General Public License. In Cisco and Juniper routers, modified versions of DRR are implemented: since the latency of DRR can be larger for some class of traffic, these modified versions give higher priority to some queues, whereas the others are served with the standard DRR algorithm.