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

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

ии3453667

С/

Бородина Александра Валентиновна

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

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

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

2 1 НОЯ 2т

Петрозаводск - 2008 г.

003453667

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

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

доктор физико-математических наук, профессор Евсей Викторович Морозов

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

доктор физико-математических наук, профессор Владимир Васильевич Рыков кандидат физико-математических наук, доцент Ирина Валерьевна Пешкова

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

Московский государственный университет

Защита состоится ". ...' .... 2001 г. в чж,. на

заседании диссертационного совета Д 212.190.03 в Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

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

Автореферат разослан п...... 200/г.

Учёный секретарь диссертационного совета Д 212.190.03

В. В. Поляков

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

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

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

Требования к повышению качества обслуживания (QoS) диктуются потребностью в надежных системах обслуживания с высокой устойчивостью к сбоям. Известным примером является сбой в сети AT&T в 1990 году, когда на протяжении 9 часов сеть была недоступна большей части зданий Нью-Йорка, что привело к большим финансовым потерям.

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

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

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

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

2, Метод существенной выборки: за счет изменения вероятностной меры редкое событие становится более вероятным.

Следует отметить, что несмотря на большой интерес к методам, основанным на ветвлении процесса (RESTART, метод расщепления), в настоящее время вопрос о статистических свойствах оценок остается в значительной степени открытым. Известно, что оценка вероятности переполнения очереди при использовании метода расщепления для марковских систем является несмещенной. Однако, только ограниченный класс систем вида М/М/- может быть описан марковским процессом. Более того, состоятельность оценки и доверительное оценивание на основе метода расщепления в общем случае тоже является открытой проблемой. Исследование состоятельности и асимптотической нормальности оценки для адаптивного многоуровневого метода расщепления было лишь недавно (2005 г.) проведено для некоторого узкого класса марковских процессов.

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

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

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

Цель диссертационной работы заключается в разработке метода ускоренного регенеративного имитационного моделирования (УРИМ) и построении на его основе состоятельных и асимптотически нормальных оценок вероятности перегрузки в одноканальных системах обслуживания. В работе решаются следующие основные задачи.

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

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

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

4. Исследовать дисперсию оценки при замене немарковского процесса очереди в системе М/G/1 на вложенную цепь Маркова.

5. Исследовать влияние зависимости циклов регенерации в методе УРИМ на точность доверительного оценивания.

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

При построении оценок вероятности перегрузки в немарковской системе обслуживания М/С/1 методом расщепления применен метод вложенной цепи Маркова.

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

Расширена область применения метода расщепления на случай оценки стационарной вероятности перегрузки, а также для проведения моделирования процесса нагрузки. Разработано программное обеспечение для оценивания вероятности перегрузки для процессов очереди и нагрузки в системах М/М/1, М/С?/1, а/0/\, а так же интервального оценивания методом УРИМ.

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

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

1. Разработал метод ускоренного регенеративного имитационного моделирования (УРИМ).

2. Построена состоятельная оценка стационарной вероятности перегрузки, получаемая методом УРИМ.

3. Доказана состоятельность оценок, построенных методом УРИМ.

