Для справедливой приоритезации доступа планировщика к очередям маршрутизатора был разработан алгоритм GPS (Generalized Processor Sharing) [Parekh93, Parekh94], являющийся модификацией алгогритма PS, рассмотренного ранее. GPS относится к классу планировщиков, «работающих непрерывно», и является идеальной моделью, обеспечивающей в непрерывном времени принцип «справедливого распределния ресурсов» в соответствии с критерием max-min для классов трафика с различными требованиями по качеству обслуживания.

Предположим, что N потоков проходят через некоторый CQS-мар-шрутизатор и разделяют его ресурсы, причем планировщик реализован на базе алгоритма GPS. Пусть для каждого потока выделяется минимальная пропускная способность r_t, т.е. должно выполняться следующее неравенство:

N

1=1

где г - пропускная способность исходящего канала. Пусть также количество потоков равно количеству очередей в рассматриваемом маршрутизаторе. Обозначим через B{t) набор активных, но не обслуживаемых в момент времени t потоков (backlogged flow, далее

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

Алгоритм G PS обладает рядом свойств:

• G PS обеспечивает возможность предоставления гарантий по полосе пропускания для каждого потока (per-flow), причем как для одного, так и для последовательности планировщиков GPS;

• G PS обеспечивает возможность предоставления гарантий по задержкам для потоков, соответствующих Token Bucket (rate,b), причем как для одного, так и для последовательности планировщиков GPS [Keshav97;

• GPS обеспечивает защиту (изоляцию) потоков друг от друга, т.е. поведение одного потока не влияет на гарантии, предоставляемые другим потокам;

• GPS не предоставляет гарантий по джиттеру, т.е. с помощью планировщика GPS невозможно ограничить значение джиттера для потоков, однако возможно оценить, что это значение будет находиться в интервале [О, ], где D_mà}, - максимальная задержка пакета рассматриваемого потока.

Дополнительно для реализации принципа «справедливой буферизации на уровне пакетов» алгоритм G PS для каждого поступающего в маршрутизатор пакета предполагает вычисление значения параметра «время окончания обслуживания» (finished tag). Каждый раз, когда заканчивается обслуживание некоторого пакета, планировщик передает на обслуживание следующий пакет с наименьшим значением параметра «время окончания обслуживания» из некоторой очереди, т.е., другими словами, на обслуживание передается тот пакет, который должен быть обслужен быстрее. Отметим, что анализируются только пакеты, стоящие первыми на обслуживание в каждой из очередей, называемые HOL-пакетами (Head-Of-Line).

Далее рассмотрим принципы распределения процессорного времени на базе алгоритма GPS. Обозначим через A_t{r,t) количество информации потока і, поступившей за интервал времени ]r,f], через - количество обслуживания, полученное потоком / (количество обслуженных бит потока і) за тот же промежуток времени и через Qj(t) - количество трафика потока і находящегося в очереди в момент времени /. Таким образом, можно записать следующее соотношение:

Отметим, что как только в некоторый момент времени система находится в состоянии простоя, т.е. отсутствия нагрузки (idle), все вышеописанные параметры должны быть обнулены. Введем ряд определений:

• «событие» - поступление или уход на обслуживание потока в рамках моделируемого алгоритма GPS (далее будем называть его сервер GPS). Обозначим через t ■ момент времени, когда происходит событие у;

• «период занятости системы» - период времени, в течение которого сервер GPS находится в состоянии обработки нагрузки;

• «бэклог-период» для некоторого потока /' - непрерывный промежуток времени, когда пакеты данного потока буферизируются, но не передаются на обслуживание, т.е. рассматриваемый поток является «бэклог»-потоком;

• «период занятости некоторого потока /» - промежуток времени такой максимальной длины ]^ri»^г2 ], что для любого значения t е]г,,г₂] пакеты потока i поступают со скоростью равной или выше, чем значение т.е. А₍(т ^,t) > r_t{t - т_х).

Рассмотрим на примере, каким образом вычисляется значение параметра «время окончания обслуживания». Для этого предположим, что существует некоторый CQS-маршрутизатор, через который проходит п потоков, причем каждому потоку отводится индивидуальная очередь. Рассмотрим наиболее точную аппроксимацию планировщика, реализованного на базе алгоритма GPS - за каждый цикл планировщик предоставляет возможность передать один бит на обслуживание каждой из п очередей. Таким образом, длина цикла планировшика является переменной и зависит от количества активных очередей где под активной будем подразумевать очередь, в которой на момент обращения планировщика присутствует хотя бы один бит, ожидающий обслуживания.

