автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели трафика в современных телекоммуникационных системах

На правах рукописи

ии347126Э

Сидорова Оксана Игоревна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ТРАФИКА В СОВРЕМЕННЫХ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ

Специальность 05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

2 2 !:.:." 2СГ:

Тверь — 2009

003471269

Работа выполнена на кафедре математической статистики и системного анализа факультета прикладной математики и кибернетики Тверского государственного университета.

Научный руководитель

доктор физико-математических наук, профессор

Ю.С. Хохлов

Официальные оппоненты:

доктор физико-математических наук, профессор доктор физико-математических наук, профессор

В.Е. Бешшг А.И. Зейфман

Ведущая организация: Московский государственный университет им. М.В. Ломоносова, механико-математический факультет

Защита состоится 22 мая 2009 г. в 14.00 на заседании диссертационного совета Д212.63.04 в Тверском государственном университете по адресу: 170000, Тверь, ул. Желябова, 33, ауд. 52.

С диссертацией можно ознакомиться в научной библиотеке Тверского государственного университета по адресу: 170000, Тверь, ул. Володарского, 44 а.

Объявление о защите диссертации и автореферат опубликованы 14.04.2009 г. на официальном сайте Тверского государственного университета по адресу: http://umversity.tversu.ru/aspirants/abstracts/.

Автореферат разослан «_» _ 2009 г.

Ученый секретарь совета

доктор технических наук, профессор

