На правах рукописи
Сидорова Оксана Игоревна
МАТЕМАТИЧЕСКИЕ МОДЕЛИ ТРАФИКА
В СОВРЕМЕННЫХ ТЕЛЕКОММУНИКАЦИОННЫХ
СИСТЕМАХ
Специальность 05.13.18 математическое моделирование, численные
методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Тверь 2009
Работа выполнена на кафедре математической статистики и системного анализа факультета прикладной математики и кибернетики Тверского государственного университета.
Научный руководитель доктор физико-математических наук, профессор Ю.С. Хохлов
Официальные оппоненты:
доктор физико-математических наук, профессор В.Е. Бенинг доктор физико-математических наук, профессор А.И. Зейфман
Ведущая организация: Московский государственный университет им. М.В. Ломоносова, механико-математический факультет
Защита состоится 22 мая 2009 г. в 14. на заседании диссертационного совета Д212.63.04 в Тверском государственном университете по адресу: 170000, Тверь, ул. Желябова, 33, ауд. 52.
С диссертацией можно ознакомиться в научной библиотеке Тверского государственного университета по адресу: 170000, Тверь, ул. Володарского, 44 а.
Объявление о защите диссертации и автореферат опубликованы на официальном сайте Тверского государственного университета по адресу:
http://university.tversu.ru/aspirants/abstracts/.
Автореферат разослан 2009 г.
Ученый секретарь совета доктор технических наук, профессор В.Н. Михно
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. До середины 90-х годов 20 века оценки производительности компьютерных сетей осуществлялись с помощью стандартных методик, основанных на формулах Эрланга. Пока трафик состоял из небольших текстовых файлов, не требовавших значительных ресурсов для обслуживания, трудностей такой подход не вызывал, но по мере очень быстрого увеличения числа пользователей и усложнения структуры передаваемой информации это привело к серьезной недооценке реальной нагрузки и значительному ухудшению качества обслуживания (QoS ). Примером является сбой в сети AT &T в 1990 году, когда на протяжении 9 часов она была недоступна большей части зданий Нью-Йорка, что вызвало большие финансовые потери.
Требования к повышению QoS стимулировали развитие надежных систем с высокой устойчивостью к сбоям, что, резко повысило интерес к исследованию свойств нагрузки в современных компьютерных системах.
Исследования (M. Crovella et al., 1996; W. Leland et al., 1994) показали, что свойства компьютерного трафика кардинально отличаются от свойств трафика в голосовых системах, например телефонных сетях. Компьютерный трафик имеет долгую память, у распределений длин периодов занятости наблюдаются тяжелые хвосты, агрегированный процесс нагрузки является самоподобным (монофрактальным).
В таких условиях вероятность переполнения буфера с ростом его размера h убывает не по экспоненте, как в линейных системах массового обслуживания (СМО) с марковскими потоками, а степенным образом (S. Resnick et al.., 1998; Б. Цыбаков и др., 1998–2001) или по закону Вейбула (I. Norros, 1994). Если для эффективного обслуживания голосового трафика буфер в 3КБ (30 пакетов размера 100Б) более чем достаточен, вероятность переполнения в этом случае имеет порядок 1014, то при степенном убывании вероятности переполнения в условиях сильной загрузки даже буфер в несколько ГБ не гарантирует для самоподобного трафика надежного обслуживания.
Вероятности переполнения для самоподобного процесса с параметрами H = 0.85 и H = 0.6 и буфера размером 2ГБ (2 · 107 пакетов размера 100Б) по некоторым оценкам (модель Б.С. Цыбакова) имеют порядок 104 и 108 соответственно. Сегодня для стабильной работы СМО требуется, чтобы данная вероятность не превышала 1 · 109.
СМО с самоподобным трафиком к настоящему времени хорошо изучены: для них описаны возможные предельные процессы для потоков нагрузки (T. Mikosh et al., 1998-99) и получены оценки для ряда показателей QoS. Данные результаты являются важным шагом вперед в рамках анализа немарковских СМО, однако они не позволяют охватить все многообразие свойств трафика в современных условиях.
Широко используемые сегодня технологии обработки информации позволяют передавать по одному каналу трафик с разными требованиями к параметрам производительности системы, вследствие чего поток может быть крайне неоднородным.
Исследования (M. Taqqu et al., 1997; A. Feldmann et al., 1998) показали, что самоподобие проявляется асимптотически, на крупных временных шкалах, а для малых периодов усреднения поведение трафика больше похоже на мультифрактал. СМО с мультифрактальными потоками изучены слабо: основной вывод из нескольких работ, посвященных моделям трафика, порождаемого неоднородными источниками, состоит в том, что свойства трафика и параметры QoS определяются источниками с самым длинным активным периодом/ тяжелыми заявками. Поведение трафика и параметров QoS в случае, когда тяжелые заявки приходят редко, а основную нагрузку порождают более легкие требования, практически не изучено. На первый взгляд наиболее очевидным в этой ситуации кажется определение размера буфера на основе потока с самыми тяжелыми заявками. Однако необоснованное увеличение размера буфера может не оказать желаемого влияния на СМО, так так выигрыш от уменьшения потерь информации, будет нивелирован из-за увеличения стоимости сетевой аппаратуры и ее обслуживания и ухудшения других параметров QoS, например, увеличения задержки при обработке информации в большом буфере.
Оптимизация затрат на создание и эксплуатацию сетей в сочетании с сохранением их высокой производительности и гарантированного качества обслуживания требует повышения адекватности существующих моделей трафика и подходов оценке параметров QoS, поэтому выбранная для исследования тема является на сегодняшний день очень актуальной.
Цели и научные задачи. Целью диссертации является разработка математических моделей трафика, отражающих мультифрактальное поведение потоков данных в реальных системах связи и исследование влияния мультифрактального трафика на асимптотическое поведение вероятности переполнения буфера.
Для достижения этой цели в работе решены научные задачи:
1. Построены математические модели входящих потоков: неоднородная ON/OFF модель, неоднородная модель Пуассона в непрерывном и дискретном времени, длины активных периодов источников в которых имеют распределения с правильно меняющимися хвостами с различными показателями 1 < (k) < 2, k = 1, r, r <.
Установлены условия, при которых источники любого типа нетривиально влияют на характеристики процесса нагрузки.
2. В неоднородной ON/OFF модели в режиме Slow Growth Condition (SGC ) найден новый предельный процесс для агрегированного процесса нагрузки.
3. Найдено асимптотическое распределение случайной суммы независимых случайных слагаемых, имеющих конечное число различных распределений.
4. Доказано, что вероятность переполнения буфера в неоднородной ON/OFF модели и неоднородной модели Пуассона в непрерывном времени и асимптотические границы для вероятностей переполнения буфера и потери пакета в неоднородной модели Пуассона в дискретном времени убывают степенным образом с ростом размера буфера. Найдены условия при которых скорость убывания может совпадать с любым из (k), k = 1, r.
5. С помощью имитационного моделирования исследованы свойства асимптотических границ для вероятности переполнения буфера в неоднородной модели Пуассона в дискретном времени.
Методы исследования. При получении теоретических результатов использовались методы теории вероятностей, теории случайных процессов и асимптотические методы математического анализа. Для проверки и уточнения полученных результатов использовалось имитационное моделирование.
Положения, выносимые на защиту.
1. Модели входящих потоков, построенные с учетом того, что доли источников разных типов в общем потоке различны.
2. Асимптотическое распределение случайной суммы независимых случайных величин, имеющих конечное число разных распределений, найденное с помощью сведения суммы со случайным числом слагаемых к сумме с неслучайным числом слагаемых.
3. Асимптотика вероятности переполнения буфера в СМО с неоднородными потоками, отражающая вклад источников разных типов.
4. Методика построения имитационной модели, основанная на использовании методов ускорения симуляции, и ее применение для уточнения константы в оценке вероятности переполнения буфера.
Научная новизна и теоретическая значимость. Результаты диссертации развивают теорию массового обслуживания в классе систем с немарковскими входящими потоками. По сравнению с существующими подходами новые модели являются более гибкими, так как учитывают влияние разных компонент трафика на свойства всего потока и на характеристики его обслуживания. Асимптотическое распределение случайных сумм, найденное ранее для одинаково распределенных с.в., перенесено на случай, конечного числа различных распределений. Данный результат обеспечивает единый подход к анализу ON/OFF модели и модели Пуассона с непрерывным временем в однородном и неоднородном случае, в отличие от известных результатов для однородного случая, при получении которых ранее использовались разные методы.
Полученная в рамках разработанных моделей трафика асимптотика для вероятностей переполнения буфера и потери пакета позволяет более адекватно оценивать потери информации и отказы в обслуживании.
Практическая значимость. Практическая значимость работы состоит в том, что результаты диссертации могут служить базой для численного анализа современных СМО с мультифрактальными входящими потоками и установления минимально необходимого размера буфера при проектировании новых систем связи.
Достоверность и обоснованность научных результатов базируются на корректном использовании вероятностно-статистических методов, теории случайных процессов и математического анализа. Все сформулированные теоретические положения имеют строгие математические доказательства. Достаточность и обоснованность полученных результатов также подтверждается методами имитационного моделирования.
Апробация работы. Основные результаты работы докладывались на международном семинаре по проблемам устойчивости стохастических моделей (г. Юрмала, Латвия, 2004), (Салерно, Италия, 2005), на конференции Ломоносовские чтения (г.
Москва, МГУ, 2005), на 31 международной конференции по стохастическим процессам и их применениям (г. Париж, Франция, 2006), на 5 международной конференции по процессам Леви (г. Копенгаген, Дания, 2007), на 13 Всероссийской школе-коллоквиуме по стохастическим методам (г. Йошкар–Ола, 2007), на научно-практической конференции Моделирование и принятие решений в условиях неопределенности (г. Тверь, ТвГУ, 2008).
Публикации. По материалам диссертации опубликовано 12 работ, среди них в изданиях рекомендованных ВАК Минобрнауки России.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 155 листах, содержит 17 рисунков, 3 таблицы и список литературы, включающий 83 наименования.
Во введении отражена актуальность выбранной темы, приведен обзор научной литературы, освещающий состояние проблемы, сформулированы цели и задачи исследования и положения, выносимые на защиту. Введение также содержит основные научные результаты с обоснованием их новизны и практической ценности и краткое содержание диссертационной работы.
В первой главе определен объект исследования, даны определения, вспомогательные понятия и описания моделей, приводящих к самоподобному трафику.
В параграфе 1 описывается объект исследования и объясняются причины самоподобия трафика в современных системах связи.
В работе рассматривается некоторая цифровая сеть связи, состоящая из одного сервера (обслуживающего прибора, канала), на который поступает нагрузка от других узлов сети пользователей. Предполагается, что сервер имеет буфер конечного размера, что является типичной ситуацией для современной системы связи в условиях сильной загрузки. Подобная модель рассматривается в литературе как базовая математическая модель маршрутизатора или коммутатора (T. Neam, 2003), которая позволяет с достаточной степенью точности воспроизводить реальные процессы и, что очень важно, является доступной для анализа даже в случае потоков нагрузки с очень сложной структурой.
В цифровых системах все сообщения разбиваются на небольшие части пакеты, каждый из которых передается получателю, где они вновь собираются в цельное сообщение. Мы не интересуемся конкретной природой передаваемой информации и процессом ее разбиения на пакеты. Исходная информация поток пакетов, которые обычно сбиваются в так называемые пачки. Потоки таких пачек между узлами связи называют трафиком телекоммуникационной системы в этой области знания. В реальных системах в зависимости от технологии передачи информации длина пакетов может колебаться от 4Б до 1500Б. Мы рассматриваем стандартные пакеты, то есть одинаковые в смысле длины и времени обработки, которое с достаточной степенью точности можно считать неслучайной константой. Примером такой системы является сеть с технологией асинхронной передачи данных (ATM ), в которой все пакеты имеют одинаковый размер 53Б и постоянное время обслуживания.
В параграфе 2 даются определения процессов с короткой и длинной памятью, распределений с тяжелыми хвостами, строго самоподобных, самоподобных в широком смысле и асимптотически самоподобных процессов непрерывного и дискретного аргумента. Приводятся определения дробного броуновского движения и -устойчивого движения Леви, 0 < 2.
Определение 1. Случайный процесс X = {X(t), t 0} называется самоподобd ным, если для любого a > 0 существует b > 0, такое что X(at) = bH X(t).
Для невырожденного, стохастически непрерывного при t = 0 самоподобного процесса X, такого что п.н. X(0) = 0 существует единственное число H > 0, для которого b = aH. Следовательно, в этом случае, X(at) = aH X(t).
Пусть случайный процесс X имеет стационарные приращения c конечной дисперсией 2. Ковариационная функция (t, s) = cov(X(t), X(s)) процесса X имеет вид Принимая во внимание цифровой и пакетный характер современных сетей связи, также будем рассматривать процессы с дискретным временем. Ковариационная и корреляционная функции процесса приращений {(n) = X(n + 1) X(n)}n=0,1,2,... при n 0 будут равны соответственно При n < 0 мы имеем (n) = (n), (n) = (n). Заметим, что при n (n) n · L(n), 0 < = 2 2H < 1, где функция L(n) медленно меняется на бесконечности. Процесс X имеет короткую память, если (n) n · L(n) 1 < < 2; n или если существуют постоянные 0 < a < 1 и 0 < b < такие, что |(n)| ban, n.
m = 1, 2,... это усредненный по блокам длины m (агрегированный) случайный процесс X. Обозначим через m (k) коэффициент корреляции процесса X (m).
Определение 3. Процесс X называется строго самоподобным в широком смысле с параметром 0 < H < 1, если для любых k N имеет место m (k) = 1/2 · [(k + 1)2 2k 2 + (k 1)2 ] := g(k).
Определение 4. Процесс X называется асимптотически самоподобным в широком смысле с параметром 0 < H < 1, если lim m (k) = g(k), k N.
Примерами самоподобных процессов являются дробное броуновское движение и -устойчивое движение Леви.
Определение 5. Непрерывный гауссовский процесс (BH (t), t 0) с нулевым средним и дисперсией 2 = E|BH (1)|2 называется дробным броуновским движением с показателем 0 < H < 1, если его ковариационная функция имеет вид (t, s) = 1/2 · 2 t2H + s2H |t s|2H.
самоподобный процесс с показателем H. Если H = 1/2, то BH (t) есть обычный винеровский процесс.
Определение 6. Случайный процесс (X(t), t 0) называется процессом Леви, если выполнены условия: 1) X(0) = 0 п.н.; 2) X(t) процесс с независимыми и однородными приращениями; 3) X(t) стохастически непрерывен; 4) траектории X(t) непрерывны справа и имеют конечные пределы слева при t > 0.
Определение 7. Случайный процесс X,, (t), X 0, где (0, 2], [1, 1], 0 называется -устойчивым движением Леви, если он имеет независимые и стационарные приращения с -устойчивым распределением.
-устойчивое движение Леви самоподобый процесс с параметром H = 1/. При = 2 мы имеем броуновское движение. Для 0 < < 2 вторые моменты процесса X бесконечны.
Определение 8. Случайная величина Z имеет распределение с тяжелым хвостом, если P (Z > x) c · x, x, где c > 0 некоторая постоянная, 0 < < параметр формы распределения.
D(Z) =.
В параграфе 3 описаны модели, порождающие самоподобный трафик и область их возможного применения.
Наиболее известными моделями, приводящими к самоподобному потоку являются однородные ON/OFF модель и модель Пуассона с бесконечным числом источников, которые рассматривались в работе Т. Микоша (Mikosch T., Resnick S., Rootzn H., e Stegeman A. Is network trac approximated by stable Lvy motion or fractional brownian motion?. Ann. Appl. Probab., 12(1), 2002, pp. 23–68). Их отличительная особенность наличие тяжелых хвостов у распределений длин периодов занятости/покоя в ON/OFF модели и длин сообщений в модели Пуассона. В рамках данных моделей было показано, что предельными процессами для агрегированных потоков нагрузки в режимах Fast Grows Condition (FGC ) и Slow Growth Condition (SGC ) являются соответственно дробное броуновское движение и -устойчивое движение Леви c 1 < < 2.
Дробное броуновское движение самоподобный процесс с долгой памятью, процесс Леви самоподобный процесс с независимыми приращениями, то есть с короткой памятью. Б.С. Цыбаковым (Tsybakov B., Georganas N. D. Overow and losses in a network queue with a self-similar input. Queuing Syst. 35, 2000, pp. 201–235) был рассмотрен дискретный аналог модели Пуассона и предложена модель входящего потока, приводящая к асимптотически самоподобному процессу.
В данной диссертации упомянутые модели и результаты являются отправной точкой для построения более сложных моделей трафика и исследования их свойств.
Вторая глава посвящена исследованию свойств процесса нагрузки в ON/OFF модели с неоднородными источниками.
В параграфе 1 предложена неоднородная ON/OFF модель, построенная с учетом того что доли источников разных типов в общем потоке различны. В рамках предложенной модели найден предельный процесс для агрегированного процесса нагрузки.
Пусть в СМО есть независимые ON/OFF источники 2 r < различных типов.
Каждый источник генерирует пакеты с постоянной скоростью u > 1 в течение своего ON периода, в течение OFF периода u = 0. Иными словами, это процесс восстановления, порожденный чередованием ON/OFF периодов.
периодов есть независимые с.в., независимые друг от друга, имеющие соответственно распределения F1 и F2 с правильно меняющимися хвостами, то есть:
ности функции. Заметим, что распределения F1 и F2 имеют конечные средние µ и µ2, но их дисперсии бесконечны. Положим µ(k) = µ1 + µ2.
Для любого k = 1, r и n 1 определим стационарную последовательность восстаk) новлений {Tn } по правилу:
где взаимонезависимые с.в. B (k), Xon,(0), Yof f,(0) не зависят от {Yof f, (Xn ), (Yn )}, с.в. B (k) имеет распределение Бернулли с P (B (k) = 1) = µ1 /µ(k), а Xon,(0) ON/OFF процесс для одного источника типа k имеет вид:
Для любого k c.в. = u, если t попадает на ON -период и Wt = 0 иначе. Процесс W (k), k = 1, r строго стационарен со средним E(Wt ) = u·µ1 /µ(k) и ковариационной функцией W (s) c s1 +1 L1 (s) при s. Таким образом процесс W (k) имеет долгую память.
Интенсивность входящего потока для сервера в момент t 0 (число активных исM (k) деления k-го типа среди M = W (k).
Определим полную входящую работу к моменту времени t и семейство агрегированных процессов нагрузки рывная слева обобщенная обратная к функции 1/F1 функция b(k) (t) = inf{x > 0 : 1/F1 (x) t} правильно меняется с показателем 1/(k), следовательно b(r) (t) = t1/ · L0 (t), где L0 (t) медленно меняющаяся функция. Далее рассматривается только случай SGC : b (M (k) (T )T )/T 0.
Определим целочисленные функции M (k) (T ) по правилу: при T В этом случае M (r) /M (T ) 1, M (k) (T )/M (T ) 0, k < r при T.
Ставится задача нахождения предельного распределения для процесса агрегированной нагрузки A(M, T t) при T и M (k) (T ), описанным выше способом.
Справедлива следующая Теорема 1. Если F1 и F2 удовлетворяют условию (3) и режим SGC выполняется для всех k и M (k) (T ), определенных в (8), то при некоторой нормировке предельный процесс для A(M, T t) существует и является суммой независимых устойчивых движений Леви с показателями 1 < 1 <... < 1.
В параграфе 2 обоснована возможность замены случайного индекса в сумме независимых с.в. на его среднее значение в доказательстве теоремы 1. Полученный результат имеет и самостоятельный интерес в теории случайных сумм.
Пусть (Xj, j 1) есть последовательность н.о.р.с.в., функции распределения F (k) (x) = P (Xj < x) которых принадлежат множеству F = {F (1),..., F (r) }, состоящему из 2 r < разных распределений. Обозначим через m(k) (n) число слагаемых в сумме, имеющих распределение F (k). Предположим, что последовательности {Xj } независимы для всех k = 1, r и µk = E(Xj ) <. Допустим также, что существует последовательность положительных чисел Bn такая, что Bn, n и где Y невырожденная с.в. с распределением G. Мы рассматриваем случай, когда распределение G есть свертка r устойчивых законов с разными индексами (k).
«