Методы упреждающего прогнозирования состояния широкополосной сети связи

УДК 004.023

методы упреждающего прогнозирования состояния широкополосной сети связи:

А.И. Власов, к.т.н..; В.В. Иванов; И.А. Косолапов

(Московский государственный технический университет (МГТУ) им. Н.Э. Баумана,

ivanov@tsystems.su)

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

Ключевые слова: фрактальные свойства, самоподобный трафик, распределение, параметр Херста.

Для достижения требуемой точности при проектировании гетерогенных широкополосных сетей передачи данных целесообразно построить модель будущей сети, учитывая типы сервисов, предоставляемых на данной сети передачи данных, а также количество пользователей. Результаты моделирования должны иметь точность 10-20 %, этого достаточно для большинства целей и не требует слишком много машинного времени. Следует иметь в виду, что для моделирования поведения реальной сети необходимо учитывать ее рабочие параметры: задержки используемых кабелей, коммутационного и серверного оборудования.

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

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

Пусть ^^ к=0, 1, 2, ...} - стационарный случайный процесс.

Учитывая стационарность и предположение о существовании и конечности двух первых моментов, введем обозначения: m=E[Xt] - среднее зна-

2

чение, или математическое ожидание; ст = =E[Xt-m2] - дисперсия; R(k)=E[(Xt+k-m)(Xt-m)] -корреляционная функция; r(k)=R(k)/r(0)=R(k)/ст2 - коэффициент корреляции.

Под {X(m)} усреднением по шкале времени будем понимать переход к такому процессу, где 1 к™ х(кт)= - £ х,.

™ 1=кш-ш+1

При моделировании сетевого трафика значения Xk интерпретируются как число пакетов (реже

- как суммарный объем данных в байтах), поступивших в канал или сеть в течение k-го интервала времени. Исходный процесс при этом уже является усредненным. В некоторых случаях, когда есть необходимость избежать такого начального усреднения, рассматривается точечный процесс, или поток событий, то есть последовательность моментов поступления единичных пакетов в сеть [2].

Случайный процесс X(t) является самоподобным с параметром Херста H, если X(t) и a_HZ(at) имеют идентичные конечномерные распределения вероятностей для всех a>0. Отметим, что на практике обычно встречаются не строго самоподобные, а асимптотически самоподобные процессы.

Параметр Херста He(0,5, 1) определяет степень самоподобия процесса. Чем ближе этот параметр к единице, тем более ярко проявляются фрактальные свойства. Напротив, равенство Н=0,5 свидетельствует об отсутствии самоподобия.

Самоподобные процессы, в том числе описывающие явления в сетях передачи данных, обладают рядом свойств, существенно отличающих их от потоков, рассматриваемых в классической теории телетрафика [1].

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

r

или (для асимптотически самоподобных процессов) корреляционной функцией R(k)»k2H-2L(t) при k^<», где L(t) - медленно меняющаяся функция

L

на бесконечности (то есть lim —= 1 для всех

L

x>0). Следовательно, корреляционная функция является несуммируемой - ряд, образованный последовательными значениями корреляционной функции, расходится. Это свойство характеризует практически все самоподобные процессы и отличает их от процессов без долговременной зависимости, у которых корреляционная функция убывает по показательному закону и суммируема [2].

Долговременная зависимость является причиной ярко выраженных пульсаций процесса, однако позволяет говорить о некоторой предсказуемости

в небольших пределах времени. С точки зрения теории очередей важным следствием коррелиро-ванности потока является неприемлемость оценок параметров очереди, основанных на предположении об одинаковом и независимом распределении интервалов во входящем потоке [1].

Медленно убывающая дисперсия. При усреднении процесса дисперсия выборочного среднего затухает медленнее, чем величина, обратная размеру выборки, по закону c2(X(m))xm2H-2 при m^ro, в то время как для традиционных стационарных случайных процессов a2(X<m))= 1

= —a (X), то есть уменьшается обратно пропор-m

ционально объему выборки.

Свойство медленно убывающей дисперсии говорит о возможности существенных, не сглаживаемых усреднением выбросов в случайном процессе и связывает самоподобие с таким понятием, как распределения с весомыми хвостами. Важное следствие свойства медленно затухающей дисперсии состоит в том, что в случае классических статистических тестов (например, вычисление доверительных интервалов) общепринятая мера среднеквадратического отклонения о является ошибочной [3]. С данным свойством связано и нехарактерное поведение индекса дисперсии, или индекса разброса, для отсчетов процесса (IDC), также называемого фактором Фано. IDC определяется как отношение дисперсии числа событий на заданном временном интервале Т к математическому ожиданию этой величины:

