Стратегии управления нагрузкой в интеллектуальных сетях

В настоящее время интеллектуальные услуги связи широко используются как в фиксированных, так и в мобильных сетях. При увеличении оператором числа предоставляемых услуг или числа пользователей ими возникает задача управ- ления сетевыми ресурсами, решение которой должно обеспечить требуемое качество обслуживания для всех пользователей. Очевидно, что при возрастании количества запросов сеть становиться более чувствительной к перегрузкам – ситуациям, когда существующих сетевых ресурсов недостаточно для обслуживания поступающей нагрузки. Их наличие подразумевает уменьшение доли обслуженных запросов, что означает не только потерю доходов оператора, но и высокий уровень неудовлетворенности пользователей. Таким образом, в быстро развивающихся интеллектуальных сетях связи (ИСС) важно использовать эффективные и гибкие стратегии управления нагрузкой, которые позволяют автоматически обнаруживать перегрузку и принимать адекватные меры для ее устранения.

Стратегии управления нагрузкой в ИСС

В ИСС наиболее уязвимыми к перегрузкам являются узлы управления услугами SCP (Service Control Point), так как они реализуют логику интеллектуальных услуг и в периоды высокой нагрузки получают большое число за- просов, как правило, от нескольких узлов коммутации услуг SSP (Service Switching Point). Имеется ряд работ, связанных с исследованиями управления нагрузкой в интеллектуальных сетях, однако все подходы можно разделить на два класса в зависимости от стратегии управления.

• 1.    Активная стратегия: узлы SSP определяют перегрузку на SCP на основании собственных измерений и предпринимают ряд профилактических действий. Таким образом, активная стратегия работает на стороне SSP и использует только локально доступные измерения для определения перегрузки SCP. Обычно измеряются задержки ответа SCP на запросы, отправляемые SSP в течение пользовательской сессии. В случае, если эта задержка слишком большая, разумно предположить, что SCP перегружен. Поэтому SSP может отбрасывать новые вызовы пользователей до тех пор, пока перегрузка не закончится. Очевидно, что такая стратегия имеет ряд недостатков, в первую очередь, связанных с используемым алгоритмом определения перегрузки на SCP. Более того, управление нагрузкой происходит децентрализованно, что не дает возможности принимать эффективные решения для сети в целом.

• 2.    Реактивная стратегия: узел SCP определяет перегрузку самостоятельно и сообщает об этом всем узлам SSP, которые, в свою очередь, осуществляют сброс новых запросов. Такая стратегия управления требует взаимодействия между алгоритмом определения перегрузки, работающим на стороне SCP, и алгоритмом сброса вызовов – на стороне узлов SSP. Алгоритм определения перегрузки работает постоянно и обнаруживает перегрузку в случае достижения заранее определенных пороговых значений для нескольких показателей производительности, сравнивая средние значения этих параметров со значениями в предыдущем интервале измерений. В том случае, если перегрузка обнаружена, SCP отправляет сообщения о перегрузке всем SSP (или только определенным SSP). Сброс новых вызовов будет продолжаться до тех пор, пока нагрузка не нормализуется.

Наиболее известны следующие стратегии реактивного управления: стратегия прореживания потока вызовов ACG (Automatic Code Gapping) [1], предусмотренная стандартами ИСС, адаптивная стратегия [2], основанная на математической оптимизации, и стратегия с использованием токенов [3]. Рассмотрим их более подробно.

Автоматическое прореживание потока вызовов (ACG)

Стандарты ИСС, используемые в США [1], предоставляют достаточно детальную спецификацию сброса вызовов на основе управления нагрузкой под названием Автоматическое прореживание потока вызовов (Automatic Code Gapping – ACG). Спецификации ACG предполагают высокую степень низкоуровневого управления поведением SSP и SCP, следовательно, дают представление о том, как реализовано ограничение вызовов в ИСС.

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

Правила перевода значений этих параметров в соответствующий уровень перегрузки SCP не указан в спецификациях и обычно разрабатывается поставщиками оборудования. В спецификации [1] предполагается, что если в течение прошлого интервала наблюдения любое число сообщений было отброшено (из-за того, что время задержки превысило пороговое значение), тогда SCP увеличивает уровень перегрузки на единицу, в противном случае уменьшает до нуля.

Спецификация определяет 15 уровней перегрузки. Каждый уровень соответствует определенному значению интервала и таймера разрыва, который используется в SSP для процедуры сброса запросов. Оба эти значения берутся из таблицы, указанной в спецификации.

