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

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

005056383

Лукашенко Олег Викторович

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

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

е ЛЕК 2012

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

Петрозаводск - 2012

005056383

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте прикладных математических исследований Карельского научного центра Российской академии наук

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

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

Ведущая организация:

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

Морозов Евсей Викторович Лифшиц Михаил Анатольевич,

доктор физико-математических наук, профессор, профессор кафедры теории вероятностей и математической статистики математико-механического факультета ФГБОУ ВПО «Санкт-Петербургский государственный университет» Шевцова Ирина Геннадьевна, кандидат физико-математических наук, ассистент кафедры математической статистики факультета вычислительной математики и кибернетики ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова» ФГБОУ ВПО «Российский университет дружбы народов»

Защита состоится 20 декабря 2012 г. в 17:00 часов на заседании диссертационного совета Д 212.190.03 на базе ФГБОУ ВПО «Петрозаводский государственный университет», расположенного по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

С диссертацией можно ознакомиться в научной библиотеке Петрозаводского государственного университета.

Автореферат разослан Ж. » ноября 2012 г. Ученый секретарь

диссертационного совета ^^^ Р. В. Воронов

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

Актуальность работы

В связи с распространением различных сетевых приложений и, как следствие, увеличением информации, передаваемой по компьютерным сетям, возникает необходимость анализа их загрузки, т. е. расчета различных характеристик, таких, например, как емкости буферов, пропускная способность и т. д. Последние два десятилетия ознаменовались существенными достижениями в исследовании сетевого трафика. Было, в частности, установлено, что процессы, протекающие в сетях передачи данных, могут обладать фрактальными свойствами (эффект самоподобия) и долговременной зависимостью (долгой памятью). Эти свойства сетевого трафика были обнаружены и изучены в работах У. Леланда, У. Вилипджера, Д. Уилсона, М. Такку, А. Эррамилли, М. Кровеллы, А. Беставроса и др. исследователей. Такие свойства радикально отличают современные модели от пуассоновских моделей, которые адекватно описывали процессы обслуживания и, в частности, сетевые процессы на протяжении долгого времени. Например, пуассоновские модели опираются на экспоненциальные распределения интервалов входного потока и времени обслуживания заявок (пакетов) и обладают короткой памятью и, с другой стороны, не обладают свойством самоподобия (фрактальности).

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

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

Степень разработанности

Гауссовские очереди (очереди с гауссовским входным потоком) обладают очень сложной структурой зависимости. Этот факт не позволяет в явном виде получить выражения для различных ключевых характеристик, в частности, для вероятности переполнения, то есть вероятности превышения некоторого уровня 6. Отсутствие точных аналитических результатов вызывает необходимость исследования асимптотик соответствующих характеристик. Применительно к очередям обычно выделяют два типа асимптотик: асимптотики при растущем размере буфере Ь, а также асимптотики в режиме многих источников: число гг.уссовских источников п растет и пропорционально растут размер буфера л скорость обслуживания. Например, для вероятности переполнения результаты вида

P(Q>6)~/i(6), оо, P(Q > пЪ) ~ /2(п), п -> оо,

где а ~ b означает что а/Ъ —> 1, называются точными асимптотиками, здесь /ъ /2 ~ некоторые явно заданные функции, Q - стационарный процесс нагрузки. Известно, что в гауссовской очереди с бесконечным буфером стационарный процесс загрузки Q (текущая незавершенная работа в системе) распреде-

1 Norros I. Studies on a model for connectionless traffic, based on fractional Brownian motion // Conference on Applied Probability in Engineering, Computer and Communication Sciences INRIA/ORSA/TLMS/SMAI, Paris. 1993.

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

1пР(д>6)~/з(Ь), 6 оо, 1пР(д > пЬ) ~ /4(п), п-> оо,

дающие менее полную информацию о вероятности переполнения. Такого рода асимптотики рассматривались в работах Н. Дуффилда, Н. О'Коннелла, В. И. Питербарга, Ю. Хюслера, О. Нараяна, Л. Массоли, А. Симоняна, К. Дсбицкого, М. Манджеса, К. Дуффи, Д. Лыоиса, У. Салливана, А. Дикера.

Наряду с вероятностью переполнения другой важной характеристикой систем обслуживания является максимум процесса нагрузки на конечном интервале [0, (пиковая нагрузка в системе). Для этой характеристики в работах А. Зееви, П. Глшша, В. И. Питербарга, Ю. Хюслера найдены асимптотики (при t —> оо) в случае входного процесса ДБД.

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

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

Методы исследований

В диссертационной работе применяются методы теории гауссовских слу-

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

Научная новизна

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

Практическая значимость

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

На защиту выносятся следующие основные результаты и положения:

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

2. Исследованы свойства альтернативной статистической ВМС-оценки вероятности переполнения гауссовской системы обслуживания.

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

4. Разработана программа для имитационного моделирования гауссовских систем обслуживания.

Апробация работы

Основные результаты диссертации докладывались на следующих конференциях: международный научный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 19-20 мая 2009 г.); 2nd Northern Triangular seminar (Стокгольм, 15-17 марта 2010 г.); международный научный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 25-26 мая 2010 г.); международный семинар «Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems» в рамках конгресса ICUMT'10 (Москва, 18-20 октября 2010 г.); международная конференция «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей» (21-я Белорусская школа-семинар по теории массового обслуживания, Минск, 3-5 февраля 2011 г.); 3rd Northern Triangular seminar (Санкт-Петербург, 11-13 апреля 2011 г.); всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (Москва, 18-22 апреля, 2011 г.) международный научный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 28 апреля 2011 г.); V Международный семинар «Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем» (Светлогорск, 10-16 октября 2011 г.); VIII Международная Петрозаводская конференция «Вероятностные методы в дискретной математике» (2-9 июня 2012 г. Петрозаводск); 9th International Workshop on Rare Event Simulation (Тронхейм, 25-27 июня 2012 г.); международная конференция «Теория вероятностей и се приложения», посвященная 100-летию со дня рождения Б. В. Гнеденко (Москва, 26-30 июня 2012 г.).

Работа поддержана РФФИ, грант 10-07-00017.