В.Н. Михно

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. До середины 90-х годов 20 века оценки производительности компьютерных сетей осуществлялись с помощью стандартных методик, основанных на формулах Эрланга. Пока трафик состоял из небольших текстовых файлов, не требовавших значительных ресурсов для обслуживания, трудностей такой подход не вызывал, но по мере очень быстрого увеличения числа пользователей и усложнения структуры передаваемой информации это привело к серьезной недооценке реальной нагрузки и значительному ухудшению качества обслуживания (фо5). Примером является сбой в сети АТ&Т в 1990 году, когда на протяжении 9 часов она была недоступна большей части зданий Нью-Йорка, что вызвало большие финансовые потери. Требования к повышению (2оЭ стимулировали развитие надежных систем с высокой устойчивостью к сбоям, что, резко повысило интерес к исследованию свойств нагрузки в современных компьютерных системах.

Исследования (М. Сюте11а а1., 1996; ДУ. Ье1ап<1 е1 а1., 1994) показали, что свойства компыотсрноготрафика кардинально отличаются от свойств трафика в «голосовых» системах, например телефонных сетях. Компьютерный трафик имеет долгую память, у распределений длин периодов занятости наблюдаются тяжелые хвосты, агрегированный процесс нагрузки является самоподобным {монофрактальным).

В таких условиях вероятность переполнения буфера с ростом его размера Л убывает не по экспоненте, как в линейных системах массового обслуживания (СМО) с марковскими потоками, а степенным образом (Б. Пввтск й а1„, 1998; Б. Цыбаков и др., 1998-2001) или по закону Вейбула (I. Моггоз, 1994). Если для эффективного обслуживания «голосового» трафика буфер в 3КБ (30 пакетов размера 100Б) более чем достаточен, вероятность переполнения в этом случае имеет порядок Ю-14, то при степенном убывании вероятности переполнения в условиях сильной загрузки даже буфер в несколько ГВ ие гарантирует для самоподобного трафика надежного обслуживания. Вероятности переполнения для самоподобного процесса с параметрами Я = 0.85 и Я = 0.6 и буфера размером 2ГБ (2 • 107 пакетов размера 100Б) по некоторым оценкам (модель Б.С. Цыбакова) имеют порядок Ю-4 и Ю-8 соответственно . Сегодня для стабильной работы СМО требуется, чтобы данная вероятность не превышала 1 • Ю-9.

СМО с самоподобным трафиком к настоящему времени хорошо изучены: для них описаны возможные предельные процессы для потоков нагрузки (Т. М1кобЬ et а!., 1998-99) и получены оценки для ряда показателей (¡>о5. Данные результаты являются важным шагом вперед в рамках анализа немарковских СМО, однако они не позволяют охватить все многообразие свойств трафика в современных условиях.

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

неоднородным. Исследования (М. Taqqu et al., 1997; A. Feldmann et al., 1998) показали, что самоподобие проявляется асимптотически, на крупных временных шкале«, а для малых периодов усреднения поведение трафика больше похоже на мультифрактал. СМО с мультифрактальными потоками изучены слабо: основной вывод из нескольких работ, посвященных моделям трафика, порождаемого неоднородными источниками, состоит в том, что свойства трафика и параметры QoS определяются источниками с самым длинным активным периодом/ «тяжелыми» заявками. Поведение трафика и параметров QoS в случае, когда «тяжелые» заявки приходят редко, а основную нагрузку порождают более «легкие» требования, практически не изучено. На первый взгляд наиболее очевидным в этой ситуации кажется определение размера буфера на основе потока с самыми «тяжелыми» заявками. Одиако необоснованное увеличение размера буфера может не оказать желаемого влияния на СМО, так так выигрыш от уменьшения потерь информации, будет нивелирован из-за увеличения стоимости сетевой аппаратуры и ее обслуживания и ухудшения других параметров QoS, например, увеличения задержки при обработке информации в большом буфере.

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

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

Для достижения этой цели в работе решены научные задачи:

1. Построены математические модели входящих потоков: неоднородная ON/OFF модель, неоднородная модель Пуассона в непрерывном и дискретном времени, длины активных периодов источников в которых имеют распределения с правильно меняющимися хвостами с различными показателями 1 < < 2, к — 1, г, г < оо. Установлены условия, при которых источники любого типа нетривиально влияют на характеристики процесса нагрузки.

2. В неоднородной ON/OFF модели в режиме «Slow Growth Condition» (SGC) найден новый предельный процесс для агрегированного процесса нагрузки.

3. Найдено асимптотическое распределение случайной суммы независимых случайных слагаемых, имеющих конечное число различных распределений.

4. Доказано, что вероятность переполнения буфера в неоднородной ON/OFF модели и неоднородной модели Пуассона в непрерывном времени и асимптотические границы для вероятностей переполнения буфера и потери пакета в неод-

неродной модели Пуассона в дискретном времени убывают степенным образом с ростом размера буфера. Найдены условия при которых скорость убывания может совпадать с любым из с№\к = 1,г.

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

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

Положения, выносимые на защиту.

1. Модели входящих потоков, построенные с учетом того, что доли источников разных типов в общем потоке различны.

-2^Д.симдтотическос^расиределение случайной суммы независимых случайных величин, имеющих конечное число разных распределений^ найденное-с помощью сведения суммы со случайным числом слагаемых к сумме с неслучайным числом слагаемых.

3. Асимптотика вероятности переполнения буфера в СМО с неоднородными потоками, отражающая вклад источников разных типов.

4. Методика построения имитационной модели, основанная на использовании методов ускорения симуляции, и ее применение для уточнения константы в оценке вероятности переполнения буфера.

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

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

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

Апробация работы. Основные результаты работы докладывались на международном семинаре по проблемам устойчивости стохастических моделей (г. Юрмала, Латвия, 2004), (Салерно, Италия, 2005), на конференции «Ломоносовские чтения» (г. Москва, МГУ, 2005), на 31 международной конференции по стохастическим процессам и их применениям (г. Париж, Франция, 2006), на 5 международной конференции по процессам Леви (г. Копенгаген, Дания, 2007), на 13 Всероссийской школе-коллоквиуме по стохастическим методам (г. Йошкар-Ола, 2007), на научно-практической конференции «Моделирование и принятие решений в условиях неопределенности» (г. Тверь, ТвГУ, 2008).

Публикации. По материалам диссертации опубликовано 12 работ, среди них — 3 в изданиях рекомендованных ВАК Минобрнауки России.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 155 листах, содержит 17 рисунков, 3 таблицы и список литературы, включающий 83 на-" именования.

Краткое содержание работы

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

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

В параграфе 1 описывается объект исследования и объясняются причины самоподобия трафика в современных системах связи.

В работе рассматривается некоторая цифровая сеть связи, состоящая из одного сервера (обслуживающего прибора, канала), па который поступает нагрузка от других узлов сети — пользователей. Предполагается, что сервер имеет буфер конечного размера, что является типичной ситуацией для современной системы связи в условиях сильной загрузки. Подобная модель рассматривается в литературе как базовая математическая модель маршрутизатора или коммутатора (T. Neam, 2003), которая позволяет с достаточной степенью точности воспроизводить реальные процессы и, что очень ражко, является доступ- ' ной для анализа даже в случае потоков нагрузки с очень сложной структурой.

В цифровых системах все сообщения разбиваются на небольшие части — пакеты, каждый из которых передается получателю, где они вновь собираются в цслыюе сообщение. Мы не интересуемся конкретной природой передаваемой информации и процессом ее разбиения на пакеты. Исходная информация — поток пакетов, которые обычно сбиваются в так называемые «пачки». Потоки таких пачек между узлами связи называют трафиком телекоммуникационной системы в этой области здания. В реальных системах в зависимости от технологии передачи информации длина пакетов может колебаться от 4Б до 1500В. Мы рассматриваем стандартные пакеты, то есть одинаковые в смысле длины и времени обработки, которое с достаточной степенью точности можно считать неслучайной константой. Примером такой системы является сеть с технологией асинхронной передачи данных (ATM), в которой все пакеты имеют одинаковый размер 53Б и постоянное время обслуживания.

В параграфе 2 даются определения процессов с короткой и длинной памятью, раепределенийстяжельши-хвостами,-строго. самоподобных, самоподоб-н ых в широком смысле и асимптотически самоподобных процессов непрерывного и дискретного аргумента. Приводятся определения дробного броуновского движения и a-устойчивого движения Леви, 0 < а < 2.

Определение 1. Случайный процесс X = (A'(í), t > 0} называется самоподобным, если для любого а > 0 существует 6 > 0, такое что X(at) = 6HX{t).

Для невырожденного, стохастически непрерывного при t = 0 самоподобного процесса X, такого что п.н. Х(0) = 0 существует единственное число H > 0, для которого b = а . Следовательно, в этом случае, X(at) = a"X(t).

Пусть случайный процесс X имеет стационарные приращения с конечной дисперсией а2- Ковариационная функция n¡(t,s) = cov{X(t),X(s}) процесса X имеет вид

7(i, s) = 1/2 • ст2 (t2li 4- s2íí — (t — s)211), s <t, 0<Я<1. (1)

Принимая во внимание цифровой и пакетный характер современных сетей связи, также будем рассматривать процессы с дискретным временем. Ковариационная и корреляционная функции процесса приращений {£(n) = Х(п + 1) — Х(п)}„=о,1,2,... при п > 0 будут равны соответственно

7 (п) = ~[(г,+ 1)2И-2п2Я + (п-1)2И], р(п) = r¿{(n+lf"-2n™ + (n-A)™), При тг < 0 мы имеем 7(п) — 7(—п), р(п) = р(—п). Заметим, что при п —+ оо

р(п) ~ Н(2Н — 1)п2П~2 = с • 0 < /3 = 2 — 2Н < 1. (2)

Определение 2. Говорят, что процесс X имеет долгую память, если p(n) ~ п-Р ■ L(n), 0 < /3 = 2 — 2H < 1, где функция L(n) медленно меняется на бесконечности. Процесс X имеет короткую память, если р(п) ~ • L(n) 1 < /3 < 2; л —» со или если существуют постоянные 0<а<1к0<Ь<оо такие, что |р(п)| < Ьап, п—юо.

Пусть ХИ = {Xt(ra) : i е iV}, где Xt(m) = m"1 ■ (Xtm_m+i + ... + Xtm) то = 1,2,... это усредненный по блокам длины ш (агрегированный) случайный процесс X. Обозначим через рш(к) коэффициент корреляции процесса ХМ.

Определение 3. Процесс X называется строго самоподобным в широком смысле с параметром 0 < Н < 1, если для любых к € N имеет место Рт(к) = 1/2 • [(к + I)2-" - 2к*-? + (к - I)2""] := д(к).

Определение 4. Процесс Jf называется асимптотически самоподобным в широком смысле с параметром 0 < Н < 1, если lim pm(k) = g(k), к е N.

т—»оо

Примерами самоподобных процессов являются дробное броуновское движение и а-устойчивое движение Леви.

Определение 5. Непрерывный гауссовский процесс (i?//(i), t > 0) с нулевым средним и дисперсией а1 = £|В//(1)|2 называется дробным броуновским движением с показателем 0 < Н < 1, если его ковариационная функция имеет вид 7(i, s) = 1/2 • а2 {<2Я + s2H - |t - s|2H}.

Bjj(t) — самоподобный процесс с показателем Н. Если Н = 1/2, то Вц{£) есть обычный винеровский процесс.

Определение 6. Случайный процесс (X(t), t > 0) называется процессом Леей, если выполнены условия: 1) Х(0) = 0 п.н.; 2) X(t) — процесс с независимыми и однородными приращениями; 3) X(t) — стохастически непрерывен; 4) траектории X(t) непрерывны справа и имеют конечные пределы слева при t >0.

Определение 7. Случайный процесс Xa<aß(t), X > 0, где а е (0,2], 0 € [—1,1], а > 0 называется а-устойчивым движением Леви, если он имеет независимые и стационарные приращения с а-устойчивым распределением.

а-устойчивое движение Леви — самоподобый процесс с параметром Н = 1 /а. При а = 2 мы имеем броуновское движение. Для 0 < а < 2 вторые моменты процесса X бесконечны.

Определение 8. Случайная величина Z имеет распределение с тяжелым хвостом, если P{Z > х) ~ с • х~а, х —► оо, где с > 0 — некоторая постоянная, 0 < а < 2 — параметр формы распределения.

Если 0 < а < 1, то E(Z) = оо, D(Z) = оо, если 1 < а < 2, то E(Z) < оо и D(Z) = оо.

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

Наиболее известными моделями, приводящими к самоподобному потоку являются однородные ON/OFF модель и модель Пуассона с бесконечным числом источников, которые рассматривались в работе Т. Микоша (Mikosch Т., Resnick S., Rootzen Н., Stegeman A. Is network traffic approximated by stable L6vy motion or fractional broumian motion?. Ann. Appl. Probab., 12(1), 2002, pp. 2368). Их отличительная особенность — наличие тяжелых хвостов у распределений длин периодов занятости/покоя в ON/OFF модели и длин сообщений

в модели Пуассона. В рамках данных моделей было показано, что предельными процессами для агрегированных потоков нагрузки в режимах «Fast Grows Condition» (FGC) и «Slow Growth Condition» (SGC) являются соответственно дробное броуновское движение и »-устойчивое движение Леви с 1 < а < 2. Дробное броуновское движение — самоподобный процесс с долгой памятью, процесс Леви — самоподобный процесс с независимыми приращениями, то есть с короткой памятью. B.C. Цыбаковым (Tsybakov В., Georganas N. D. Overflow 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 < г < оо различных типов. Каждый источник генерирует пакеты с постоянной скоростью и > 1 в течение своего ON периода, в течение OFF периода и = 0. Иными словами, это процесс восстановления, порожденный чередованием ON/OFF периодов.

Для любого к = Т/г длины Х&\ х[к),х£\... и ON и

OFF периодов есть независимые с.в., независимые друг от друга, имеющие соответственно распределения и F^ с правильно меняющимися хвостами, то есть:

F[k\x) = x'^L^ix), F^k)(x) = х~а<^ L(k]{x), х>0, (3)

где a, а^ € (1,2), а^ < а^' и есть медленно меняющиеся на бес-

(к) ffc)

конечности функции. Заметим, что распределения F^ и ij имеют конечные средние ¡¿^ и но их дисперсии — бесконечны. Положим = + ¡х^.

Для любого к = 1,г н п > 1 определим стационарную последовательность восстановлений {Т,^} по правилу:

Tlk) = + + (4)

где взаимонезависимые с.в. В(к\ (о)> ^о// (о) не зависят 011

C.B.

имеет распределение Бернулли с

а ^оп(О) И

У«(0) есть с.в. с функциями распределения Fj^(x) = l/ц^ I F$k\s)ds и

fX

Р2%)(х) = 1/$) / H\s)ds соответственно.

ON/OFF процесс для одного источника типа к имеет вид:

