Алгоритм GPS в реальном оборудовании реализовать невозможно, однако в рамках маршрутизатора можно моделировать сервер GPS в непрерывном времени на уровне пакетов (per-packet) и передавать на обслуживание пакет, функция «виртуальное время окончания обслуживания» которого была вычислена при помощи алгоритма GPS в непрерывном времени.

Именно таким образом строится достаточно точная аппроксимация планировщика GPS, называемая «взвешенная справедливая буферизация» (Weighed Fair Queuing, далее - WFQ). Отметим, что зачастую в документации к сетевому оборудованию можно увидеть информацию о том, что алгоритм WFQ реализован, однако это вовсе не говорит о том, что это именно рассматриваемый ниже алгоритм, скорее всего реализован более простой планировщик.

Этот факт объясняется тем, что достаточно часто под WFQ понимается целый класс алгоритмов, аппроксимирующих GPS, WFQ используется просто как коммерческое имя для «продвинутых», относительно RR и DRR, планировщиков.

Алгоритм планировщика \\Т(3»определеяется в соответствии с принципами алгоритма GPS и реализует принцип «справедливой буферизации на уровне пакетов» PFQ. Обозначим через d^^PSвремя окончания обслуживания пакета р, другими словами, время, когда центральный процессор передает пакет р в исходящий канал. Аппроксимирующий

GPS алгоритм должен обслуживать пакеты в соответствии со знамениj GPS

ем параметра а , придерживаясь стратегии, что пакет с меньшим значением этого параметра должен быть обслужен раньше, чем пакет с большим значением. Однако, на практике такую стратегию поведения планировщика реализовать достаточно сложно - возможно только, если алгоритм планировщика относится к классу «работающие с паузами». Этот факт можно объяснить на следующим примере. Пусть планировщик выбирает пакет, который должен быть передан на обслуживание, т.е. он осуществляет проверку значения функции «виртуальное время окончания обслуживания» для всех доступных в этот момент времени HOL-пакетов. Может иметь место случай, когда пакет с необходимым значением этой функции еще не поступил в систему, в связи с чем планировщик должен будет либо забрать на обслуживание другой пакет с большим значением (класс планировщиков «работающие непрерывно»), либо ждать еще не поступивший пакет (класс планировщиков «работающие с паузами»). Реализация класса «работающих с паузами» планировщиков требует обладания информацией о пакетах, которые поступят в будущем, что на практике невозможно. Алгоритм планировщика WFQ предполагает моделирование сервера GPS в непрерывном времени на уровне пакетов - планировщиком выбирается на обслуживание тот пакет, который в соответствии с моделируемым алгоритмом GPS уже должен был быть обслужен.

Атгоритм планировщика WFQ для реализации функции, подобной функции вычисления «виртуального времени окончания обслуживания», реализованной в GPS, использует подход вычиления значения функции «виртуальное время» (virtual time, далее эту функцию будем называть «виртуальное время GPS»), которая будет сейчас рассмотрена.

Обозначим время поступления первого пакета через /, = 0. Очевидно, что для j ~ 2, 3,… количество потоков, находящихся в «периоде занятости» в интервал времени фиксировано. Обозначим это количество через переменную Bj. Значение функции «виртуальное время GPS» V(t) для любого момента времени, когда центральный процессор простаивает, т.е. отсутствует нагрузка, равно нулю. Далее рассмотрим некоторый период занятости, начинающийся в момент времени 1 = 0. Начальное значение функции «виртуальное время GPS» в этот момент равно 0, а далее вычисляется в соответствии со следующей формулой:

Скорость изменения значения параметра V, т.е. (1У{1;₎+ т)1(}т, вычисляется как отношение 1^ • Учитывая формулу (2.1) для каждого «бэклог»-потока / скорость обслуживания определяется как:

Таким образом, параметр V может быть интерпретирован как скорость, с которой обслуживаются «бэклог»-потоки.

Далее пусть к-й пакет потока i поступает в систему (в одну из очередей из классификатора) в момент времени a_ikи имеет длину L_ik. Усложним задачу и введем две новые функции: функцию «виртуальное время поступления» (virtual start time или start potential) пакета в очередь S_jk, и функцию окончания обслуживания «виртуальное время окончания обслуживания» (virtual finish time или finish potential) F_jk- Положив F_j0=0 для всех i, имеем следующие отношения:

Отметим, что ввод V(a_lk) в данное выражение необходим для сброса значения S_ikпосле того как очередь / стала активной, т.е. в пустую очередь стала поступать нагрузка [Stiliadis96, Bennett97]. За счет этого достигается достаточно точная аппроксимация GPS, с точки зрения вычисления времени начала обслуживания пакета, поступившего в пустую (неактивную) очередь.

Можно, как минимум, привести следующие положительные качества использования функции «виртуальное время GPS» для работы планировщика WFQ, с точки зрения реализации на практике:

• значение этой функции возможно вычислять в момент поступления пакета в очередь;

• пакеты обслуживаются поочередно в соответствии со значением этой функции;

• в процессе функционирования необходимо лишь обновлять значение этой функции, в то время как в GPS необходимо обрабатывать события.

В качестве недостатка представленного подхода отметим накладные расходы, связанные с хранением и управлением множества значений Bj, необходимого для обновления значения функции «виртуальное время GPS».

Сравним последовательность ухода пакетов на обслуживание для двух случаев - когда время окончания обслуживания вычисляется сервером G PS и с использованием функции V(t).

В первом случае обозначим к-й пакет «бэклог»-потока / через (/,йГ'_А), где df[^s- время окончания обслуживания этого потока сервером GPS. На рис. 2.37 представлены графики обслуживания нагрузки сервером G PS в непрерывном времени и планировщиком WFQ, в соответствии с принципом «справедливой буферизации на уровне пакетов» PFQ, и последовательность ухода пакетов из системы для примера, приведенного ранее. Отметим, что пакеты уходят из системы в соответствии со значением параметра df'_k ^s, вычисленного сервером GPS. В случае, если пакеты имеют одинаковое значение параметра df_k ^s, то они обслуживаются в произвольном порядке.

Во втором случае обозначим каждый пакет через (i,F_lt). На рис. 2.39 представлен график изменения значения функции «виртуальное время GPS» V(t), вычисленного в соответствии с формулой (2.2). На рис. 2.38 представлены графики изменения значения функции «виртуальное время окончания обслуживания» и последовательность ухода пакетов на обслуживание для примера, приведенного ранее. Функция F₍(t) является ступенчатой, для которой F_j(a_jк) = F_{t к}, а время поступления a_{i k}к-то пакета потока i вычисляется в соответствии с формулой (2.3).

Сравнивая оба случая, отметим, что в последнем случае пакеты уходят из системы в том же порядке, что и в первом, когда время окончания обслуживания вычисляется сервером G PS. Этот факт позволяет констатировать, что использование функции «виртуальное время GPS» для функционирования планировщика WFQ является достаточно точной аппроксимацией алгоритма G PS.

Рис. 2.37. Графики обслуживания нагрузки сервером GPS в непрерывном времени и планировщиком WFQ в соответствии с принципом «справедливой буферизации на уровне пакетов» PFQ

Рис. 2.38. Графики изменения значения параметров «временная метка» F,(t) и последовательность ухода пакетов на обслуживание.

F^t) рассчитывается на основе функции «виртуального времени GPS» V(t). Уход пакетов осуществляется в соответствии с параметром F_;(t)

Рис. 2.39. Изменение значения функции «виртуальное время GPS»

Также для сравнения функционирования GPS и его аппроксимации WFQ можно использовать параметр задержки пакета на обслуживание внутри рассматриваемой системы (latency). Под задержкой такого рода в рамках некоторой системы ^ будем подразумевать минимальное неотрицательное значение параметра , удовлетворяющее следующему соотношению:

для любого промежутка времени после момента времени Г, причем t > г, когда «период занятости» /-го потока начинается, и до тех пор, пока все поступившие пакеты этого потока за рассматриваемый «период занятости» не будут обслужены. Графическая интерпретация параметра W^{T,t) представлена на рис. 2.40 - значение этого параметра определяет границу количества обслуживания, предлагаемого потоку / за промежуток времени, пока этот поток находится в «периоде занятости». Значение же параметра задержки ©Г отражает ту максимальную детерминированную задержку, которой подвергается первый пакет рассматриваемого потока i за время нахождения этого потока в «периоде занятости» и если этот поток является «бэк-лог»-потоком.

В случае для сервера GPS данные нового только поступившего в систему потока передаются на обслуживание практически моментально, при этом назначается интенсивность их обслуживания равная или превышающая интенсивность поступления этих данных в систему. Таким образом обеспечивается значение параметра задержки ©<", равное нулю.

В свою очередь, для алгоритма WFQ максимальная детерминированная задержка, которой подвергается первый пакет рассматриваемого потока / за время нахождения этого потока в «периоде занятости», а также если этот поток является «бэклог»-потоком, моjWQ

жет быть определена как разность а₁- а,-,, где а,, является временем поступления пакета в систему. Учитывая выражение (2.3), имеем:

Рис. 2.40. Графическая интерпретация задержки пакета на обслуживание внутри рассматриваемой системы

Недостатком алгоритма WFQ можно считать его вычислительную сложность O(N), связанную с накладными расходами по управлению и хранению множества B_jtкоторое необходимо для расчета функции «виртуальное время GPS», где N - максимальное количество «бэклог»-потоков в рассматриваемой системе. Существуют более простые, с точки зрения вычислительной сложности, алгоритмы построения планировщиков, заключающиеся в применении различных алгоритмов аппроксимации функции виртуального времени GPS. Далее рассмотрим другие планировщики, идея построения которых идентична WFQ, а отличие состоит в используемых алгоритмах аппроксимации GPS и в принципах выбора пакетов [Stiliadis96,Bennett97].

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