Публикации

Материалы диссертации опубликованы в 10 работах, из них 3 статьи в рецензируемых журналах [1-3] (в том числе 2 работы в изданиях из перечня российских рецензируемых журналов [1, 2j), 3 статьи в сборниках трудов конференций [4-6] и 4 тезиса докладов [7-10]. Получено свидетельство о регистрации электронного ресурса [11].

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения, перечня сокращений и условных обозначений, библиографии и списка иллюстраций. Общий объем диссертации 106 страниц, включая 19 рисунков. Список литературы включает 108 наименований.

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

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

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

A(t) = mt + X(t), t > 0, (1)

где параметр т > 0, а X := t > 0} - центрированный гауссовский

процесс со стационарными приращениями, такой, что Х(0) = 0. В диссертации рассматриваются системы с одним обслуживающим устройством с постоянной скоростью обслуживания С > 0. Введем коэффициент г := С — т, имеющий смыл коэффициента загрузки и обозначим W(t) := X(t)-rt,t> 0.

Пусть Q(t) величина нагрузки (незавершенная работа) в момент времени f. Если Q(0) = 0 и система имеет неограниченный буфер, то справедливо соотношение

Q(t) = sup (W(t) - ИЧ*)). (2)

0<s<t

Условие г > 0 обеспечивает существование стационарного режима, и стационарная величина нагрузки при этом определяется следующим образом:

Q = sup W(t), (3)

<ет

где Т = Z+ или Т = R+. Вероятность того, что величина стационарной нагрузки Q превысит некоторое пороговое значение Ь (т. е. вероятность переполнения) определяется как

P(Q > Ь) = Р ^sup W(t) > bj , (4)

Пусть в данную систему поступает нагрузка от п независимых одинаково распределенных (н. о. р.) гауссовских источников вида (1). В этом случае вероятность переполнения (4) запишется в виде:

тгn(b) = Р (sup{у/ЩХ{Ь) - rt) > . (5)

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

Рассмотрим систему с конечным буфером размера Ь и будем анализировать ее в дискретном времени. Динамика процесса нагрузки {Qb(k), к = 1,2,...} описывается следующим образом: в начальный момент времени система пуста (<2,;(0) = 0). Далее нагрузка в момент времени к рассчитывается по следующему рекуррентному соотношению (один из вариантов так называемой рекурсии Линдли):

Qb(fc) = min (b, (Qb(k - 1) - г + X*(*))+) , (6)

где Х'(к) := Х(к) - Х{к - 1).

Доля потерянной работы на интервале [0,Т] определяется как отношение объема потерянной работы к общему объему поступившей работы на указанном интервале, т. е.

1:Шк-1)-г + Х*{к)-Ь)+ ЫЬ, Т) = &---. (7)

Тогда стационарная вероятность потери определяется следующим образом:

Р£(Ь) = Нш Рх(6,Т), (8)

Т-юо

когда этот предел существует.

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

Х(1) = ВН1(1) + В1Гг(1) (9)

с дисперсией Шф) = г;(£) = £2Я' +£2Н2, где Нг есть показатель Херста потока г = 1,2.

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

Теорема 2.1.1. Для стационарной нагрузки (3) справедлив следующий асимптотический результат:

г2 я

ш^ыпя > Ь) = -2Я2я(1_ яр-яг ^

где Н = тах(Нх, Н2).

Данный результат говорит о том, что в асимптотическом анализе вероятности переполнения буфера системы, на вход которой поступает сумма независимых ДБД, доминирующую роль играет ДБД с наибольшим значением параметра Херста. Доказательство логарифмической асимптотики (10) основано на технике, использованной в работе Н. Дуффилда и Н. О'Коннеллг?, где в качестве компоненты X фигурирует единственный процесс ДБД. Более общий результат получен в работе К. Дуффи, Д. Лыоиса и У. Салливана?. Именно, в случае, если дисперсия v(t) процесса X(t) правильно меняется на бесконечности с показателем 0 < V < 2, то

lim 4P InP(Q > b) = -в, (11)

il—> ОС b

где параметр © > 0 имеет вид

2 / г \ У

6 - сГмТ]^ Ы • (12)

Формально результат (10) является следствием асимптотики (11), хотя строго говоря, соотношение (10) доказано лишь для дискретного времени, поскольку рассматривается гораздо более широкий класс систем обслуживания (не обязательно гауссовских). В диссертации в ходе доказательства теоремы 2.1.1 было показано, что асимптотика (10) выполнена в непрерывном времени.

В третьей главе исследуется асимптотическое поведение максимума процесса нагрузки Q. Основное предположение состоит в том, что дисперсия гауссовской компоненты входного процесса v(t) = DA'(i) правильно меняется па бесконечности с индексом 0 < V < 2, т. е. представима в виде

v(t) = tvL(t), (13)

2 Duffield N., O'Connell N. Large deviations and overflow probabilities for the general single server queue, with applications // Proceedings of the Cambridge Philosophical Society. 1995. Vol. 118. Pp. 363-374.

3 Duify K-, Lewis J. T., Sullivan W. G. Logarithmic asymptotics for the supremum of a stochastic process // Ann. Appl. Probab. 2003. Vol. 13, no. 2. Pp. 430-445.

где £(£) - медленно меняющаяся на бесконечности функция. Обозначим /3 = 1 а также выберем и зафиксируем любое £ £ (0,2- V). Будем далее считать, что функция Ь{1) является дважды дифференцируемой на К+.. Кроме, того, предположим, что также выполнены следующие условия (при£ -» оо):

¿(4^(4)) ~ т, (14)

£"(*) = о ■ (15)

