> 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**.

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLldZ0B77c7MSzkP%2Fimage-150.png?generation=1537171631481681\&alt=media)

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

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

## WRR — Weighted Round Robin

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

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLlg6iDst5SNCILg%2Fimage-106.png?generation=1537171638783959\&alt=media)

## DWRR — Deficit Weighted Round Robin

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

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

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLlitEBndrX1Icix%2Fimage-97.png?generation=1537171637169531\&alt=media)

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

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

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLlk4M3GXclxH3eX%2Fimage-89.png?generation=1537171632361662\&alt=media)

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

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLlmIcNLWpeTjERN%2Fimage-130.png?generation=1537171627890940\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLloyqk10wqQEuxa%2Fimage-111.png?generation=1537171630351074\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLlqwEALw9LT3d0-%2Fimage-82.png?generation=1537171627804122\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLlsa5KvwChTh--h%2Fimage-21.png?generation=1537171634091655\&alt=media)

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

* Очередь 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 байтов.

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLluTK2JhKSrqz4R%2Fimage-80.png?generation=1537171626720921\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLlwiVg3k_sLEwrl%2Fimage-7.png?generation=1537171632246993\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLly44cq9PORv49_%2Fimage-69.png?generation=1537171638897178\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLm-2-Ry5ljBmAA6%2Fimage-123.png?generation=1537171635771550\&alt=media)

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

* Очередь 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 байтов.

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLm24jdR_Hmx04M4%2Fimage-107.png?generation=1537171638210141\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLm4WqtENwMJREK5%2Fimage-131.png?generation=1537171637119624\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLm6Ts7LH1ShgzIk%2Fimage-6.png?generation=1537171635205634\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLm8lqpJ5cyZ_bJa%2Fimage-135.png?generation=1537171627284673\&alt=media)

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

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

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLmAU5T3Ohrm7Ynl%2Fimage-32.png?generation=1537171626947938\&alt=media)

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLmCkjpmQ791LznO%2Fimage-88.png?generation=1537171630938730\&alt=media)

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

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

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

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

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

## PB-DWRR — Priority-Based DWRR

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

![](https://3903873742-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIgRTPaaN7wUujKIWEz%2F-LMaZAd3eKxVTz6opO3a%2F-LMaZLmFbX89S8FtnRBE%2Fimage-9.png?generation=1537171638201241\&alt=media)

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

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