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

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

УДК 519.218, 519.254 48492110 ^

т

ГАЛАКТИОНОВА Ольга Владимировна

МОДЕЛИРОВАНИЕ И ОЦЕНКА ПАРАМЕТРОВ

НЕОДНОРОДНОГО ВХОДЯЩЕГО ПОТОКА В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

9 ИЮН 2011

ТВЕРЬ 2011

4849208

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

Научный руководитель доктор физико-математических наук,

профессор Хохлов Юрий Степанович

Официальные оппоненты: доктор физико-математических наук,

профессор Бенинг Владимир Евгеньевич доктор физико-математических наук, профессор Зейфман Александр Израилевич

Ведущая организация Нижегородский государственный университет

им. И.И.Лобачевского

Защита состоится 24 июня 2011 г. в 1200 часов на заседании диссертационного совета Д212.263.04 при Тверском государственном университете по адресу: 170100, г. Тверь, Садовый пер., 35, ауд. 200.

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

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

Автореферат разослан 23 мая 2011 года.

Ученый секретарь диссертационного совета доктор физико-математических наук, доцент

С.М. Дудаков

Общая характеристика работы

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

С развитием технологий изменилась и сама структура процессов, происходящих в телекоммуникационных сетях. Были выявлены новые свойства трафика: наличие самоподобной природы и долговременной зависимости исследуемого процесса. К настоящему времени показано, что самоподобной структурой обладает телетрафик в проводных сетях при работе широко распространенных протоколов Ethernet, ОКС7, VoIP, TCP, и др. Аналогичные эффекты обнаружены в сотовых телефонных сетях с коммутацией пакетов, в сетях с технологией беспроводного доступа.

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

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

Другой подход заключается в том, что трафик рассматривается как совокупность нескольких компонент, каждая из которых отражает свойства трафика некоторой группы абонентов с одинаковыми характеристиками (C.D'Apice и др.2, И.И.Цитович, И.В.Шмелев). Предполагается, что деление на компоненты осуществляется по "природе происхождения" трафика: голосовой трафик, трафик данных, видео в режиме реального времени и т.д. Компоненты такого процесса являются, как правило, статистически независимыми. Именно этот подход выбран для дальнейших исследований, поскольку такие модели способны более точно воспроизводить свойства реальпого трафика, аппроксимируя поведение неоднородного трафика и не используют гро-

1Rledi R.H., M.S.Grouse, V.Ribiero, R.G.Baraniuk. A multifractal wavelet model witti application to TCP network traffic. // IEEE Trans. Inform. Theory. - April 1996. - V. 45. -P.992-1018.

2D'Apice C., Manzo R., Khokhlov Yu., Sidirova O. Convergence of superpositions of scaled ' renewal prouesses with finile numbei of différent distributions. // J. Math. Sciences. - 2006. - V. 132, № 5. - P. 602-609.

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

В настоящее время наблюдается глобализация всех процессов. В области телекоммуникаций это отражается в том, что появились глобальные телекоммуникационные сети, в которых число абонентов достигает сотни тысяч. В связи с этим важной задачей является определение полной нагрузки на сервера в таких системах, то есть необходимо определить распределение совокупного входящего потока в телекоммуникационной системе с большим числом источников. В течении последних 20 лег эта задача является актуальной. Единого мнения, какая модель более подходит для описания предельного процесса, нет. Две основные модели: устойчивое движение Леви и дробное броуновское движение. Однако, появились практические исследования (Sarvotham S. и др.3), в которых при анализе данных между конечными устройствами, было показано, что описать весь входящий поток одной из известных моделей невозможно, поскольку в одном потоке могут присутствовать два совершенно различных типа трафика. Их называют альфа и бета компонентами процесса. Альфа-трафик состоит из относительно небольшого количества сообщений большого объема (который доминирует над всеми другими) и является чрезвычайно пульсирующим. Остаточный бета-трафик связан с передачами по узкополосным полосам связи и описывается гауссовским процессом с долговременной зависимостью. Математическая модель для описания подобного явления не предложена.

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

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

Основные задачи.Для достижения поставленной цели необходимо решить следующие научные задачи:

• предложить математическое описание класса стохастических процессов, обобщающего самоподобные процессы;

• построить математические модели неоднородного трафика;

3Sarvotham S., Riedi R.H., Baraniuk R.G. Connection-level Analysis and Modeling of Network Traffic. // ACM Internet Measurement Workshop Nov. - 2001. - P. 99-103.

• разработать алгоритм оценки параметров неоднородного процесса с долговременной зависимостью;

• разработать комплекс процедур в среде МаМаЬ для численного моделирования неоднородного трафика и оценки параметров исследуемого процесса.

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

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

• Разработка математических моделей телетрафика, объединяющие дробное броуновское движение и устойчивое движение Леви.

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

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

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

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

• при проектировании телекоммуникационных систем,

• при расчетах в конкретных системах различных параметров (таких, как размер буфера, мощность сервера, скорость соединения и др.) для выбора оптимальных режимов работы,

• для обеспечения гарантированного качества обслуживания,

• при проектировании механизмов управления соединениями. Достоверность и обоснованность научных результатов основала

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на Студенческо-аспирантской конференции "Ломоносов-2005" (МГУ, 14 апреля 2005), XXVI международном семинаре по проблемам устойчивости стохастических моделей (Совата-Баи, Румыния, Август 27 - Сентябрь 2, 2006), международной конференции "Пространство Скорохода. 50 лет спустя" (Киев, Украина, 17-23 июня, 2007), XXVII международном семинаре по проблемам устойчивости стохастических моделей (Карми-ель, Израиль, 22-26 октября, 2007), XIII международной летней конференции по вероятности и статистике (Созополь, Болгария, 22-27 июня, 2008), международной конференции по ультрасовременным телекоммуникациям (Санкт-Петербург, 12-14 октября, 2009), II международном научно-практическом конгрессе по комплексному моделированию, анализу и синтезу информационно-телекоммуникационных систем "Ультрасовременные телекоммуникации и системы управления ЮиМР-2010"(Москва, 18-20 октября, 2010), второй Российской школе-конференции для молодых ученых " Математика, информатика, их приложения и роль в образовании", (Тверь, Декабрь, 2010).

Диссертационная работа была выполнена при поддержке гранта РФФИ 06-01-00626.

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

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения и приложений. Полный объем диссертации 143 страницы текста с 8 рисунками и 5 таблицами. Список литературы содержит 87 наименований, включая публикации автора.

Содержание работы

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

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

Во втором разделе подробно рассхмотрено свойство самоподобия телетрафика. Перечислены причины самоподобия. Приведены основные определения самоподобпых процессов.

Определение 1. Стохастический процесс Y = (Y(t),t > 0) называется самоподобным, если для некоторого Н 6 Л1 и всех с> 0

{Y[ct), t>G)= (cHY{t), t >0) .

Число H называется параметром Херста этого самоподобного процесса.

Описаны основные характеристики самоподобных процессов: долговременная зависимость, параметр Херста и тяжелые хвосты распределений.

Определение 2. Говорят, что процесс X обладает долговременной зависимостью (ДВЗ) ¡long-range dependence - LRDJ, если выполняется

1х(к)~кг1>1ф),к—+оо, (1)