В статье Т. Константопоулоса, М. Зазаниса и Г. Векианы4 показано, что на одном вероятностном пространстве можно задать процесс 1У(4) = Х^—гЬ и стационарный процесс <3* := {<3*(*)> 4 е таким образом, что одновременно выполнены условия

<Э*№ =<1 Я Для всех * > 0, (16)

Я*(1) = \¥(1) + тах{д*(0),Ь*(1)}, 1>0, (17)

где =4 означает равенство по распределению, = - пипп<,,<({1У(5)}. Обозначим

М(«) = тетд(в), ЛГ(4) = тахд*(5), (18)

и пусть

7(г) = Ь[(1пг)Д] 1п4. (19)

Основной результат третьей главы содержит

Теорема 3.1.1. Пусть дисперсия гауссовской компоненты X входного процесса (1) удовлетворяет условиям (14), (15), а также г > 0. Тогда

M*(t) (1

т щ \е

Р

а ' (20)

4 Konstantopcmlos T., Zazanis M., Veciana G. D. Conservation !aws and reflection mappings with application to multiclass mean value analysis for stochastic fluid queues // Stochastic Processes and their Applications. 1996. Vol. 65. Pp. 139-146.

M(t) /1Y

VW^UJ ' i~>0°' (21)

где означает сходимость no вероятности, а параметр 0 удовлетворяет соотношению (12). Этот результат обобщает работу А. Зееви и П. Глипна5, где процесс X = Вн является ДБД с параметром Херста Я е (1/2, 1). При некоторых дополнительных ограничениях сходимость по вероятности можно усилить до сходимости в пространстве Lp:

Теорема 3.2.1. Пусть выполнены условия теоремы 3.1.1, а условие{ 14) усилено до того, что существует предел

lim L(t) = Л 6 (0, оо). (22)

Тогда в (20), (21) имеет место сходимость в пространстве Lp, р € [1, оо).

Аналогичная асимптотика получена и для нестационарного случая, т. е.

для случая, когда параметр г < 0:

Теорема 3.3.1. Пусть г < 0, тогда для максимума процесса нагрузки

M(t) справедлива следующая сходимость

Mit) +rt .N

Щ0,1), t -» оо, (23)

где Af(0,1) - стандартная нормальная случайная величина (с. в.)

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

Т{Ь) = inf{f > 0 : Q*{t) > Ь}.

Отметим, что распределение максимума стационарного процесса нагрузки M*(t) определяет распределение Т(Ь) п силу того, что

{Т(Ь) <t} = {M*(t) > b}. (24)

5 Zeevi A., Glynn P. On the maximum workload in a queue fed by fractional Brownian motion // Ann. Appl. Probab. 2000. Vol. 10. Pp. 1084-1099.

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

Теорема 3.4.1. Пусть дополнительно к условиям теоремы 3.1.1. функция 7(£) монотонно возрастает на некотором луче. [¿о,оо), тогда имеет место сходимость

Четвертая глава посвящена статистическому моделированию гауссов-ских систем обслуживания, важность которого определяется отсутствием точных аналитических результатов. В начале главы описано функциональное назначение разработанной программы для оценивания характеристик гаус-совских систем. В первом разделе приведен краткий обзор методов моделирования гауссовских процессов (моделирования случайной компоненты X входного потока (1)). Описана процедура моделирования процесса нагрузки, как в случае бесконечного, так и конечного размера буфера. Большое внимание в данной главе уделено оцениванию вероятности переполнения в режиме большого числа н. о. р. источников, которая определяется соотношением (5). Известно, что так называемая относительная ошибка оценивания (отношение стандартного отклонения оценки к ее среднему) неограниченно растет, если искомая вероятность убывает, что и происходит с ростом п. По этой причине прямой метод Монте-Карло при большом п требует значительных вычислительных затрат, необходимых для построения оценки с заданной точностью. Поэтому для эффективного вычисления оценок вероятности тг„(&) необходимо применение специальных ускоренных методов, уменьшающих дисперсию оценки. В диссертации исследованы свойства следующей ВМС-оценки (Bridge Monte Carlo), предложенной в работе С. Джордано, М. Губипслли и М. Па-гапо6. Кратко поясним идею, лежащую в основе построения оценки. Фикси-

6 Giordano S., Gubinelli M-, Pagano M. Bridge Monte-Carlo: a novel approach to rare events of Gaussian processes // Proc. of the 5th St.Petersburg Workshop on Simulation. St. Petersburg, Russia: 2005. Pp. 281-286.

руется произвольное т 6 Т и для процесса X вводится в рассмотрение так называемый гауссовский мост

у(*) = х(ь) - ф(г)х{т), (26)

где

а Г - ковариационная функция процесса X. Обозначим через Ф хвост распределения стандартной нормальной с. в. Можно показать, что вероятность переполнения представима в виде

7Г „(Ъ) = Е

УГ(т,т)/п.

где

y:=Mb + rt-VT^Y{t)

tsT ip(t) к '

На основе независимых реализаций i = 1,..., N} процесса Y строится

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

Хотя выбор значения т произволен, на практике, как правило, выбирается г = argmin | згой)' ^ ^ - так называемое наиболее вероятное время переполнения. Несмотря на то, что ВМС-оценка не является асимптотически эффективной, ее дисперсия меньше дисперсии оценки, полученной с помощью метода существенной выборки одинарным сдвигом (single-twist estimator). Кроме того, данный метод оценивания является гибким в том смысле, что он применим для любого гауссовского процесса X с заданной ковариационной функцией Г. Для проверки качества оценки (28) были проведены численные эксперименты. Полученные по формуле (28) оценки для различных типов

гауссовских процессов (в том числе ДБД, сумма независимых ДБД, интегральный процесс Орнштейна-Уленбека) сравнивались с известными асимптотическим результатами. Во всех случаях результаты моделирования хорошо согласуются с теоретическими результатами. Так, например, при больших значениях п, минимум в (27) на практике почти всегда достигается около наиболее вероятного времени переполнения т. При этом для значений вероятности порядка Ю-12 относительная ошибка все еще составляет не более 1%.

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

A(t) = mt + y/mB{t), (29)

где {B(t)} - процесс броуновского движения. В силу того, что приращения {S(i)} независимы, процесс нагрузки {Qb(t), t = 1,2,...} является марковским, а значит возможно применить регенеративную теорию. Моменты регенерации (в данном случае моменты опустошения системы) определяются следующим образом:

Pk+i = min{i > рк : Qb(t - 1) > 0, Qb(t) = 0, к > 1}, Д, = 0. (30)