SCP может информировать SSP об уровне перегрузки одним из двух способов: заполнять TCAP-компонент в ответном сообщении, которое отправляется к SSP в течение следующего интервала, или создавать и отправлять независимое ACG-сообщение. Сообщение ACG применяется только для определенных SSP. Если ACG-запросы объединяются в ответные сообщения, тогда эти запросы будут относиться только к источнику этих сообщений, и таким образом также будет достигаться избирательность при отбросе сообщений.

В сообщении ACG, которое получает SSP, содержатся два параметра: таймер разрыва g. и интервал разрыва T. При приеме сообщения ACG с ненулевым значением gj SSP активирует стандартную процедуру сброса сообщений: только один запрос сервиса может быть принят за gj секунд, в течение времени T. Процедура проиллюстрирована на рис. 1.

Целью использования параметра интервала разрыва является ограничение периода активности процедуры сброса сообщений в случае, когда SSP не получит по каким-либо

Рис. 1. Работа алгоритма ACG на SSP

v

время

Принятый сервисный V запрос

Отброшенный сервисный ) ( запрос

причинам от SCP новых обновлений параметров ACG.

Следует отметить, что для прореживания сообщений используются случайные значения таймера разрыва и интервала разрыва в диапазоне между 90% и 110% от значений, полученных в сообщении ACG, что позволяет обойти синхронности сброса сообщений на всей сети.

Оптимизированная стратегия

В этом разделе рассмотрим оптимизированную стратегию управления нагрузкой в ИС, предложенную в [2]. Стратегия формулирует задачу математической оптимизации, решение которой определяет наилучшие значения коэффициентов для выборочного ограничения трафика, выполняемого на стороне узлов SSP. Оптимизация предполагает получение максимального дохода с учетом существующих ограничений на SCP и SSP.

Оптимизационная стратегия состоит из двух независимых оптимизационных процессов, один работает на стороне SCP, другой на стороне SSP. В заданные интервалы SCP запускает оптимизационный процесс, исходными данными для которого являются: интенсивность вызовов в заданный интервал, целевой коэффициент загруженности SCP, вес каждого типа сервиса и другая информация, касающаяся услуг. Результатом работы оптимизации являются ограничивающие коэффициенты для каждого типа сервиса каждого SSP в сети. Значения этих коэффициентов передаются узлам SSP, которые используются там, в качестве исходных данных для процесса оптимизации, работающего на их стороне. В результате оптимизации на SSP эти коэффициенты могут измениться из-за локальных ограничений, изменений интенсивности запросов и дополнительных требований для сервиса, не относящегося к ИСС.

Важной в оптимизационной стратегии является концепция весовых значений для каждого типа сервиса, которая соответствует важности успешного установления сессии определенного типа по сравнению с другими типами сервиса (аналог приоритета). В описании стратегии вес вычисляется, используя информацию о доходе для каждого сервиса, наличии необходимой процессорной емкости и соглашения о качестве обслуживания SLA (Service Level Agreement) между оператором и заказчиком.

В частности, вес сервиса j на ресурсе x (SSP или SCP) в момент времени t определяется согласно [2] следующим выражением:

,11   • юх.ДО = —-----------’

Е ^^^.т.^т.., где R – доход от сервиса j; q, – уровень качества обслуживания для сервиса j; ех / – число сообщений в сессии для сервиса типа j на ресурсе x; //т j – средняя интенсивность сообщений для сервиса типа j на ресурсе x; J – число типов сервиса, поддерживаемых на узле.

Уровень качества обслуживания назначается произвольно оператором на основе таких факторов, как возможная задержка, важность заказчика или штрафы несоблюдения SLA.

Теперь рассмотрим оптимизационный процесс в SCP. На первом шаге определяется интенсивность поступающих запросов. Это вычисление основывается на знаниях предыдущих значений ограничивающих коэффициентов, а также измерениях количества запросов от SSP в предыдущем интервале. Таким образом, используя описание стратегии [2], имеем:

<,«)-

л нам / ,\

Р SCP.k.j U — Р )