где 0 < /3 < 1 u Li - медленно меняюищяся на бесконечности функция, то есть Ню(_voo = 1 для всех х > 0.

Наиболее важной характеристикой самоподобного процесса является характеристика степени самоподобия - параметр Херста. Параметр Херста лежит в пределах Н € (0.5; 1) и определяет степень самоподобия процесса. Случай Н = 0.5 свидетельствует об отсутствии самоподобия, а Я = 1 определяет детерминированный характер процесса. Самоподобный процесс характеризуется значениями параметра Херста, ограниченными строгим неравенством 0.5 < Н < 1, причем, чем ближе этот параметр к единице, тем более ярко проявляются фрактальные свойства и долговременная зависимость возрастает.

Третий раздел посвящен описанию моделей телетрафика. Приведены традиционные модели телетрафика. Эти модели обладают следующими свойствами: интервалы времени между появлениями последовательных заявок независимы, распределения имеют экспоненциально убывающие хвосты, автокорреляционная функция является быстро убывающей. При описании реального трафика с долговременной зависимостью наиболее ¡популярными считаются ON/OFF-модель и модель Пуассона с бесконечным числом источников. Эти модели рассмотрены в работе Mikosch Th., Resnick S., Rootzen H., Stegeman A.Is network traffic approximated by stable Levy motion or fractional Brownian motion? // Ann. Appl.Probab , 2002, V. 12, № 1,P. 23-68. Показало, что для модели Пуассона с бесконечным числом источников асимптотическое поведение полной нагрузки (теоремы 1,2 далее) па сервер (совокупность всех сообщений из всех источников) зависит от двух условий:

Условие медленного роста (Slow Growth Condition - SGC):

b(\{T)-T)

----► 0 , T —> oo . (2)

Условие быстрого роста (Fast Growth Condition - FGC):

тт)-т)

----oo , 1 ■ oo . (3)

7

Здесь Х(Т) - интенсивность появления сообщения источников, Т - параметр агрегирования процесса.

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

Определение 3. Стохастический процесс В{[ = > 0) назы-

вается дробным броуновским движением с параметром Херста Н тогда и только тогда это гауссовский процесс с нулевым средним Вн№), t > 0 с независимыми приращениями , если он имеет ковариационной функцией вида:

Определение 4. Стохастический процесс 8а = (За(1),1 > 0) называется а-устойчивым движением Леви если:

• 5а(0) = 0 п.п.;

• 5а имеет независимые и стационарные приращения;

• приращения Ба имеют а-устойчивое распределение;

• Ба стохастически непрерывен при любом Ь > 0;

• траектории 5а непрерывны справа и имеют пределы слева п.н.

Теорема 1.3.1 Предположим, что для процесса Вт(Ь), описывающего полную нагрузку на сервер, выполнено условие медленного роста. В этом случае выполняется следующая сходимость:

где > 0) есть а-устойчивое движение Леви.

Теорема 1.3.2 Предположим, что для процесса Вт(1), описывающего полную нагрузку на сервер, выполнено условие быстрого роста. В этом случае выполняется следующая сходимость:

где (£?#(£),< > 0) - стандартное дробное броуновское движение;

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

Щ,а) = Е{Вн№н(8)) = ^(|*|2Я + И2Н - - для <7Н > о, Я € (0,1).

Рассмотрим следующую ситуацию. Пусть мы имеем г независимых стохастических процессов (Xj(t),t > 0), j = 1,г, действительную функцию (Л(А),А > 0) такую, что Л(А) > 0, Л(А) /" оо при А /* оо, и действительные функции Cj(A), j = 1,г, такие, что для всех j Cj(А) > 0, с_,(А) у оо при А У оо, Ci(A) +... +Сг(А) = А. Примем, что имеет место следующая сходимость Х1(с1(Л)0+...+Хг(сг(А)0

Щ ^V{t)' {4)

при А —> оо.

Нам необходимо описать класс предельных стохастических процессов Y = (Y(t),t> 0) в (4).

В этом случае справедлив следующий результат:

Теорема 2.1.3 Положим, что стохастический процесс Y = (Y(t),t > 0) есть непрерывным по вероятности при t = 0 и распределение Y(t) невырождено для каждого t > 0. Тогда Y есть предельный процесс в схеме (4) тогда и только тогда, когда существуют независимые стохастические процессы (Zi(t),t >0), ... , (Zk(t),t > 0), к < г, действительные функции Ь(А), fyW, j = 1, к, А > 0, такие что

• bj(\)> о, ЕМА) = А, А > о,

j=l

• bj(\) / оо, А / оо,

• 6(А) > О, 6(А) / оо, А / оо, и следующее представление

1)~ Ь{ А)

выполняется для всех А > 0.

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

Теорема 2.1.4 Если предельный процесс Y в (4) есть сумма независимых самоподобных процессов Yj с различными параметрами Херста Hj, j = 1 ,г, тогда после перестановки индексов X мы имеем Xj 6 D(Yj,Hj),

j = 17?.

Теорема 2.1.5 Предельный процесс Y в (4) есть сумма независимых самоподобных процессов Yj с параметрами Херста Hj, 0 < Нг < ... < Hj < 1, j = 1,... ,г, тогда и только тогда, когда

• Xj £ D(Yj, Hj) с нормализующей функцией Л,(А), j = 1,..., г,

• lim cv(A)/A = 1,

А—юо

. lim Л;(сДА))М;(с,-(А)) = Рф

А—»оо

О < Pij < оо, Vi, j = 1,..., г. В этом случае нормализующая функция Л(А) может быть выбрана равной АГ(А).

9

Здесь X е D(Y, Н) означает, что процесс X принадлежит области притяжения самоподобного процесса Y.

Определение 5. Стохастический процесс Z = (Z(t),t > 0) называется псевдосамоподобным, если следующее представление

7(г, d Zl(bl(\)t) + ... + Zk(bkWt)

т=-щ ' (5)

выполняется для всех Л > 0, где

• стохастические процессы Zk, независимы,

• b{\) > 0, bj{X) > 0, £ bj(X) = А, А > 0,

j=i

• 6(A) /" оо, bj(X) /" оо, А / оо,

4) для любого фиксированного m,j ut множество с.в. {Zrn(bj(X)-t)/Ь(Х)} стохастически компактно при А У оо.

Определение 6. Множество стохастических процессов

(Xi(t),..., Xk(t)) принадлежит области нормального притяжения стохастического процесса Z вида (5), если

X1(bl(\)t) + ...+Xk(bk(X)t) ---^ Z[t},

при X —* оо. Здесь Ь(А),ЬДА),Ь(А),г = 1 ,к взяты из определения 5. Справедлива следующая терема:

Теорема 2.1.6 (Xi(i),... ^Xk{t)) принадлежит области нормального притяжения псевдосамоподобного процесса Z вида (5) тогда и только тогда, когда для любого j = 1, к и ii,..., tm

С[(Х№(Х)Ъ),... ,Xj(bj(X)tm))/b(X)}-

¿[(ZjibjWh),..., г^(х)гт))/ь(х)} - о,

при А —» оо. Здесь £(Х) обозначает распределение случайного вектора.