Для любого fc с.в. W^ = и, если i попадает на ON-период и = 0 иначе. Процесс к = 1, г строго стационарен со средним E(W^) = и ■ /4*'//^ и ковариациошюй функцией (s) ~ cs_Qi при s —» оо. Таким обра-

зом процесс

имеет долгую память. Интенсивность входящего потока для сервера в момент f > О (число ак-

г мм ...

тивных источпиков) равна iV(f) = Nm{Î) — J2 J2 Wt я»> гДе -M»" есть число

fc=l m=l

появлений распределения fc-ro типа среди M = А/^ первых членов после-

*=1

дователыюсти процессов W^.

Определим полную входящую работу к моменту времени t

A(t) = A(M,t) = f* N(s)ds, t> 0 (6)

J о

и семейство агрегированных процессов нагрузки

А(М, T, t) := А(М,Т ■ t), Т> 0. (7)

Пусть < с42) < ... < а(хг), и М<кЦТ) оо при Т оо для всех к. Непрерывная слева обобщенная обратная к функции l/Fj^ функция b«(f) = inf{a: > 0 : 1/Р[к)(х) > t}

правильно меняется с показателем l/a®, следовательно b^(t) = f1/«'*''. Lo(t), где L$(t) — медленно меняющаяся функция. Далее рассматривается только случай SGC: Ь^к\М^к\Т)Т)/Т -* 0. Определим целочисленные функции М^к\Т) по правилу: при Т —► оо

1 > T-[LW(6M(MT)] ' С >U' '

М(г\т) = М(Т) - М(1\т) - ... - M^-V. (8)

В этом случае ММ/М(Г)

—» 1, М№(Т)/М(Т) —+ 0, к < г при Т —* оо. Ставится задача нахождения предельного распределения для процесса агрегированной нагрузки A(M,Tt) при Т —» оо и М^(Т) —* оо, описанным выше способом.

Справедлива следующая Теорема 1. Если

и F^ удовлетворяют условию (3) и режим SGC выполняется для всех к и определенных в (8), то при некоторой нор-

мировке предельный процесс для А(М, Tt) существует и является суммой независимых устойчивых движений Леви с показателями а^ < а^ < ... < а^.

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

Пусть ] > 1) есть последовательность н.о.р.с.в., функции распре-

деления < х) которых принадлежат множеству Т -

состоящему из 2 < г < оо разных распределений. Обозначим через пг^(п) число слагаемых в сумме, имеющих распределение Предположим, что последовательности {Х^'} независимы для всех к = 1,г и Цк = Е(Х^) < оо. Допустим также, что существует последовательность положительных чисел Вп такая, что Вп —► оо, п —» оо и

г т* *=1j=l

~гдё~У — невырожденная спв.с-распределепиемС.- Мы. рассматриваем.случай, когда распределение С есть свертка г устойчивых законов с разными индексами а(кК

Пусть {Л«1'},..., {А^} есть независимые последовательности положительных целочисленных с.в., определенных на том же вероятностном пространстве, что и (Х^) и, возможно, зависимых от них.

Положим

г

= В'1 - тк ■ м)) = Тп + ип, (10)

к=1 >=1

г

Тп = в-1 £ - м); им = - шк) ■ ы = ^ СИ) *=1 }=1 к=1

Основной результат данного параграфа представлен в виде теоремы 2.

Теорема 2. Если //*> ф 0 и [Л*>, п -> оо, А; = 17?, г/ = £ 1/<-к\

4=1

тогда п оо и с.в. Z допускает представление 2 = У + и, где У п II

независимы.

Полученный результат обобщает выводы из работы Е. В. Рыбко (Рыбко Е. В. Асимптотические свойства случайных сумм независимых случайных величин. — Канд. дисс. М.: МГУ, 1994, 139 с.)

Третья глава посвящена анализу характеристик (¿ов в СМО с самоподобными и мультифрактальными входящими потоками.

В параграфе 1 приводятся примеры основных характеристик (¿оБ.

Эффективное обслуживание трафика не возможно без учета его свойств. Однако сложная структура и высокая неоднородность в плане требований к параметрам сети современных потоков данных способны неограниченно расширить круг «главных» характеристик (¿оБ. Поэтому проектировщики систем

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

В параграфе 2 сравнивается асимптотическое поведение вероятности переполнения буфера в моделях с марковскими и самоподобными (дробное броуновское движение и а-устойчивый процесс Леви) входящими потоками. Также рассматриваются верхние и нижние асимптотические границы для вероятностей переполнения буфера и потери пакета, полученные Б.С. Цыбаковым для СМО с асимпотически самоподобным трафиком.

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

ON/OFF модель с неоднородными источниками. Рассматривается СМО, имеющая буфер размера h < оо, на вход которой поступает поток Wt, порождаемый одним источником, попеременно находящимся в ON и OFF состоянии. Структура рассматриваемого потока определена в (5). Длина X* активного периода имеет распределение

г г

Fi = J2 aW(t) ' Fik) = M(k\T)/M{T) • F[k). (12)

*=i Jt=i

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

Ставится задача нахождения асимптотики для вероятности переполнения буфера в рассматриваемой СМО.

Обозначим через Z(t) и Ап = (г — 1) - величины заполнения буфера в момент t ив течение тг-го активного периода соответственно. Тогда величины {Wn = Z(T„), n > 1}, где {Tn, n > 0} есть определенный в (4) стационарный процесс восстановления, удовлетворяют уравнению Линдли: W„+1 = [Wn + А„- У„(4)]+, где (*)+ = max(0,x).

Обозначим mi = mi(T) - М(А„), т2 = m2(T) = M(F„W). Известно, что если mi/шг < 1, то Wn => W при п —» оо, причем с.в. W имеет распределение

оо

P{W > ас) = (1 - б) • Е вк ■ P(Vx + ... + Vfc > х), где (V*, к>1) есть носледо-к=1

вательность н.о.р.с.в. — «возрастающих лестничных высот», построенных по последовательности (Ап — м > 1), и 0 < 0 < 1.

Основной результат для данной модели представлен в виде теоремы 3.

Теорема 3. Если хвосты распределений F^ и F^ удовлетворяют условию (3), а величины выбраны по правилу (8), то справедливо соотношение

P{W > h) ~ (1 - в)/в ■ P(V1 > h) ~ (1 - в)/в - h~ai)+1 • L(*\h), Л - оо, (13)

где L,(')(x) есть медленно меняющаяся на бесконечности функция.

Выбирая подходящим образом частоты МЮ/М появления активных периодов с разными распределениями, можно получить скорость убывания вероятности переполнения с любым показателем к — 1, г (в данном случае с

Модель Пуассона с неоднородными источниками. Источники подают нагрузку на один сервер, имеющий буфер размера h > 0 и скорость обслуживания т*2 = 1. В активном периоде источники генерируют пакеты со скоростью

П = 1.

Длины активных периодов есть независимые с.в., распределения которых принадлежат множеству Т = ...,F^}, состоящему из 2 < г < ой раз-

личных законов таких, что F^(x) = x~aWЬ^кЦх), к = 1 ,г, где 1 < а^ < функции Ь(кЦх) — медленно меняются на бесконечности. Число источников N(t), активных в момент t, имеет распределение Пуасс-

г

- сона с параметром, А_=_ У. Х^}, _ где_А('V А — доля распределения F^> в общем «=1

потоке.

Рассмотрим смешанное распределение

х) = (14)

X 00

Положим Fq{x) = fij} f F(y)dy, i*f ~ f xdF{x).

о о

Ставится задана нахождения асимптотика для вероятности переполнения буфера в рассматриваемой С МО.

Пусть (Xj, j > 1) это последовательность н.о.р.с.в., имеющих распре-

т

деление F, и S(t) = JZ — t. Вероятность переполнения буфера равна j=i

Pover(h) = P(supS(t) > h). t> 0

Положим h = h(T) и A^ - \(кЦТ), где T > О есть некоторый параметр. Для любого 0 <

№

< оо, к — 1,г — 1 определим доли AW(T) по правилу:

ляр, . * * л«(Г). л-|л«ет. (15,

Легко видеть, что А®(Т) —>0,А:=1,г—1и \(ТЦТ) —> А при Т —» оо. Основной результат для данной модели представлен в виде теоремы 4-Теорема 4. Если ЦТ) —» оо при Г —> оо, величины А^(Т) удовлетворяют условию (15) и А • pf < 1. то

