Модификацией алгоритма RR для пакетов переменной длины является «циклическая очередность с дефицитом времени» (Deficit-Round Robin, далее - DRR) [Shree96]. Принцип функционирования идентичен RR, только в связи с тем, что обслуживаемые пакеты имеют переменную длину, в DRR добавлена функция накопления квантов выделяемого процессорного времени.

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

- таким образом могут быть обслужены пакеты любой длины.

Рассматриваемые ниже механизмы и алгоритмы призваны обеспечивать качество обслуживания посредством предоставления гарантий по задержкам и полосе пропускания для различных классов трафика в домене DiffServ. Поэтому возникает задача, каким образом обеспечить, с одной стороны - справедливый доступ к ресурсам, который должен обеспечивать планировщик, а с другой стороны - «справедливый прием пакетов в очередь» (fair buffer acceptance), потому что именно совместная реализация этих функций позволит гарантировать необходимые для обеспечения качества обслуживания параметры задержки и пропускной способности. Напомним, что существуют различные алгоритмы обеспечения справедливого приема поступающих пакетов в очередь, как правило, становящиеся актуальными в тот момент, когда в очередь, в которой нет свободных мест для ожидания, необходимо поместить новый пакет. Подробно эти алгоритмы будут рассмотрены ниже, а сейчас необходимо уделить внимание алгоритмам функционирования планировщиков.

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

Можно предположить, что это как раз то, что нам необходимо - потоки, принадлежащие различным классам качества обслуживания, должны получать различное количество ресурсов. Это правильно, но отметим, что получение различных по количеству ресурсов также должно быть регламентировано, т.е. все равно должен соблюдаться принцип «справедливого распределения ресурсов», но «справедливость» должна определяться классом качества обслуживания, к которому принадлежит рассматриваемый поток, а не размером пакета. Таким образом, принцип «справедливого распределения ресурсов» должен быть реализован и в том случае, когда на сети реализованы различ ные классы качества обслуживания. Ниже, когда это будет необходимо, мы вернемся к обсуждению этого вопроса, только здесь автор считает необходимым заметить, что на самом деле под различными классами качества обслуживания могут пониматься не только потоки, дифференцированные в домене DiffServ, но и обычный трафик Best Effort, если, например, трафик TCP и UDP помещается в различные очереди с различными приоритетами.

Принцип «справедливого распределения ресурсов» при обслуживании пакетов различной длины, принадлежащих различным классам качества обслуживания, трансформируется в принцип «справедливой буферизации на уровне пакетов» (packet-by-packet fair queuing, далее - PFQ), заключающийся в следующем: каждый пакет, независимо от длины, должен быть передан на обслуживание в соответствии с требованиями по качеству обслуживания того класса, к которому данный пакет принадлежит.

Для обеспечения гарантий по задержкам в данном контексте может быть использован планировщик с приоритетами, реализованный па базе модифицированного алгоритма PS (Priority Processor Sharing, далее - PPS). Идея заключается в том, что каждой из очередей присваивается приоритет, т.е. планировщик выделяет процессорное время для обслуживания нагрузки из некоторой очереди в соответствии с назначенным ей приоритетом. В качестве предельного случая можно рассмотреть пример, когда в некотором CQS-марш-рутизаторе реализовано три очереди А, В и С, в которые поступают пакеты трех потоков с различными приоритетами. Пусть очереди А назначен высший приоритет, а С - низший. Алгоритм функционирования планировщика представлен на рис. 2.33.

При освобождении процессора планировщик проверяет очереди на наличие необслуженной нагрузки в соответствии с их приоритетами. Если очередь А пуста, то планировщик обращается к очереди В, в свою очередь, если В пуста, то планировщик обращается к очереди С. Подобный алгоритм функционирования планировщика имеет такие положительные стороны, как простота реализации и возможность обеспечения низкой задержки для пакетов высокоприоритетного потока, а также и отрицательные, среди которых необходимо отметить отсутствие возможности исключения влияния потоков друг на друга

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

ppp^

152

Компоненты обеспечения качества обслуживания иринести определенные преимущества, но при этом необходимо обеспечить:

• реализацию механизмов контроля количества и интенсивности поступаемой нагрузки: чтобы изменение характера поведения пользовательской нагрузки было обработано должным способом заранее при помощи алгоритмов сглаживания трафика и Leaky/ Token Bucket, и не смогло быть причиной блокировки потоков с более низким приоритетом;

• гибкий алгоритм приоритезации доступа планировщика к очередям маршрутизатора.

Передача пакета на обслуживание планировщиком:

if (queue(А) не пуста) обслуживать queue(А) eise

if (queue(В) не пуста) обслуживать queue(В) eise

if (queue(С) не пуста) обслуживать queue(С)

Рис. 2.33. Метакод алгоритма PSP

⇐Алгоритм round robin | Управление трафиком и качество обслужевания в сети | Алгоритм gps⇒