# 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, любой пришедший в приоритетную очередь пакет изымается сразу. В других, обращение к ней происходит каждый раз при переходе диспетчера между очередями. В третьих и для неё вводится кредит и квант, чтобы приоритетная очередь не могла отжать всю полосу.

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://linkmeup.gitbook.io/sdsm/15.-qos/6.-upravlenie-peregruzkami-congestion-management/3-rr-round-robin.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.