PWer(h(T)) ~ рМ/( 1 - PW) F0(h(T)). (16)

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

Модель B.C. Цыбакова с неоднородными источниками (неоднородная модель Пуассона в дискретном времени). Рассматривается од-ноканальная СМО вида У* ¡D/C/h, функционирующая в дискретном времени, где У есть входящий поток, D — время обслуживания пакета, С — пропускная способность канала (в пакетах) и h — размер буфера (в пакетах). Пусть Zt — число пакетов в буфере в момент t. Введем класс дисциплин обслуживания D{h), такой что: 1) если Yt + Zt >0, то min{Yt + Zt, 1} пакетов попадаете канал в момент t; 2) если Yt + Zt<h +1, то ни одна ячейка не теряется в момент t; 3) если Yt+Zt> h+l,ioYt+Zt — h — l пакетов теряется в момент t. Какие пакеты обслуживаются, а какие теряются, определяется дисциплиной d е D{h) и на дальнейшие рассуждения не влияет. Пусть С = 1 и на обслуживание пакета тратится 1 единица времени.

В СМО источники могут быть 2 < г < оо разных типов. Источник типа к характеризуется своей длиной активного периода т^к\ которая имеет дискретное распределение Парето с параметром 1 < к < г:

Р(т№ = n) = 4fc)n~0,W~1, fc= lTn 1<а(1)<...а(г><2 (17)

и генерирует пакеты в активном периоде с постоянной скоростью R = 1.

Пусть с.в. {£(''}, где есть количество источников типа г, «проснувшихся» в момент t, независимы и имеют распределение Пуассона с параметрами

A= Т7г. С.в. ^ = Е также имеет распределение Пуассона с парам ет-t=i

г т t л

ром А = Е AW. Входящий поток Yt* = Е ^t ~~ суперпозиция независимых

«=1 «=1 процессов Y(k\ где с.в. есть количество активных источников типа к в

__/м

момент t. Для любого к = 1,г при фиксированном f с.в. У4 ' имеет распределение Пуассона со средним Х^Ет^. Корреляционная функция потока имеет вид: p(k\l) ~ 1 —> оо, то есть У^' есть процесс с долгой памятью.

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

Предположим, что трафик У* порождается источниками одного типа, имеющими смешанное распределение. Для этого введем с.в. и г*, распределения которых Р(£* = тп) = Е - m) и Р(т* = х) = Е dWp(r<fe> = ж) есть

Jt=l к=1

смесь распределений с.в. и т^' соответственно, взятых с весами d^.

Выберем веса следующим образом

#) = /!a(l,-«(r), dM = 1_d(i)_..._d(r-D. (18)

Легко видеть, что

d« —>0, к = 1,г — 1 и d«- 1 при h —► оо.

Ставится задача нахождения асимптотических границ для вероятностей переполнения буфера и потери пакета в системе Y*/D/l/h.

Справедлива следующая

Теорема 5. В модели Y*/D/\/h для вероятностей переполнения буфера и потери пакета в стационарном режиме при h —► оо верны асимптотические границы:

С! • h-aM+1 < Pover < С2 • h-aM+\ h ■ < Ploa, < b2 • Г«"'«, (19)

где

1 r x r /.W c,=_I_V_is_ c, =_2_У °o

1 + 2 (1-A£TM)^qW(QW-1)'

(20)

1 (irW+^'+i^aWtaW-l)' 2 (1 - АЯтМ) ^ a«(a№ - 1)'

(21)

и Як = [1 - e-*]-1 - 1.

Варьируя доли источников разных типов в общем потоке, можно показать, что любой из них нетривиально влияет на вероятности~переполнения буфе-_ ра и потери пакета. Данные границы обобщают результаты B.C. Цыбакова, полученные для однородного случая (г = 1).

В четвертой главе описывается имитационная модель для СМО Y*/D/l/h и анализируется качество оценок для вероятности переполнения буфера.

В параграфе 1 обоснована необходимость применения имитационного моделирования для изучения свойств оценок вероятностей переполнения буфера в модели Цыбакова B.C. с неоднородными источниками.

Во-первых константы с\ и сг в оценках вероятности переполнения буфера могут различаться в десятки и сотни раз. Так например, для СМО с параметрами {<*« = 1.1, а<2> = 1.3, а<3> = 1.5; Л = 0.5} и {а™ = 1.1, а<2> = 1.8; Л = 0.4} соотношения констант составят С2/С1 = 428.86 и ¿2/С1 = 43.895 соответственно. Во-вторых эти оценки являются асимптотическими и нет точного указания на то, начиная с каких значений Л интервал [с\, сг] является адекватным. Поэтому нас интересует для каких h «истинная» константа Cover = Pover/h~a+1 попадает в указанные границы и где именно она располагается в интервале [ci, Сг]. Для этого необходимо найти «истинную» константу в предложенной асимптотике и сравнить ее с граничными значениями. Для уточнения значения константы в среде Matlab была разработана имитационная модель системы Y*/D/1/h.

В параграфе 2 обосновывается невозможность применения стандартного метода Монте-Карло (ММК) дая анализа редких событий и описывается метод ускоренной симуляции, используемый в данной имитационной модели.

Для надежной работы современных систем связи вероятность потери информации должна быть мала. Событие А, вероятность которого у « 0 называют редким.

Несмещенной оценкой вероятности 7 по ММК будет величина п

7мс = S 6 А), где Х\,Х%, • ■ ■ ,Хп есть п независимых траекторий 1

изучаемой системы. При 7 —► 0 относительная ошибка оценки ВЕ{умс) = (п7)~1/Г2 • л/i — 7 и (717)-1/2 —► оо . Кроме того, пусть например, 7 = Ю-9, тогда минимальное число траекторий, необходимых для достижения точности г = 0.01 равно п* и (г27)-"1 и 1Q13. Этот пример показывает, что при 7 —» О требуется огромный размер выборки, и моделирование в таких условиях может занимать от нескольких часов до многих лет. Поэтому, при моделировании редких событий нужно использовать более эффективные методы, например, методы ускорения симуляции.

Пусть случайный процесс X = t > 0} с пространством состояний X и начальным значением Xq, Хо S X, описывает функционирование некоторой СМО. Будем рассматривать процесс очереди {f(Xt) = Zt,t > 0}, где Zt есть число необслуженных заявок в системе в момент t. Определим множества А = {х 6 X : f(x) > L] и В = {х е X : /(¡г) < 0}, где L = h +1 и h есть размер буфера. Положим f{X0) $ А и /(Хо) G В.

Обозначим через г л = inf{{ > 0 : Zt > L] и тв = inf{i > 0 : Zt — 0} моменты первого попадания в область А и первого возвращения в область В. С.в. тд также есть длина цикла регенерации.

Вероятность 7(L) переполнения буфера на 1 цикле регенерации равна 7(L) = Р(тл <тв) = Р( max {Zt} > L).

0<t<TB

Вероятность 7s(L) переполнения буфера в стационарном режиме определяется по формуле: 7s(L) = lim P(Zt > L) = 7(b) £(Т|Г > 0)/£(тв)), где T

t—»оо

— время, в течение которого буфер был переполнен.

В настоящее время для моделирования редких событий, широко применяется метод расщепления. Метод заключается в разбиении пространства состояний изучаемого процесса на непересекающиеся области Дь, таким образом, что достижение области D^ из области Dk-i не является редким событием. Траектория достигнувшая новой области, расщепляется на несколько копий, которые развиваются дальше вместе с основной траекторией, и, таким образом, увеличивается вероятность достижения множества А. Границы {Li : 0 = Lo < L\ < ... < Lm - L} областей называются уровнями или порогами. Между порогами моделирование осуществляется согласно обычному ММК.

Оценка вероятностипереполнения в цикле строится по правилу:

7(L) = П р* = Rx/No ■ Да/Ni • • • ■ ' JW^m-i, fc=1

где Rk есть число траекторий, стартовавших из D^-i и достигших D^, N¡■-1 > Rk-i — общее число траекторий, стартовавших на уровне D^-i, Pk = Rk/Nk-i — оценка условной вероятности рь = P(Dk\Dk~i).

Обозначим через ETi, Et и ET оценки для среднего времени переполнения, средней длины цикла регенерации и величины Е(Т\Т > 0) соответственно.

Тогда

7s(L) = ETl/Et = Щ) ■ ЕТ/Ет.