Второй раздел посвящен описанию моделей неоднородного трафика. В первом подразделе предложены модели неоднородного телетрафика, в которых объединены Устойчивое Движение Леви (УДЛ) и Дробное Броуновское Движение (ДБД). Эти модели позволяют дать четкое математическое обоснование для явления, описанного в работе Sarvotham S. и др. Connection-level Analysis and Modeling of Network Traffic. Модели разработаны на основе ON/OFF-моделй и Пуассоновской модели с бесконечным числом источников. Приведем результаты для Пуассоновской модели с бесконечным числом источников.

Предполагаем, что система имеет бесконечное число источников и в момент времени Г^ происходит соединение и источник с номером А: начинает передачу данных на сервер в течение некоторого времени с постоянной скоростью. Предполагается, что случайные величины (X,к,к 6 Z) независимые случайные величины и не зависят от процесса моментов включения (появления) источников.

Мы рассматриваем пуассоновскую модель с бесконечным числом источников, зависящую от некоторого параметра Т > 0 - параметра агрегирования процесса, такого, что интенсивность Л = А(Г) стремится к бесконечности при Т —> оо. Л = А(Т) - интенсивность появления сообщений.

Источники в модели бывают двух типов. Интенсивность появления сообщения от источника к типа есть X,к(Т) (к = 1,2). Длины сообщений xf* (к — 1,2) от источников первого и второго типа имеют функции распределения Fk{x) (к = 1,2), причем

Fk(x) = P(Xm >х) = х~аЧк{х) , х > 0 , 1 < ак < 2, к = 1,2.

Пусть bk{t) есть обобщенная обратная функция к 1/Fk(x) (к = 1,2). Тогда

bk(t) = t^Lk(t) , i>0,fc = l,2,

где ¿i(x), L2(x), Li(t), L2(t) - медленно меняющиеся функции при х —> оо и t —> оо.

Нас интересует предельное поведение случайного процесса (Bx{t) := A(T-t),t> 0):

#г(<) = Л(1>(71(Г) • <) + А^{Т2{Т) .t),t> 0, при Т - оо,

где A^(t) есть полная нагрузка на сервер, приходящая в систему от источников к-го типа (к = 1,2), Ti(T) и Т2(Т) - положительные, возрастающие функции и Ti(T) + Т2{Т) = Т (в соответствии с описанием процессов из введенного класса процессов). Здесь Тг/Т и Т2/Т частоты появления сообщений первого и второго типа.

Предположим, что для первой компоненты агрегированного про-

цесса выполнено условие медленного роста (2), а для второй компоненты выполнено условие быстрого роста (3).

Наша задача состоит в нахождении при некоторой общей нормировки С(Т), при которой процесс Br(t),t > 0 сходился бы при Т —> оо к некоторому предельному процессу, причем обе компоненты допредельного процесса вносили бы нетривиальный вклад. Для этого потребуем, чтобы нормировки в теоремах и совпадали.