Части траекторий процесса нагрузки Gд. = {Qi,(t), Рк < t < Рк+х}, к > О называются циклами регенерации. Пусть L(,(t) - общий объем потерь за время [0, £]. Обозначим также через EL - средний объем потерь на цикле регенерации, ЕЛ - средний объем поступившей на цикле регенерации работы. Тогда стационарная вероятность потери представима в следующем виде:

Lb(t) EL

WL = im = 57T- (31)

i-юо A{t) EA [ ;

При регенеративном моделировании генерируется (достаточно большое число) N циклов регенерации. При этом подсчнтываются величины потерь Li; и

поступившей работы Ак на каждом цикле регенерации к ~ 1,..., N. В силу (31) оценка стационарной вероятности потери примет вид:

1 1 М ^ N Р1 := Рь(Ю = ~ где Ь := Ь{М) = - £ ¿ь А := А{М) = ТтУ^Ак.

Более того, данный подход позволяет построить асимптотический доверительный интервал для вероятности потери (с заданной доверительной вероятностью 7) следующего вида:

Цц

где

N

1

N

а Ф - функция Лапласа.

В Заключении сформулированы основные итоги диссертационной работы.

Заключение

Основные итоги диссертационной работы состоят в следующем:

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

2. Исследовано асимптотическое поведение максимума процесса нагрузки в жидкостной системе обслуживания с одним сервером. На вход системы поступает процесс, содержащий линейную (детерминированную) компоненту и случайную компоненту, описываемую центрированным гауссовским процессом, у которого дисперсия является правильно меняющейся функцией с показателем V € (0, 2). Показано, что при соответствующей нормировке максимум процесса нагрузки на интервале

[О, £] сходится по вероятности (при t —> оо) к явно выписанной константе.

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

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

5. Исследованы свойства альтернативной статистической ВМС-оценки вероятности переполнения гауссовской системы обслуживания.

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

Список публикаций

1. Лукашенко О. В., Морозов Е. В. Асимптотика максимума процесса нагрузки для некоторого класса гауссовских очередей // Информатика и ее применения. 2012. Т. 6, № 3. С. 81-89.

2. Лукашенко О. В., Морозов Е. В., Пагано М. Статистическое моделирование гауссовской очереди // Труды Карельского научного центра Российской академии наук. 2011. № 5. С. 55-62.

3. Лукашенко О. В., Морозов Е. В., Пагано М. Применение гауссовских процессов в моделировании сетевого трафика // Труды Карельского научного центра Российской академии наук. 2010. № 3. С. 51-58.

4. Goricheva R. S., Lukashenko О. V., Morozov Е. V., Pagano М. Regenerative analysis of a finite buffer fluid queue // Proceedings of 2010 International

Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT). 2010. Pp. 1132-1136.

5. Lukashenko О. V., Morozov E. V. Gaussian Processes in Communication Networks // Proceedings of AMICT'2009. 2009. Pp. 112-118.

6. Lukashenko О. V., Morozov E. V., Pagano M. Estimation of loss probability in Gaussian queues // Proceedings of the International Conference "Modern Probabilistic Methods for Analysis and optimization of Information and Telecommunication Networks". 2011. Pp. 142-147.

7. Лукашенко О. В. Имитационное моделирование гауссовских систем с потерями // Тезисы докладов Всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» Москва, РУДН. 2011. С. 257-259.

8. Lukashenko О. V., Morozov Е. V. Estimation of the overflow and loss probability in some gaussian queus // XXIX International Seminar on Stability Problems for Stochastic Models and V International Workshop «Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems», Book of Abstracts. Moscow: Institute of Informatics Problems, RAS. 2011. Pp. 79-80.

9. Lukashenko О. V. Gaussian queues in communication networks // Third Northern Triangular seminar. Programe and abstract. 2011. P. 14.

10. Lukashenko О. V., Morozov E. V. On the maximum workload for a class of Gaussian queues // International conference «Probability theory and its applications» in Commemoration of the Centennial of В. V. Gnedenko. 2012. Pp. 231-232.

11. Лукашенко О. В. Программа «Имитационное моделирование систем обслуживания с гауссовской очередью» [Электронный ресурс] // Хроники объединенного фонда электронных ресурсов "Наука и образование". 2012. № 8. Режим доступа: http://ofernio.ni/portal/newspaper/ofernio/2012/8.doc, свободный.

Подписано в печать 06.11.12. Формат 60x84 1/16 Гарнитура «Times». Уч.-изд. л. 1,0. Усл. печ. л. 1,0.Тираж 100 экз. Изд. № 339. Заказ № 90.

Карельский научный центр РАН Редакционно-издательский отдел 185003, Петрозаводск, пр. А. Невского, 50

Введение

Глава 1. Основные определения и предварительные результаты

1.1. Гауссовские процессы.

1.2. Дробное броуновское движение и его свойства.

1.3. Предельные теоремы для сетевых процессов.

1.4. Жидкостные модели

1.5. Элементы теории больших уклонений.

1.6. Правильно меняющиеся функции и их свойства.

Глава 2. Асимптотики больших уклонений гауссовских систем обслуживания.

2.1. Асимптотики при растущем буфере.

2.2. Асимптотики при растущем числе независимых источников

2.3. Асимптотики корреляционных характеристик.

Глава 3. Асимптотики максимума процесса нагрузки.

3.1. Сходимость по вероятности.

3.2. Сходимость в пространстве Ьр.

3.3. Нестационарный режим.

3.4. Асимптотика времени достижения растущего порогового значения

Глава 4. Статистическое моделирование гауссовских систем обслуживания

4.1. Моделирование гауссовских процессов

4.2. Оценивание некоторых характеристик

4.3. Регенеративный подход.

4.4. Альтернативные оценки вероятности переполнения.

Актуальность работы

В связи с распространением различных сетевых приложений и, как следствие, увеличением информации, передаваемой по компьютерным сетям, возникает необходимость анализа их загрузки, т. е. расчета различных характеристик, таких, например, как емкости буферов, пропускная способность и т. д. Последние два десятилетия ознаменовались существенными достижениями в исследовании сетевого трафика. Было, в частности, установлено, что процессы, протекающие в сетях передачи данных, могут обладать фрактальными свойствами (эффект самоподобия) и долговременной зависимостью (долгой памятью) [32, 54, 55, 75, 107]. Такие свойства радикально отличают современные модели от пуассоновских моделей, которые адекватно описывали процессы обслуживания и, в частности, сетевые процессы на протяжении долгого времени. Например, пуассоновские модели опираются на экспоненциальные распределения интервалов входного потока и времени обслуживания заявок (пакетов) и обладают короткой памятью и, с другой стороны, не обладают свойством самоподобия (фрактальности).

Столь существенное отличие в свойствах сетевого трафика потребовало разработки новых моделей и методов их анализа. В частности, наличие долговременной зависимости между данными сетевого трафика сделало весьма популярными модели, основанные на гауссовских процессах. Самым известным и изученным самоподобным гауссовским процессом с долговременной зависимостью является ДБ Д. Так, например, данный процесс, названный фрактальным трафиком, впервые был использован в качестве модели входного потока в работе [91]. Выбор такого рода входных потоков продиктован с одной стороны функциональными предельными теоремами, согласно которым гауссовские процессы возникают при суперпозиции большого числа независимых так называемых оп/оА>источников с тяжелыми хвостами на больших масштабах времени [88, 103], с другой стороны - статистическим анализом реальных сетевых процессов [57, 68, 104].

Степень разработанности

Гауссовские очереди (очереди с гауссовским входным потоком) обладают очень сложной структурой зависимости. Этот факт не позволяет в явном виде получить выражения для различных ключевых характеристик, в частности, для вероятности переполнения, то есть вероятности превышения некоторого уровня Ь. Отсутствие точных аналитических результатов вызывает необходимость исследования асимптотик соответствующих характеристик. Применительно к очередям обычно выделяют два типа асимптотик: асимптотики при растущем размере буфере 6, а также асимптотики в режиме многих источников: число гауссовских источников п растет и пропорционально растут размер буфера и скорость обслуживания. Например, для вероятности переполнения результаты вида

Р№>Ь)~/1(Ь), оо,

2 > пЪ) ~ /г(п), поо, где а ~ Ь означает что а/Ъ 1, называются точными асимптотиками, здесь Л; /2 некоторые явно заданные функции, - стационарный процесс нагрузки. Известно, что в гауссовской очереди с бесконечным буфером стационарный процесс загрузки <3 (текущая незавершенная работа в системе) распределен как максимум гауссовского процесса с отрицательным линейным сносом на положительной полуоси [97]. Иногда удается получить лишь логарифмические асимптотики, т. е.