Для получения оценки ETl = 7(L) ■ ET в метод расщепления добавим еще один шаг, на котором будем оценивать время переполпения, вместо условной вероятности достижения следующего уровня.

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

Основная проблема при реализации метода расщепления заключается в определении числа уровней т и порогов Li, г = 1,то— 1. Оптимальный выбор параметров (М. Garvels, 2000) возможен лишь в СМО вида М/М/1, когда для 7 можно получить аналитическое решение. В общем случае задать априори параметры метода невозможно. В нашей модели пороги определяются рекурсивно (F. Ccrou et al., 2005) по максимальным (минимальным) значениям процесса очереди, достигнутым иа траекториях системы на каждом шаге. Траектории, -нсдостигнувшис текущего пороганслу_чайным образом замещаются на одну из

«удачных» траекторий. Моделирование продолжается до достижения уровня L = h + 2 (Lo = 0). Такой алгоритм обычно не дает оптимальные число и значения порогов, но позволяет учитывать при их выборе свойства изучаемой системы.

В параграфе 3 описывается имитационная модель системы Y*/D/1/h и приводятся результаты ее численного моделирования.

На рисунке 1 приведены оценки констант для вероятности переполнения буфера в системе Y*/D/l/h при некоторых значениях исходных параметров. Нижняя с/от, и верхняя copper горизонтальные линии соответствуют теоретическим границам ci и сг для «истинной» константы стеТ-

Constant for mod «I: afchaj=1.1.apfta_2=1 А. Iarnbd3=0 5, (arrDda-6tau_3=0.76

Conttantfor model: tlphaj =12. alpba_2=1.5. alpha_3=17.tambda0 45. ¡ámbda-EtauJ3=0 73

UM) 13.30

1зоо

I IM ИЗО 1030 040

SI» 0.« _ 7.70

I im

о 030

¿3 SM

UW оо чэ я s 3 2 2 i i "—

-e-c_tow -»-cjffer ^-с over

<00 tooo 3M0 «00

butlwsiz*

7 JO 7 Ой 630 too

400 420 ¡ 330 seo 2.10 140 070 ОНО

Г» р § 1 5 1 i о * 1 *

-e-cjovv -»-c_upper -♦-с over

600 IODO 3900 9ttn ШО

birffer size

Рис. 1: Константа в оценке вероятности переполнения для систем с {а'1' = 1.1,а'2' = 1.8; А = 0.5} и {а(1> = Х.2, а<2> = 1.3, а<3> = 1.5;А = 0.45}

Моделирование показывает, что в области значений параметра Л, при которых величина загрузки р = XErМ > 0.7, оценка константы сотег лежит в интервале [ci,C2] ближе к нижней границе при любых рассмотренных h. При р <0.7 справедлива только верхняя граница для <Wr- В этой области значений

параметров для нижняя граница для вероятности переполнения не достигается, по-крайней мере для конечных Л.

В заключении приведен обзор результатов, полученных в данной работе.

1) Построены новые модели трафика, порождаемого источниками, длины активных периодов которых имеют распределения с разной степенью «тяжести» хвоста е (1,2), к = 1,г.

2) Для процесса нагрузки в неоднородной ON/OFF модели в режиме SGC получен новый предельный процесс, являющийся суммой независимых а-устойчивых движений Леви с разными показателями aSk\k — 1,г .

3) Найдено асимптотическое распределение случайной суммы независимых с.в., распределения которых принадлежат конечному множеству Tq, состоящему из г различных законов. Данный результат применен при нахождения предельного распределения процесса нагрузки в неоднородной ON/OFF модели.

4) В неоднородных ON/OFF модели, модели Пуассона и в непреывном и дискретном времени найдена асимптотика/асимптотические границы для вероятности переполнения буфера и указаны условия, при которых каждый источник может нетривиально влиять на эту вероятность. Показало, что вероятность переполнения буфера с ростом его размера убывает степенным образом.

5) С помощью имитационной модели системы Y*/D/l/h проведено уточнение константы в оценке вероятности переполнения буфера в неоднородной модели Пуассона в дискретном времени.

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

Публикации по теме диссертации в изданиях, рекомендованных ВАК России:

1. Сидорова О.И., Хохлов Ю.С. Уточнение константы задаче оценки вероятности переполнения буфера. — Вестник ТвГУ, сер. Прикл. матем., 27(55), вып. 7, 2007, с. 51-60.

2. Сидорова О.И., Хохлов Ю.С. Вероятность переполнения буфера в модели с различными распределениями длины активных периодов. — Обозрение прикл. и пром. математики, т. 14, вып. 1, 2007, с. 78-79.

3. Сидорова О. И. Верхняя и нижняя границы для вероятности потери пакета и вероятности переполнения буфера в модели с неоднородными источниками. — Вестник ТвГУ, сер. Прикл. матем., 35(95), вып. 4(11), 2008, с. 53-61.

в других изданиях:

1. Хохлов Ю.С., Сидорова О.И. Аппроксимация вероятности переполнения буфера для случая различных распределений длины активных периодов. — Сложные системы: Обр. инф., моделир. и оптим.: Сб. пауч. тр.. Тверь, 2004, вып. 2, с. 68-77.

2. D'Apice С., Khokhlov Yu.S., Manzo R., Sidorova О. I. Approximation о/ network traffic by pseudostable Levy motion. — Trans, of the XXIV International Seminar on Stability Problems for Stoch. Models, Jurmala, Latvia, Sept. 10-17,

2004, pp. 178-184.

3. Галактионова O.B., Жукова E.A., Сидорова О.И. Границы для вероятности переполнения буфера сервера в случае конечного числа различных распределений активных периодов. — Межд. конф. студ. и аспир. «Ломоносов-2005».

4. D'Apice С., Khokhlov Yu. S., Sidorova O.I. Bounds to buffer-overflow probability in the case of different distributions of system active periods. — Trans, of The-5th St.-Petersb.-Workshop on.Simul., St._Petersb.,Jlussia, June 26-JuIy 2,

2005, pp. 223-226.

5. D'Apice C., Khokhlov Yu. S., Sidorova O.I. On an extension of class of self-similar processes. — Trams, of The XXV International Seminar on Stability Problems for Stochastic Models, Salerno, Italy, Sept. 20-24, 2005, pp. 35-38.

6. D'Apice C., Gargiulo G., Khokhlov Yu., Sidorova O. Convergence of superpositions of scaled renewal processes with finite number of different distributions. — J. Math. Sciences, vol. 132, issue 5, feb. 2006, pp. 602-609.

7. D'Apice C., Khokhlov Y., Sidorova O. Sums of selfsimilar processes as scaling limits. — Abstr. of 31st International Conference on Stochastic processes and their Application, Paris, July 17-26, 2006, pp. 82.

8. D'Apice C., Khokhlov Yu., Sidorova O. Asymptotic properties of random sums. — Trans, of 5th International Conference on Levy Processes: Theory and Applications, Copenhagen, August 13-17, 2007, pp. 68.

9. D'Apice C., Khokhlov Yu., Sidorova O., Galaktionova O.Gnedenko problem and extension of class of self-similar processes. — Trans, of the XXVI International Seminar on Stability Problems, Karmiel, Israel, October 22-26, 2007, pp. 64-76.

Технический редактор A.B. Жильцов Подписано в печать 10.04.2009. Формат 60x84 1/16. Усл. печ. л. 1,25. Тираж 100 экз. Заказ 143. Тверской Государственный университет Редакционно-издательское управление Адрес: Россия, 170100, г. Тверь, ул. Желябова, 33. Тел. РИУ: (4822) 35-60-63.

Список условных обозначений

Введение

Глава 1. Самоподобные входящие потоки.

§1. Описание объекта исследования

1.1. Системы массового обслуживания.

1.2. Технологии передачи информации в современных сетях связи

§2. Вспомогательные понятия

2.1. Самоподобные процессы и их свойства.

2.2. Распределения с тяжелыми хвостами

2.3. Дробное броуновское движение и устойчивый процесс Левн

2.4. Устойчивые распределения и самоподобные процессы