4. Разработан алгоритм построения состоятельной оценки вероятности перегрузки и вероятности достижения заданного уровня на цикле регенерации процессом очереди и процессом нагрузки в системах М/С/1, а[й/!. Разработан комплекс программ для построения оценок.

5. Предложен метод уменьшения дисперсии оценки для процесса очереди в М/(3/1 на основе вложенной цепи Маркова.

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

Связь работы с научными программами, темами. Работа поддержана Российским Фондом Фундаментальных исследований, гранты 04-01-00671, 04-07-90115, 07-07-00088.

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:

1. 23-25 ноября 2005. Международная школа-конференция "Информационно-телекоммуникационные системы" МГИЭТ. Москва. Ускоренные методы моделирования в регенерирующих процессах обслуживания.

2. 23 - 25 августа 2006. Annual International Workshop. Advances in Methods of Information and Communication Technology (AMICT'06). ПетрГУ. Regenerative rare event estimation based on permutations.

3. 26 - 31 августа 2006. Russian-Scandinavian Symposium "Probability theory and applied probability"(PTAP'06). Using of regenerative sequences in Splitting method.

4. 21 - 22 августа 2007. Annual International Workshop. Advances in Methods of Information and Communication Technology (AMICT'07). ПетрГУ. Regeneration cycles dependence in Confidence Estimation by Splitting.

5. 10 - 12 сентября 2007. International workshop. Distributed Computer and Communication Networks: Theory and Application (DCCN'2007). Институт проблем передачи информации им А. А. Харкевича, Москва.

6. 22 - 26 октября 2007. XXVI International Seminar Stability Problems for Stochastic Models, Nahariya, Israel. Speed-up consistent estimation of a high workload probability in M/G/l queue.

7. 20 - 22 мая 2008. Annual International Workshop. Advances in Methods of Information and Communication Technology (AMICT'07). ПетрГУ. On Modification of Regenerative Splitting for Embedded Markov Chain.

8. 1 - 6 июня 2008. VII Международная Петрозаводская конференция "Вероятностные методы в дискретной математике". Регенеративная модификация метода расщепления.

9. 24 - 26 сентября 2008. RESIM, International Workshops on Rare Event Simulation, Rennes, France. A regenerative modification of the multilevel splitting.

По материалам диссертации опубликовано 10 работ, из них 8 статей [1,2, 3, 4, 5, 6, 7, 8] и тезисы 2 докладов [9, 10]

Структура и объем работы.

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

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

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

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

7

:= J I(x € A)f(x)dx = Е1(Х €А) = Р(Х € А),

где X - случайная величина с плотностью f(x), принимающая значения из множества Е, А С Е, 1{Х 6 А) - индикатор. Если 7 « 0, то событие {X 6 А} называют редким, а множество А редким множеством.

Дается обзор существующих методов имитационного моделирования, применяемых для оценивания вероятностей перегрузки очень малого порядка. К ним относятся метод классического имитационного моделирования Монте-Карло (МК), а также современные методы ускоренного моделирования: метод существенной выборки, RESTART, метод расщепления.

При оценивании вероятностей очень малого порядка (например, Ю-20 и меньше), классический метод МК становится неэффективен. Оценка 7 строится в форме выборочного среднего

7 =

N ■

Поэтому, при стремлении 7 —> 0 относительная ошибка оценивания у/Удг(7) _ ^/7 - 72 1

Л(7)

£7 7\fN VW

Таким образом, чтобы достигнуть заданной точности при малых значениях вероятности 7 требуется огромный размер выборки ЛГ, и значительно возрастает время моделирования.

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

Эффективность метода напрямую зависит от удачного выбора /(ж). Оптимальный выбор /(х) возможен при известном 7 (тогда \гаг(7) = 0), т. е. когда решение можно получить аналитически. Для сложных систем, где аналитическое решение получить невозможно, использование метода не всегда приводит к уменьшению дисперсии. Для некоторых /(ж), Уаг{7лг(/)) —» оо. В этой связи, иногда выгоднее воспользоваться стандартным методом моделирования МК, чем найти "хорошую" плотность /(ж).

Метод расщепления и метод RESTART являются методами ускоренного имитационного моделирования. Суть обоих методов состоит в разделении пространства состояний процесса на М вложенных подмножеств, границы которых называют порогами (уровнями) Li, i 6 [0,М]. При достижении некоторого уровня, траектория процесса расщепляется на несколько траекторий-потомков. Те из них, которые достигнут следующего уровня, тоже будут расщеплены. Между порогами траектория процесса моделируется стандартным методом МК. Таким образом, при увеличении количества траекторий, увеличивается шале достижения редкого множества. В формулу оценок входит множитель, компенсирующий искусственное размножение траекторий.

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

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

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

Преимуществом метода RESTART и метода расщепления является существенное сокращение времени получения оценки по сравнению с методом МК. Однако, статистические свойства оценок (в первую очередь, состоятельность и асимптотическая нормальность) недостаточно исследованы.

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

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

Во второй главе даны необходимые определения, свойства и теоремы теории регенерирующих процессов. Описан метод регенеративного моделирования для построения состоятельных и асимптотически нормальных оценок стационарных характеристик регенерирующего процесса на основе регенеративной центральной предельной теоремы (РЦПТ).

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

В третей главе описан метод ускоренного регенеративного имитационного моделирования (УРИМ) малых вероятностей. Рассматриваются два сле-

дующих случайных процесса, непрерывных справа.

• Процесс очереди {^(t), t > 0}, где u{t) - количество заявок в системе в момент времени £, включая заявку, которая обслуживается сервером. Для стационарной очереди обозначим слабый предел v{t) => и (что означает слабую сходимость P(f(i) & •) => P(v 6 •) при t —♦ оо).

• Процесс нагрузки (времени ожидания) {Wn, п > 1}, где Wn - время ожидания в очереди заявки с номером п. Обозначим Woo стацинарное время ожидания, когда существует слабый предел Wn =>■ Woo.

Сначала рассмотрим процесс очереди, а затем, модифицировав алгоритм моделирования, исследуем процесс нагрузки. Рассмотрим систему обслуживания GI/G/1 с бесконечным буфером для ожидающих требований, в предположении, что коэффициент загрузки р < 1.

Обозначим in и - момент прихода и ухода заявки с номером п, соответственно. Определим для процесса очереди X = {^(¿), t > 0} последовательность моментов регенерации уровня 0 (моментов 0-регенерации) т = (тг, г > 1), где моменты п определяются рекурсивно:

го = 0, п = min(i„ > г,-1 : u(tn — 0) = 0).

П>1

Обозначим at = т, — т,_1, г > 1, длины циклов регенерации уровня 0. Далее будем строить точечные оценки для следующих вероятностей:

1. вероятность того, что очередь достигнет (большого) значения L на цикле регенерации, т. е.

7(1) = Р( max iAt) > L),

O<t<ori W — '

2. вероятность того, что стационарная очередь превысит значение L, т. е.

7(2> = Р(„ > L).

При больших значениях уровня L вероятности 7'1) и малы и более того 7(1) -> 0, 7(2) -» 0 при L -> оо.

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

Метод построения циклов регенерации на основе расщепления приводится для двухуровневой модели (с единственным и множественными расщеплениями). Затем метод обобщается для общего случая многоуровневой модели расщепления с несколькими расщеплениями на каждом уровне. Построенная математическая модель циклов регенерации является основой метода УРИМ.

В методе УРИМ моделирование происходит по циклам регенерации, которые сгруппированы в пучки. Циклы регенерации принадлежат одному пучку,

если они имеют общую точку расщепления на первом уровне (¿1). Моделирование пучка начинается при старте одной траектории с уровня Ьо = 0. Расщепляя траекторию на заданных уровнях Ь^ мы увеличим вероятность достижения уровня Ь в Б :— Л1Д2 • • • Ям раз, где Я, - число расщеплений на уровне Ьг.

С точки зрения теории регенерации это означает, что вместо одного цикла регенерации (как в классическом методе МК) одним запуском мы генерируем Д (зависимых) циклов регенерации (пучок).

Если траектория, расщепившаяся на уровне Ьг, не достигает уровня ¿¡+1, то она, очевидно, не может расщепиться и на последующих уровнях ¿1+2,

¿¿+3____В этом случае фактически мы теряем := Яг+\Яг+2 • • • Да/ циклов

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

Используя эту идею, для каждой траектории, стартующей с уровня Ьо, мы получим пучок циклов, состоящий из Г> := Я1 • Я2 ■ • • Ям зависимых циклов регенерации.

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

Последовательность циклов регенерации, полученная методом УРИМ, представлена на рис. 1. Все циклы можно разбить на Яо групп зависимых цик-

Рис. 1: Регенеративная последовательность уровня Lo

лов, каждая группа содержит ровно D < оо циклов. Для любого j £ [(г — 1)D + 1, i О] длины циклов o/.j являются одинаково распределенными, но зависимыми случайными величинами, г € [1, Яо]. Всего генерируется п := Яо • Ri • ■ • Ям = Яо • D циклов.

На рис. 1 видно, что последовательность зависимых циклов регенерации сама регенерирует в моменты r,.d, i G [0, Яо], когда стартует новый пучок траекторий с уровня Ьо. Поэтому последовательность зависимых циклов является регенерирующей. Это можно назвать вложенной регенерацией. Циклы

вложенной (по моментам старта пучков) регенерации являются независимыми. Длины таких циклов - независимые одинаково распределенные случайные величины (н. о. р. с. в.), и равны сумме из D длин исходных (зависимых) циклов, составляющих данный пучок:

ÍD

Pi- ^ Oíj, i - l,...Ro.

j=(i-l)-D+l

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

В системах обслуживания с Пуассоновским входным потоком заявок (М/ • /•) выполняется специальное свойство, состоящее в том, что доля заявок, которые в момент прихода наблюдают систему в некотором состоянии А, совпадает в пределе с долей времени, когда система находится в сотоянии А. Это свойство носит название PASTA (Poisson Arrivals See Time Averages).

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

При моделировании методом УРИМ в работе также использовано субэкспоненциальное распределение Парето в качестве распределения времени обслуживания в системе M/G/1 (а также распределения интервалов между приходами) требований в GI/G/1). Выбор данного распределения обусловлен результатами наблюдения за реальным трафиком в информационных сетях. Необходимые определения приводятся в четвертом параграфе.

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

Рассмотрим построение оценки вероятности 7'1'. Задача оценивания такой вероятности является традиционной для метода расщепления. Как правило, исследования свойств оценки ограничены обоснованием несмещенности в случае марковского процесса.

Для каждого пучка введем случайные величины

«х>

Yt:= Y1 í = !,■••,Яо,

J=(¿-1) D+1

где /= 1, если очередь достигает уровня L на j-м цикле регенерации. Последовательность j > 1} является регенеративной с постоянной длиной циклов рг = D, i € [1, До] и моментами регенераци тго, г S [0, ño], п = RqD.

Регенеративный метод дает следующее выражение для 7'1', если Eßi < 00:

N

7(1)= lim y^I^/N = EYi/Eßi = Р( max v{t)>L).

TV—»00 ' 0<t<ai

Регенеративная оценка вероятности 7'1' имеет стандартную форму выборочного среднего

Vß° Y• V" г О')

Стандартная оценка 7^^(До) вероятности 7'1' методом расщепления равна

^W(Jto) =--.

R0R1.....Rm

Теорема 1 Оценка ■у^(До) вероятности 7^ = Р( max v(t) > L), получен-

0<t<ai

пая методом УРИМ, совпадает с регенеративной оценкой , построенной на п — RqD циклах регенерации, т. е.

7(1)(ßo)=7i1)-

Следствие 1 Оценка 7'^ (До), построенная методом УРИМ, является сильно состоятельной оценкой вероятности 7^.

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

7(1).

На основе методов теории случайных блужданий доказана

Теорема 2 Пусть в системе М/М/1 выполняется условие стационарности р = \/ß < 1. Тогда аналитическое выражение для имеет вид:

7(1) = Р( max vlt) > L) — pL 7 1 •

0<t<aj 4 ' ~ ' pL — 1

Моделирование системы М/М/1 показывает хорошее согласие метода УРИМ с аналитическим результатом. В области малых значений порога L < 20 численные значения также соответствуют формуле из теоремы 2.

Построим состоятельную оценку вероятности 7® = Р(и > L) для непрерывного и дискретного случая (т. е. соответственно, оценку доли времени, когда очередь пребывает выше заданного уровня L, и оценку доли заявок, которые приходят в систему при величине очереди, большей L).

Теорема 3 Оценка вероятности

£ Г I(v(t) > L)dt

ЧгР —

построенная no n = RoD циклам регенерации, полученным методом УРИМ, является строго состоятельной.

При переходе от непрерывного случая к дискретному, структура регенеративной последовательности не меняется. Мы делаем переход от шкалы непрерывного времени к шкале событий (приходы/уходы).

Пусть Zj - число событий (приходов/уходов) когда очередь превышала порог L на j-м цикле регенерации, и - длина j-го цикла, равная числу событий на j-м цикле, j = 1,... ,D-Rq. Последовательность (а также

{аз}j-i'0) является регенеративной и регенерирует в моменты г,о, г 6 [0, До] (см. стр. ??). Число циклов регенерации равно числу пучков До. Определим величины

i-D »D

Y, := Zi' А := *=1>--->До-

j = «-l)D+l j=(.-l)D+l

По построению, случайные величины {У,} (а также {/?>}) являются н. о. р. Заметим, что в терминах событий величина У< равна числу событий {v(t) > L} на пучке траекторий и Yi = Nm+i- Длина цикла Pi равна количеству всех событий на траекториях пучка с номером г.

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

я0

& = Nso№ • • • RM+l) + Ngi (Д2 • ■ ■ Rm+l) + --- + NgM, Rm+1 = 1.

3 = 1

Оценка вероятности = P(v > L), построенная методом УРИМ, в дискретном случае имеет вид:

7(2)(^M+i) = м ,nNA^L+i r ,. Ям+i = 1.

Теорема 4 В системе М/G/l выполняется равенство

7i2)=7(2)(NM+О,

где п = RoD.

Следствие 2 Оценка 7®(ЛГм+1) вероятности 7®, построенная методом УРИМ, является строго состоятельной.

В системе М/С/1 оценку 7^(Л?м+1) можно использовать как для непрерывного, так и для дискретного времени. В случае системы более общего вида а/й/1 оценку 7'2'(Л^м+1), построенную методом УРИМ, можно использовать только для дискретного времени.

Результаты моделирования системы М/М/1 показали, что метод УРИМ дает оценку, которая очень хорошо согласуется с аналитической формулой 7^ = рс+1, в том числе в области малых значений Ь.

Если процесс не является марковским, то траектории после расщепления являются зависимыми. В системе М/С/1 процесс очереди не является марковским. В момент прихода заявки остается незавершенное время обслуживания с неизвестным распределением и, поэтому, после расщепления траектории процесса будут зависимыми. Эта зависимость может значительно повлиять на дисперсию оценки.

Для устранения данной проблемы при моделировании системы М/С/1, можно применить метод вложенной цепи Маркова. Вместо немарковского процесса Ь > 0, моделируется цепь Маркова и* = ), где С -моменты ухода. Для сохранения вида оценок 7^(До),7^2'(Лгм+1.), требуется внести изменения в алгоритм метода УРИМ.

Условие расщепления: Если в момент ухода заявки траектория, стар-туюхцая в области Сг = [Ь,, £¿+1), пересекла некоторый уровень г + к < М + 1, то она расщепляется на П£=1 Кг+з траекторий (11м= 1).

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

Для сравнения результатов эксперимента в системе М/С/1 с субэкспоненциальным распределением интервалов обслуживания 5 используется асимптотическая формула

Р(» > к) ~ р) У)с1у, к - оо,

