Регенеративная модификация метода расщепления для оценивания вероятности перегрузки в системах обслуживания тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Бородина, Александра Валентиновна

• Бородина, Александра Валентиновна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Бородина, Александра Валентиновна

Введение

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, а так же интервального оценивания методом УРИМ.

Список литературы диссертационного исследования кандидат физико-математических наук Бородина, Александра Валентиновна, 2008 год

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.