§3. Модели самоподобного трафика

3.1. ОИ/ОРР-модель входящего потока

3.2. Модель Пуассона с бесконечным числом источников.

3.3. Модель Б.С. Цыбакова

Глава 2. Новая модель входящего потока.

§1. Модель трафика с неоднородными источниками.

1.1. Задача Гнеденко

1.2. ОМ/ОРР-модель с неоднородными источниками

§2. Асимптотические свойства случайных сумм

2.1. Постановка задачи

2.2. Вспомогательные результаты

2.3. Доказательство теоремы 12.

Глава 3. Оценка качества обслуживания.

§1. Качество обслуживания в компьютерных сетях

§2. Обзор известных результатов

2.1. Модель Б.С. Цыбакова

§3. Характеристики С^ов модели с неоднородными источниками

3.1. (Ж/О-^-модель с неоднородными источниками

3.2. Модель Пуассона с неоднородными источниками

3.3. Модель Б.С. Цыбакова с неоднородными источниками

Глава 4. Уточнение константы в оценке вероятности переполнения буфера.

§1. Моделирование редких событий

1.1. Моделирование редких событий и метод Монте-Карло

1.2. Методы ускорения симуляции

§2. Метод расщепления

2.1. Вероятности переполнения буфера в цикле и в стационарном режиме

2.2. Алгоритм оценки вероятности переполнения буфера

2.3. Варианты метода расщепления.

2.4. Подбор параметров

2.4. Определение уровней

§3. Результаты моделирования

3.1. Имитационная модель

3.2. Анализ результатов

Актуальность темы. Связь является одним из важнейших компонентов инфраструктуры современного общества. Стремительно растущий спрос на услуги связи и прогресс в области современных технологии сбора, храпения, обработки и передачи информации стимулируют динамичное развитие данной отрасли. Менее чем за полтора столетия системы связи прошли путь от традиционных «голосовых» систем — телеграфных и телефонных сетей, появившихся соответственно в середине и конце XIX века, до современных цифровых систем связи, обеспечивающих передачу интегральной информации — речи, данных, видео и т.п., в рамках одной мулътисервисной сети связи.

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

Первые эксперименты но созданию компьютерных систем связи начались в 60-х годах 20 века. Изначально при проектировании таких систем стали использовать не ■коммутацию каналов, как в традиционной телефонии, а коммутацию пакетов, которая существенно изменила структуру потоков дан-пых в сети и явилась впоследствии одной из причин возникновения проблемы самоподобия трафика. В отличие от технологий передачи информации развивавшихся очень быстро, теоретическая база, на основе которой проектировались компьютерные сети, долгое время оставалась практически неизменной. Вследствие этого до середины 90-х годов 20 века оценка производительности сетей осуществлялась с помощью стандартных методик, основанных на формулах Эрланга. На заре компьютерных систем, когда они носили преимущественно локальный характер, передаваемый трафик состоял из небольших текстовых файлов, а ресурсы, требуемые для его обслуживания не являлись дефицитными, трудностей такой подход не вызывал. Однако по мере появления и развития глобальных сетей типа Интернет, экспоненциального ро-сга числа их пользователей и усложнения структуры передаваемой информации это привело к серьезной недооценке реальной нагрузки и значительному ухудшению качества обслуживания ( QoS). Примером является сбой в сети AT&T в 1990 году, когда на протяжении 9 часов она была недоступна большей части зданий Нью-Йорка, что вызвало большие финансовые потери. Требования к повышению' QoS стимулировали развитие надежных систем с высокой устойчивостью к сбоям, что, в свою очередь, резко повысило интерес к исследованию свойств нагрузки в современных компьютерных системах.

Многочисленные эмпирические исследования [24], [25], [41], [44], [55], [65[, [66], [67] показали что свойства компьютерного трафика кардинально отличаются от свойств трафика в традиционных «голосовых» системах, в том числе телефонных сетях.

В «голосовых» СМО входящие потоки хорошо аппроксимируются пуас-соновскими процессами или стационарными процессами типа ARMA, а интервалы времени между прибытиями заявок полагаются независимыми случайными величинами, имеющими распределения с легкими хвостами. В силу экспоненциального убывания корреляционной функции трафика в подобных моделях агрегированный поток при увеличении масштаба усреднения приближается по свойствам к белому шуму, то есть обладает короткой памятью. Если такой поток поступает на вход некоторой СМО, то характеристики ее производительности, в частности, вероятность переполнения буфера конечного размера, убывают экспоненциальным образом в зависимости от увеличения некоторого характерного параметра, например, размера буфера.

Компьютерный трафик имеет долгую память, у распределений длин периодов занятости/покоя наблюдаются тяжелые хвосты, агрегированный процесс нагрузки статистически выглядит одинаково пр любом масштабе усреднения, то есть является самоподобным (монофрактальньш). В таких условиях вероятность переполнения буфера с ростом его. размера Н убывает не по экспоненте, как в линейных СМО с марковскими потоками, а степенным образом [46], [45], [23] [75] — [77] или но закону Вейбула [63]. И если для эффективного обслуживания «голосового» трафика буфер в 3КБ (30 пакетов размера 100Б) более чем достаточен, вероятность переполнения в этом случае имеет порядок Ю-14, то при степенном убывании вероятности переполнения в условиях сильной загрузки даже буфер в несколько ГБ не гарантирует для самоподобного трафика надежного обслуживания. Вероятности переполнения для самоподобного процесса с параметрами' Н — 0.85 и Н = 0.6 и буфера размером 2ГБ (2 • 107 пакетов размера 100Б) по некоторым оценкам (см. например [75] —[77] ) имеют порядок 10~4 и 10~"8 соответственно. Сегодня для стабильной работы СМО требуется, чтобы данная вероятность не превышала

1 • ю-9.

СМО с самоподобным трафиком к настоящему времени хорошо изучены: построены модели, приводящие к самоиодобным процессам, для них описаны возможные предельные процессы для потоков нагрузки [60], [61], [73] и получены оценки для ряда показателей С^оЯ. Данные результаты являются важным шагом вперед в рамках анализа немарковских СМО, однако они не позволяют охватить все многообразие свойств трафика в современных условиях.

Следует отметить, что широко используемые сегодня технологии обработки информации позволяют передавать трафик с разными требованиями к параметрам С^оЯ по одному каналу, вследствие чего поток может быть крайне неоднородным. Исследования трафика в ряде систем [34], [72] подтверждают, что самоподобие проявляется асимптотически, на крупных временных шкалах, а для малых периодов усреднения поведение трафика больше похоже на мультифрактал. СМО с мультифрактальными потоками изучены слабо: основной вывод из нескольких работ, посвященных моделям трафика, порождаемого источниками с различными распределениями длин активных периодов, состоит в том, что свойства трафика и параметры С^оБ определяются источниками с самым длинным активным периодом/«тяжелыми» заявками [73]. Поведение трафика и параметров (¿оБ в случае, когда «тяжелые» заявки приходят редко, а основную нагрузку порождают более «легкие» требования, практически не изучено. На первый взгляд наиболее очевидным в этой ситуации кажется определение размера буфера на основе потока с самыми «тяжелыми» заявками. Однако необоснованное увеличение размера буфера может не оказать желаемого влияния на СМО, так так выигрыш от уменьшения потерь информации, будет нивелирован из-за увеличения стоимости сетевой аппаратуры и ее обслуживания и ухудшения других параметров С^ов, например, увеличения задержки при обработке информации в большом буфере.

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

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

Для достижения этой цели в работе решены научные задачи:

1. Построены математические модели входящих потоков: неоднородная ON/OFF-моделъ, неоднородная модель Пуассона в непрерывном и дискретном времени, длины активных периодов источников в которых имеют распределения с правильно меняющимися хвостами с различными показателями 1 < < 2, k = l,r, г < оо. Установлены условия, при которых источники любого типа нетривиально влияют на характеристики процесса нагрузки.

2. В неоднородной ON/OFF-модели в режиме «Slow Growth Condition» (SGC) найден новый предельный процесс для агрегированного процесса нагрузки.

3. Найдено асимптотическое распределение случайной суммы независимых случайных слагаемых, имеющих конечное число различных распределений.

4. Доказано, что вероятность переполнения буфера в неоднородной ON/OFF-модели п неоднородной модели Пуассона е непрерывном времени и асимптотические границы для вероятностей переполнения буфера и потери пакета в неоднородной модели Пуассона в дискретном времени убывают степенным образом с ростом размера буфера. Найдены условия при которых скорость убывания может совпадать с любым из к = 1,г.

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

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

Положения, выносимые на защиту.

1. Модели входящих потоков, построенные с учетом того, что доли источников разных типов в общем потоке различны.

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

3. Асимптотика вероятности переполнения буфера в СМО с неоднородными потоками, отражающая вклад источников разных типов.

4. Методика построения имитационной модели, основанная на использовании методов ускорения симуляции, и ее применение для уточнения константы в оценке вероятности переполнения буфера.

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

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

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

Апробация работы. Основные результаты работы докладывались на международном семинаре по проблемам устойчивости стохастических моделей (г. Юрмала, Латвия, 2004), (Салерно, Италия, 2005), на конференции «Ломоносовские чтения» (г. Москва, МГУ, 2005), па 31 международной конференции по стохастическим процессам и их применениям (г. Париж, Франция, 2006), на 5 международной конференции по процессам Леви (г. Копенгаген, Дания, 2007), на 13 Всероссийской школе-коллоквиуме по стохастическим методам (г. Йошкар-Ола, 2007), на научно-практической конференции «Моделирование и принятие решений в условиях неопределенности» (г. Тверь, ТвГУ, 2008).

Публикации. По материалам диссертации опубликовано 12 работ, среди них — 3 в изданиях рекомендованных ВАК Минобрнауки России.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 155 листах, содержит 17 рисунков, 3 таблицы и список литературы, включающий 83 наименования.

ЗАКЛЮЧЕНИЕ

1) В работе предложены три новых модели входящих потоков, распределения длин активных периодов в которых имеют конечное число Т, состоящему из г > 2 вероятностных законов, имеющих правильно меняющиеся хвосты с различными показателями скорости убывания а^ € (1, 2), к = 1, г: ОЫ/ОРР-моделъ с неоднородными источниками; неоднородная модель Пуассона с бесконечным числом источников в непрерывном времени; неоднородная модель Пуассона в дискретном времени.

2) Для процесса агрегированной нагрузки в неоднородной ОИ/ОРР-модели в режиме БйС получен новый предельный процесс, являющийся суммой независимых а-устойчивых движений Леви с показателями о^1),.,

3) Найдено асимптотическое распределение случайной суммы независимых случайных величин, распределения которых принадлежат конечному множеству ^о, состоящему из г различных законов. Данный результат применен при нахождения предельного распределения процесса нагрузки в неоднородной ОМ/ОРР- модели.

