Управление перегрузками

Главная Назад

Когда всё плохо, приоритет обработки следует отдать более важному трафику. Важность каждого пакета определяется на этапе классификации.

Но что такое плохо? Необязательно все буферы должны быть забиты, чтобы приложения начали испытывать проблемы. Самый простой пример — голосовые пакетики, которые толпятся за большими пачками крупных пакетов приложения, скачивающего файл. Это увеличит задержку, испортит джиттер и, возможно, вызовет отбрасывания. То есть мы имеем проблемы с обеспечением качественных услуг при фактическом отсутствии перегрузок. Эту проблему призван решить механизм управления перегрузками (Congestion Management). Трафик разных приложений разделяется по очередям, как мы уже видели выше. Вот только в результате всё снова должно слиться в один интерфейс. Сериализация всё равно происходит последовательно. Каким же образом разным очередям удаётся предоставлять различный уровень сервисов? По-разному изымать пакеты из разных очередей. Занимается этим диспетчер (schedler).

Мы рассмотрим большинство существующих сегодня диспетчеров, начиная с самого простого:

• FIFO — только одна очередь, все в BE, С — несправедливость.
• PQ — дорогу олигархам, холопы уступают.
• FQ — все равны.
• RR - все равны только на бумаге
• WFQ, DWRR — все равны, но некоторые ровнее.

FIFO — First In, First Out.

Простейший случай, по сути отсутствие QoS, — весь трафик обрабатывается одинаково — в одной очереди.

Пакеты уходят из очереди ровно в том порядке, в котором они туда попали, отсюда и название: первым вошёл — первым и вышел.

FIFO не является ни диспетчером в полном смысле этого слова, ни вообще механизмом DiffServ, поскольку фактически никак классы не разделяет.

Если очередь начинает заполняться, задержки и джиттер начинают расти, управлять ими нельзя, потому что нельзя выдернуть важный пакет из середины очереди.

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

В FIFO все классы сливаются в CS0.

Однако несмотря на все эти недостатки именно так работает сейчас Интернет.

У большинства вендоров FIFO и сейчас является диспетчером по умолчанию с одной очередью для всего транзитного трафика и ещё одной для локально-сгенерированных служебных пакетов. Это просто, это крайне дёшево. Если каналы широкие, а трафика мало — всё отлично. Квинтэссенция мысли о том, что QoS — для бедных — расширяй полосу, и заказчики будут довольны, а зарплата твоя будет расти кратно.

Только так когда-то и работало сетевое оборудование.

Но очень скоро мир столкнулся с тем, что так просто не получится. С тенденцией в сторону конвергентных сетей стало понятно, что у разных типов трафика (служебные, голосовые, мультимедиа, интернет-сёрфинг, файлообмен) принципиально разные требования к сети.

FIFO стало недостаточно, поэтому создали несколько очередей и начали плодить схемы диспетчеризации трафика.

Однако FIFO никогда не уходит из нашей жизни: внутри каждой из очередей пакеты всегда обрабатываются по принципу FIFO.

PQ — Priority Queuing.

Второй по сложности механизм и попытка разделить сервис по классам — приоритетная очередь.

Трафик теперь раскладывается в несколько очередей согласно своему классу — приоритету (например, хотя не обязательно, те же BE, AF1-4, EF, CS6-7). Диспетчер перебирает одну очередь за другой.

Сначала он пропускает все пакеты из самой приоритетной очереди, потом из менее, потом из менее. И так по кругу.

Диспетчер не начинает изымать пакеты низкого приоритета, пока не пуста высокоприоритетная очередь.

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

PQ работает почти так же в лоб, как FIFO.

Он отлично подходит для таких видов трафика, как протокольные пакеты и голос, где задержки имеют критическое значение, а общий объём не очень большой. Ну, согласитесь, не стоит придерживать BFD Hello из-за того, что пришли несколько больших видео-чанков с ютуба? Но тут и кроется недостаток PQ — если приоритетная очередь нагружена трафиком, диспетчер вообще никогда не переключится на другие. И если какой-то Доктор ЗЛО в поисках методов завоевания мира решит помечать весь свой злодейский трафик наивысшей чёрной меткой, все другие будут покорно ждать, а потом отбрасываться. О гарантированной полосе для каждой очереди говорить тоже не приходится. Высокоприоритетные очереди можно прирезать по скорости обрабатываемого в них трафика. Тогда другие не будут голодать. Однако контролировать это непросто.

Следующие механизмы ходят по всем очередям по очереди, забирая из них некое количество данных, тем самым предоставляя более честные условия. Но делают они это по-разному.

FQ - Fair Queuing.

Следующий претендент на роль идеального диспетчера — механизмы честных очередей.

FQ — Fair Queuing.

История его началась в 1985, когда Джон Нейгл предложил создавать очередь на каждый поток данных. По духу это близко к подходу IntServ и это легко объяснимо тем, что идеи классов сервиса, как и DiffServ тогда ещё не было. Честность заключается в том, что диспетчер оперирует числом не пакетов, а числом битов, которые можно передать из каждой очереди.