где Л - интенсивность приходов, интенсивность загрузки р < 1. Результаты имимтационных экспериментов показывают хорошую близость оценок, полученных методом УРИМ с использованием вложенной цепи Маркова к результатам, полученным по формуле, а также более стабильное поведение оценки по сравнению с обычным методом расщепления. При этом выигрыш в дисперсии оценки составляет 2-3 порядка.

Метод расщепления применяется преимущественно для целочисленного процесса, где скачки имеют значения ±1. В таком случае расщепления можно проводить точно на каждом заданном уровне 1ц.

Алгоритм метода можно модифицировать для оценки вероятностей, аналогичных 7^,7®, но определенных для процесса времени ожидания (нагрузки).

Такая задача рассмотрена в шестом параграфе. В терминах процесса нагрузки 7'1' - вероятность того, что нагрузка превысит фиксированный уровень L в течение цикла регенерации, т. е. 7'1' = Р( max Wn > L). Вероят-

0<n<«i

ность = Р(1Уоо > L) - вероятность превышения стационарной нагрузкой значения L, где Wn => Woo.

Процесс нагрузки даже в системе GI/G/1 является цепью Маркова и удовлетворяет рекуррентному соотношению Линдли

Wn+1 = (wn + Хп)+, п > 1, m = О,

где Хп = Sn — т„, тп = tn — in_ 1 - интервал между приходами п-й и п — 1-й заявок, Sn - время обслуживания п-й заявки. За один скачок процесс может пересечь несколько порогов Ьг между двумя последовательными расщепления.