4) Доказано, что вероятность переполнения буфера в неоднородной ОЫ/ОРР-модели и неоднородной модели Пуассона в непрерывном времени и асимптотические границы для вероятностей переполнения буфера и потери пакета в неоднородной модели Пуассона в дискретном времени убывают степенным образом с ростом размера буфера. Найдены условия при которых скорость убывания может совпадать с любым из к — 1, г.

5) С помощью имитационной модели системы У* / 0/1/к проведено уточнение константы в оценке вероятности переполнения буфера в неоднородной модели Пуассона в дискретном времени.

Полученные результаты обеспечивают развитие математического аппарата теории массового обслуживания применительно к СМО с мультифракталь-ными потоками и предлагают новые методы исследования в дан 11011 области.

1. Алеыичев A.B. Система массового обслуживания с динамической маршрутизацией и распределением Вейбулла времени обслуживания. — Информационный процессы, т. 5, #5, 2005, с. 432-442.

2. Аленичев A.B., Лиханов Н. Б. Динамическая маршрутизация в системе с заявками, имеющими степенной закон распределения времени обслуживания. — Информационный процессы, т. 5, #3, 2005, с. 213-226.

3. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. — М.: Техносфера, 2003, 512 с.

4. Галактионова О.В., Жукова Е.А., Сидорова О.И. Границы для вероятности переполнения буфера сервера в случае конечного числа различных распределений активных периодов. — Международная конференция студентов и аспирантов «Ломоносов-2005».

5. Зингер A.A. Об одном классе паределеных распределений для норлшро-ванных сумм независимых случайных величии. — Теория вероятностей и ее применения, т. 10, вып. 4, 1965, с. 672-692.

6. Ибрагимов И.А., Линник Ю.В. Независимые и стационарно связанные величины . — М: Наука, 1965, 524 с.

7. Рыбко Е. В. Асимптотические свойства случайных сумм независимых случайных величин. — Кандидатская диссертация, М.: МГУ, 1994, 139 с.

8. Сидорова О.И., Хохлов Ю.С. Уточнение константы в задаче оценки вероятности переполнения буфера. — Вестник ТвГУ, серия Прикладная математика, 27(55), вып. 7, 2007, с. 51-60.

9. Сидорова О. И. Верхняя и нижняя границы для вероятности потери пакета и вероятности переполнения буфера в модели с неоднородными источниками. — Вестник ТвГУ, серия Прикладная математика, 35(95), вып. 4(11), 2008, с. 53-61.

10. Феллер В. Введение в теорию вероятностей и ее приложения, Т.2. Пер с англ. — М: Мир, 2-ое издание, 1984, 751 с.

11. Цыбаков B.C. Модель телетрафика на основе самоподобного случайного процесса. — Радиотехника, 5, 1999, с. 24-31.

12. Asmussen S. Applied probability and Queues. — Wiley, 1987.

13. Barbe Ph., McCormick W.P., Zhang C. Tail Expansions for the distritions of the maximum of a random walk with ngative drift and regularly varying increments. — http://www.arxiv.org/abs/math Pr./0604377vl.

14. Beran.J. Statistics for Long-Memory Process. Monographs on Statistics and Applied Probability. — Chapman and Hall, NY, 1994.

15. Bingham N.H., Goldie C.M., Teugels J.L. Regular Variation. — Cambridge University Press, 1987.

16. Cerou F., Gyuader A. Adaptive multilevel splitting for rare event analysis. — Tech. Rep. 5710, INRIA. Oct., 2005.

17. Borst S., Boxma O., Jelenkovic P. Generalized processor sharing with longtailed traffic sources. — In: Teletraffic Engineering in a Competitive World, P. Key and D. Smith eds., Elsevier, 1999, pp. 3451,1354.