F (т)_ Var [N (T)] F ( T)_ E[N(T)] •

Здесь N(T) - число событий исследуемого потока, наступивших в интервале (окне) Т. Для самоподобных процессов логарифм индекса разброса F(T) линейно возрастает: ln[F(T)-1]= =(2H-1)lnT+y.

Распределения с весомыми хвостами. Случайная величина Z имеет распределение с весомым хвостом (РВХ), если вероятность P[Z>x]»cxa при x^-<x), то есть хвост распределения затухает по степенному закону. Пример распределения с весомым хвостом - распределение Парето. При 0<а<2 величина Z обладает бесконечной дисперсией, при 0<а<1 среднее значение также бесконечно. Наиболее существенная особенность случайной величины, обладающей распределением с весомым хвостом, - чрезвычайная изменчивость. С вероятностью, которая не является пренебрежимо малой, в выборке может присутствовать некоторое число очень больших значений. Такие распределения существенно снижают точность статистических оценок; скажем, конечный объем выборки приводит к заниженной оценке среднего и дисперсии [4].

Наличие РВХ во внешних по отношению к рассматриваемым процессам явлениях является одной из причин возникновения самоподобия в соответствующих стохастических моделях.

Часто при рассмотрении самоподобных процессов говорят о комплексе взаимосвязанных понятий: самоподобии, масштабировании, долговременной зависимости, РВХ и степенных законах статистических характеристик. Этот комплекс свойств отличает процессы, называемые самоподобными, от классических случайных процессов, например пуассоновского.

Исследуемый трафик. Многочисленные измерения показывают наличие существенно самоподобных свойств трафика в клиент-серверных ИС различной архитектуры - от классических двухзвенных до многоуровневых с web -доступом и терминальных.

Фрактальный характер можно рассмотреть на примере среза трафика, полученного при работе удаленного подразделения из нескольких рабочих мест с сервером СУБД. Параметры среза трафика следующие: длительность - 21 936 с; длительность - 6,093 ч; число пакетов - 688108; интенсивность X - 31,368 с-1; средний объем пакета -193,2 байта; рабочих мест - 25; параметр Херста Н (IDC) - 0,729; параметр Херста Н (автокорреляция) - 0,724 [5].

Данные были получены путем перехвата кадров на FastEthernet-интерфейсе сервера СУБД с помощью программы tcpdump. Исходя из предположения о дуплексности канала, к рассмотрению принят трафик одного направления - исходящий по отношению к рабочим станциям.

Сервером СУБД является сервер Oracle8i; приложение (биллинговая система оператора связи) реализовано по классической двухзвенной клиент-серверной схеме, то есть сетевое взаимодействие происходит на базе TNS/SQL*net поверх TCP. Поскольку пропускная способность рассматриваемого канала (100 Мбит/с FastEthernet) существенно превышает суммарный трафик, а сторонняя нагрузка в день исследований пренебрежимо мала, срез можно считать свободным трафиком (в терминологии, введенной И. Норросом), то есть трафиком, полностью определяемым своим источником и не испытывающим влияния сети.

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

На рисунке 1 приведен график коэффициента корреляции для процесса, соответствующего исследуемому срезу трафика. Если процесс самопо-добен, угловой коэффициент P=2-2H. При полученном значении 0=0,55004 параметр Херста оказывается равным 0,724.

На рисунке 2а для сравнения приведена кривая, соответствующая значениям коэффици-

° о

"'---.... а»

% ° О -S5

0 12 3 4

.'од к

Рис. 1. Значения коэффициента корреляции

ента корреляции строго самоподобного процесс -са [5].

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

0,4

0,3

0,1

о

20 40 60 80 100 120 140 160 100 200 220 240 к. с

ч "VJV тСЛ, Wi »(Л Stf

20 40 60 80 100 120 140 160 180 200 220 240 к, с

Рис. 2. График коэффициента корреляции для трафика:

а) в сравнении с кривой коэффициента корреляции строго самоподобного процесса (1) при в=0,55;

б) в сравнении с кривой коэффициента корреляции с перемешанными случайным образом интервалами