1пР(<Э > Ь) ~/3(Ь), Ъ —>• оо, 1пР(<2 > пЪ) ~ /4(п), п ->■ оо, дающие менее полную информацию о вероятности переполнения. Отметим наиболее важные работы [33, 39, 48, 52, 53, 65, 86, 90], посвященные этой проблематике.

Наряду с вероятностью переполнения другой важной характеристикой систем обслуживания является максимум процесса нагрузки на конечном интервале [0, £] (пиковая нагрузка в системе). Для этой характеристики в работах [66, 96, 108] найдены асимптотики (при £ —> оо) в случае входного процесса

ДБД.

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

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

Методы исследований

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

Научная новизна

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

Практическая значимость

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

На защиту выносятся следующие основные результаты и положения:

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

2. Исследованы свойства альтернативной статистической ВМС-оценки вероятности переполнения гауссовской системы обслуживания.

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

4. Разработана программа для имитационного моделирования гауссовских систем обслуживания.

Апробация работы

Основные результаты диссертации докладывались на следующих конференциях: международный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 19-20 мая 2009 г.); 2nd Northern Triangular seminar (Стокгольм, 15-17 марта 2010 г.); международный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 25-26 мая 2010 г.); международный семинар «Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems» в рамках конгресса ICUMT'10 (Москва, 18-20 октября 2010 г.); международная конференция «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей» (21-я Белорусская школа-семинар по теории массового обслуживания, Минск, 3-5 февраля 2011 г.); 3rd Northern TYiangular seminar (Санкт-Петербург, 11-13 апреля 2011 г.); всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (Москва, 18-22 апреля, 2011 г.) международный семинар «Advances in Methods of Information and Communication Technology» (Петрозаводск, 28 апреля 2011 г.); V Международный семинар «Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем» (Светлогорск, 10-16 октября 2011 г.); VIII Международная Петрозаводская конференция «Вероятностные методы в дискретной математике» (2-9 июня 2012 г. Петрозаводск); 9th International Workshop on Rare Event Simulation (Тронхейм, 25-27 июня 2012 г.); международная конференция «Теория вероятностей и ее приложения», посвященная 100-летию со дня рождения Б. В. Гнеденко (Москва, 26-30 июня 2012 г.).

Работа поддержана РФФИ, грант 10-07-00017.

Публикации

Материалы диссертации опубликованы в 10 работах, из них 3 статьи в рецензируемых журналах [9-11], 3 статьи в сборниках трудов конференций [62, 79, 82] и 4 тезиса докладов [7, 78, 80, 81]. Получено свидетельство о регистрации электронного ресурса [8].

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения, перечня сокращений и условных обозначений, библиографии и списка иллюстраций. Общий объем диссертации 106 страниц, включая 19 рисунков. Список литературы включает 108 наименований.

Заключение