18. Crovella M., Kim G., Park K. On the relationship between file sizes, transport protocols, and self-similar network traffic. — In: Proceedings of the Fourth International Conference on Network Protocols (ICNP'96), 1996, pp. 171-180.

19. Choudry G.L., Whitt W. Long tail buffer content distributions in broadband networks. — Performance Evaluation, 30, 1997, pp. 177-190.

20. D'Apice C., Khokhlov Yu. S., Sidorova O.I. On an extension of class of self-similar processes. — In: Transactions of The XXV International Seminar on Stability Problems for Stochastic Models, Salerno, Italy, September 20-24, 2005, pp. 35-38.

21. D'Apice C., Gargiulo G., Khokhlov Yu., Sidorova O. Convergence of superpositions of scaled renewal processes with finite number of different distributions. — J. Math. Sciences, vol. 132, issue 5, feb. 2006, pp. 602-609.

22. D'Apice C., Khokhlov Y., Sidorova O. Sums of self similar processes as scaling limits. — Abstracts of 31st International Conference on Stochastic processes and their Application, Paris, July 17-26, 2006, pp. 82.

23. D'Apice C., Khokhlov Yu., Sidorova O. Asymptotic properties of random sums. — In: Transactions of 5th International Conference on Lévy Processes: Theory and Applications, Copenhagen, August 13-17, 2007, pp. 68.

24. D'Apice C., Khokhlov Yu., Sidorova O., Galaktionova O. Gnedenko problem and extension of class of self-similar processes. — Trans, of the XXVI International Conference on Seminar on Stability Problems, Karmiel, Israel, October 22-26, 2007, pp. 64-76.

25. Garvels M.J.J. The splitting method in rare event simulation. — Thesis, University of Twente, Twente, May 2000, http://\vww.math.uttwente.nl/dos/sor/AiO's/ Garvels/Thesis

26. Glasserman P., Heidelberger P., Shaliabuddin P. and Zajic T. Multilevel splitting for estimating rare event probabilities. — Oper. Res., 47(4), 1990, pp. 585-600.

27. Goldie C. M., Klüpelbeg C. Subexponential Distributions. — In: Practical Guide to Heavy Tails: Statistical Tehniques for Analysing Heavy Tails, 1997, Birkhauser, Basel.

28. Gorg C., Shreiber F. The RESTART/LRE method for rare event simulation. — In: Proced. of the 1996 Winter Simulation Conference, 1996, pp. 390-397.

29. Gorg C., Lamers E., Fus O., Hegard P. Rare event simulation. — Computer Systems and Telmatics, Norwegian Instiute of Tehnolgy, Teh. Rep. COST 257, 2001.

30. Guerin C.A., Nyberg H., Perin O., Resnick S., Rootzén H., Starica C. Empirical testing of the infinite sourse Poisson data traffic model. — Stochastic models, 19, 2003, pp. 151-200.

31. Gut A. Stopped random walks: Limits Theorems and Applications. — Springer Verlag, NY, 1988.

32. Jain R. Congestion control and traffic management in ATM networks: recent advances and survey. — Computer Networks and ISDN Systems, 28(13), February 1995, pp. 1723-1738

33. Jagerman D. L., Melamed B., Willinger W. Stochastic modelling of traffic processes. — In: Frontiers in Queuing: Models, Methods and Problems, J. Dshalalow ed., CRC Press Boca.aton, pp. 271-310.

34. Heath D., Resnick S., Samorodnitsky G. Patterns of buffer overflow in class of queues with long memory in the input stream. — Ann. Appl. Probab., 7(4), 1997, pp. 1021-1057.

35. Heath D., Resnick S., Samorodnitsky G. Heavy tails and long range dependence in on/off processes and associate fluid models. — Math. Oper. res., 23(1), 1998, pp. 125-165.

36. Heegard P.E. A survey of Speed-up simulation techniques. — Workshop tutorial on Rare Event Simulation, Aahen, Germany, 1997.

37. Heidelberger P. Fast simulation of rare events in queieng and relaiblity models. — Performance Evaluation of Computers and Comuniations Systems Springer-Verlag, LN in Computer Sci., Vol. 729, 193, pp. 165-20.

38. Kalashnikov V. Bounds for ruin probabilities in the presence of large claims and their comparison. — Noth American Actuaial Journal, Vol.3, #2, 1999, pp. 116-129.

39. Khokhlov Yu. S., Sidorova O.I. Pseudostable Levy motion as a model of network traffic. — In: VI International Congress on Mathematical Modelling, Nizhny Novgorod, September 20-26, 2004. Book of Abstracts, p. 250.

40. Krunz M. M., Makowski A. M. A source m.odel for VBR video traffic based on M/G/oo input processes. — In Proceedings of IEEE Infocom'98, 1998.

41. Laghoux A. Rare event similation. — PEIS, 2005, http://www.lsp.ups-tlse.fr/FP/Lagnoux/

42. Laghoux Renaudie A. Effective branching splitting method under cost constraint. — Submitted to Stochastic Processes and their Aplication, October 17, 2007.

43. L'Ecuyer P., Demers V., Tuffin B. Splitng for rare event simulation. — In: Proceedings of the 2006 Winter Simulation Conference, 2006.

44. Leland W., Taqqu W., Willinger W., Wilson D. On the self similar nature of the Ethernet traffic (extended version). — In: IEEE/ACM Transactions oil Networking, 2, 1994, pp. 1-15.

45. Likhanov N., Tsybakov B. Georganas N. D. Analysis of an ATM buffer with self similar («fractal») input traffic. — In: Poceedings of the 14 Annual IEEE/INFOCOM, 2, 1995. pp. 985-992.

46. Likhanov N., Mazumdar R. R. Cell loss aymptotis in buffers fed by hetrogenous long-tailed sourses. — Proceedings of the IEEE INFOCOM Conference, Tel-Aviv, Israel, Mar. 26-30, 2000.

47. Likhanov N., Mazumdar R. R., Ozturk 0. Large Buffer Asymptotics for fluid queues with heterogeneous M/G/oo Weibullian inputs. — Oueueing Systems, #45, 2003, pp. 333-356.

48. Mason J.D. Convolutions of stable laws as limit distribution of patial sums. Ann. Math. Statist., Vol. 41, 1, 1970, pp. 101-114.

49. Mikosch T., Resnick S., Rootzen H., Stegeman A. Is network traffic approximated by stable Levy motion or fractional brownian motion? — Ann. Appl. Probab., 2002, 12(1), pp. 23-68.

50. Mikosch T., Stegeman A. The interplay betiueen heavy tails and rates in self-similar network traffic. — Technical report University of Groningen, Department of Mathematics, 1999.

51. Neam T. Characteisation and modelling of INTERNET traffic streams. — Thesis, University of Melbourne, February 2003.

52. Norros I. A storage model luith self-similar input. — Queuing Systems and Their Applications, 1994, 16, pp. 377-396.

53. Ozturk O., Mazumdar R. R., Likhanov N. Buffer occupancy asymptotics in networks with heterogeneous long-tailed inputs. — Preprint submitted to Elsevier Science, March 3, 2004.

54. Park K., Kim G., Crovella M. On the relationship between file sizes, transport protocols, and selfsimilar network traffic. — In: Proc. of IEEE International Conference on Network Protocols, 1996, pp. 171-180.

55. Resnick S.I. Adventures in Stochastics Processes. — Birkhâuser, Boston, 1992.

56. Resnick S., Samorodnitsky G. Seady-state distribution of the buffer content for M/G/oo input fluid queues. — Bernoulli, 7(2), 2001, pp. 191 210.

57. Robbins H. The asymptotic distibution of th sum of a random number of andom variables. Bull. A.M.S. 54, 1948, pp. 1151-1161.

58. Taqqu M.S., Teverovsky V., Willinger W. Estimators for long range dependence an empincal study. — Fractals 3, #4, 1995, pp. 785-798.

59. Taqqu M. S., Teverovsky V., Willinger W. Is network traffic self-similar or multifractal? — Fractals 5, 1997, pp. 63-73.

60. Taqqu M. S., Willinger W., Sherman R. Proof of a fundamental result in self-similar traffic modelling. — Computer Communications Review, 27(2), 1997, pp. 5-23.

61. Tsybakov B., Georganas N. D. On selfsimilar traffic in ATM queues: • Definitions, overflow probability bound and cell delay distribution. —

62. EE/ACM Transactions on Networking, 5(3), 1997, pp. 379-409.

63. Tsybakov B., Georganas N. D. Selfsimilar traffic and upper bounds to buffer overflow in an ATM queue. — Performance Evaluation, 36(1), 1998, pp. 5780.

64. Tsybakov B., Georganas N.D. Overflow and loss probabilities in a finite ATM buffer fed by self-similar traffic. — Queueing systems 32, 1999, pp. 233-256.

65. Tsybakov B., Georganas N. D. Overflow and losses in a network queue with a self-similar input. — Queueing systems 35, 2000, pp. 201-235

66. Tucker H.G. Convolutions of distributions attacted to stable laws. — Ann. Math. Stat., Vol. 39, #5, 1968, pp. 1381-1390.

67. Vilen-Altamirano M., Vilen-Altamirano J. RESTART: A Method for Accelerating Rare Event Simulations. — In: Proceed, of the 13-th International Teletraffic Congres, Queing, Performance and Control in ATM, 1991, pp.71-76.

68. Vilen-Altamirano M., Vilen-Altamirano J. RESTART: A Straightforward Method for Fast Simulation of Rare Events. — In: Proceed, of the 1994 Winter Simulation Confernce, 1994, pp. 282-289.

69. Willinger W., Taqqu M., Erramilli A. A bibliographical guide to self similar traffic and performance modeling for modern high - speed networks. — In: Stochastic Networks: Theory and Applicatons, 1996, pp. 339-366.

70. Willinger W., Taqu M., Sherman R., Wilson D.V. Self similarity through high variability: Statictical analysis of Ethernet LAN traffic at source level (Extended version). — IEEE/ACM TVans. on Networking, 5(1), 1997, pp. 71-86.

71. Willinger W., Paxton V. Where mathematics meets the Internet. — Notices of the AMS 45, 1998, pp. 961-970.