Для построения оценок используется метод УРИМ с таким же условием расщепления, как и для случая вложенной цепи Маркова, только расщепление происходит в момент прихода.

В системе М/М/1 верны соотношения

7<2> = P(Woo > L) =

7'1' = Р( max CD

0<n<ai ' 1 — pe-^-X>L

Сравнение оценок, полученных при моделировании процесса нагрузки методом УРИМ, и значений, вычисленных по аналитическим формулам (1) показало хорошую точность метода УРИМ.

Для более сложных систем M/G/l, GI/G/1 было проведено сравнение оценок, полученных методом УРИМ, с оценками, построенными классическим методом МК. Численные эксперименты подтверждают близость двух оценок, однако метод МК дает большую дисперсию. При этом время моделирования методом МК существенно (ira несколько порядков) при достаточно большом L превышает время моделирования методом УРИМ.

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

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

циклами в пучке. Число пучков равно Ro, в каждом пучке D = R\ - ■■ Им циклов, общее количество циклов при моделировании равно п = Ro ■ D. При доверительном оценивании вероятности

Р( max u{t) >L) = 7(1) = EYi/D,

0<t<ai

(точечная состоятельная оценка 7'1' = 7^^ (До) которой строится методом УРИМ при n=Ro-D) для каждого пучка вводится случайная величина

i-D

У, := IU),i=l,..-,Rо.

j=(i-l)-D+l

Пусть EYx < 00. Для Ro циклов регенерации (при а, = D и щ = D) несмещенная оценка vr0 дисперсии Var(Y\ — D ■ 7'1') равна:

До

vRo = 1/(Ло - 1) - D ■ 7(1))2, Ro > 1. i=1

Выражение для 100(1 — S)% доверительного интервала имеет вид:

7(1> ±

D^Ro(Ro - 1)

где удовлетворяет условию Р(Аг(0,1) < гь) = 1 — 5/2, а точечная оценка 7^ строится методом УРИМ.

Для доверительного оценивания вероятности 7^ = > Ь) определяются величины

{■О г£>

У, := А := а,, г= 1,...,Ло,

¿=(»-1)-С+1 ¿=(¿-1)0+1

где - число событий когда очередь превышала порог Ь на ]-м. цикле. Выражение для 100(5 — 1)% доверительного интервала имеет вид:

7(2)±

у/МЪ-Ц-Ръ

а точечная оценка = 7^2'(Лгл/+1) строится методом расщепления.

Для системы М/С/1 доверительный интервал можно записать в более удобной для вычислений форме:

7<2>±

NM+W(RO-1)

Во втором параграфе исследована роль зависимости циклов регенерации

при построении доверительных интервалов с использованием метода УРИМ

для вероятности 7^ = Р( шах u{t) > L). Циклы в пучках зависимы и дис-

0<t<ai

персия о-2 = VarZi = Var(Yi - D~/w) имеет вид

а2 = D ■ Var(I^) + 2^ ^ E(/(,)/(i+J_1)) - (7<х>)2 • D(D - 1).

3=2 i=l

Пусть cik - число редких событий на г-м пучке. Теорема 5 При п = RoD —> с» имеет место сходимость с в. 1

а2

Vn~>D>

где

пк=1 1

и оценка 71 ' вероятности у* ' строится методом УРИМ.

Для исследования вклада зависимости циклов внутри пучка в длину доверительного интервала вводятся величины: Д - половина длины доверительного интервала с учетом зависимости и Д1 - половина доверительного интервала без учета зависимости (т. е. если считать циклы в пучке независимыми).

Пусть х = Д102/7^ - точность вычисления доверительно интервала (х% от и у := ]Д — Д1|102/7^ - погрешность оценивания (в % от 7'1') в

случае, если пренебречь зависимостью циклов регенерации.

Теорема 6 Пусть гв удовлетворяет условию Р(ЛГ(0,1) < г^) = 1 — <5/2, и выполняется п > 1/7^, тогда справедливо соотношение

Дг < . / 10Ч2

Д у х27 10е г2

Следствие 3 При условии у^п > —где х € (0, 100] выполняется

У- € (0.9, 1]. х

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

пренебрежения зависимостью внутри пучка точность вычисления практически совпадает с ошибкой оценивания. Например, в проведенных экспериментах 7(1)га и 10®. Если х = 10, гг = 1.96, тогда Д1/Д < 0.061 и у/х « 0.938.

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

Список опубликованных работ по теме диссертации

Статьи

[1] Бородина А. В., Морозов Е. В. Доверительное оценивание вероятности переполнения буфера на основе ускоренного регенеративного моделирования системы М/М/1. Труды ИПМИ КарНЦ РАН, 2006, т, 7, с. 125-135, (вклад диссертанта 50%).