где A* j (О – оценочное количество запросов в момент времени t для сервиса j , поступившее от k -го SSP; ^SCP.k. j ^ – интенсивность начальных сообщений типа j , поступивших на SCP от k -го SSP; РSCP.k.j^ Р^ – значения ограничивающих коэффициентов, установленных в начале текущего периода измерений длительностью T для сервиса j и k -го SSP. Ограничивающие коэффициенты обновляются несколько раз в течение интервала измерений в каждом субинтервале a .

Задача оптимизации формулируется следующим образом:

Max ТЛАААр'^А

Pscpa.i-Ascp.k.j *^=| j='

при ограничениях:

- по нагрузке на SCP:

/ , / ,                              — Pscp ’

Pscpj

- по значению ограничивающих коэффициентов:

0

• - по весовым коэффициентам:

^^PscP-kj-^ ^«scpj^ ^ ^_g^ _K^

PSCP.k.j^ ®SCP.j

j,j'e\\...jY j*j;

где ®scp.j’^max(^ft?scp,i ■•• ®scpjV Pscp – целевой коэффициент загруженности SCP; ^scp.j – максимальный вес, соответствующий сервису типа j.

Заметим, что целевая функция и ограничения – линейные функции от коэффициентов PSCP.k.j W , соответственно, функция оптимизации попадает в категорию задач линейного программирования, которые достаточно легко решаются.

Ограничивающие коэффициенты PSCP.k. j V) передаются в SSP и используются в качестве входных данных для процесса оптимизации в нем. Если в SSP не используется собственный процесс оптимизации, то на узле будут использованы коэффициенты, переданные от SCP. В случае, когда оптимизация на SSP используется, ограничивающие коэффициенты SCP используются в качестве верхних пороговых значений. На SSP задача оптимизации формируется аналогично SCP, то есть максимизация получаемого дохода при заданных ограничениях.

Стратегия, основанная на использовании токенов

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

Процесс генерации токенов нацелен на достижение максимальной прибыли. Значение прибыли назначается оператором для каждого типа сервиса (возможны различные для SSP) в зависимости от получаемого дохода и финансовых штрафов с учетом SLA.

Аналитические модели стратегий

Определим параметры аналитической модели для расчета характеристик процесса обслуживания запросов в SCP. Входными параметрами модели будут средняя нагрузка на SCP и средняя длина очереди запросов в заданном интервале измерения.

Пусть SCP обслуживает запросы от K SSP и от каждого SSP поступают J запросов для разного типа сервиса.

Введем следующие обозначения: T – продолжительность интервала измерений, в течение которого работает стратегия управления нагрузкой; ^-kjV^ – средняя интенсивность запросов типа j от k-го SSP в момент времени t; Pk / (0 – коэффициент для выборочного прореживания запросов j от k-го SSP в момент времени t, значения этих коэффициентов выступают в роли вероятности обслуживания запроса в течение интервала T.

Тогда средняя скорость поступления сессий сервиса j от k-го SSP в момент времени t ^SCP.k. j (0 будет определяться выражением

^SCP.k.j ^ ~ Pk.j (0 ‘ Vj W •

Так как очередь на SCP распределяется по J серверам, интенсивность обслуживания на каждом сервере обозначим как PsCP.j , а интенсивность поступления сообщений j типа в момент времени t – У scp.j (0 . Если ^eSCP,j – число сообщений в сессии для сервиса типа j, а PsCP.j W – нагрузка на SCP в момент времени t, то интенсивность входящих сообщений сервиса типа j определяется следующим образом:

к

• УSCP.j (0 ~ ^eSCPJ ^ ^SCP.kJ (0 ~

4=1

⁼ ^SCP./^A,/^^--^)Л,/(0 •

4=1

Теперь определим нагрузку на SCP:

kA - V¹УSCP.j W

Pscp.j^ —           ■

M Pscp.j

На основании данных [4] средняя длина очереди определяется выражением где k^SGP W – квадрат коэффициента вариации для интервала времени между поступлением сообщений на SCP, который равняется

У^р^-^к^

bScPv)=^^---------■

^е_8СР,Хр^-ти_к.^ /=1         4=1

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

Так, для метода с прореживанием потока вызовов ACG, учитывая, что Sk.jV) – величина интервала разрыва на SCP для сервиса j на k-ом SSP в момент времени t, в случае, когда gk.j№T, ограничивающий коэффициент будет равен нулю, то есть ОИ-если gu№T. Когда gkAtVT, необходимо учесть тот факт, что на SCP принимаются все запросы, прибывающие, пока таймер разрыва активен, в то же время все запросы отбрасы- ваются, когда таймер неактивен. Следовательно, предполагая, что таймер разрыва неактивен в начале и конце контрольного интервала T в течение времени неакт. ’ значение P k j ^^ может быть определено как дробь вида

P^a_kjW=^T-^,ec™ g_k ^      (1)

Определим общее время, в течение которого таймер разрыва был активен:

^Такт. ⁼k_{scp k j} (t + T") T g_kJ (?) =

= рак,АМаА^Т) T gkj(t), где ^-SCP.k. j V + T ) T – число запросов, которые были приняты в течение контрольного интервала T. Тогда неакт.          акт.

= т-p“j(t)\j(tA-T) т g_kjVY (2)

Решая систему уравнений (1)-(2), получим

T+^a+T) gk .(t)’ если gk j(t)

Теперь рассчитаем эквивалентные значения ограничивающих коэффициентов для метода с токенами. В этом случае, если число сервисных запросов, прибывающих в течение интервала времени Т, меньше или равно числу выделенных токенов ^k j ^0 , тогда ограничивающий коэффициент равен 1. В противном случае коэффициент будет вычисляться путем деления числа выделенных токенов на число прибывающих запросов в течение интервала измерения Т:

рак,ДО =

1, еслиЛ, //¹+ T)T < n_{k j}(t);

= * nk . (t)

------------, если2_А_ (t + T)T > n_k (t)

Akij(t + T)T

Анализ работы методов управления нагрузкой

В этой части работы представлены результаты сравнения алгоритмов управления нагрузкой, используя аналитические модели, рассмотренные в предыдущем разделе.

Расчет выполнен с использованием программного продукта Mathcad на примере интеллектуальной сети, которая функционирует на базе технологии CAMEL [5] и предоставляет услуги абонентам мобильной сети GSM. Сеть состоит из одного узла SCP и четырех узлов SSP. Пусть посредством ИСС предоставляются три типа услуги: входящие вызовы, исходящие вызовы и исходящие SMS-сообщения. Доли запросов для каждой услуги от общего количества запросов на SCP составляют, соответственно, 0,45:0,5:0,05. В режиме нормальной нагрузки на SCP суммарная поступающая нагрузка составляет 0,35 Эрл, в режиме перегрузки – 1,4 Эрл. Количество запросов и, соответственно, нагрузка увеличиваются в момент времени t = 600 с и уменьшаются в момент времени t = 1200 с. Как в нормальном режиме, так и в режиме перегрузки сервисные запросы поступают по случайному закону с экспоненциальным распределением интервалов времени между запросами от k = 4 узлов

SSP. Нагрузка на SCP для метода ACG находится в диапазоне от 0,8 до 0,9 Эрл, а для других методов равняется 0,9 Эрл.

Поступающая и пропущенная нагрузки на SCP для трех рассматриваемых методов показаны на рис. 2. Как можно убедиться, метод ACG показал наихудшее поведение, значения пропущенной нагрузки значительно колебались вокруг целевого значения. Это происходило потому, что использовались стандартные значения интервалов разрыва.

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

а) метод ACG                     б) метод с токенами            в) адаптивная стратегия