Пусть Ai(Т) и Л2(Т) уже выбраны, причем Ai(T) /* оо, А2(Г) оо при Г —> оо и для них выполнены условия (2) и (3). Для заданного Т > 0 найдем Ti = Ti(T) и Т2 = Ti(T) такие, что выполнено равенство

MAi(Ti) • ТО = (А2(Т2) ■ Т23 • F2(T2) • о2)1'2 . (6)

11

В этом случае имеет место следующая теорема:

Теорема 2.1.1 Пусть случайный процесс (,&r(i),i > 0) определяется описанным выше образом, интенсивности Ai(T) и Лг (Г) появления источников первого и второго типов таковы, что выполнены условия (2) и (3), а величина Т\ = 7\(Т) а Г2 = Ti(T) определяется из уравнения (6). Тогда имеет место следующая сходимость при Т —> оо

Вт® ~ Тг ■ ЛХ(Г1) • ■ t - Т2 ■ Л2(Г2) ■ № • t

{Х2(Т2) .т?2 ■ F2(T2) ■ + , (7)

где 5"а = (Sa(t),t > 0) - а-устойчивое движение Леей, а = аь 5Я = {Вн{Ь), t > 0) - стандартное дробное броуновское движение, Н — (3 — аг)/2, процессы Вн и Sa независимы, а сходимость в (7) - сходимость конечномерных распределений.

Таким образом, математическую модель неоднородного трафика телекоммуникационной системы с большим количеством источников можно представить в следующем виде:

Sa(t)+BH(t).

В предложенной модели предельный процесс является суммой двух независимых процессов а-устойчивого движения Леви и дробного броуновского движения. Важным вопросом в данном случае является правильный выбор коэффициентов масштабирования и коэффициентов нормализации (которые с технической точки зрения связаны с частотой различных типов потоков).

Нагрузка, составленная большим числом отдельных ON/OFF-потоков часто моделируется с помощью ДБД. Во втором подразделе рассмотрен еще один частный случай моделей - модели, в которых присутствуют два независимых ДБД с различными показателями Херста. В этом разделе дано описание модели, подробное описание процесса ДБД, а также приведены методы моделирования ДБД.

При проектировании телекоммуникационных систем необходимо учитывать все компоненты трафика. В различных исследованиях параметра Херста показано, что его значение зависит от интенсивности трафика, а также от типа передающейся информации. Поэтому важной практической задачей является оценка параметров Херста каждой аддитивной компоненты в отдельности для неоднородного трафика. Для моделей, объединяющих ДБД и УДЛ, решение данного вопроса остается открытым. В то же время, для моделей, в которых присутствуют два независимых ДБД с различными показателями Херста в третьей главе диссертационной работы предложен алгоритм оценки параметров Херста.

Как было замечено ранее, самоподобные процессы обладает свойством долговременной зависимости. Определение процесса с долговременной зависимостью можно дать в терминах автоковариационной функции 7х(т) (1), а

12

также используя спектральную плотность

fxW) ~ cf\v\-a,v оо

при а 6 (0,1).

Каждое из этих определений включает два параметра: (аили (а,с/), причем

<7 = 2(270-

Параметр Херста описывает (асимптотически) самоподобие кумулятивного трафикового процесса /0' X(s)ds, в то время как а описывает долговременную зависимость процесса X(t). Эти два параметра связаны между собой соотношением H = (1 + а)/2.

Для оценок параметра ДВЗ а и параметра Херста H за основу был взят метод, предложенный Patrice Abry и Darryl Veitch в 1996 году, основная идея которого заключается в использовании последовательности вейвлет-коэффи-циентов процесса.

Пусть фа (f) 6 L2(R) - так называемый материнский вейвлет. Также выполнены следующие предположения:

1. Базисная система функций строится с использованием оператора масштабного преобразования:

Фз,о = 2-j/Vo(2 ~Ч).

2. ф0 имеет N нулевых моментов, т.е. для к = 0,..., N — 1 (по не для к > N\):

J t%{t)dt = 0.

Коэффициенты вейвлет-преобразования определяются по правилу:

dj* = J 4j*(t)X(t)dt,

где интеграл понимается в среднеквадратическом смысле.

Вейвлет-коэффициенты обладают следующими свойствами:

1. В силу Предположения 1, имеет место точная масштабная инвариантность (степенное поведение):

E[(dj,kf] = УЪС , (8)

где С = / М~а|ФоМ|2с^ , Фо - преобразование Фурье функции фо-

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

Далее используется обозначение г^ = Также предполагаем, что

для процесса Х{{) выполнены следующие дополнительные условия:

1. Процесс Х(£) и, следовательно, dj¿ являются гауссовскими.

2. Для фиксированного ] с.в. независимы и одинаково распределены.

3. Последовательности при разных ] независимы.

В силу аддитивности преобразования Фурье рассматриваемая модель неоднородного трафика может быть определена следующим образом: при \ъ>\ > 0 спектральная плотность случайного процесса удовлетворяет соотношению:

/хМ ~ схМ-"1 + О < «2 < «1 < 1.

Тогда

где

Zj = 2^'С, + 2ja7C-2, (9)

Ci = Ci J |ФоИ|2|1/Га'^.

Поскольку «2 < ai, то при больших j первое слагаемое в правой части (9) доминирует второе

Zj ~ 2""Ci.

Поэтому при больших j для оценки а\ и log2 Ci можно применить метод оценки параметров случайного процесса с долговременной зависимостью, предложенный Patrice Abry и Darryl Veitch. С другой стороны, имея оценку для первого слагаемого, мы можем оценить второе исходя из того, что

Zj - 2jaiCi = 2jmC2

при тех j, для которых f(u) = Cf\v\~a.

Алгоритм оценки параметров неоднородного трафика, состоит из следующих этапов:

• Применяя дискретное вейвлет-преобразование к исследуемому процессу X(t) получаем вейвлет-коэффициенты djj:.

Находим величины fj,j и у3 по формулам

1 п'

Уз = log2Hj - gj,

где nj - число коэффициентов, доступных для анализа в октаве j, g¡ = #V/2)/1n2-loga(ny/2). • Далее, используя МНК, рассчитываем оценки (6i,ói) параметров «i и log2 Сь

01 =--

где £> = ^ 1/(7?, 5г = 2 5Х1 = £ х?/<т], в качестве фактора вы-

ступает номер октавы х^ — 3. Расчегы выполняются по второй половине октав исходного диапазона [«//2,...,,/].

• Находим величины /х^ по формулам:

^ = <5^(61,0!), (10)

где (¡} = (6,3) = 9 = П^'ЗД^Д?^» и определено

только для тех j для которых + у^ + п^/2 > 0.

- несмещенная оценка 2-,а1С,1 (см. (8)), следовательно

ЕцГ = 2^2С2.

• Определим

2/} =

• Пусть ц'0 > 0 - некоторое фиксированное число. Будем считать определенным только для тех для которых > /4- Обозначим это множество за

• Далее, используя МНК, рассчитываем оценки (Ь2,аг) параметров а2 и

с2 при условии, что величины у^ определены только для ) 6 ^ =

В работе показано, что полученные оценки являются несмещенными и состоятельными (разделы 3.1.2.1, 3.1.2.2, 3.1.3.2).

Для анализа точности полученных теоретических результатов было использовано численное моделирование. В качестве исходных данных использовался модельный процесс, состоящий из двух независимых дробных броуновских шумов с различными параметрами Херста (т.е. приращений ДБД, кото-

15

рые образуют стационарную последовательность). Для моделирования процесса ДБД использовался метод случайного перемещения средней точки (RMA-метод (Random Midpoint Displacement). Суть метода заключается в рекурсивном расширении сгенерированной выборки путем добавления новых значений в средних точках относительно значений в конечных точках.

Неоднородный процесс Однородный процесс

Рис. 1: Результаты линейной регрессии для смоделированных данных

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

Предлагаемый алгоритм опробован па реальных траекториях трафика интернет. Данные взяты из открытых источников и являются фактическими стандартами в данной области. В качестве тестируемых данных выбраны три различные реализации телетрафика, отражающие трафик Интранет внутри крупной компании (ВСрАт^) и трафик между компанией и внешними абонентами глобальной сети Иптернет (БесРкиТСР, ЬЫСопп7).

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

Таблица 1: Оценка параметров реального трафика

Трафик Вид процесса Параметр Херста (однородный процесс) Параметры Херста (неоднородный процесс)

ВСрА^ неоднородный Н = 0.8035 Нх = 0.8824; Я2 = 0.6326

БесРШТСР неоднородный Я = 0.5974 #1 = 0.7684; Я2 = 0.5371

ЬЫСопп7 однородный Я = 0.6250 Нх = 0.6290; Я2 = 0.2321

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

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

• Описаны условия сходимости к некоторому специальному процессу такого класса.

• Предложены новые модели неоднородного входящего потока, объединяющая дробное броуновское движение и устойчивое движение Леви на основе пуассоновской модели с бесконечным числом источников и 01М/ОРР-модели.

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

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

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

Публикации автора по теме диссертации

• Галактионова О.В., Хохлов Ю.С. Оценка параметров неоднородного трафика. // Вестник Тверского госуниверситета, сер. Прикладная математика. - Вып. 3 (18). - 2010. - С. 89-103.

• Галактионова О.В. Анализ алгоритма обнаружения неоднородности телетрафика. // Вестник Тверского госупиверситета, сер. Прикладная математика. - Вып. 1 (20). - 2011. - С. 131-138.

• Галактионова О.В., Хохлов Ю.С. Модель телетрафика, объединяющая устойчивое движение Леви и дробное броуновское движения. // Вестник Тверского госуниверситета, сер. Прикладная математика. - Вып. 1 (3). -2006. - С. 163-167.

• Галактионова О.В., Жукова Е.А., Сидорова О.И. Границы для вероятности переполнения буфера сервера в случае конечного числа различных распределений активных периодов. // Студенческо-аспирантская конференция "Ломоносов-2005". - МГУ. - 14 апреля, 2005. - Тез.докл., С. 35.

• Галактионова О.В. Моделирование неоднородного трафика телекоммуникационных систем. //Математика, информатика, их приложения и роль в образовании: Материалы второй Российской школы-конференции с международным участием для молодых ученых: статьи, обзоры и тезисы докладов. - Тверь: Твер. гос. ун-т, 2010. - С. 64-69.

• D'Apice С., Manzo R., Khokhlov Yu.S., Galaktionova O.V. Pseudo-selfsimilar processes. // XXVI Seminar on Stability Problems for Stochastic Models. - Sovata-Bai, Romania. - Aug.27 - Sept.2, 2006. - Absracts, P.46.

• Khokhlov Yu.S., Galaktionova O.V. Convergence to pseudo-selfsimilar process. // International Conference "Skorokhod Space. 50 Years On". - 17-23 June, 2007. - Kyiv, Ukraine. - Abstracts, Part II. - P. 121.

• D'Apice C., Khokhlov Yu., Sidorova O.I., Galaktionova O.V. Gnedenko problem and an extension of class of selfsimilar process. //Transactions of the XXVI International Seminar on Stability Problems for Stochastic Models. -22-26 October, 2007. - Karmiel, Israil. - Part I. - P. 64-71.

• Khokhlov Yu.S., Galaktionova O.V. Parameter estimation of multifractal traffic. // XHI-th International Summer Conference on Probability and Statistics (ISCPS). - Bulgaria. - 22-27 June, 2008. - Abstracts, P. 19-20.

• D'Apice C., Galaktionova O., Khokhlov Yu., Sidorova O. New model of non-homogeneous traffic. // International Conferences on Ultra Modern Telecommunications and Control Systems. - 12-24 October, 2009. - St.Petersburg. -Part I. - P. 34-36.

• D'Apice C., Galaktionova O., Khokhlov Yu., Pagano M. Modeling of network traffic. // International Congress on Ultra Modern Telecommunications and Control Systems. - 18-20 October, 2010. - Moscow. - 5 p.

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

ВВЕДЕНИЕ

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ТЕЛЕТРАФИКА

1.1 Телетрафик.

1.1.1 Предмет и основные задачи теории телетрафика.

1.1.2 Исторический обзор теории телетрафика.

1.2 Самоподобный телетрафик

1.2.1 Причины самоподобности в телетрафике.

1.2.2 Определение самоподобного процесса.

1.2.3 Основные свойства самоподобных процессов.

1.3 Модели телетрафика.

1.3.1 Моделирование телекоммуникационных систем.

1.3.2 Традиционные модели трафика.

1.3.3 Пуассоновская модель с бесконечным числом источников

1.3.4 ОТ^/ОРР-модель.

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

1.4 Выводы по первой главе.

ГЛАВА 2. МОДЕЛИ НЕОДНОРОДНОГО ТЕЛЕТРАФИКА

2.1 Новый класс стохастических процессов

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

2.1.2 Проблема Гнеденко.

2.1.3 Область притяжении нового класса стохастических процессов

2.2 Модель телетрафика, объединяющая устойчивое движение Леви и дробное броуновское движение.

2.2.1 Описание модели.

2.2.2 Результаты.

2.3 Модель неоднородного телетрафика на основе дробного броуновского движения.

2.3.1 Описание модели.

2.3.2 Дробное броуновское движение.

2.4 Выводы по второй главе.

ГЛАВА 3. ОЦЕНКА ПАРАМЕТРОВ НЕОДНОРОДНОГО ТРАФИКА НА ОСНОВЕ ВЕЙВЛЕТ-АНАЛИЗА

3.1 Вейвлет-анализ самоподобных процессов

3.1.1 Оценки, основанные на вейвлет-преобразовании.

3.1.2 Оценка параметров процесса с долговременной зависимостью

3.1.3 Оценка параметров модели неоднородного телетрафика

3.2 Численная модель неоднородного трафика

3.2.1 Численное моделирование.

3.2.2 Анализ реальных траекторий трафика.

3.3 Выводы по третьей главе

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

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

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

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

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

При конструировании трафика одним из наиболее важных вопросов, на который необходимо ответить, - какой процесс описывает движение информационных потоков в сетях связи?

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

На основе исследования Эрланга, были получены многие другие результаты традиционной теории телетрафика (см. Исторический обзор теории телетрафика). На их основе основаны так называемые традиционные модели трафика.

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

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

К настоящему времени показано, что самоподобной структурой обладает телетрафик в проводных сетях при работе широко распространенных протоколов Ethernet (W.E.Lcland, M.S.Taqqu, W.Willinger, D.V.Willson), OKC7 (А.Ю.Криштофович), VoIP (T.D.Dang, D.Sonkoly, S.Molnar), TCP (W.Feng, P.Tinnakornsrisuphap) и др. Аналогичные эффекты обнаружены в сотовых телефонных сетях с коммутацией пакетов, в сетях с технологией беспроводного доступа (В.В.Петров, В.В.Платов) .

Для анализа телекоммуникационной системы необходимо наиболее точное построение ее модели. В настоящее время модели, учитывающие вновь выявленные свойства трафика, уже созданы и достаточно хорошо изучены ("\¥.Е.Ье1апс1, М.Э.Таоди, \У.\УШ^ег, Б.УЛУПкюп, Ы.ШесИ, Д.Ьеуу Уе-Ье1, ТЬ.ЗУШтозсЬ, Б.Кезшск, Н.11оо1геп, A.Stegeman, ИЧоггоэ, Б.С.Цыбаков, И.И.Цитович).

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

В диссертационной работе рассматриваются математические модели неоднородного входящего потока в телекоммуникационных системах. При описании неоднородного потока в настоящее время используются два подхода. Во-первых, используют модели (11.ШесН и др., M.S.Taqqu, У.Теуегоузку, "\¥.\¥11]ш§ег), в которых трафик описывается с помощью мультифрактально-го процесса. Такую структуру называют мулътифрактальной (см. [25]). В рамках гауссовских процессов такие модели могут быть охарактеризованы переходом от дробного Броуновского движения с постоянным параметром Н к процессу, где параметр Н в свою очередь подчинен некоторому случайному процессу Н = 77(2). Хотя мультифрактальные модели являются более общими и, по-видимому, способны преодолеть недостатки самоподобных моделей, сложность таких моделей делает их практическое использование затруднительным.

Другой подход заключается в том, что трафик рассматривается как совокупность нескольких компонент, каждая из которых отражает свойства трафика некоторых групп абонентов с одинаковыми характеристиками (С.Б'Арюе и др., И.И.Цитович, И.В.Шмелев). Предполагается, что деление на компоненты осуществляется по "природе происхождения" трафика: голосовой трафик, трафик данных, видео в режиме реального времени и т.д. Компоненты такого процесса являются, как правило, статистически независимыми.

За счет наличия нескольких аддитивных компонент такие модели

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

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

В настоящее время наблюдается глобализация всех процессов. В области телекоммуникаций это отражается в том, что появились глобальные телекоммуникационные сети, в которых число абонентов достигает сотни тысяч. В связи с этим важной задачей является определение полной нагрузки на сервера в таких системах, то есть необходимо определить распределение совокупного входящего потока в телекоммуникационной системе с большим числом источников. В течении последних 20 лет эта задача является актуальной. Единого мнения, какая модель более подходит для описания предельного процесса, нет. Две основные модели: устойчивое движение Леви (С.А.Оиегт. Н.ЫуЬех^, О.Ретп, З.Неэтск, Н.Йх^геп) и дробное броуновское движение (М.Б.Тадяи, Ы-БЬегтап). Практические исследования показали, что при сильной загруженности телекоммуникационной системы распределение совокупного входящего потока должно быть гауссовским. Однако если мы рассматриваем трафик, в котором загруженность сети умеренная, а длина сообщений достаточно большая, то в данном случае более адекватной является модель аппроксимации распределения совокупного входящего потока устойчивым законом. Однако, появились практические исследования [62], в которых при анализе данных между конечными устройствами, было показано, что описать весь входящий поток одной из известных моделей невозможно, поскольку в одном потоке могут присутствовать два совершенно различных типа трафика. Их называют альфа и бета компонентами процесса. Альфа-трафик состоит из относительно небольшого количества сообщений большого объема (который доминирует над всеми другими) и является чрезвычайно пульсирующим. Остаточный бета-трафик связан с передачами но узкополосным полосам связи и описывается гауссовским процессом с долговременной зависимостью. Математическая модель для описания подобного явления не предложена.

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

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

Для достижения поставленной цели необходимо решить следующие научные задачи:

• предложить математическое описание класса стохастических процессов, обобщающего самоподобные процессы;

• построить математические модели неоднородного трафика;

• разработать алгоритм оценки параметров неоднородного процесса с долговременной зависимостью;

• разработать комплекс процедур в среде МаЙаЬ для численного моделирования неоднородного трафика и оценки параметров исследуемого процесса.

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

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

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

• при проектировании телекоммуникационных систем,

• при расчетах в конкретных системах различных параметров (таких, как размер буфера, мощность сервера, скорость соединения и др.) для выбора оптимальных режимов работы,

• для обеспечения гарантированного качества обслуживания,

• при проектировании механизмов управления соединений.

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

Аппробация работы. Основные результаты диссертационной работы докладывались и обсуждались на Студенческо-аспирантской конференции "Ломоносов-2005" (МГУ, 14 апреля 2005), XXVI международном семинаре по проблемам устойчивости стохастических моделей (Совата-Баи, Румыния, Август 27 - Сентябрь 2, 2006), международной конференции "Пространство Скорохода. 50 лет спустя" (Киев, Украина, 17-23 июня, 2007), XXVII международном семинаре по проблемам устойчивости стохастических моделей (Кармиель, Израиль, 22-26 октября, 2007), XIII международной летней конференции по вероятности и статистике (Созополь, Болгария, 22-27 июня, 2008), международной конференции по ультрасовременным телекоммуникациям (Санкт-Петербург, 12-14 октября, 2009), II международном научно-практическом конгрессе по комплексному моделированию, анализу и синтезу информационно-телекоммуникационных систем "Ультрасовременные телекоммуникации и системы управления 1СиМР-2010" (Москва, 18-20 октября, 2010), второй Российской школ с-конференции для молодых ученых "Математика, информатика, их приложения и роль в образовании", (Тверь, Декабрь, 2010).

Диссертационная работа была выполнена при поддержке гранта РФФИ 06-01-00626.

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

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

Приведены наиболее популярные модели телетрафика. Описаны традиционные модели, ОМ/ОРР-модель, пуассоновская модель с бесконечным числом источников, модель Цыбакова Б.С. Приведены формулировки условий медленного и быстрого роста и теоремы о совокупной предельной нагрузке на сервер. 5

Вторая глава посвящена описанию моделей неоднородного телетрафика. Дано математическое описание класса стохастических процессов, который обобщает понятие самоподобных процессов. Этот класс процессов можно использовать для моделирования трафика, поскольку он позволяет принимать во внимание присутствие нескольких компонентов трафика с разными статистическими свойствами и определять соответствующие условия для сходимости суммарного трафика в предельных процессах. Предложены новые модели, учитывающие неоднородность телетрафика, а именно: наличие альфа и бета компоненты трафика. На основе пуассоновской модели с бесконечным числом источников предложена новая модель телетрафика, объединяющая дробное броуновское движение и устойчивое движение Леви. На основе ОМ/ОРР-модели предложена новая модель телетрафика, объединяющая дробное броуновское движение и устойчивое движение Леви. Сформулированы и доказаны условия, при которых возможно одновременное выполнение условий быстрого и медленного роста. Рассмотрен частный случай предложенных моделей: сумма двух дробных броуновских движений. Подробно рассмотрен процесс дробного броуновского движения и способы его моделирования.

При проектировании телекоммуникационных систем необходимо учитывать все компоненты трафика. В различных исследованиях параметра Хер-ста показано, что его значение зависит от интенсивности трафика, а также от типа передающейся информации. Поэтому важной практической задачей является оценка параметров Херста каждой аддитивной компоненты в отдельности для неоднородного трафика. Для хмоделей, объединяющих ДБД и УДЛ, решение данного вопроса остается открытым. В то же время, для моделей, в которых присутствуют два независимых ДБД с различными показателями Херста в третьей главе диссертационной работы предложен алгоритм оценки параметров Херста. Данный алгоритм можно использовать для моделей неоднородного трафика, в которых одновременно присутствуют две компоненты, каждая из которых описывается процессом дробного броуновского движения с различными показателями Херста. Алгоритм основан на известном методе оценки параметра Херста и параметра долговременной зависимости с использованием вейвлет коэффициентов, предложенном Р.АЬгу и D.Veitch. На основе предложенного алгоритма разработана численная процедура оценки параметров процесса. Проведено численное моделирование неоднородного трафика. Выявлены закономерности, позволяющие определять однородность-неоднородность трафика. Процедура тестировалась на смоделированных данных, а затем применялась к траекториям реального трафика.

В заключении сформулированы основные результаты работы.

В приложениях оформлена дополнительная информация, используемая в диссертации.

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

• Результаты работы могут быть использованы:

• при проектировании телекоммуникационных систем;

• при расчетах в конкретных системах различных параметров (таких, как размер буфера, мощность сервера, скорость соединения и др.) для выбора оптимальных режимов работы; ^

• для обеспечения гарантированного качества обслуживания;

• при проектировании механизмов управления соединений.

ЗАКЛЮЧЕНИЕ

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

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

Для достижения этой цели в работе сделано следующее:

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

• Рассмотрены основные существующие математические модели для моделирования входящего потока: традиционные модели, ОМ/ОРР-модель, пуассоновская модель с бесконечным числом источников, модель Цыбакова Б.С.

• Поставлена и решена задача описания неоднородного входящего потока телекоммуникационных систем.

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

• Описаны условия сходимости к некоторому специальному процессу такого класса.

• Предложена новая модель неоднородного входящего потока, объединяющая дробное броуновское движение и устойчивое движение Леви на основе пуассоновской модели с бесконечным числом источников. Предложена новая модель неоднородного входящего потока, объединяющая дробное броуновское движение и устойчивое движение Леви на основе (Ж/СЖР-модели.

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

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

С точки зрения реализации, процедура оценивания фактически состоит из

• построения вейвлет-преобразования исходных данных,

• двукратного применения взвешенной линейной регрессии, что позволяет говорить о вычислительной эффективности предлагаемой схемы.

Полученные оценки параметров процесса являются несмещенными и состоятельными.

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

1. Список использованных источников

2. Александров A.M. Безопасность сетей связи и некоторые задачи теории телетрафика. — Электросвязь. — 2003. — №12. — С. 20-24.

3. Башарин Г.Н. Лекции по математической теории телетрафика: Учеб. пособие. М: Изд-во РУДН, 2004. — 186 с.

4. Бестутин А.Р., Богданова А.Ф., Стогов Г.В. Контроль и диагностирование телекоммуникационных сетей. — СПб: Политехника, 2003. — 174 с. 94

5. Городецкий А.Я., Заборовский B.C. Информатика. Фрактальные процессы в компьютерных сетях: Учеб.пособие. — СПб.: Изд-во СПбГТУ, 2000.- 102 с.

6. Зюльков И.А. Самоподобные свойства трафика систем с повторными вызовами. // Вестник ВГУ, Серия физика, математика. — 2002. — №1. — С. 20-25.

7. Кендел М. Временные ряды. — Пер. с англ. и предисл. Ю.П.Лукашина.

8. М: Финансы и статистика. — 1981. — 199 с.

9. Корольков И.В., Кудерметов Р.К. О применении самоподобных процессов для моделирования трафика в телекоммуникационных сетях с пакетной коммутацией. // Вестник ХНТУ. 2006. - №3(26). - С. 62-68.

10. Крюков Ю.А., Кубарский М.А., Чернягин Д.В. Метод сбора данных о текущих характеристиках в высокоскоростных каналах пакетной передачи данных.// Системный анализ в науке и образовании. — 2009. — №3. — С. 1-11.

11. Лившиц Б.С., Пшеничников А.П., Харкевич А.Д. Теория телетрафика.

12. Учебник для вузов. — 2-е изд., перераб. и доп. — М.: Связь, 1979. — 224 с. 20

13. Ю.Нейман В.И. Самоподобные процессы и их применение в теории телетрафика. // Труды MAC. 1999. - № 1(9).- С. 11-15.

14. П.Симонина О.А., Яновский Г.Г. Характеристики трафика в сетях IP. // Труды учебных заведений связи. СПБГУТ, СПб. - 2004. — № 171. - С. 8-14.

15. Цитович И.И. Устойчивые модели трафика мультисервисных сетей. // 60-я Научная сессия, посвященная дню радио, 17-19 мая 2005. — Санкт-Петербург. С.271-273.

16. Цыбаков Б.С. Модель телетрафика на основе самоподобного случайного процесса. — Радиотехника. — 1999. — № 5. — С. 24-31. 53

17. Шелухин О.И., Тенякшев A.M., Осин А.В. Фрактальные процессы в телекоммуникациях. — М: Радиотехника, — 2003. — С. 480. 24, 89, 96

18. Шелухин О.И., Осин А.В. Исследование самоподобной структуры трафика Ethernet. // Вестник МГУ С. Серия: Радиоэлектроника и информатика. Тематич. вып. "Современные технологии в радио и телекоммуникациях: Сб. науч. тр. М.: МГУ С., - 2002. - с. 12-27.

19. Abry P., Veitch D. Wavelet Analysis of Long Range Dependent Traffic. // IEEE Transactions on Information Theory. — Vol. 44, № 1. — January 1998. 113, 121

20. Abry P. Ondelettes et Turbulence-Multiresolutions, Algorithmes de Decomposition, Invariance D'Echelle et Signaux de Pression. — Paris, France: Diderot Editeur. 1994. - Pp. 289. 112

21. Adler R.J., Feldman R.E., Taqqu M.S. A practical Guide to Heavy Tails.

22. Statistical Techniques and Applications, Birkhauser. — Boston. — 1998.

23. Beran J. A goodness of fit test for time series with long-range dependence. // Journal of the Royal Statistical Society. — 1992. — Series B, № 54. — P. 749-760.

24. Beran J. Statistics for Long-Memory Processes. — Chapman&Hall. — 1994.

25. Beran J. Statistical Methods for Data with Long-Range Dependence. // Statistical Science. — 1992. — Volume 7, Issue 4. — P. 404-416. 32

26. Beran J., Sherman R., Taqqu M.S., Willinger W. Variable Bit Rate Video Traffic and Long Range Dependence. — accepted for publication in IEEE // ACM Trans on Networking, subject to revisions — 1992.

27. Cohen A., Daubechies I., Vial P. "Wavelet on the interval and fast wavelet transforms". // Appl. Computat. Harmonic Anal. — 1993. — vol. 1, no. 1. — Pp. 54-81. 113

28. D'Apice C., Khokhlov Yu., Sidorova O. 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. P. 35-38. 9, 62

29. D'Apice C., Manzo R., Khokhlov Yu., Sidirova O. Convergence of superpositions of scaled renewal processes with finite number of different distributions. // J. Math. Sciences. 2006. - V. 132, № 5. - P. 602-609.

30. Doukhan D., Oppenheim G., Taqqu M.S. Theory and Applications of LongRange Dependence. — Birkhauser, Basel. — 2003.

31. Embrechts P., Maejima M. An introduction to the theory of self-similar stochastic processes. — 2000. Preprint.

32. Embrechts P., Maejima M. Selfsimilar Process. — Prinston University Press. 2002. 61

33. Flandrin P. On the spectrum of fractional Brownian motion. // TEEE Trans. Inform. Theory. — Jan. 1989. Vol. 35. - P. 197-199.

34. Flandrin P. Wavelet analysis and synthesis of fractional brownian motion. // IEEE Transactions on Infofmation Theory. 1992 — Vol.IT-38. — P. 910-917.

35. Feldmann A., Gilbert A.C., Willinger W. Data networks as cascades: Investigating the multifractal nature of Internet WAN traffic. // Computer Communication Review. — 1998. — V. 28, № 4. — P. 42-55.

36. Jaderman D.L., Melamed B., Willinger W. Stochastic modeling of traffic processes. // In: Frontiers in Queueing: Models, Methods and Problems. — Boca Raton. 1997. - P. 271-310.

37. Gaigalas R., Kaj I. Convergence of scaled renewal processes and a packet arrival model. — To appear: Bernoulli. — 2002.

38. Empirical testing of the infinite source Poisson data traffic model. / C.A.Guerin, H.Nyberg,O.Perrin, S.Resnick, H.Rootzen, CA.Stari. / Technical Report 1257, School of ORIE. — Cornell Univ. Available at www.orie.cornell.edu. 1999. 75

39. Kaj I. Stochastic modeling in broadband communications systems. — SIAM Monogf. Math. Model. Comput. Philadelphia: Sosiety for Industrial and Applied Mathematic. — 2002.

40. Lamperti J.W. Semi-stable stochastic processes. // Transactions of the American mathematical Society. — 1962. — Vol. 104. P. 62-78. 60, 61

41. Leland W.E. LAN traffic behavior from milliseconds to days. — In Proceedings of the ITC 7th Specialist Seminar. — Morristown. — 1990.

42. Leland W.E., Taqqu M.S., Willinger W., Wilson D.V. On the self-similar nature of Ethernet traffic.// Computer Communications Review. — 1993. — № 23. — P. 183-193. // Proceedings of the ACM/SIGCOMM93. San Francisco,

43. Statistical analysis of high time resolution Ethernet LAN traffic measurements. / W.E.Leland, M.S.Taqqu, W.Willinger, D.V.Wilson; editors - M.E.Tarter, M.D.Lock. // Statistical Applications of Expanding Computer Facilities. — V. 25. - P. 146-155.

44. On the self-similar nature of Ethernet traffic (Extended version). / W.E.Leland, M.S.Taqqu, W.Willinger, D.V.Willson. // IEEE/ACM Trans. Networking. 1994. - V. 2. - P. 1-15. 33, 121

45. Levy J.B., Taqqu M.S. On renewal processes having stable inter-renewal intervals and stable rewards. // Les Annales des Sciences Mathématiques du Quebec. 1987. - № 11. - P. 95-110.

46. Levy J.B., Taqqu M.S. Renewal reward processes with heavy-tailed inter-aarival times and heavy tailed rewards. // Bernoulli. — 2000. — V. 6, № 1. — P. 23-44. 74

47. Levy P. Calcul del probabilités. — Gauthier-Villars, Paris. — 1925. 59, 60

48. Levy Vehel J., Riedi R. Fractional brownian motion and data traffic modeling: The other end of the spectrum. // In Fractals in Engineering 97. — Springer, 1997. P. 185-202.

49. Mason J.D. Convolutions of stable laws as limit distributions of partial sums. // Ann.Math.Statist. 1970. — Vol. 41, № 1. - P. 101-114.

50. Mandjes M. Large deviations for Gaussian queues. — John Wiley & Sons, Chichester. — 2007.

51. Mikosch Th., Resnick S., Rootzen H., Stegeman A. Is network traffic approximated by stable Levy motion or fractional Brownian motion? // Ann. Appl.Probab. 2002. - V. 12, № 1. - P. 23-68. 43, 45, 47, 48, 52

52. Narayan O. Exact asymptotic queue lenght distribution for fractional Brownian traffic. // Advances in Perfomance Analysis. — 1998. — V. 1, № 1. — P. 39-63.

53. Norros I. A storage model with self-similar input. // Queueing Systems And Their Applications. 1994. — № 16. - P. 387-396.

54. Norros I. On the use of fractional Brownian motion in the theory of connectionless networks. // IEEE Journal on Selected Areas in Communications, 1995.- № 13. 953-962.

55. Noitos I. Four approaches to the fractional Brownian storage. // Fractals in Engineering. 1997. — P. 154-169.

56. Park K., Willinger W. Self-Similar Network Traffic and Perfomance. — Wiley Interscince. — 2000.

57. Paxson V., Floyd S. Wide area treffic: The failure of Poisson modeling. // IEEE/ACM Trans. Netwoking 3. 1995. - P. 226-244.

58. Riedi R.H., Grouse M.S., Ribiero V., Baraniuk R.G. A multifractal wavelet model witti application to TCP network traffic. // IEEE Trans. Inform. Theory.- April 1996. V. 45. - P. 992-1018.

59. Riedi R. , Levy Vehel J. TCP traffic is multifractal: a numerical study. // Inria research report, Project Fractales. — INRIA Rocquencourt, 1997. — № 3129. — submitted to IEEE Transactions of Networking.

60. Riedi R., Mandelbrot B. Inversion formula for continuous multifractals. // Advances in Applied Mathematics. — 1997. — № 19. — P. 332-354.

61. Resnick S., Van Den Berg E. Weak convergence of high-speed network traffic models. // Appl. Probab. 2000. - №37. - P. 575-597. 75

62. Samorodnitsy G., Taqqu M.S. Stable Non-Gaussian Processes: Stochastic Models with infinite Variance. — Chapman and Hall, New York. 1994. 61

63. Sarvotham S., Riedi R.H., Baraniuk R.G. Connection-level Analysis and Modeling of Network Traffic. // ACM Internet Measurement Workshop Nov. — 2001. P. 99-103. 11, 75

64. Taqqu M., Abry P., Veitch D. On the automatic selection of the onset of scaling. // Fractals.- 2003. Vol. 11. - P. 377-390.

65. Taqqu M.S., Levy J.B. Using renewal processes to generate long-range dependence and high variability. // In: E.Eberlein and M.S.Taqqu, eds. Dependence in Probability and Statistics. — Boston: Birkhauser. — 1986. — P. 73-89.

66. Taqqu M.S. , Teverovsky V., Willinger W. Is network traffic self-similar or multifractal? // Fractals. 1997. V. 5. - P. 63-73.

67. Taqqu M.S. Proof of a fundamental result in self-similar traffic modeling./ M.S.Taqqu, W.Willinger, R.Sherman. // Computor Communications Review. — 1997. V. 27, N. 2. - P. 5-23. 75

68. Taqqu M.S. Self-similar processes. / In S.Kotz and N.Johnson, editors. // Encyclopedia of Statistical Sciences. — Wiley, New York, 1988. — V. 8. — P. 352-357.

69. Taqqu M.S., Levy J. Using renewal processes to generate long-range dependence and high variability. / In E.Eberlein, M.S.Taqqu, editors. // Dependence in Probability and Statistics. — Boston, 1986. — P. 73-89.

70. The Internet Traffic Archive, — http : //ita.ee.lbl.gov/html/traces.html

71. Tsybakov B., Georganas N.D. On Self-Similar Traffic in ATM Queues:Definitions, Over flow Probability Bound, and Cell Delay Distributions.

72. IEEE/ACM Transactions on Network ing. 1997. - № 5(3). - P. 397-409. 53, 121

73. Tsybakov B.S., Georganas N.D. Self-similar processes in communications networks. // IEEE Trans. Inform. Theory, vol. 44. Sep. 1998. P. 1713-1725. 34

74. Veitch D., Abry P. A wavelet based joint estimator of the parameter of long-range dependence. // IEEE Transaction on Information Theory. — 1999. — V. 45, № 3. P. 878-897. 96, 97, 121, 142

75. Willinger W., Paxson V. Where mathematics meets the Internet. // Notices of the AMS. 1998. - V.45, № 8. - P. 961-970.

76. Self-similarity through high variability: statistical analysis of ethernet lan traffic at the source level. / W.Willinger, M.S.Taqqu, R.SHERMAN, D.Wilson. // Comput. Comm. Rev. (1995). - № 25. - P. 100-113. 48

77. Zinger A.A. On a class of limit distributions for normalized sums of independent random variables. // Theory Probab. Appl. — 1965. — Vol. 10, № 4. — P. 607-626.

78. Zolotarev V.M., Korolyuk V.S. On a hypothesis proposed by B.V. Gne-denko. // Theory Probab. Appl. 1961. - Vol. 6, № 2. - P. 431-435.

79. Список публикаций соискателя

80. А. Галактионова О.В., Хохлов Ю.С. Оценка параметров неоднородного трафика. // Вестник Тверского госуниверситета, сер. Прикладная математика. — Вып. 17. 2010. — С. 89-103.

81. А. Галактионова О.В. Анализ алгоритма обнаружения неоднородности телетрафика. // Вестник Тверского госуниверситета, сер. Прикладная математика. Вып. !!!. - 2011. - С. !!!-!!!.

82. А. Галактионова О.В., Хохлов Ю.С. Модель телетрафика, объединяющая устойчивое движение Леви и дробное броуновское движение. // Вестник Тверского госуниверситета, сер. Прикладная математик. — Вып. 3. — 2006.- С. 163-167.

83. А. Pseudo-selfsimilar processes. / C.DApice, R.Manzo, Yu.S.Khokhlov, O.V.Galaktionova. — XXVI Seminar on Stability Problems for Stochastic Models.- Sovata-Bai, Romania. — August 27 September 2, 2006. — Absracts, P. 46.

84. A. Khokhlov Yu.S., Galaktionova O.V. Convergence to pseudo-selfsimilar process. // International Conference "Skorokhod Space. 50 Years On". — 17-23 June, 2007. Kyiv, Ukraine. — Abstracts, Part II. — P. 121.

85. A. Khokhlov Yu.S., Galaktionova O.V. Parameter estimation of multifractal traffic. // XHI-th International Summer Conference on Probability and Statistics (ISCPS). Sozopol, Bulgaria. - 22-27 June, 2008. - Abstracts, P. 19-20.

86. A.New model of nonhomogeneous traffic. / C.D'Apice, O.Galaktionova., Yu.Khokhlov, O.Sidorova. // International Conferences on Ultra Modern Telecommunications and Control Systems. — 12-24 October, 2009. — St.Petersburg. Part I. - P. 34-36.

87. A.Modeling of network traffic. / C.D'Apice, O.Galaktionova, Yu.Khokhlov. M.Pagano. // International Congress on Ultra Modern Telecommunications and Control Systems. — 18-20 October, 2010. — Moscow. — 5 p.

88. Временные реализации реального сетевого (самоподобного) трафика и традиционной несамоподобной (Пуассоновской) модели телетрафика2 1.5 10.52 1.5 1052 1.510.5