Так агрессивный TCP-поток не может затопить интерфейс, и все получают равные возможности.

В теории. FQ так и не был реализован на практике как механизм диспетчеризации очередей в сетевом оборудовании.

Недостатка тут три:

1. Первый - очевидный - это очень дорого - заводить очередь под каждый поток, считать вес каждого пакета и всегда беспокоиться о пропускаемых битах и размере пакета.
2. Второй — менее очевидный — все потоки получают равные возможности в плане пропускной способности. А если я хочу неравные?
3. Третий — неочевидный — честность FQ абсолютная: задержки у всех тоже равные, но есть потоки которым задержка важнее, чем полоса. Например, среди 256 потоков присутствуют голосовые, это значит, что до каждого из них дело будет доходить только раз из 256-и. И что делать с ними непонятно.

Здесь вы можете видеть, что из-за большого размера пакета в 3-ей очереди, в первые два цикла обработали по одному пакету из первых двух. Описание механизмов bit-by-bit Round Robin и GPS уже за пределами это статьи, и я отсылаю читателя к самостоятельному изучению.

WFQ — Weighted Fair Queuing.

Второй и отчасти третий недостатки FQ попытался закрыть WFQ, обнародованный в 1989 году. Каждая очередь наделялась весом и соответственно правом за один цикл отдавать трафика кратно весу.

Вес высчитывался на основе двух параметров: ещё актуальном тогда IP Precedence и длине пакета.

В контексте WFQ чем больше вес, тем хуже.

Поэтому чем выше IP Precedence, тем меньше вес пакета.

Чем меньше размер пакета, тем меньше и его вес.

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

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

Про суровую машинерию WFQ, с её packet finish time, виртуальным временем и Теоремой Парика можно почитать в любопытном цветном документе.

Впрочем первую и третью проблемы это никак не решало. Flow Based подход был так же неудобен, а потоки, нуждающиеся в коротких задержках и стабильных джиттерах, их не получали.

Это, впрочем, не помешало WFQ найти применение в некоторых (преимущественно старых) устройствах Cisco. Там имелось до 256 очередей, в которые потоки помещались на основе хэша от своих заголовков. Этакий компромисс между Flow-Based парадигмой и ограниченными ресурсами.

CBWFQ — Class-Based WFQ.

Заход на проблему сложности сделал CBWFQ с приходом DiffServ. Behavior Aggregate классифицировал все категории трафика в 8 классов и, соответственно, очередей. Это дало ему имя и значительно упростило обслуживание очередей.

Weight в CBWFQ приобрел уже другой смысл. Вес назначался классам (не потокам) вручную в конфигурации по желанию администратора, потому что поле DSCP уже использовалось для классификации.

То есть DSCP определял в какую очередь помещать, а настроенный вес — сколько полосы доступно данной очереди.

Самое главное, что это косвенно немного облегчило жизнь и low-latency потокам, которые теперь были агрегированы в одну (две-три-…) очереди и получали свой звёздный час заметно чаще. Жить стало лучше, но ещё не хорошо — гарантий никаких так и нет — в целом в WFQ все по-прежнему равны в плане задержек. Да и необходимость постоянного слежения за размером пакетов, их фрагментации и дефрагментации, никуда не делась.

CBWFQ+LLQ — Low-Latency Queue.

Последний заход, кульминация бит-по-биту подхода, — это объединение CBWFQ с PQ.

Одна из очередей становится так называемой LLQ (очередь с низкими задержками), и в то время, пока все остальные очереди обрабатываются диспетчером CBWFQ, между LLQ и остальными работает диспетчер PQ. То есть пока в LLQ есть пакеты, остальные очереди ждут, растят свои задержки. Как только пакеты в LLQ кончились — пошли обрабатывать остальные. Появились пакеты в LLQ — про остальные забыли, вернулись к нему. Внутри LLQ работает также FIFO, поэтому не стоит туда пихать всё, что ни попадя, увеличивая утилизацию буфера и заодно задержки. И всё-таки чтобы неприоритетные очереди не голодали, в LLQ стоит ставить ограничение по полосе.

Вот так и овцы сыты и волки целы.

RR — Round-Robin.

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

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

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

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

WRR — Weighted Round Robin.

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

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

DWRR — Deficit Weighted Round Robin.

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

Каждая очередь имеет отдельную кредитную линию в битах.

При проходе из очереди выпускается столько пакетов, на сколько хватает кредита.

Из суммы кредита вычитается размер того пакета, что в голове очереди.

Если разность больше нуля, этот пакет изымается, и проверяется следующий. Так до тех пор, пока разность не окажется меньше нуля.

Если даже первому пакету не хватает кредита, что ж, увы-селявы, он остаётся в очереди.