[2] Borodina A., Morozov Е. Simulation of rare events with speed-up techniques: Splitting and RESTART. Proceedings of Finnish Data Processing Week at the Petrozavodsk State University (FDPW'2005), 2006, vol. 7, pp. 152-173, (вклад диссертанта 50%).

[3] A. Borodina. Rare Events Regenerativ Estimation of Queues Based on Splitting. //Proceedings of International workshop. Distributed Computer and Communication Networks: Theory and Application (DCCN'2007), V. 1. Moscow: IITP RAS, 2007, pp. 50-55.

[4] Бородина А. В., Морозов E. В. Ускоренное регенеративное моделирование вероятности перегрузки односерверной очереди. ОПиПМ, 2007, т. 14, в. 3, с. 385-397, (вклад диссертанта 50%).

[5] А. В. Бородина. Влияние зависимости циклов, полученных методом расщепления, при доверительном оценивании вероятности перегрузки в системе M/G/1. Труды ИПМИ КарНЦ РАН, 2007, т. 8, с. 76-83.

[6] Alexandra V. Borodina, Evsey V. Morozov. Speed-up consistent estimation of a high workload probability in M/G/1 queue. // Transactions of XXVI International Seminar Stability Problems for Stochastic Models, Nahariya, Israel, 2007, V. I, pp. 36-42, (вклад диссертанта 50%).

[7] Бородина А. В., Морозов Е. В. Ускоренное состоятельное оценивание вероятности большой загрузки в системах M/G/1, GI/G/1. Сб. Статистические методы оценивания и проверки гипотез, Пермь, 2007, с. 124140, (вклад диссертанта 50%).

[8] A. Borodina, Е. Morozov. A regenerative modification of the multilevel splitting. // Proceedings of 7th International Workshop on Rare Event Simulation (RESIM 2008), September 24-26, 2008, Renn, c. 276-282, (вклад диссертанта 50%).

Тезисы докладов

[9] Alexandra V. Borodina. Using of regenerative sequences in Splitting method. Extended abstracts of Russian-Scandinavian symposium, Probability theory and applied probability (PTAP'06, August 26-31, 2006, Petrozavodsk), pp. 18-20.

[10] А. В. Бородина. Ускоренные методы моделирования в регенерирующих процессах обслуживания. Сборник тезисов Международной школы-конференции "Информационно-телекоммуникационные системы МГИ-ЭТ, 2005, с. 45.

Формат 60x84 V16. Бумага офсетная. Гарнитура «Times». Уч.-изд. л. 1,0. Усл. печ. л. 1,2. Подписано в печать 29.10.08. Тираж 100 экз. Изд. № 126. Заказ № 755.

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

Введение

1 Ускоренные методы оценивания вероятностей редких событий

1.1 Проблема оценивания вероятностей редких событий.

1.2 Классическое имитационное моделирование.

1.3 Метод существенной выборки.1£г

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

1.4.1 Алгоритм метода расщепления.19,

1.4.2 Оптимальное разбиение.

1.5 Метод RESTART.

1.5.1 Алгоритм метода RESTART.

2 Регенеративное имитационное моделирование

2.1 Регенерирующие процессы

2.2 Метод имитационного регенеративного моделирования.

2.3 Достаточное условие применимости регенеративного метода

2.4 Доверительное регенеративное оценивание в случае зависимых циклов.

3 Точечное оценивание методом УРИМ в системах с одним сервером

3.1 Оцениваемые вероятности.

3.2 Построение циклов регенерации методом расщепления.

3.2.1 Двухуровневая модель.

3.2.2 Многоуровневая модель.

3.3 Свойство PASTA для системы M/G/1.

3.4 Субэкспоненциальные распределения.

3.5 Точечное оценивание для процесса очереди.

3.5.1 Построение оценки вероятности 7^).

3.5.2 Вычисление оценки вероятности 7^) для конкретных моделей

3.5.3 Построение оценки вероятности 7^).

3.5.4 Вычисление оценки вероятности 7^ для конкретных моделей

3.5.5 Метод расщепления для вложенной цепи Маркова

3.5.6 Вычисление оценки 7^ с использованием метода вложенной цепи Маркова в системе М/Pareto/1.

3.6 Точечное оценивание для процесса нагрузки.

3.6.1 Асимптотика для субэкспоненциального времени обслуживания

3.6.2 Метод УРИМ для оценивания вероятностей 7^, 7^

3.6.3 Результаты моделирования для некоторых моделей

Интервальное оценивание методом УРИМ

4.1 Доверительное оценивание для процесса очереди.

4.1.1 Доверительный интервал для вероятности 7^).

4.1.2 Доверительный интервал для вероятности 7^).

4.2 Влияние зависимости циклов в пучке на длину доверительного интервала для оценки вероятности 7^)

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

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

Требования к повышению качества обслуживания (QoS) диктуются потребностью в надежных системах обслуживания с высокой устойчивостью к сбоям. Известным примером является сбой в сети AT&T в 1990 году, когда на протяжении 9 часов сеть была недоступна большей части зданий Нью-Йорка, что привело к большим финансовым потерям [33].

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

Целью имитационного моделирования систем (сетей) обслуживания обычно является построение оценки некоторых стационарных или переходных характеристик, от которых зависит качество системы (сети) с точки зрения пользователя. Примерами таких характеристик являются стационарное время ожидания заявок в очереди, вероятность потери заявок при перегрузке буфера требований, вероятность превышения интервала ожидания заявки в очереди, вероятность переполнения буфера до того, как система станет пустой и т.д. При этом оцениваемые характеристики очень малы (порядка Ю-9 и ниже) [42, 45], следовательно применение стандартного метод Монте-Карло требует слишком много времени для получения результата с высокой точностью.

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

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

2. Метод существенной выборки: за счет изменения вероятностной меры редкое событие искусственно становится более вероятным.

Следует отметить, что несмотря на большой интерес к методам, основанным на расщеплении (RESTART, метод расщепления), в настоящее время открытыми остаются вопросы о статистических свойствах оценок. Известно, что оценка вероятности переполнения очереди при использовании метода расщепления для марковских систем является несмещенной (см. [34]). Однако, только ограниченный класс систем вида MJMJ- может быть описан марковким процессом. Более того, состоятельность оценки и доверительное оценивание на основе метода расщепления в общем случае тоже является открытой проблемой. Исследование состоятельности и асимптотической нормальности оценки для адаптивного многоуровневого метода расщепления было лишь недавно (2005 г.) проведено для некоторого узкого класса марковских процессов (см. [23]).