В диссертации рассмотрены стохастические системы с постоянной скоростью обслуживания, на вход которых поступает гауссовский процесс со стационарными приращениями. Приведен обзор основных теоретических результатов для процесса нагрузки в гауссовских системах обслуживания, включая асимптотики вероятности переполнения как при растущем буфера, так и при растущем числе потоков от отдельных источников (пользователей). Исследовано асимптотическое поведение максимума процесса нагрузки в системе обслуживания с одним сервером. На вход системы поступает процесс, содержащий линейную (детерминированную) компоненту и случайную компоненту, описываемую центрированным гауссовским процессом, у которого дисперсия является правильно меняющейся на бесконечности функцией с показателем V (О, 2). К такому классу процессов, в частности, относится сумма независимых ДБД. Показано, что при соответствующей нормировке максимум процесса нагрузки на интервале [0, сходится по вероятности (при £ оо) к некоторой явно выписанной константе. Этот результат обобщает соответствующий результат, полученный ранее в работе [108] для случая единственного входного процесса ДБД. Кроме того, проведено имитационного моделирование гауссовских систем обслуживания для оценивания вероятности переполнения/потери. Представлены результаты численных экспериментов, которые дают хорошее согласие с приведенными аналитическими результатами.

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

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

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

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

ФГШ — фрактальный гауссовский шум.

ЦПТ — центральная предельная теорема.

КХ — математическое ожидание с. в. X. Ю>Х — дисперсия с. в. X. те<і(Х) — медиана с. в. X. 1(А) — индикатор события А.

N(<2, а2) ~ нормально распределенная с. в. с параметрами а, а1. равенство по распределению. х+ — тах(0, х).

- — сходимость по вероятности. й — сходимость по распределению.

1. Биллингсли П. Сходимость вероятностных мер. М.: Наука, 1977.

2. Боровков А. А. Асимптотические методы в теории массового обслуживания. М.: Наука, 1980.

3. Жакод Ж., Ширяев А. Н. Предельные теоремы для случайных процессов. М.: Физматлит, 1994.

4. Кельтон В., Лоу А. Имитационное моделирование. Спб.: Питер, 2004.

5. Лидбеттер М., Линдгрен Г., Ротсен X. Экстремумы случайных последовательностей и процессов. Москва: Мир, 1989.

6. Лифшиц М. А. Гауссовские случайные функции. Киев: ТВиМС, 1995.

7. Лукашенко О. В., Морозов Е. В. Асимптотика максимума процесса нагрузки для некоторого класса гауссовских очередей // Информатика и ее применения. 2012. Т. 6, № 3. С. 81-89.

8. Лукашенко О. В., Морозов Е. В., Пагано М. Применение гауссовских процессов в моделировании сетевого трафика // Труды Карельского научного центра Российской академии наук. 2010. № 3. С. 51-58.

9. Лукашенко О. В., Морозов Е. В., Пагано М. Статистическое моделирование гауссовской очереди // Труды Карельского научного центра Российской академии наук. 2011. № 5. С. 55-62.

10. Льюис Д., Фистер К. Термодинамическая теория вероятностей: некоторые аспекты больших уклонений // Успехи математических наук. 1995. Т. 50. С. 47-88.

11. Питербарг В. И. Лекции по теории гауссовских процессов. М.: Изд-во МГУ, 1986.

12. Питербарг В. И. Асимптотические методы в теории гауссовских случайных процессов и полей. М.: Изд-во МГУ, 1988.

13. Сенета Е. Правильно меняющиеся функции. Москва: Наука, 1985.

14. Такач Л. Комбинаторные методы в теории случайных процессов. М.: Мир, 1971.

15. Addie R., Mannersalo P., Norros I. Performance formulae for queues with Gaussian input // Proceedings of ITC 16. 1999. Pp. 1169-1178.

16. Addie R., Mannersalo P., Norros I. Most probable paths and performance formulae for buffers with Gaussian input traffic // European Transactions in Telecommunications. 2002. Vol. 13. Pp. 183-196.

17. Adler R. J. An introduction to continuity, extrema, and related topics for general Gaussian processes. Institute of Mathematical Statistics, Hayward, CA, 1990.

18. Asmussen S. Applied Probability and Queues. Springer, 2002.

19. Asmussen S., Glynn P. Stochastic Simulation: algorithms and analysis. Springer, 2007.

20. Baldi P., Pacchiarotti B. Importance Sampling for the Ruin Problem for General Gaussian Processes. 2004.

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

22. Botvich D., Duffield N. Large deviations, the shape of the loss curve, and economies of scale in large multiplexers // Queueing Systems. 1995. Vol. 20. Pp. 293-320.

23. Bucklew J. A. Large Deviation Techniques in Decision, Simulation, and Estimation. Wiley, 1990.

24. Burnecki Z., Michna Z. Simulation of Pickands constants // Probab. Math. Stat. 2002. Vol. 22. Pp. 193-199.

25. Chang C. S. Performance Guarantees in Communication Networks. Springer, 2000.

26. Choe J., Shroff N. A central-limit-theorem-based approach for analyzing queue behavior in high-speed networks // IEEE/ACM Trans. Netw. 1998. Vol. 6. Pp. 659-671.

27. Choe J., Shroff N. On the supremum distribution of integrated stationary Gaussian processes with negative linear drift // Adv. Appl. Probab. 1999. Vol. 31. Pp. 135-157.

28. Choe J., Shroff N. Use of the supremum distribution of Gaussian processes in queueing analysis with long-range dependence and selfsimilarity // Stoch. Models. 2000. Vol. 16. Pp. 209-231.

29. Coeurjolly J. F. Simulation and identification of the fractional Brownian motion: a bibliographical and comparative study // Journal of Stat. Software. Vol. 5. 2000.

30. Crovella M. E., Bestavros A. Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes // IEEE/ACM Transactions on Networking. 1997. Vol. 5, no. 6. Pp. 835-846.

31. Debicki K. A note on LDP for supremum of Gaussian processes over infinite horizon // Stat. Probab. Lett. 1999. Vol. 44. Pp. 211-220.

32. Debicki K. Ruin probabilities for Gaussian integrated processes // Stoch. Process. Appl. 2002. Vol. 98. Pp. 151-174.

33. Debicki K. Gaussian Processes // Encyclopedia of Actuarial Sciences. 2004. Vol. 2. Pp. 752-757.

34. Debicki K. Some properties of generalized Pickands constants // Prob. Th. Appl. 2006. Vol. 50. Pp. 290-298.

35. Debicki K., Es-Saghouani A., Mandjes M. Transient characteristic of Gaussian fluid queues // Queueing Syst. 2009. Vol. 62. Pp. 383-409.

36. Debicki K., Kisowski P. A note on upper estimates for Pickands constants // Stat. Probab. Lett. 2008. Vol. 78. Pp. 2046-2051.

37. Debicki K., Mandjes M. Exact overflow asymptotics for queues with many Gaussian inputs //J. Appl. Probab. 2003. Vol. 40. Pp. 702-720.

38. Debicki K., Mandjes M. Traffic with an FBM limit: convergence of the stationary workload process // Queueing Syst. 2003. Vol. 46. Pp. 113-127.

39. Debicki K., Michna Z., Rolski T. Simulation of the asymptotic constant in some fluid models // Stoch. Models. 2003. Vol. 19. Pp. 407-423.

40. Debicki K., Palmowski Z. Heavy traffic Gaussian asymptotics of on-off fluid model // Queueing Syst. 1999. Vol. 33. Pp. 327-338.

41. Debicki K., Rolski T. A Gaussian fluid model // Queueing Syst. 1995. Vol. 20. Pp. 433-452.

42. Debicki K., Rolski T. Gaussian fluid models; a survey // Symposium on Performance Models for Information Communication Networks, Sendai, Japan. 2000.

43. Debicki K., Rolski T. A note on transient Gaussian fluid models // Queueing Syst. 2002. Vol. 41. Pp. 321-342.

44. Dembo A., Zeitouni O. Large Deviations Techniques and Applications. Springer, 1998.

45. Dieker A. B. Simulation of fractional Brownian motion. Master's thesis, the Vrije Universiteit, Amsterdam, 2002.

46. Dieker A. B. Extremes of Gaussian processes over an infinite horizon // Stoch. Process. Appl. 2005. Vol. 115. Pp. 207-248.

47. Dieker A. B. Extremes and fluid queues: Ph. D. thesis / the Vrije Universiteit, Amsterdam. 2006.

48. Dieker A. B., Mandjes M. On asymptotically efficient simulation of large deviation probabilities // Adv. in Appl. Probab. 2005. Vol. 37. Pp. 539-552.

49. Dieker A. B., Mandjes M. Fast simulation of overflow probabilities in a queue with Gaussian input // ACM Trans. Model. Comput. Simul. 2006. Vol. 16, no. 2. Pp. 119-151.

50. Duffield N., O'Connell N. Large deviations and overflow probabilities for the general single server queue, with applications // Proceedings of the Cambridge Philosophical Society. 1995. Vol. 118. Pp. 363-374.

51. Duffy K., Lewis J. T., Sullivan W. G. Logarithmic asymptotics for the supre-mum of a stochastic process // Ann. Appl. Probab. 2003. Vol. 13, no. 2. Pp. 430-445.

52. Erramilli A., Narayan O., Willinger W. Experimental queueing analysis with long-range dependent packet traffic // IEEE/ACM Trans. Netw. 1996. Vol. 4. Pp. 209-223.

53. Erramilli A., Roughan M., Veitch D., Willinger W. Self-similar traffic and network dynamics // Proc. IEEE 90. 2002. Pp. 800-819.

54. Es-Saghouani A., Mandjes M. On the correlation structure of Gaussian queues. // Stoch. Models. 2009. Vol. 25. Pp. 221-247.

55. Fraleigh C., Tobagi F., Diot C. Provisioning IP backbone networks to support latency sensitive traffic // Proc. IEEE Infocom. 2003.

56. Ganesh A., O'Connell N., Wischik D. Big Queues. Springer, 2004.

57. Giordano S., Gubinelli M., Pagano M. Bridge Monte-Carlo: a novel approach to rare events of Gaussian processes // Proc. of the 5th St.Petersburg Workshop on Simulation. St. Petersburg, Russia: 2005. Pp. 281-286.

58. Glynn P., Whitt W. Logarithmic asymptotics for steady-state tail probabilities in a single-server queue //J. Appl. Probab. 1994. Vol. 31 A. Pp. 413-430.

59. Heidelberger P. Fast simulation of rare events in queueing and reliability models // ACM Transactions on Modeling and Computer Simulation. 1995. Vol. 5. Pp. 43-85.

60. Hollander F. Large Devations. Fields Institute Monographs, AMS, 2000.

61. Hiisler J., Piterbarg V. I. Extremes of a certain class of Gaussian processes // Stochastic Processes and their Applications. 1999. Vol. 83. Pp. 257-271.

62. Hiisler J., Piterbarg V. I. Limit theorem for maximum of the storage process with fractional Brownian as input // Stochastic Processes and their Applications. 2004. Vol. 114. Pp. 231-250.

63. Kaj I., Taqqu M. Convergence to fractional Brownian motion and to the Telecom process: the integral representation approach: Tech. rep.: Department of Mathematics, Uppsala University, U.U.D.M., 2004.

64. Kilpi J., Norros I. Testing the Gaussian approximation of aggregate traffic // In Proceedings of the 2nd Internet Measurement Workshop. 2002. Pp. 49-61.

65. Kim H. S., Shroff N. B. Loss Probability Calculations and Asymptotic Analysisfor Finite Buffer Multiplexers // IEEE/ACM Transactions on Networking. 2001. Vol. 9. Pp. 755-768.

66. Kim H. S., Shroff N. B. On the Asymptotic Relationship between the Overflow Probability and the Loss Ratio // Advances in Applied Probability. 2001. Vol. 33. Pp. 836-863.

67. Konstantopoulos T., Zazanis M., Veciana G. D. Conservation laws and reflection mappings with application to multiclass mean value analysis for stochastic fluid queues // Stochastic Processes and their Applications. 1996. Vol. 65. Pp. 139-146.

68. Kroese D. P., Taimre T., Botev Z. I. Handbook of Monte Carlo Methods. Wiley, 2011.

69. Kulkarni V., Rolski T. Fluid model driven by an Ornstein-Uhlenbeck process // Probability in the Engineering and Informational Sciences. 1994. Vol. 8. Pp. 403-417.

70. Lau W., Erramilli A., Wang J. L., Willinger W. Self-similar traffic generation: the random midpoint displacement algorithm and its properties // Proceedings of ICC '95. 1995.

71. Leland W. E., Taqqu M. S., Willinger W., Wilson D. V. On the self-similar nature of ethernet traffic (extended version) // IEEE/ACM Transactions of Networking. 1994. Vol. 2. Pp. 1-15.

72. Lewis J. T., Russell R. An Introduction to Large Deviations for Teletraffic Engineers //In Performance '96, October 1996. 1996.

73. Likhanov N., Mazumdar R. Cell loss asymptotics in buffers fed with a largenumber of independent stationary sources // Journal of Applied Probability. 1999. Vol. 36. Pp. 86-96.

74. Lukashenko 0. V. Gaussian queues in communication networks // Third Northern Triangular seminar. Programe and abstract. 2011. P. 14.

75. Lukashenko 0. V., Morozov E. V. Gaussian Processes in Communication Networks // Proceedings of AMICT'2009. 2009. Pp. 112-118.

76. Lukashenko O. V., Morozov E. V. On the maximum workload for a class of Gaussian queues // International conference «Probability theory and its applications» in Commemoration of the Centennial of B. V. Gnedenko. 2012. Pp. 231-232.

77. Mandelbrot B. B., van Ness J. W. Fractional Brownian motions, fractional noises and applications // SIAM Review. 1968. Vol. 10. Pp. 422-437.

78. Mandjes M. Large Deviations of Gaussian Queues. Chichester: Wiley, 2007.

79. Marcus M. B., Shepp L. A. Sample behaviour of Gaussian processes // Proc. Sixth Berkeley Symp. Math. Stat. Prob. 1971. Vol. 2. Pp. 423-442.

80. Massouli6 L., Simonian A. Large buffer asymptotics for the queue with FBM input // J. Appl. Probab. 1999. Vol. 36. Pp. 894-906.

81. Michna Z. On tail probabilities and first passage times for fractional Brownian motion // Math. Methods Oper. Res. 1999. Vol. 49. Pp. 335-354.

82. Mikosch T., Resnick S., Rootzen H., Stegeman A. Is Network Traffic Apprixi-mated by Stable Levy Motion or Fractional Brownian Motion? // Ann. Appl. Probab. 2002. Vol. 12, no. 1. Pp. 23-68.

83. Morozov E. Communications Systems: Rare Events and Effective Bandwidths. Public University of Navarre, 2004.

84. Narayan O. Exact asymptotic queue length distribution for fractional Brownian traffic // Advances in Performance Analysis. 1998. Vol. 1. Pp. 39-63.

85. Norros I. Studies on a model for connectionless traffic, based on fractional Brownian motion // Conference on Applied Probability in Engineering, Computer and Communication Sciences INRIA/ORSA/TIMS/SMAI, Paris. 1993.

86. Norros I. A storage model with self-similar input // Queueing Syst. 1994. Vol. 16. Pp. 387-396.

87. Norros I. On the use of fractional Brownian motion in the theory of connectionless networks // IEEE J. Sel. Areas Comm. 1995. Vol. 13. Pp. 953-962.

88. Norros I., Mannersalo P., Wang J. Simulation of fractional Brownian motion with conditionalized random midpoint displacement // Advances in Performance Analysis. 1999. Vol. 2. Pp. 77-101.

89. Pickands J. Asymptotic properties of the maximum in a stationary Gaussian process // Trans. Amer. Math. Soc. 1969. Vol. 145. Pp. 75-86.

90. Piterbarg V. Large deviations of a storage process with fractional Brownian motion as input // Extremes. 2001. Vol. 4. Pp. 147-164.

91. Reich E. On the On the integrodifferential equation of Takacs I. // Ann. Math. Stat. 1958. Vol. 29. Pp. 563-570.

92. Ross S. M. Simulation. Elsevier, 2006.

93. Rubino G., Tuffin B. Rare Event Simulation using Monte Carlo Methods. Wiley, 2009.

94. Samorodnitsky G., Taqqu M. S. Stable Non-Gaussian Random Processes: Stochastic Models With Infinite Variance. Chapman & Hall, 1994.

95. Shao Q. M. Bounds and estimators of a basic constant in extreme value theory of Gaussian processes // Stat. Sin. 1996. Vol. 6. Pp. 245-257.

96. Simonian A., Virtamo J. Transient and stationary distributions for fluid queue and input processes with density // SIAM Journal of Applied Mathematics. 1991. Vol. 51. Pp. 1731-1739.

97. Taqqu M. S., Willinger W., Sherman R. Proof of a fundamental result in self-similar traffic modeling // Computer communication review. 1997. Vol. 27. Pp. 5-23.

98. Van de Meent R., Mandjes M., Pras A. Gaussian traffic everywhere? //In Proceedings of the IEEE International Conference on Communications. 2006.

99. Weiss A. A new technique for analyzing large traffic systems // Adv. Appl. Probab. 1986. Vol. 18. Pp. 506-532.

100. Whitt W. Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and their Application to Queues. Springer, New York, NY, USA, 2002.

101. Willinger W., Taqqu M. S., Leland W. E., Wilson D. V. Self-similarity in highspeed packet traffic: analysis and modeling of Ethernet traffic measurements // Statistical Sciences. 1995. Vol. 10, no. 1. Pp. 67-85.

102. Zeevi A., Glynn P. On the maximum workload in a queue fed by fractional Brownian motion // Ann. Appl. Probab. 2000. Vol. 10. Pp. 1084-1099.1. Список иллюстраций

103. Стабилизация оценки 7Гю(1) с ростом числа наблюдений.71

104. Сравнение двух методов оценки стационарной вероятности переполнения 7ГП(1).72

105. Зависимость вероятности переполнения 7ГП(1) от количества источников п.72

106. Точность аппроксимации (2.40).74

107. Выборочные траектории процессов нагрузки (конечный и бесконечный буфер).75

108. Доверительный интервал для Р^(4).78

109. Зависимость длины доверительного интервала от размера буфераЪ. 78

110. Относительная ошибка оценки (ДБД).87

111. Оценка 7Г1 (6) в сравнении с аппроксимацией (2.9).88г)

112. Выборочные реализации У .89

113. Гистограмма распределения У (п = 50).89

114. Гистограмма распределения У (п = 100) .90

115. Гистограмма распределения У (п — 500) .90

116. Гистограмма распределения У (п = 2000).91г)

117. Выборочные реализации У .91