Далее предположим, что время непрерывно, причем функционирование системы начинается в момент времени I = 0. Обозначим через V{[) количество циклов, пройденных планировщиком к моменту времени т.е. это значение можно выразить как отношение пропускной способности канала г (т.е. скорости обслуживания) к количеству активных очередей:

Таким образом получаем, что функция У(0 является кусочно-непрерывной и изменяет наклон при изменении количества активных очередей. Далее, пусть к-й пакет потока г поступает в пустую очередь в момент времени а_1к, а его длина равна Ь_1к. Учитывая факт, что в каждый момент времени планировщик забирает на обслуживание из очереди всего один бит, очевидно, что обслуживание этого пакета займет Ц_кциклов. Таким образом,- время завершения обслуживания пакета может быть записано следующим образом:

Значение Р._ки есть значение параметра «время окончания обслуживания». С другой стороны, если пакет поступает в непустую очередь, в которой находится один пакет, то при вычислении необходимо учитывать и время обслуживания этого пакета. В результате имеем следующее выражение:

Другими словами, значение параметра времени завершения обслуживания к-го пакета, принадлежащего потоку i при соблюдении принципа «справедливой буферизации», учитывая, что время непрерывно, равно времени t, когда значение V(t) достигает значения F_ik. Следует отметить, что параметр «время окончания обслуживания» в этом случае не обязательно точно равен реальному времени завершения обслуживания пакета, т.к. количество процессорного времени, выделяемое рассматриваемой очереди, зависит от количества активных очередей, которое, в свою очередь, постоянно изменяется.

В качестве примера рассмотрим С5(}-маршрутизатор, в котором в момент времени / = 0 в очереди 1 находится один пакет, длиной в одну условную единицу, а в очереди 2 - также один пакет, по длиной в две условных единицы. Пусть скорость обслуживания данных г равна одной условной единице в секунду. Если рассматривать модель в непрерывном времени, то, изначально каждой очереди будет выделено по 50% процессорного времени. Таким образом, как показано на рис. 2.34, обслуживание очереди 1 будет закончено в момент времени * = 2, а обслуживание очереди 2 будет закончено в момент времени ? = 3, причем после завершения обслуживания очереди 1 все процессорное время будет передано на обслуживание очереди 2. Если же рассмотреть функционирование модели в дискретном времени на уровне пакетов, т.е. реализацию РГО, то расчет параметра «время окончания обслуживания» для пакета из очереди 1 вычисляется следующим образом:

Рис. 2.34. «Справедливая буферизация» для непрерывного и дискретного (РРО) случаев

В связи с тем, что значение параметра «время окончания обслуживания» для пакета из очереди 1 ниже, чем для пакета из очереди 2, то планировщик первым на обслуживание заберет пакет из очереди 1. Принимая во внимание принятую скорость обслуживания, очевидно, что обслуживание пакета из очереди 1 будет закончено в момент времени t = 2, после чего планировщиком на обслуживание будет забран пакет из очереди 2 и его обслуживание будет закончено в момент времени t = 3.

Рассмотрим другой пример, модель которого представлена на рис. 2.35. Отметим, что далее принципы функционирования планировщиков, реализованных на базе различных алгоритмов, будут рассмотрены на этом примере. Главным предположением здесь будет являться фиксированная длина пакетов. Очевидно, что это справедливо для сетей ЛТМ, но не справедливо для сетей на базе протокола IP, поэтому отметим, что это предположение сделано лишь для облегчения понимания прнципов работы алгоритмов планировщиков.

Пусть в некотором CQS-маршрутизаторе планировщик, обслуживающий три очереди с разными приоритетами, реализован с использованием сервера GPS, и пропускная способность исходящего канала г равна единице. Предположим, что в данный маршрутизатор поступает нагрузка трех потоков 1, 2 и 3 (пакеты каждого потока помещаются в отдельную очередь), причем относительные скорости обслуживания этих потоков равны г_х= 1/6, г_г-\!Ъ и = 1/2, соответственно.

В связи с тем, что длина пакета фиксирована, очевидно, что обслуживание пакета занимает некоторый фиксированный интервал времени. Пронормируем этот интервал, т.е. время обслуживания пакета равно единице. Пусть в момент времени t = 0 поток 1 переходит в состояние «периода занятости». Пусть в момент времени t = 1 пакеты потока 2 начинают поступать в соответствующую очередь с такой же скоростью, как и для потока 1. Далее пусть пакеты потока 3 начинают поступать в соответствующую очередь в момент времени t = 3. Предположим, что скорость поступления пакетов всех потоков в соответствующие очереди равна одному пакету в интервал времени, равный единице.

Для рассматриваемого примера сервер GPS должен распределить процессорное время между конкурирующими потоками в соответствии со следующими правилами:

Функции поступления и обслуживания пакетов в очередях для всех потоков представлены на рис. 2.36. Отметим, что значение g,(0 может быть определено как угол наклона функции обслуживания потока i в момент времени /, т.е. W_t(t). Кроме того, в связи с тем, что планировщик GPS относится к классу «работающих непрерывно», соблюдается следующее равенство:

Таким образом, время окончания обслуживания первого пакета потоков 1, 2 и 3 равно 1, 2.5 и 5, соответственно.

Важным параметром функционирования алгоритма планировщика является реализация принципа «справедливого распределения ресурсов». Для некоторого «бэклог»-потока / математически этот принцип может быть определен как отношение количества обслуживания, полученного ПОТОКОМ I , к относительной скорости обслуживания этого потока, т.е. г_:. Таким образом, за интервал времени ]г_рг₂]

для двух любых «бэклог»-потоков / и У можно утверждать, что рассматриваемый планировщик соблюдает принцип «справедливого распределения ресурсов», если выполняется следующее равенство: Щт„т₂)Щт„т₂)

^гI

Поток 3

А,(0Л)

3 4 5

Рис. 2.36. Функции поступления и обслуживания нагрузки в очередях для всех потоков Для планировщика GPS данное выражение справедливо, хотя, следует отметить, что реально реализуемые алгоритмы класса PFQ, рассмотренные ниже, являются аппроксимацией GPS, и не предполагают, что размер обслуживаемого пакета бесконечно мал. Базовой идеей алгоритмов PFQ является реализация глобальной (по отношению к рассматриваемой системе) функции, называемой «виртуальное время поступления» (virtual start time или start potential) [Parekh93,Stiliadis96], при помощи которой осуществляется моделирование планировщика GPS в непрерывном времени на уровне пакетов.

На базе этой функции вычисляется функция окончания обслуживания «виртуальное время окончания обслуживания» (virtual finish time или timestamp) для каждого пакета или для каждого HOL-na-кета каждого активного потока.

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