В данной работе основное внимание уделяется системам обслуживания, которые характеризуются пуассоновским потоком и произвольно распределенной длительностью обслуживания при одном обслуживающем канале, а также системам общего вида (M/G/l, GI/G/1 в символике Кендалла [48]), где процесс очереди не является марковским.

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

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

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

2. Построить состоятельную оценку стационарной вероятности перегрузки в одноканальной системе общего вида методом УРИМ для процессов очереди и нагрузки.

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

4. Исследовать дисперсию оценки при замене немарковского процесса очереди в системе М/G/l на вложенную цепь Маркова.

5. Исследовать влияние зависимости циклов регенерации в методе УРИМ на точность доверительного оценивания.

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

Применен метод вложенной цепи Маркова при построении оценок вероятности перегрузки в немарковской системе обслуживания М/G/l методом расщепления.

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

Расширена область применения метода расщепления на случай оценки стационарной вероятности перегрузки, а также для проведения моделирования процесса нагрузки. Разработано программное обеспечение для оценивания вероятности перегрузки для процессов очереди и нагрузки в системах М/М/1, M/G/l, GI/G/1, а так же интервального оценивания методом УРИМ.

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

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

1. Метод ускоренного регенеративного имитационного моделирования , (УРИМ) на базе метода расщепления.

2. Построена состоятельная оценка стационарной вероятности перегрузки, получаемая методом УРИМ.

3. Доказана состоятельность оценок, построенных методом УРИМ.

4. Разработан алгоритм построения состоятельной оценки вероятности перегрузки и вероятности достижения заданного уровня на цикле регенерации процессом очереди и процессом нагрузки в системах M/Gf 1, GI/G/1. Разработан комплекс программ для построения оценок.

5. Предложен метод уменьшения дисперсии оценки для процесса очереди в М/G/1 на основе вложенной цепи Маркова.

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

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

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:

1. 23-25 ноября 2005. Международная школа-конференция "Информационно-телекоммуникационные системы" МГИЭТ. Ускоренные методы моделирования в регенерирующих процессах обслуживания.