Рис. 2. Изменение поступающей и пропущенной нагрузки, Эрл (серая линия - поступающая нагрузка, черная - пропущенная нагрузка)

а) метод ACG

б) метод с токенами

Рис. 3. Изменение доли успешных вызовов

в) адаптивная стратегия

Таблица 1. Сравнение методов управления нагрузкой в ИС

Критерий	ACG	Математическая оптимизация	Система с токенами
Нагрузка на SCP во время перегрузки	Нагрузка колеблется из-за использования стандартного таймера разрыва	Наблюдаются колебания около целевой загруженности, что связано с использованием ограничивающих коэффициентов.	Нагрузка чуть ниже целевой. Использование токенов гарантирует непревы-шение целевого значения
Коэффициент использования SCP	Колебания могут приводить к отбросу сообщений из-за переполнения очереди на SCP	Отброс сообщений из-за переполнения очереди маловероятен	Отброс сообщений из-за переполнения очереди маловероятен
Доля успешно обработанных сервисов	Доля успешных запросов не максимальна, так как коэффициент использования SCP невысок	Ограничивается внутри установленных границ для получения максимальной прибыли	Ограничивается внутри установленных границ для получения максимальной прибыли
Время реакции на начало перегрузки	До одного контролируемого интервала до отброса сообщений	До одного контролируемого интервала до отброса сообщений при новых ограничивающих коэффициентах	Какие-либо значительные колебания в размере очереди SCP маловероятны
Устойчивость к высокому уровню поступающей нагрузки	Стандартные интервалы разрыва не подходят при изменении нагрузки	Средний коэффициент использования процессора SCP близок к целевому независимо от поступающей нагрузки	Количество принятых запросов ограничено количеством токенов, поэтому перегрузка невозможна
Простота внедрения	Управление с использованием таблиц легко реализуется на практике	Требуется трудоемкое решение задач линейного программирования	Требуется внедрение сложного алгоритма генерации токенов и отброса сообщений

Сравнение рассмотренных методов управления нагрузкой в ИСС по различным критериям приведено в таблице 1.

Заключение

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