> For the complete documentation index, see [llms.txt](https://linkmeup.gitbook.io/sdsm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://linkmeup.gitbook.io/sdsm/15.-qos/6.-upravlenie-peregruzkami-congestion-management/3-rr-round-robin.md).

# RR — Round-Robin

## RR - Round Robin

Рука об руку с FQ шёл и **RR**.

Один был честен, но не прост. Другой совсем наоборот.

![](/files/-LMaZLldZ0B77c7MSzkP)

RR перебирал очереди, извлекая из них равное число пакетов. Подход более примитивный, чем FQ, и оттого нечестный по отношению к различным потокам. Агрессивные источники легко могли затопить полосу пакетами размером в 1500 байтов.

Однако он очень просто реализовывался — не нужно знать размер пакета в очереди, фрагментировать его и собирать потом обратно.\
Однако его несправедливость в распределении полосы перекрыла ему путь в мир — в мире сетей чистый Round-Robin не был реализован.

## WRR — Weighted Round Robin

Та же судьба и у WRR, который придавал очередям вес на основе IP Precedence. В WRR вынималось не равное число пакетов, а кратное весу очереди.

Можно было бы давать больший вес очередям с более мелкими пакетами, но делать это динамически не представлялось возможным.

![](/files/-LMaZLlg6iDst5SNCILg)

## DWRR — Deficit Weighted Round Robin

И вдруг, крайне любопытный подход в 1995-м году предложили M. Shreedhar and G. Varghese.

Каждая очередь имеет отдельную **кредитную линию** в битах.\
При проходе из очереди выпускается столько пакетов, на сколько хватает кредита.\
Из суммы кредита вычитается размер того пакета, что в голове очереди.\
Если разность больше нуля, этот пакет изымается, и проверяется следующий. Так до тех пор, пока разность не окажется меньше нуля.\
Если даже первому пакету не хватает кредита, что ж, увы-селявы, он остаётся в очереди.\
Перед следующим проходом кредит каждой очереди увеличивается на определённую сумму, называемую **квант**.\
Для разных очередей квант разный — чем большую полосу нужно дать, тем больше квант.

Таким образом все очереди получают гарантированную полосу, независимо от размера пакетов в ней.

![](/files/-LMaZLlitEBndrX1Icix)

Мне бы из объяснения выше не было понятно, как это работает.

### **Давайте по шагам разрисуем**

* DRR (без W),
* 4 очереди,
* в 0-й все пакеты по 500 байтов,
* В 1-й — по 1000,
* Во 2-й по 1500,
* А в 3-й лежит одна колбаса на 4000,
* Квант — 1600 байтов.

![](/files/-LMaZLlk4M3GXclxH3eX)

#### **Цикл 1**

**Цикл 1. Очередь 0**\
Начинается первый цикл, каждой очереди выделяется по 1600 байтов (квант)\
Обработка начинается с 0-й очереди. Диспетчер считает:\
Первый пакет в очереди проходит — Пропускаем (1600 — 500 = 1100).\
Второй — проходит — пропускаем (1100 — 500 = 600).\
Третий — проходит — пропускаем (600 — 500 = 100).\
Четвёртый — уже не проходит (100 — 500 = -400). Переходим к следующей очереди.\
Финальный кредит — 100 байтов.

![](/files/-LMaZLlmIcNLWpeTjERN)

**Цикл 1. Очередь 1**\
Первый пакет проходит — пропускаем (1600 — 1000 = 600).\
Второй не проходит (600 — 1000 = -400). Переходим к следующей очереди.\
Финальный кредит — 600 байтов.

![](/files/-LMaZLloyqk10wqQEuxa)

**Цикл 1. Очередь 2**\
Первый пакет проходит — пропускаем (1600 — 1500 = 100).\
Второй не проходит (100 — 1000 = -900). Переходим к следующей очереди.\
Финальный кредит — 100 байтов.

![](/files/-LMaZLlqwEALw9LT3d0-)

**Цикл 1. Очередь 3**\
Первый пакет уже не проходит. (1600 — 4000 = -2400).\
Переходим к следующей очереди.\
Финальный кредит — те же 1600 байтов.

![](/files/-LMaZLlsa5KvwChTh--h)

Итак, по окончании первого цикла работы диспетчера пропустили:

* Очередь 0 — 1500
* Очередь 1 — 1000
* Очередь 2 — 1500
* Очередь 3 — 0

  Имеющийся кредит:
* Очередь 0 — 100
* Очередь 1 — 600
* Очередь 2 — 100
* Очередь 3 — 1600

#### **Цикл 2**

В начале цикла к кредиту очереди прибавляется заданный квант — то есть 1600 байтов.

**Цикл 2. Очередь 0**\
Кредит увеличивается до 1700 (100 + 1600).\
Первые три пакета в очереди проходят — пропускаем их (1700 — 3\*500 = 200).\
Четвёртому уже не хватает кредита.\
Финальный кредит — 200 байтов.

![](/files/-LMaZLluTK2JhKSrqz4R)

**Цикл 2. Очередь 1**\
Кредит увеличивается до 2200 (600 + 1600).\
Первые два пакета в очереди проходят — пропускаем их (2200 — 2\*1000 = 200).\
Третий уже не проходит.\
Финальный кредит — 200 байтов.

![](/files/-LMaZLlwiVg3k_sLEwrl)

**Цикл 2. Очередь 2**\
Кредит увеличивается до 1700 (100 + 1600).\
Первый пакет в очереди проходит — пропускаем его (2200 — 1500 = 200).\
А второй — уже нет.\
Финальный кредит — 200 байтов.

![](/files/-LMaZLly44cq9PORv49_)

**Цикл 2. Очередь 3**\
Кредит увеличивается до 3200 (1600 + 1600).\
Но она всё равно в пролёте (3200 — 4000 = -800)\
Финальный кредит — 3200 байтов.

![](/files/-LMaZLm-2-Ry5ljBmAA6)

Итак, по окончании второго цикла работы диспетчера пропустили:

* Очередь 0 — 3000
* Очередь 1 — 3000
* Очередь 2 — 3000
* Очередь 3 — 0

  Имеющийся кредит:
* Очередь 0 — 200
* Очередь 1 — 200
* Очередь 2 — 200
* Очередь 3 — 3200

#### **Цикл 3**

В начале каждого цикла к кредиту очереди прибавляется квант — 1600 байтов.

**Цикл 3. Очередь 0**\
Кредит увеличивается до 1800 (200 + 1600).\
И снова три пакета в очереди проходят — пропускаем их (1800 — 3\*500 = 300).\
Четвёртому опять не хватает кредита.\
Финальный кредит — 300 байтов.

![](/files/-LMaZLm24jdR_Hmx04M4)

**Цикл 3. Очередь 1**\
Кредит увеличивается до 1800 (200 + 1600).\
Один пакет проходит — пропускаем (1800 — 1000 = 800).\
Финальный кредит — 800 байтов.

![](/files/-LMaZLm4WqtENwMJREK5)

**Цикл 3. Очередь 2**\
Кредит увеличивается до 1800 (200 + 1600).\
Один пакет проходит — пропускаем (1800 — 1500 = 300).\
Финальный кредит — 300 байтов.

![](/files/-LMaZLm6Ts7LH1ShgzIk)

**Цикл 3. Очередь 3**\
Будет и в 3-й очереди праздник!\
Кредит увеличивается до 4800 (3200 + 1600).\
Пакет наконец проходит — пропускаем (4800 — 4000 = 800).\
Финальный кредит — 800 байтов.

![](/files/-LMaZLm8lqpJ5cyZ_bJa)

Итак, по окончании третьего цикла работы диспетчера пропустили:

* Очередь 0 — 4500
* Очередь 1 — 4000
* Очередь 2 — 4500
* Очередь 3 — 4000

  Имеющийся кредит:
* Очередь 0 — 300
* Очередь 1 — 800
* Очередь 2 — 300
* Очередь 3 — 800

![](/files/-LMaZLmAU5T3Ohrm7Ynl)

Достаточно наглядна здесь работа DRR. В масштабах многих итераций все очереди получат причитающуюся часть полосы.\
Если кому не лень, смотрите анимации.

![](/files/-LMaZLmCkjpmQ791LznO)

Отличие DWRR от DRR только в том, что в начале цикла каждой очереди выделяется квант, полагающийся именно ей, а не одинаковый для всех.

Выше был описан подход DRR, в котором очереди нельзя уходить в минус — если кредитов не хватает, пакет не пропускается.

Однако есть и более либеральный: пакеты пропускаются, пока очередь не в минусе. В следующий раз пакет пройдёт как только кредит окажется опять положительным.

С DWRR всё же остаётся вопрос с гарантией задержек и джиттера — вес его никак не решает.

Теоретически, здесь можно поступить как и с CB-WFQ, добавив LLQ.\
Однако это лишь один из возможных сценариев набирающего сегодня популярность

## PB-DWRR — Priority-Based DWRR

Собственно практически мейнстримом сегодня становится PB-DWRR — Priority Based Deficit Weighted Round Robin.\
Это тот же старый злой DWRR, в который добавлена ещё одна очередь — приоритетная, пакеты в которой обрабатываются с более высоким приоритетом. Это не значит, что ей отдаётся бóльшая полоса, но то, что оттуда пакеты будут забираться чаще.

![](/files/-LMaZLmFbX89S8FtnRBE)

Существует несколько подходов к реализации PB-DWRR. В одних из них, как в PQ, любой пришедший в приоритетную очередь пакет изымается сразу. В других, обращение к ней происходит каждый раз при переходе диспетчера между очередями. В третьих и для неё вводится кредит и квант, чтобы приоритетная очередь не могла отжать всю полосу.

Разбирать мы их, конечно, не будем.