2. 23 - 25 августа 2006. Annual International Workshop. Advances in Methods of Information and Communication Technology (AMICT'06). ПетрГУ. Regenerative rare event estimation based on permutations.

3. 26 - 31 августа 2006. Russian-Scandinavian Symposium "Probability theory and applied probability" (PTAP'06). Using of regenerative sequences in Splitting method.

4. 21 - 22 августа 2007. Annual International Workshop. Advances in Methods of Information and Communication Technology (AMICT'07). ПетрГУ. Regeneration cycles dependence in Confidence Estimation by Splitting.

5. 10 - 12 сентября 2007. International workshop. Distributed Computer and Communication Networks: Theory and Application (DCCN'2007). Институт проблем передачи информации им А. А. Харкевича, Москва.

6. 22 - 26 октября 2007. XXVI International Seminar Stability Problems for Stochastic Models, Nahariya, Israel. Speed-up consistent estimation of a high workload probability in M/G/l queue.

7. 20 - 22 мая 2008. Annual International Workshop. Advances in Methods of Information and Communication Technology (AMICT'07). ПетрГУ. On Modification of Regenerative Splitting for Embedded Markov Chain.

8. 1 - 6 июня 2008. VII Международная Петрозаводская конференция "Вероятностные методы в дискретной математике". Регенеративная модификация метода расщепления.

9. 24 - 26 сентября 2008. RESIM, International Workshops on Rare Event Simulation, Rennes, France. A regenerative modification of the multilevel splitting.

По материалам диссертации опубликовано 9 работ, из них 7 статей [3, 4, 5, 6, 18, 19, 20] и тезисы 2 докладов [2, 17]

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

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

Во второй главе даны необходимые факты из теории регенерирующих процессов. Описан метод регенеративного моделирования для построения состоятельных и асимптотически нормальных оценок стационарных характеристик регенерирующего процесса на основе регенеративной центральной предельной теоремы (РЦПТ). Описаны достаточные условия применимости регенеративного метода и доверительное регенеративное оценивание в неклассическом случае fc-зависимых циклов регенерации.

В третей главе описан способ построения циклов регенерации (регенеративная модель) с использованием метода расщепления для двухуровневой и многоуровневой модели с расщеплением. С учетом выделенной регнератив-ной структуры доказана состоятельность оценки вероятности превышения заданного уровня, получаемой методом УРИМ. Задача оценивания такой вероятности является традиционной для метода расщепления [34]. Как правило, исследования свойств оценки ограничиваются обоснованием несмещенности в случае марковского процесса [29]. Также в данной главе предложен метод построения оценки стационарной вероятности'перегрузки, который основан на методе расщепления с запуском по циклам регенерации. Обоснована^'состоятельность такой оценки для регенерирующих процессов. Для процесса очереди в системе МjParetoj 1 с пуассоновским потоком и интервалами обслуживания, распределенными по закону Парето, дана модификация метода расщепления с использованием метода вложенной цепи Маркова. Предложено расширение метода расщепления для моделирования процесса нагрузки вч системах М/С/1, GI/G/1. Приведены результаты экспериментов, подтвер-ждаюие согласованность значений оценок, полученных методом УРИМ, с аналитическими формулами (где это возможно) и значениями, полученными методом Монте-Карло.

В четвертой главе исследуется асимптотическая нормальность состоятельных оценок, полученных в главе 3. Приведены формулы для построения доверительного интервала вероятности достижения заданного уровня на цикле регенерации и стационарной вероятности переполнения для процесса очереди и процесса нагрузки. В данной главе исследована также роль зависимости циклов регенерации, полученных методом УРИМ.

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

Заключение

В работе представлен метод ускоренного регенеративного имитационного моделирования (УРИМ) для оценивания вероятностей редких событий при моделировании регенерирующих процессов в одноканальных системах обслуживания. Суть метода заключается в применении теории регенерации для исследования свойств оценки вероятности редких событий в методе расщепления.

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

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

Разработан алгоритм построения состоятельной оценки вероятности перегрузки и вероятности достижения заданного уровня на цикле регенерации процессами очереди о нагрузки в системах M/G/l, GI/G/1.

Доказана состоятельность и асимптотичекая нормальность точечных оценок, построенных методом УРИМ.

Предложен метод уменьшения дисперсии оценки для процесса очереди в М/G/l на основе вложенной цепи Маркова. Доказана эффективность (дисперсии оценки) замены немарковского процесса очереди в системе М/G/l на вложенную цепь Маркова.

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

Полученные результаты носят как теоретический так и прикладной характер, представляя расширение алгоритма традиционного метода расщепления на область регенерирующих (вообще говоря, немарковских) процессов в одноканальных системах обслуживания. Разработан комплекс программ для оценивания вероятности редких событий для процесса очереди и нагрузки в системах М/М/1, М/G/l, GI/G/1, а так же интервального оценивания методом УРИМ.

1. А. Боровков. О субэкспоненциальных распределениях и асимптотике распределения максимума последовательных сумм. // Сибирский математический журнал, 2002, вып. 43, 6, с. 1235-1263.

2. А. В. Бородина. Ускоренные методы моделирования в регенерирующих процессах обслуживания. // Сборник тезисов Международной школы-конференции "Информационно-телекоммуникационные системы МГИЭТ, 2005, с. 45.

3. А. В. Бородина. Влияние зависимости циклов, полученных методом расщепления, при доверительном оценивании вероятности перегрузки в системе M/G/1. Труды ИПМИ КарНЦ РАН, 2007, т. 8, с. 76-8з!

4. А. В. Бородина, Е. В. Морозов. Доверительное оценивание вероятности переполнения буфера на основе ускоренного регенеративного моделирования системы М/М/1. Труды ИПМИ КарНЦ РАН, вып. 7, 2006,125-135.

5. А. В. Бородина, Е. В. Морозов. Ускоренное регенеративное моделирование вероятности перегрузки односерверной очереди. ОПиПМ, 2007, т. 14, в. 3, с. 385-397.

6. В. А. Ивницкий. Теория сетей массового обслуживания. М.: Издательство Физико-математической литературы, 2004.

7. Д. JL Иглехарт, Д. С. Шедлер. Регенеративное моделирование сетей массового обслуживания, М., Радио и связь, 1984.

8. В. Феллер. Введение в теорию вероятностий и ее приложения. Том 1. Изд. М.:Мир, 1964.

9. А. Н. Ширяев. Вероятность. Наука, Москва, 1980.

10. S. Asmussen. Applied probability and queues. Institute of Mathematical Statistic, University of Copenhagen, Denmark. John Wiley & Sons Ltd, 1987.

11. S. Asmussen. Applied Probability and Queues, 2nd ed., Springer, NY, 2003.

12. S. Asmussen, S. G. Foss. Renovation, regeneration, and coupling in multi-server queues in continuous time. Proceedings of the 3rd Finnish-Soviet Symposiu on Probability Theory in Mathematical Statistics, 1992.

13. S. Asmussen, C. Kluppelberg, K. Sigman. Sampling at subexponential times, with queueing applications. Stochastic Process. Appl. 79 (1999) 265-286.

14. A. J. Bayes. Statistical techniques for simulation models. The Australian Computer Journal, 2(4):180-184, 1970.

15. A. J. Bayes. A minimum variance technique for simulation models. Journal of the Association for Computing Machinery, 19:734-741, 1972.

16. A. V. Borodina. Using of regenerative sequences in Splitting method. //Extended abstracts of Russian-Scandinavian symposium, Probability theory and appliedprobability (PTAP'06, August 26-31, 2006, Petrozavodsk), pp. 18-20.

17. A. Borodina. Rare Events Regenerativ Estimation of Queues Based on Splitting. //Proceedings of International workshop. Distributed Computer and CommunicE Networks: Theory and Application (DCCN'2007), V. 1. Moscow: IITP RAS, 2007, pp. 50-55.

18. A. Borodina, E. Morozov. Simulation of rare events with speed-up techniques: Splitting and RESTART. Proceedings of Finnish Data Processing Week at the Petrozavodsk State University (FDPW'2005), 2006, Vol. 7, pp. 152-173.

19. A. V. Borodina, E. V. Morozov. Speed-up consistent estimation of a high workload probability in M/G/l queue. // Transactions of XXVI International Seminar Stability Problems for Stochastic Models, Nahariya, Israel, 2007, V. I, pp. 36-42.

20. P. Bratley, B. L. Fox, and L. E. Schrage. A guide to simulation. Second edition. Springer-Verlag, New York, 1987.

21. P. Billingsley. Convergence of Probability Measures. Wiley, New York, 1968.

22. F.Cerou, A. Guyader. Adaptive multilevel splitting for rare event analysis, INRIA, reseracrh report No 5710, Oct. 2005.

23. V. P. Chistyakov. A theorem on sums of independent random variables and its application to branching random processes. Th. Prob. Appl. 9, pp. 640-648, 1964.

24. M. Crane, D. L. Iglehart. Simulating stable stochastic systems, III: Regenerative processes and discrete-event simulations. Operations Research 23: pp. 33-45, 1975.

25. М. Е. Crovella, A. Bestavros. Self-similarity in World Wide Web traffic:evidence and possible causes. // IEEE/ACM Transactions on Networking, Vol. 5, No. 6, pp. 835-847, December 1997.

26. H. Damerdji. Strong consistency of the variance estimator in steady-state simulation output analysis. Mathematics of operations research. Vol. 19, No. 2, 1994.

27. H. Damerdji, S. G. Henderson, P. W. Glynn. Computational efficiency evaluation in output analysis. Proceedings of the 1997 Winter Simulation Conference.

28. P. L'Ecuyer, V. Demers, B. Tuffin. Splitting for rare-events simulation. //Proceed of the 2006 Winter Simulation Conference.

29. P. Embrechts, С. M. Goldie. On closure and factorization theorems for subexpone and related distributions. J. Austral. Math. Soc. Ser. A 29, pp. 243-256, 1980.

30. A. Feldmann. Characteristics of TCP Connection Arrivals. 1998.

31. T. Ferguson. A course in large sample theory. Chapman and Hall, 1996.

32. K. Fitzgerald. Vulnerability exposed in AT&T's 9-hour glitch. The Institute, 14(3) :1, 6, March 1990. A news supplement to IEEE Spectrum.

33. M. Garvels. PhD Thesis. "The splitting method in rare event simulation The University of Twente, The Netherlands May, 2000.

34. M. Garvels, D. Kroese. A comparison of RESTART implementations. Proceeding! of the 1998 Winter Simulation Conference, pp. 601-608.

35. P. Glasserman, P. Heidelberger, P. Shahabuddin, and T. Zajic. A look at multilevel splitting. In H. Niederreiter, editor, Monte Carlo and Quasi Monte

36. Carlo Methods 1996, Lecture Notes in Statistics, volume 127, pages 99-108. Springer Verlag, 1996.

37. P. Glasserman, P. Heidelberger, P. Shahabuddin, and T. Zajic. Splitting for rare event simulation: analysis of simple cases. Proceedings of the 1996 Winter Simulation Conference.

38. P. W. Glynn, D. L. Iglehart. A joint central limit theorem for the sample mean and regenerative variance estimator. Annals of Operations Research 8, 1987, 41-55.

39. P. W. Glynn, D. L. Iglehart. Conditions for the applicability of the regenerative method. Management Science 39: 1108-1111, 1993.

40. P. W. Glynn. Some topics in regenerative steady state simulation. 1993.

41. С. M. Goldie, C. Kluppelberg. Subexponential distributions. In a Practical Guide to Heavy Tails: Statistical Techniques for Analysing Heavy Tails, 1997, Birkhauser, Basel.

42. C. Gorg, E. Lamers, 0. Fub, P. Heegaard. Rare event simulation. Computer Systems and Telematics, Norwegian Institute of Technology, Tech. Rep. COST 257, 2001.

43. I. S. Gradshteyn, I. M. Ryzhik. Table of Integrals, Series, and Products (6th edition). Academic Press, San Diego, 2000.

44. M. Greiner, M. Jobmann, C. Kluppelberg. Telecommunication traffic, queueing models and subexponential distributions. 1999.

45. P. E. Heegaard. A survey of Speedup simulation techniques. Workshop tutorial on Rare Event Simulation, Aachen, Germany. 1997.

46. P. Heidelberger. Fast simulation of rare events in queuieng and relaibility models, Performance Evaluation of Computers and Communications Systems Springer-Verlag, LN in Computer Sci., v. 729, 1993, pp. 165-202.

47. H. Kahn and Т.Е. Harris. Estimation of Particle Transmission by Random Sampling. National Bureau of Standards Applied Mathematics Series, 1951.

48. А. М. Law, W. D. Kelton. Simulation modeling and analysis, second edition. McGraw-Hill, New York, 1991.

49. W. Leland, M. Taqqu, W. Willinger and D. Wilson. On the self-similar nature of Ethernet traffic. IEEE/ACM Transactions on Networking, Vol. 2, No. 1, pp. 1-15, February 1994.

50. M. Matsumoto, T. Nishimura. Mersenne twister: A 623-dimensionally equidistrib uniform pseudorandom number generator, ACM Trans, on Modeling and Computer Simulations, 1998.

51. E. V. Morozov. Self-similarity and long-range dependence in network traffic modeling. Proceedings of FDPW'99, Developments in Distributed Systems and Data Communications, Vol. 2, pp. 32-40, 1999.

52. E. V. Morozov. Elements of Queueing Theory with Applications to Communicatic Networks, 2001.

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

54. E. Morozov and I. Aminova. Steady-state simulation of some weak regenerative networks, European Transactions on Telecommunications ETT, Vol. 13, No. 4, July/August, 2002, pp. 409-418.

55. S. Nadarajah, S. Kotz. On the Laplace transform of the Pareto distribution. Queueing Systems, Vol. 54, pp. 243-244, 2006.

56. V. Paxson, S. Floyd. Wide-area traffic: The failure of Poisson modeling. IEEE/ACM Transactions on Networking, 3(l):226-244, 1995.

57. S. M. Ross, S. Seshadri. Hitting Time in an М/G/l Queue. J. Appl. Prob, 36, pp. 934-940, 1999.

58. G. Samorodnitsky. Long range dependence, heavy tails and rare events lecture notes. MaPhySto, Centre for Mathematical Physics and Stochastic, Aarhus, 2002.

59. K. Sigman, R. Wolff. A review of regenerative processes. SIAM Review, Vol. 35, No. 2, pp.269-288. 1993.

60. P. Shahabuddin. Rare Event Simulation in Stochastic Models. Proceedings of the WSC 1995, IEEE Press., pp. 178-185.

61. W. L. Smith. Regenerative stochastic processes. Proc. of the Royal Stat. Society, A, 232, pp. 6-31, 1955.

62. D. Starobinski, M. Sidi. Modeling and analysis of power-tail distributions via classical teletraffic methods. Queueing Systems, Vol. 36, pp. 243-267, 2000.

63. L. Takacs. Introduction to the Theory of Queues. Oxford University Press, New York. 1962.

64. M. Villen-Altamirano, J. Villen-Altamirano. RESTART: A Method for Accelerati Rare Event Simulations. Proceedings of the 13-th International Teletraffic Congress, Queueing, Perform-ance and Control in ATM, 1991, pp. 71-76.

65. M. Villen-Altamirano, J. Villen-Altamirano. RESTART: A Straightforward Method for Fast Simulation of Rare Events. Proceedings of the 1994 Winter Simulation Conference, 1994, pp. 282-289.

66. M. Villen-Altamirano, J. Villen-Altamirano. About the Efficiency of RESTART. Proceedings of the RESIM'99 Workshop, University of Twente, the Netherlands 1999, pp. 99-128.

67. M. Villen-Altamirano, J. Villen-Altamirano. Analysis of RESTART Simulation: Theoretical Basis and Sensitivity Study. European Transactions on Telecommuni< vol. 13, N. 4, 2002, pp. 373-385.

68. M. Villen-Altamirano, J. Villen-Altamirano. On the Efficiency of RESTART for Multidimensional Systems. Submitted in ACM Transaction On Modeling And Computer Simulation.

69. R. W. Wolff. Poisson Arrivals See Time Average. Opns. Res, 30, 223-231. 1982.

70. R. W. Wolff. Stochastic modeling and the theory of queues. Prentice Hall, Englewood, NJ, 1989.