Программные продукты и системы

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

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

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

Пусть {Xk; k=0, 1, 2, …} – стационарный случайный процесс.

Учитывая стационарность и предположение о существовании и конечности двух первых моментов, введем обозначения: m=E[Xt] – среднее значение, или математическое ожидание; s2= =E[Xt–m2] – дисперсия; R(k)=E[(Xt+k–m)(Xt–m)] – корреляционная функция; r(k)=R(k)/r(0)=R(k)/s2 – коэффициент корреляции.

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

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

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

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

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

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

или (для асимптотически самоподобных процессов) корреляционной функцией R(k)»k2H–2L(t) при k®¥, где L(t) – медленно меняющаяся функция на бесконечности (то есть  для всех x>0). Следовательно, корреляционная функция является несуммируемой – ряд, образованный последовательными значениями корреляционной функции, расходится. Это свойство характеризует практически все самоподобные процессы и отличает их от процессов без долговременной зависимости, у которых корреляционная функция убывает по показательному закону и суммируема [2].

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

Медленно убывающая дисперсия. При усреднении процесса дисперсия выборочного средне- го затухает медленнее, чем величина, обратная размеру выборки, по закону s2(X(m))µm2H–2 при m®¥, в то время как для традиционных ста- ционарных случайных процессов s2(X(m))= (X), то есть уменьшается обратно пропорционально объему выборки.

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

.

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

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

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

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

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

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

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

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

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

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

На рисунке 2а для сравнения приведена кривая, соответствующая значениям коэффициента корреляции строго самоподобного процессса [5].

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

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

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

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

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

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

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

Рассмотрим второй вариант более подробно. Допустим, имеются n отдельных (парциальных) источников. Пусть процессы x1(M[x1], D[x1]), …, xn(M[xn], D[xn]) имеют одинаковые математические ожидания M[xi]=m и дисперсии D[xi]=s2 (рис. 4). Тогда при условии независимости и одинаковом распределении x1, x2, …, xn коэффициент вариации результирующего процесса xS в магистральном канале будет равен

Как видим, коэффициент вариации представляет собой отношения среднеквадратичного отклонения процесса к его математическому ожиданию. В данном случае коэффициент вариации отражает степень сглаживания результирующего процесса xS при увеличении количества мульти- плексируемых парциальных каналов. Эффект зрительного сглаживания процесса xS при росте n достигается благодаря более быстрому росту среднего процесса xS по отношению к его среднеквадратическому отклонению [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.