Существует два основных класса планировщиков. Рассмотрим, чем ' они друг от друга отличаются и какими характеристиками обладают:

• «работающие непрерывно» (work-conserving scheduler): планировщик такого класса всегда, если центральный процессор не загружен и если в хотя бы в одной очереди существует хотя бы один пакет, передаст этот пакет на обслуживание. Другими словами, если существует нагрузка и свободное процессорное время

- она обслуживается. На практике этот класс планировщиков реализуем и на базе этого класса строятся все рассмотренные ниже реальные алгоритмы;

• «работающие с паузами» (non-work-conserving scheduler): планировщик такого класса не всегда, даже если центральный процессор не загружен и если хотя бы в одной очереди существует хотя бы один пакет, передаст этот пакет на обслуживание. Другими словами, если существует нагрузка и свободное процессорное время, то планировщик не всегда осуществляет передачу нагрузки на обслуживание. Преимуществом такого класса планировщиков является возможность обеспечения ограниченного сверху значения джиттера для пакетов некоторого потока. Отметим, что в чистом виде этот класс планировщиков на практике не реализуем.

Принимая во внимание ранее рассмотренную стратегию CQS и тот факт, что маршрутизатор с традиционной архитектурой не способен обеспечивать качество обслуживания, под рассматриваемым далее, будем подразумевать CQS-маршрутизатор. Каждый CQS-маршрути-затор, по сравнению с традиционным, имеет дополнительную функцию - реализацию планировщика распределения процессорного времени. Задачей планировщика является определение, из какой очереди очередной пакет будет отправлен на обслуживание. Поэтому, именно за счет планировщика решается задача разделения полосы пропускания исходящего канала в соответствии с заданными параметрами по качеству обслуживания, т.е., например, очереди, в которой находятся высокоприоритетные пакеты, планировщик отдает больше процессорного времени, чем очереди, содержащей низкоприоритетные пакеты. Таким образом, планировщик для определенного класса обслуживания имеет возможность обеспечить минимальную доступную полосу пропускания. Следовательно, при правильной реализации планировщиков во всех маршрутизаторах в маршруте некоторого потока, возможно обеспечение для него ограниченного сверху значения задержки пакетов. Например, для трафика типа Best Effort, проходящего через CQS-маршрутизатор, задача планировщика (класса «работающий непрерывно») может быть сформулирована как обеспечение следующего равенства в некоторый момент функционирования t для некоторой очереди queue[j]:

Отметим, что в данном случае предполагается, что время непрерывно. Такой алгоритм функционирования планировщика называется «разделение времени процессора» (Processor Sharing, далее - PS). Этот алгоритм способен обеспечить принцип «справедливого распределения ресурсов» в соответствии с критерием max-min, причем независимо от механизмов управления перегрузкой, реализованных в рассматриваемом маршрутизаторе, и независимо от поведения источников. Таким образом, путем реализации в маршрутизаторе только лишь алгоритма PS может быть обеспечен принцип «справедливого распределения ресурсов». Однако, важнейшим недостатком алгоритма PS является невозможность его практической реализации, т.к. в реальном маршрутизаторе возможно реализовать только лишь его аппроксимацию. Этот факт объясняется достаточно просто - реальные системы являются дискретными, в то время как модель алгоритма PS строится в непрерывном времени.

Для понимания различия непрерывного идеального алгоритма PS от его аппроксимации, реализуемой на практике, рассмотрим следующий пример. Предположим, что существует некоторый CQS-марш-рутизатор, на входе которого пакеты постоянной длины классифицируются и помещаются в две различных очереди в зависимости от приоритета. Пусть, как показано на рис. 2.32, обе очереди содержат по одному пакету длиной L бит, т.е. в некоторый момент ? = 0, когда освобождается процессорное время, обе очереди могут передать свой пакет на обслуживание. Также предположим, что скорость обслуживания данных С равна одному пакету в секунду. Таким образом, в идеальной модели алгоритма Р5 с непрерывным временем каждый пакет будет обслуживаться со скоростью 1/2 пакета в секунду и передача обоих пакетов займет 2 секунды, при этом каждый пакет (т.е. очередь) получит по 50% процессорного времени. Если же рассматривать аппроксимацию, то очевидно, что необходимо сначала полностью обслужить один пакет, и только после этого - второй. Таким образом, получаем, что первый пакет, независимо от того, в которой из очередей он находился, будет обслужен через одну секунду, а второй пакет - через 2 секунды, соответственно. Рассмотренный пример проиллюстрирован на рис. 2.32, где показаны функции обслуживания пакетов для непрерывного и дискретного случаев.

2

Рис. 2.32. Алгоритм РБ и его аппроксимация (для пакетов одинаковой длины)

⇐Планирование обслуживания пакетов | Управление трафиком и качество обслужевания в сети | Сглаживание профиля трафика на базе планировщика⇒