Параметр Херста. Традиционно самоподобие в стохастическом процессе выявляется путем определения параметра Херста Н. Тот факт, что 0,5<H<1, то есть значение параметра Херста отлично от 0,5, считается достаточным основанием для признания процесса самоподобным (по крайней мере, асимптотически) [6].

Следует отметить, что значение Н, близкое к единице, может означать, что процесс является детерминированным: для ряда строго детерминиро-

ванных процессов структура строго повторяется на любом масштабе, что приводит к единичному значению параметра Херста.

В рассматриваемом случае значения параметра Херста, определенные из вида кривой коэффициента корреляции и путем анализа IDC (0,724 и 0,729 соответственно), практически совпадают. При этом значение говорит о существенно выраженных фрактальных свойствах.

На рисунке 3 приведены значения ln[F(T)-1] в зависимости от lnT. Для процесса с перемешанными случайным образом интервалами значение получается существенно меньше: H=0,563. Этот факт совместно с видом корреляционной структуры исходного и перемешанного процессов позволяет утверждать, что для рассматриваемого трафика самоподобие заключено не столько в тяжелом распределении интервалов, сколько в долгосрочной зависимости - группировке коротких интервалов в пачки [3].

1 2 3 4 5 6

Рис. 3. Определение параметра Херста Н по значениям IDC

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

Алгоритм статистического мультиплексирования потоков широко используется в телекоммуникациях, поскольку позволяет экономно использовать пропускную способность магистральных каналов. Рассмотрим простейший пример передачи информации от многих источников по одному магистральному каналу. В принципе, за каждым из источников можно закрепить определенную часть ресурсов магистрального канала (скажем, разделив их по частоте). В этом случае каждый источник может использовать только ту часть ресурсов, которая ему отведена. Другой способ передачи, называемый статистическим мультиплексированием, состоит в том, что потоки отдельных источников складываются (агрегируются) в магистральном канале с экономией пропускной способности dC [4].

Рассмотрим второй вариант более подробно. Допустим, имеются п отдельных (парциальных) источников. Пусть процессы ^^[£1], D[|1]), ...,

^(ВД^], D[¡П]) имеют одинаковые математические ожидания M[¡i]=ц, и дисперсии D[¡i]=a2 (рис. 4). Тогда при условии независимости и одинаковом распределении ¡2, ..., ¡п коэффициент вариации результирующего процесса в магистральном канале будет равен

cov

Tofe] + Ç +...+ Ç. ]

M [ÇE] M [Ç, + Ç +... + Ç. ]

У"• D[Çz]_ g2

n • m[çs]

Рис. 4. Схема статистического мультиплексирования ..., с получением

в магистральном канале процесса ¡¡е

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

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

Типичный вид агрегированного сетевого трафика показан на рисунке 5.

Каждая точка на данном графике представляет собой количество байтов, переданных в магистральном канале за 1 секунду. Длительность реализации составляет 3000 точек, или 50 минут. Коэф-

фициент Херста соответствует примерно 0,8. Как видно из рисунка, процесс имеет высокую изменчивость (поскольку подчиняется распределению с тяжелым хвостом) и его вряд ли можно назвать сглаженным. Чтобы такой трафик передавать без потерь, пропускная способность канала должна соответствовать уровню пиковых выбросов, то есть в данном случае быть не менее 1,4 х105 бит/с [2]. Поскольку средний уровень трафика все-таки достаточно низкий, можно заметить, что пропускная способность будет расходоваться неэффективно. Другими словами, коэффициент использования такого канала будет низким.

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

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

Литература

1. Шелухин О.И., Тенякшев А.М., Осин А.В. Фрактальные процессы в телекоммуникациях. Монография; [под ред. О.И. Шелухина]. М.: Радиотехника, 2003. 480 с.

2. Miloucheva I., Muller E., Anzaloni A. A practical approach to a forecast Quality of Service parameters considering outliers. 2003.

3. Foag J., Wild T. Traffic prediction algorithm for speculative network processors // 17th Intl. Symposium for High Performance Computing Systems and Applications HPCS 2003. -Sherbrooke, May 2003.

4. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. СПб: Питер, 1999.

5. Управление неоднородными сетями. URL: http://www.citforum.ru/nets/tpns/glava_16.shtml (дата обращения: 12.12.2010).

6. Trajcovic L., Neudhardt A., Internet traffic prediction // Centre for Systems Science, Simon Fraser University, Vol. 12, Is. 1, Mar. 2000.