Перед следующим проходом кредит каждой очереди увеличивается на определённую сумму, называемую квант.

Для разных очередей квант разный — чем большую полосу нужно дать, тем больше квант.

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

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

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

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

Цикл 1

Цикл 1. Очередь 0

Начинается первый цикл, каждой очереди выделяется по 1600 байтов (квант)

Обработка начинается с 0-й очереди. Диспетчер считает:

Первый пакет в очереди проходит — Пропускаем (1600 — 500 = 1100).

Второй — проходит — пропускаем (1100 — 500 = 600).

Третий — проходит — пропускаем (600 — 500 = 100).

Четвёртый — уже не проходит (100 — 500 = -400). Переходим к следующей очереди.

Финальный кредит — 100 байтов.

Цикл 1. Очередь 1

Первый пакет проходит — пропускаем (1600 — 1000 = 600).

Второй не проходит (600 — 1000 = -400). Переходим к следующей очереди.

Финальный кредит — 600 байтов.

Цикл 1. Очередь 2

Первый пакет проходит — пропускаем (1600 — 1500 = 100).

Второй не проходит (100 — 1000 = -900). Переходим к следующей очереди.

Финальный кредит — 100 байтов.

Цикл 1. Очередь 3

Первый пакет уже не проходит. (1600 — 4000 = -2400).

Переходим к следующей очереди.

Финальный кредит — те же 1600 байтов.

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

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

Цикл 2. Очередь 1

Кредит увеличивается до 2200 (600 + 1600).

Первые два пакета в очереди проходят — пропускаем их (2200 — 2*1000 = 200).

Третий уже не проходит.

Финальный кредит — 200 байтов.

Цикл 2. Очередь 2

Кредит увеличивается до 1700 (100 + 1600).

Первый пакет в очереди проходит — пропускаем его (2200 — 1500 = 200).

А второй — уже нет.

Финальный кредит — 200 байтов.

Цикл 2. Очередь 3

Кредит увеличивается до 3200 (1600 + 1600).

Но она всё равно в пролёте (3200 — 4000 = -800)

Финальный кредит — 3200 байтов.

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

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

Цикл 3. Очередь 1

Кредит увеличивается до 1800 (200 + 1600).

Один пакет проходит — пропускаем (1800 — 1000 = 800).

Финальный кредит — 800 байтов.

Цикл 3. Очередь 2

Кредит увеличивается до 1800 (200 + 1600).

Один пакет проходит — пропускаем (1800 — 1500 = 300).

Финальный кредит — 300 байтов.

Цикл 3. Очередь 3

Будет и в 3-й очереди праздник!

Кредит увеличивается до 4800 (3200 + 1600).

Пакет наконец проходит — пропускаем (4800 — 4000 = 800).

Финальный кредит — 800 байтов.

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

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

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

Если кому не лень, смотрите анимации.

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

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

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

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

Теоретически, здесь можно поступить как и с CB-WFQ, добавив LLQ.

Однако это лишь один из возможных сценариев набирающего сегодня популярность

PB-DWRR — Priority-Based DWRR.

Собственно практически мейнстримом сегодня становится PB-DWRR — Priority Based Deficit Weighted Round Robin.

Это тот же старый злой DWRR, в который добавлена ещё одна очередь — приоритетная, пакеты в которой обрабатываются с более высоким приоритетом. Это не значит, что ей отдаётся бóльшая полоса, но то, что оттуда пакеты будут забираться чаще.

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

Короткий итог про механизмы диспетчеризации.

Десятилетиями человечество пыталось решить сложнейшую проблему обеспечения нужного уровня сервиса и честного распределения полосы. Основным инструментом являлись очереди, вопрос был только в том, как из очередей забирать пакеты, пытаясь их запихнуть в один интерфейс.

Начиная с FIFO, оно изобрело PQ — голос смог сосуществовать с сёрфингом, но не было речи про гарантию полосы.

Появились несколько монструозные FQ, WFQ, работавшие если не per-flow, то почти так. CB-WFQ пришёл к классовому обществу, но не стал от этого проще.

Как альтернатива ему развивался RR. Он превратился в WRR, а затем и в DWRR.

И в глубине каждого из диспетчеров живёт FIFO.

Однако, как видите, нет некоего универсального диспетчера, который все классы обрабатывал так, как они того требуют. Это всегда комбинация диспетчеров, один из которых решает задачу обеспечения задержек, джиттера и отсутствия потерь, а другой распределения полосы.

CBWFQ+LLQ или PB-WDRR или WDRR+PQ.

На реальном оборудовании можно указать какие именно очереди каким диспетчером обрабатывать.

CBWFQ, WDRR и их производные — это сегодняшние фавориты.

PQ, FQ, WFQ, RR, WRR — не скорбим и не помним (если, конечно, не готовимся к CCIE © Клиппер).

Итак, гарантировать скорость диспетчеры умеют, но как же ограничить её сверху?

Главная Назад