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 стоит ставить ограничение по полосе.

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