Оценивание качества обслуживания коммуникационных систем с использованием теории больших уклонений и регенеративного анализа тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Жукова Ксения Алексеевна

• Жукова Ксения Алексеевна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Жукова Ксения Алексеевна

Введение

Глава 1. Основные результаты теории больших уклонений

1.1 Базовые понятия и результаты

1.2 Принцип больших уклонений

1.3 Применение теории больших уклонений в анализе систем массового обслуживания

Глава 2. О вероятности большого уклонения в системах с

повторными вызовами

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

2.1.1 Описание модели

2.1.2 Нижняя граница вероятности большого уклонения на

цикле занятости

2.1.3 Верхняя граница вероятности большого уклонения на

цикле занятости

2.2 Анализ многосерверной системы с повторными вызовами .... 32 2.2.1 Верхняя и нижняя границы

2.3 Результаты численных экспериментов и описание программного комплекса

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

инфо-коммуникационной сети

3.1 Эффективная пропускная способность и теория больших уклонений

3.2 Применение принципа больших уклонений в моделях массового обслуживания

3.3 Расчет ЭПС методами теории больших уклонений

3.4 Численные методы оценивания ЭПС

3.4.1 Метод группового среднего оценивания ЭПС

3.4.2 Регенеративное оценивание ЭПС

3.4.3 Оценивание ЭПС дельта-методом

3.5 Сравнительный анализ методов оценивания ЭПС на основе имитационного моделирования регенеративной сети

3.5.1 Исследование свойств метода группового среднего

3.5.2 Исследование свойств регенеративного метода

оценивания ЭПС

3.5.3 Переоценивание и его свойства на примере тандемной сети

3.6 Численное исследование величины А

3.6.1 Анализ на основе регенерации

3.6.2 Зависимость А от рандомизации размера группы

3.6.3 Рандомизация в методе группового среднего

Глава 4. Неравенства типа Поллачека-Хинчина для

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

4.1 Свойство PASTA

4.2 Входной поток типа НЛС/НХС

4.3 Численные эксперименты

Заключение

Список литературы

Список литературы

Список публикаций по теме работы

Приложения

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

Введение

Актуальность темы. Важной и актуальной задачей при разработке и поддержке современных инфокоммуникационных систем для обработки и передачи данных является возможность построения и выбора режимов работы, позволяющих обеспечить выполнение заданных требований качества обслуживания (quality of service, QoS). Эти требования, которые отражают интересы пользователя, должны быть сбалансированы с интересами разработчиков или провайдеров услуг, что приводит к необходимости постановки и решения соответствующих оптимизационных задач. В частности, такими требованиями могут быть ограничения на среднее время ожидания выполнения задания или на вероятность того, что время ожидания задания в очереди превысит заданный порог [72]. Как правило, параметры QoS выбираются в зависимости от особенностей системы и тех задач, которые она решает. Важнейшими параметрами QoS в инфокоммуникационных системах является вероятность превышения большого значения очереди и/или заданное ограничение времени ожидания. Так, например, в высокоответственных системах ключевым требованием является ограничение вероятности превышения процессом нагрузки заданного значения [9]. В связи с постоянным совершенствованием и усложнением современных систем и сетей передачи данных для анализа параметров качества обслуживания необходимо привлекать сложные современные математические методы, в частности, теорию больших уклонений и регенеративный метод. Применение этих методов к анализу инфокоммуникационных систем позволяет не только получить новые теоретические результаты, касающиеся асимптотики поведения вероятности большого уклонения, но и построить эффективные методы оценивания параметров системы, которые определяют качество обслуживания.

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

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

1. Исследована асимптотика стационарной вероятности большого значения очереди для широкого класса систем с повторными вызовами.

2. Проведен сравнительный анализ методов оценивания эффективной пропускной способности модели коммуникационного узла с применением методов теории больших уклонений и регенеративного анализа.

3. Исследованы свойства средней стационарной нагрузки в системах с непуассоновским входным процессом.

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

Научная новизна работы.

1. Доказана экспоненциальная асимптотика стационарной вероятности большого размера орбиты для широкого класса систем с повторными вызовами.

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

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

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

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

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

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

3. Неравенства типа Поллачека-Хинчина для многосерверной системы с входным потоком с распределением специального класса.

4. Комплекс программ имитационного моделирования для оценивания эффективной пропускной способности коммуникационного узла.

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

1. Всероссийская конференция с международным участием:«Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем 2015» (Москва, РУДН, 20-24 апреля 2015);

2. 29th European Conference on Modelling and Simulation (26-29 мая, 2015, Болгария);

3. Distributed computer and communication networks: control, computation, communications, DCCN-2015 (19-22 October, ICS RAN, Moscow, Russia, 2015)

4. The Second International Symposium on Stochastic Models in Reliability Engineering, Life Science and Operations Management (Israel, Beer-Sheva, Shamoon College of Engineering, February 15-18, 2016);

5. IX международная конференция «Вероятностные методы в дискретной математике» (Петрозаводск, Россия, 30 мая - 3 июня 2016 г.);

6. 19th International Conference on distributed computer and communication networks DCCN-2016 (Moscow, Russia, 21-25 ноября 2016 г.);

7. Двадцатая международная научная конференция «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь» (Москва, 25-29 сентября 2017 г., ИПУ РАН);

8. International Conference on Man-Machine Interactions, Poland, Krakow, 3-6 October. 2017.

9. European Conference on Queueing Theory 2018 (Jerusalem, Israel, July 2-4, 2018);

10. Distributed computer and communication networks: control, computation, communications, DCCN-2018 (Москва, 17-21 сентября 2018 г., ИПУ РАН).

Публикации. По материалам и результатам диссертации опубликовано 12 печатных работ, из них 2 статьи в российском журнале из списка ВАК [103; 104], 5 статей в сборниках трудов международных конференций [105] - [109], индексируемые в реферативной базе Scopus, и 5 тезисов докладов [110] - [114], индексируемых РИНЦ. Получено свидетельство о государственной регистрации программы для ЭВМ [102].

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложения. Общий объем диссертации 111 страниц, включая 16 рисунков. Список литературы включает 101 наименование.

Глава 1. Основные результаты теории больших уклонений

Исследования свойств реального интернет - и инфокоммуникационного трафика, в частности, наличие долговременной памяти, привело к необходимости усложнять модели, описывающие основные процессы в системах массового обслуживания и сетях передачи данных. Такие модели сложно (а иногда и невозможно) исследовать классическими техниками, которые позволяют рассчитать точное решение. В связи с этим возникла необходимоть в математических методах, которые бы позволили решать задачи, связанные с исследованиями сложных моделей. Одним из таких подходов является теория больших уклонений. Этот раздел занимается исследованием хвостов распределений случайных величин (с.в.), и зачастую ассоциируется с теорией редких событий. Хвостом распределения с.в. X с функцией распределения Р(х) будем называть функцию Р(х) = 1 — Р(х). Согласно Закону больших чисел, д обладает следующим свойством:

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

систем).

1.1 Базовые понятия и результаты

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

Определение 1.1. [37] Логарифмической производящей функцией моментов с.в. X называется функция Л : R ^ R U {ж}:

Л(0) = ln e[eex ],

где параметр в > 0.

Определение 1.2. [37] Функция f : R ^ R называется полунепрерывной снизу, если для любых хп ^ х выполнено lim f (хп) ^ f (х).

Свойство 1.1. [37], [48] Логарифмическая производящая функция моментов Л является выпуклой, полунепрерывной снизу и дифференцируемой на внутренности множества {х : Л(х) < 0} с производной

цхё>* ]

Л (в) = „А(в) •

Доказательство. Согласно определению функция /(х) : X ^ К является выпуклой, если для 0 ^ а ^ 1 и Ух\,х2 £ X выполнено неравенство

/(ах\ + (1 - а)х2) ^ а/(х\) + (1 - а)/(х2).

Рассмотрим выражение для 0 ^ а ^ 1

E

е

(oßi+(1-о)в2)Х

E

еав1Х е(1-а)в2Х

E

1— а

По неравенству Гельдера

E

(■e°ix)a (ев*х)1-а ^ (E [e°ix])a (E [е0^])

1— а

Отсюда следует, что

Е

,(а01+(1-а)в2)Х

^ (Е [е°1х])а (Е [е°2х])

1— а

(1.1)

Логарифмируя правую и левую части выражения (1.1), получаем

Л(ав 1 + (1 - а)в2) = 1п Е

,(ав1+(1-а)в2)Х

<

1п (Е [е°1х])а (Е [е^])1-а = аЛ(^) + (1 - а)Л(в2),

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

Чтобы показать полунепрерывность снизу, зафиксируем точку в € К и рассмотрим произвольную последовательность 9п € К, сходящуюся к точке в. Тогда по лемме Фату

Е[Ншт£ евпХ] < Ишт£ Е[евпХ ].

впХл

п—>оо

п—>оо

(1.2)

Выполняя предельный переход в левой части выражения (1.2), получаем

е[е°х] < 11ш1п£ Е[еу"Л],

п—>оо

а это и является определением полунепрерывности функции снизу.

Чтобы показать дифференцируемость, рассмотрим внутреннюю точку в множества {в : Л(в) < 0}. Заметим, что по свойству линейности математического ожидания

1

ГАо 6

Нш - ^Е

е

(в+6)Х

- е[евхЛ = Нт Е V ^о

е(в+5)Х - евХ 6

(1.3)

Теперь рассмотрим следующее выражение

е(в+5)Х - евХ 6

(1.4)

Легко заметить, что оно сходится поточечно к Хе°х при 6 ^ 0

е(в+5)Х - евХ 6

= Хе

ех

(е5Х - 1 \

V ж )

ех

Более того, выражение (1.4) для любого 5 £ (—£, е) не превосходит

' ^ 1'

Я =

По нашему предположению 6 - внутренняя точка множества {6 : Л(6) < 0}, а значит для достаточно малых £ точки 6—£ и 6+е также являются внутренними. Следовательно, Е Я < то, и по теореме Лебега о мажорируемой сходимости получаем

Е

е — 1

^ е[хевх] при 0. (1.5)

Из (1.3) и (1.4) получим

(Е[е ех ])' = е[Х е ех ].

Так как А(0) = 1п Е[ евх], то

(Л(0))' = (1п Е[ е ** ])'

е[хевх] _ е[хевх] Е[ е] = еЛв) .

□

Определение 1.3. [37], [48], [58] Функцией действия или преобразованием Ле-жандра функции Л(6) называется функция

Л* (а) = 8ир[6>а — Л(0)],

в

где параметр 6 > 0.

Свойство 1.2 [37], [48] Преобразование Лежандра Л* (а) является выпуклой функцией.

Доказательство. Согласно определению функция /(х) : X ^ К является выпуклой, если для 0 ^ а ^ 1 и любых х1,х2 £ X выполнено неравенство

¡(ах\ + (1 — а)х2) < а/(х\) + (1 — а)/(х2).

Покажем это для функции Л*(а):

Л*(аа1 + (1 — а)а2) = Бир^аа + 6(1 — а)а2 — Л(0)] =

в

sup[a(6>a\ - Л(9)) + (1 - а)(ва,2 - Л(0))] <

в

a sup[aai - Л(0)] + (1 - a) sup[6»a2 - Л(0)] = аЛ*(а^ + (1 - а)Л*(а2). в в

□

Свойство 1.3. [37], [48] Преобразование Лежандра Л*(а) является полунепрерывным снизу для любой функции Л(0).

Доказательство. Рассмотрим сходящуюся последовательность чисел ап ^ а при п ^ <ж и заметим, что Л*(ап) ^ вап - Л(в) для любого 0. Выполняя предельный переход ап ^ а, получаем

lim Л*(ап) ^ в а - Л(в) для любого 9. Отсюда следует, что

lim Л*(ап) ^ sup[ 9а - Л(0)] = Л*(а).

ап ^а q

□

Свойство 1.4. [37] Если Л(0) — выпуклая и дифференцируемая для всех 9 функция, тогда

0Л'(0) - Л*(Л'(0)) = Л(0).

Доказательство. Так как мы полагаем, что Л(0) — выпуклая и дифференцируемая для любого , то супремум в определении преобразования Лежанд-ра достигается в такой точке 9, что Л'(9) = а. В этом случае, так как (Л*(а))' = а - Л'(9) = 0, получаем

Л*(а) = 9а- Л(9), Л'(0) = а.

Следовательно, 9Л'(9) - Л*(Л'(9)) = Л(0). □

Свойство 1.5. [48] Пусть функция Л(0) - выпуклая и дифференцируемая для всех 9, и выполнено равенство Л(0) = 0. Тогда справедливы следующие условия: (1) Функция действия Л* (а) неотрицательна;

(2) Л*(а) достигает своего минимума в точке а = Л'(0), Л*(Л'(0)) = 0 и Л*(а) > 0 для любого а = Л'(0);

(3) Л*(а) строго возрастает для Л'(0) < а < то и строго убывает для -то < а < Л'(0).

Доказательство. (1) По условию Л(0) = 0, поэтому

Л* (а) = яир[0а - Л(0)] ^ 0 •а - Л(0) = 0.

в

(2) Воспользуемся свойством 1.4 для 0 = 0:

Л*(Л'(0)) = 0 • Л'(0) - Л(0) = 0.

Так как функция Л(0) по условию выпуклая и дифференцируемая, то при разложении в ряд Тейлора в точке а = 0 получим

Л(0) > Л(0) + (0 - 0)Л'(0),

в случае Л'( 0) = Л'(0). Так как Л(0) = 0 и 0Л'(0)-Л*(Л'(0)) = Л(0) (по свойству 1.4), то для Л'(0) = Л'(0) выполнено неравенство Л*(Л'(0)) > 0.

(3) Из выше доказанного условия (2) свойства следует, что для Л'(0) < а < Ь выполнено неравенство Л*(Ь) > 0. Функция Л*(а) - выпуклая, следовательно выполняется

Л*(а» < ЩЛ*<Л'<°» + а-Л!Л*<&» =

=а-ЛИЛ*<6 х л*<&).

Доказательство для случая а < Л'(0) аналогично. □

Итак, представленные выше свойства функции действия Л* (а) позволяют сделать вывод о виде этой функции, представленном на Рис. 1.1: Л* (а) неотрицательна и достигает своего минимума в точке а = еХ.

Приведем один из основных результатов теории больших уклонений.

а

Рисунок 1.1 — Типичный график функции действия

Теорема Чернова. [48] Пусть Х1, Х2,... - последовательность независимых одинакого распределенных (н.о.р.) с.в. и еХ < то. Пусть

= + ■ ■ ■ + Хп, 8п = 8п/п.

Тогда для любого а > еХ и всех п

Р (<§п > а) < е~пА*(а).

Если, кроме того, ее°х < то для всех 0 в некоторой положительной окрестности нуля и супремум в определении Л* достигается в точке 9* внутри этой окрестности, то для каждого е > 0 существует п0 такое, что

р (зп > а) ^ е~п(А*(а)+е), п ^ по.

1.2 Принцип больших уклонений

Рассмотрим последовательность н.о.р.с.в. Х1,Х2,... с типичной с.в. X.

п

Теорема Крамера. [37], [48] Пусть Sn = iJ^^i. Пусть Еевх < то для

п i=i

любого в Е R. Тогда выполнены следующие условия:

1) (Верхняя граница) Для каждого замкнутого множества F Е R

lim sup1 ln P(Sn Е F) ^ - inf Л*(а);

п—то — aEF

2) (Нижняя граница) Для каждого открытого множества G Е R

liminfiln P(Sn Е G) ^ - inf Л*(а).

п—то n аЕС

Функция Л*(а) — введенная ранее функция действия. Расширением теоремы Крамера на последовательности необязательно независимых с. в. является теорема Гартнера-Эллиса. Рассмотрим последовательность с. в. Y1,Y2,.... Определим последовательность функций

Лп(в) = — ln Е[е]. n

Теорема Гартнера-Элиса. [37], [48], [64] Пусть

1) lim Лп(в) = Л(0) < то для всех О Е R;

п—^то

2) Л(в) — дифференцируема для всех в Е R. Тогда верны следующие утверждения:

1) (Верхняя граница) Для каждого замкнутого множества F Е R

lim sup1 ln pi — Е F J < - inf Л* (а);

п—то — \— J аЕ-F1

2) (Нижняя граница) Для каждого открытого множества G Е R

lim inf1 ln pi — Е G ) ^ - inf Л*(а).

П—то n \n J аЕС

Более детально о теории больших уклонений можно найти, например, в [48], [37], [64].

1.3 Применение теории больших уклонений в анализе систем

массового обслуживания

Первые исследования хвостов распределений процесса очереди и процесса незавершенной нагрузки в односерверной системе типа GI/GI/1 (с общим распределением входного потока и времен обслуживания) осуществлялись анализом, в рамках которого устанавливается связь между распределением незавершенной нагрузки и распределением максимума случайного блуждания, которое и анализировалось в дальнейшем [23], [47]. Однако в [61] было показано, что этот анализ невозможно обобщить на случай многосерверных систем.

Попытки расширить исследования на многосерверные модели были предприняты в [92], где авторы показали экспоненциальную асимптотику хвоста распределения незавершенной нагрузки в системах с входным потоком фазового типа. Аналогичные результаты были получены и для многосерверных моделей со стационарными марковскими распределениями входного потока и времен обслуживания GM/GM/m с использованием экспоненциального изменения меры (exponential twisting techniques) для цепей Маркова и теоремы Крамера [35], [82], [77]. Схожие результаты по асимптотике вероятности большого уклонения в контексте ускоренного моделирования редкого события (переполнения буфера) были получены также в [42], [62] и [78].

Одной из ключевых работ по обобщению ранее полученных результатов является статья [85], где авторы показали экспоненциальную асимптотику вероятности превышения общего числа заявков в системе на цикле занятости в многосерверной системе типа GI/GI/m. Полученный результат справедлив в условиях стационарности и p(S > т) > 0 (последнее условие требуется для положительной возвратности и наличия бесконечного числа циклов занятости с вероятностью 1). После публикации этих результатов стало появлятся большое число исследований асимптотики большого уклонения в разных постановках и с различными приложениями, напрмер, в контексте ускоренного моделирования, как в [39], или для определения и расчета эффективной пропускной способности [46], [58]). Такой интерес к вероятности большого уклонения в моделях систем массового обслуживания был связан с актуальностью проблем разработки и обслуживания коммуникационных сетей. Помимо результатов в [85],

касающихся асимптотики вероятности большого уклонения на цикле занятости, активно изучались и асимптотики стационарных вероятностей. Сначала результаты были получены для систем типа GI/GI/1 для стационарных процессов незавершенной нагрузки и общего времени пребывания в системе [17; 18; 57], а затем были рассмотрены и более общие модели в работах [19; 20; 40; 41; 98]. Чуть позже задачи оценивания асимптотики большого уклонения были распространены и на более сложные по своей структуре модели коммуникационных и компьютерных сетей. Так, в исследованиях [38; 97] было показано, что в древовидных сетях распределение процесса очереди заявок имеет экспоненциально убывающих хвост. Схожие асимптотики были представлены в работах [49; 50] для вероятности большого уклонения в тандемных сетях с входным процессом восстановления. В [32] рассмотрена ациклическая сеть с общим входным процессом и независимыми временами обслуживания на каждом узле. Авторы рассчитали хвосты распределений стационарных процессов незавершенной нагрузки и длины очереди на каждом узле сети. Одно их последних исследований, посвященных вероятности большого уклонения в тандемной сети типа G//G//1 — • /G//1 — • • • — •/GI/1, статья [36], где авторы показывают эспо-ненциальную асимптотику вероятности превышения для стационарного процесса общего числа заявок в сети на цикле занятости. Ряд исследований посвящен асимптотике большого уклонения в системах с повторными вызовами (retrial systems). В [60;89] изучены хвосты распределния процесса очереди в системах с повторными вызовами типа M/G/1, а позже эти результаты были расширены на класс моделей с асимптотически пуассоновским входным MAP-потоком. В рамках данной диссертации удалось обобщить эти результаты: показана экспоненциальная асимптотика вероятности большого уклонения в многосерверных системах с повторными вызовами с общим входным процессом и произвольно распределенными временами обслуживания (см. Главу 2).

Глава 2. О вероятности большого уклонения в системах с

повторными вызовами

В этой главе представлен анализ вероятности большого уклонения в системах с повторными вызовами с классической и постоянной интенсивностью повторных вызовов в условиях стационарности. В системах с классической дисциплиной повторных вызовов интенсивность поступления заявок с орбиты на облуживание пропорциональна размеру орбиты, т. е. числу тех заявок, которые в момент прихода в систему встретили сервер занятым и были отправлены на орбиту - виртуальный буфер бесконечной вместимости. В системах с постоянной дисциплиной интенсивность поступления заявок с орбиты не зависит от размера орбиты и остается неизменной. Модели систем с повторными вызовами активно изучаются последние десятилетия. Такой интерес продиктован практическим применением подобных моделей в современных телекоммуникационых системах и мобильных сетях [21; 70; 73; 74;79].

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

мы были использованы моментные свойства циклов регенерации классических систем, полученные в [93], а также результаты теории восстановления [24].

Представленное ниже исследование дополняет уже известные аналогичные результаты по асимптотике вероятности большого уклонения в классической многосерверной системе [85], тандемных сетях [36] и в системах с повторными вызовами типа М/С/1 [59; 60], расширяя класс рассмотренных систем (до многосерверных систем с повторными вызовами) и тип входного процесса (до общего процесса восстановления).

2.1 Односерверная система с орбитой с классической и постоянной

интенсивностью повторных вызовов

2.1.1 Описание модели

Рассмотрим односерверную систему с орбитой с входным процессом восстановления. Обозначим моменты поступления заявок в систему £ п, п ^ 1, н.о.р. времена между приходами заявок тп := Ьп+1 — 1п, п ^ 1, ^ =0, и н.о.р. времена обслуживания Бп,п ^ 1. В дальнейшем для удобства будем опускать порядковый индекс у с.в. тп и Бп, обозначая через т типичный интервал между приходами и через Б - типичное время обслуживания. Заметим, что с.в. ти5 имеют то же распределение, что и с.в. тп и Бп соответственно. Пусть внешний входной поток заявок в систему имеет интенсивность Л := 1/Ет € (0,то), а интенсивность обслуживания при этом д := 1/ЕБ € (0,то).

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

при постоянной орбитальной скорости эта интенсивность равна независимо от размера орбиты (т. е. числа заявок на ней). В этом случае удобно рассматривать орбиту как очередь FIFO типа (First In, First Out или «первым пришёл

— первым ушёл»), в которой только первая в очереди (т.е. самая «старая») орбитальная заявка делает попытки занять сервер [28]. Стоит отметить, что дисциплина FIFO здесь относится именно к заявкам, поступающим на орбиту и уходящим с нее на обслуживание.

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

р := Х/р < 1. (2.1)

Как видно, условие (2.1) совпадает с критерием стационарности классической системы GI/G/1. Чтобы более формально определить стационарность (стационарный режим), обозначим Q(t) общее число заявок в системе (на сервере и на орбите) в момент времени tПусть начальное состояние процесса нулевое: Q(0) = 0, t1 = 0. Определим моменты регенерации процесса Q:

Zn+i = min(iк > Zn : Q(tк) = 0), n ^ 0, ZQ = 0. (2.2)

Стационарность означает, что регенеративный процесс Q является положительно возвратным, т. е. типичный цикл регенерации имеет конечное среднее. Пусть Т - типичная длина цикла занятости системы, в которой есть хотя бы одна заявка. Рассмотрим вероятность превышения процессом общего числа заявок в системе некоторого (большого) значения N > 1 на цикле занятости.

Обозначим 3 — число приходов заявок в течение цикла занятости, а Dk

— интервал между к - 1 и к уходами из системы, к ^ 2. Обозначим Кn номер первой заявки, которая достигла уровня N на цикле занятости и определим этот номер следующим образом [36]:

( п-1 n-N+1 Л

KN = min < n ^N : ^ тк < ^ Dk\ , (2.3)

I k=i k=i )

где мы полагаем min 0 = то, а значит Кn := то, для случая, когда на цикле занятости не было превышения уровня N. Если К^ < то, то превышение на цикле было, и значит К^ ^ ß. Обозначим К0 номер заявки, которая поступает в пустую систему (т. е. видит систему пустой в момент прихода)

( i-i 1-1 л

Ко = min i I > 1 : ^ Tk > ^Dk\ .

I k=i k=i J

Dkj . (2.4)

Нетрудно заметить, что порядок поступления заявок в систему не обязательно совпадает с порядком их поступления на обслуживание и ухода из системы. Однако, учитывая тот факт, что времена обслуживания заявок S¡, 1, являются н.о.р. с.в., а орбиту можно рассматривать как очередь типа FIFO, будем назначать значение соответствующего времени обслуживания S¡ заявки непосредственно при поступлении ее на сервер. Таким образом, мы перенумеровываем заявки, сохраняя соответствие между временами обслуживания S¡, 1, интервалами между приходами r¡, 1 и интервалами между уходами D¡, 1. Это позволяет определить интервалы Dk следующим образом:

Список литературы диссертационного исследования кандидат наук Жукова Ксения Алексеевна, 2018 год

Список литературы

1. Байхельт Ф., Франкен П. Надежность и техническое обслуживание. Математический подход. М.: Радио и связь, 1988. С. 392.

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

3. Боровков А. А. Теория вероятностей. 2 изд. М.: Наука, 1986. С. 432.

4. Бородина А. В., Морозов Е.В. Сравнение двух оценок эффективной пропускной способности систем обслуживания. Труды Карельского научного центра РАН. 2012. №6. С. 8-17.

5. Бородина А. В., Морозов Е. В. Об оценивании эффективной пропускной способности в системе с регенеративным входным процессом. Информатика и ее применения. 2013. Т. 7. Вып. 2. С. 26-33.

6. Бородина А. В., Морозов Е. В. Оценивание эффективной пропускной способности узла в инфокоммуникационной тандемной сети // Системы и средства информатики, 2014. Т. 24, Вып. 2. С. 37-54.

7. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Наука, 1987. С. 336.

8. Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений. 4-е изд. — М.: Физматгиз, 1963. — 1100 с.

9. Коваленко И.Н. Анализ редких событий при оценке эффективности и надежности систем. - М: Советское Радио, 1980. 239 с.

10. Мацкевич И. П. Теория вероятностей и математическая статистика. Минск : Высшая школа, 1993. 264 с.

11. Морозов Е. В. Теория массового обслуживания: учеб. пособие. Петрозаводск : Изд-во ПетрГУ, 1991. 41 с.

12. Морозов Е. В., Некрасова Р. С. Об оценивании вероятности переполнения конечного буфера в регенеративных системах обслуживания // Информатика и ее применения. 2012. Т. 6, № 3. С. 90-98.

13. Рыков В. В. Аналитические методы исследования систем массового обслуживания // Техническая кибернетика. 1983. Т. 6. С. 13-20.

14. Рыков, В. В. Исследование одноканальной системы общего вида методом регенерирующих процессов. ii. исследование основных процессов на периоде регенерации / В. В. Рыков // Техническая кибернетика. — 1984. — Т. 1. — С. 126-132.

15. Тихоненко О. М. Модели массового обслуживания в системах обработки информации. Минск: Университетское. 1990. С. 148.

16. Феллер В. Введение в теории вероятностей и ее приложения. 2е изд. М.: Мир, 1964. Т. 2. С. 765.

17. Abate J., Choudhury G. L., Whitt W. Exponential approximations for tail probabilities os queues, I: waiting times. Operations Research. Vpl. 43. 1995. P. 885-901.

18. Abate J., Choudhury G. L., Whitt W. Exponential approximations for tail probabilities os queues, II: Sojourn Time and Workload. Operations Research. Vol. 44. 1996. P. 758-763.

19. Abate J., Choudhury G. L., Whitt W. Asymptotics for Steady-State Tail Probabilities in Structured Markov Queueing Models. Stochastic Models, vol. 10, No. 1, 1994, pp. 99-143

20. Abate J., Choudhury G. L., Whitt W. Waiting-Time Tail Probabilities in Queues with Long-Tail Service-Time Distributions. Queueing Systems, vol. 16, 1994, pp. 311-338.

21. Amar Aissani, Tuan Phung-Duc. Profiting the idleness in single server system with orbit-queue, Valuetools 2017, December 5-7, 2017, Venice, Italy, 2017. DOI: https://doi.org/10.1145/3150928.3150929

22. Artalejo J. R., Resing J. A. C. Mean value analysis of single server retrial queues, Asia-Pacific Journal of Operational Research, Vol. 27, No. 3 (2010) 335-345 DOI: 10.1142/S0217595910002739.

23. Asmussen S. Conditioned limit theorems relaring a random walk to its associate, with applications to risk reserve processes and the GI/G/1 queue. Adv. Appl. Prob., vol. 14, P. 143-170. 1982.

24. Asmussen S. Applied Probability and Queues - 2nd Ed. Springer, 2003. 451 p.

25. Asmussen S., Glynn P. Stochastic Simulation: algorithms and analysis. -Springer, 2007. 476 p.

26. Avrachenkov K., Morozov E. Stability Analysis of GI/GI/c/K Retrial Queue with Constant Retrial Rate. Mathematical Methods of Operations Research, Vol. 79, 273-291, 2014.

27. Avrachenkov K., Yechiali U. Retrial networks with finite buffers and their application to Internet data traffic // Probability in the Engineering and Informational Sciences. 2008. Vol. 22. Pp. 519 - 536.

28. K. Avrachenkov, E. Morozov, R.Nekrasova, B.Steyaert. Stability analysis and simulation of N-class retrial system with constant retrial rates and Poisson inputs. Asia-Pacific Journal of Operational Research Vol. 31, No. 2, (18 pages), 2014.

29. Avrachenkov K., Morozov E., Nekrasova R., Steyaert B. On stability of a two-class retrial system with constant retrial rate // Proceedings of 9th International workshop on retrial queues 2012. 2012. Pp. 15-16.

30. Avrachenkov K., Morozov E., Steyaert B. Sufficient stability conditions for multi-class constant retrial rate systems. Queueing Syst (2016) 82:149-171.

31. Belyy A., Morozov E. Quasi-regenerative and A-cycle queueing simulation // Proceedings of Finnish Data Processing Week at the Petrozavodsk State University (FDPW'03-04): Advances in Methods of Modern Information Technology, 2005. Petrozavodsk, P. 157-170.

32. Bertsimas D., Paschalidis I., Tsitsiklis J. On the large deviations behavior of acyclic networks of G/G/1 queues. Ann. Appl. Probab. Volume 8, Number 4 (1998), 1027-1069.

33. Borovkov A.A., Altman E. On the stability of retrial queues, Queueing systems. 1997. V. 26. P. 343-363.

34. Borovkov A. Stochastic processes in queueing theory. 1976. Springer.

35. Bucklew J. A., Ney P., Sadowsky J.S. Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Prob., P. 44-59, 1990.

36. Buijsrogge A., P.-T. de Boer, Rosen K., Scheinhardt W. (2017). Large deviations for the total queue size in non-Markovian tandem queues. Queueing Systems. 85, 305-312.

37. Chang C.-S. Performance guarantees in communication networks. Springer, 2000.

38. Chang C.-S. Sample Path Large Deviation and Intree Network. Queueing Systems. V. 20. 1995. P. 7-36.

39. Chang C.-S., Heidelberger P., Juneja S., Shahabuddin P. Effective bandwidth and fast simulation of ATM intree networks. IBM T. J. Walson Research Center, Yorktown Heights, NY. 1992.

40. Choudhury G. L., Whitt W., Lucantoni D. Squeezing the Most Out of ATM. IEEE Transactions on Communications, vol. 44, No. 2, 1996, pp. 203-217.

41. Choudhury G. L., Whitt W. Heavy-Traffic Asymptotic Expansions for the Asymptotic Decay Rates in the BMAP/G/1 Queue. Stochastic Models, vol. 10, No. 2, 1994, pp. 453-498.

42. Cottrell M., Fort J.-C., Malgouyres G. Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Automat. Contr., V. AC-28, P. 907-920. 1983

43. Crosby S., Leslie I., Huggard M., Lewis J. T., McGurk B., Russel R. Predicting bandwidth requirements of ATM and Ethernet traffic // Proc. of 13th IEE UK Teletraffic Symposium. — Glasgow, U.K., 1996.

44. Dyudenko I., Morozov E., Pagano M. Regenerative estimator for effective bandwidth // Mathematical methods for analysis and optimization of

information telecommunication networks: Proceedings of the International Conference. — Minsk: Belarusian State University, 2009. P. 58-60.

45. Dyudenko I., Morozov E., Pagano M., Sandmann W. Comparative study of effective bandwidth estimators: batch means and regenerative cycles // Proceedings of the 6th St.Petersburg Workshop on simulation. Vol. II. St-Petersburg, 2009. P. 1003-1007.

46. Elwalid A. I., Mitra D. Effective bandwidth of general Markovian traffic sources and admission control of high speen networks. IEEE/ACM Trans. Networking 1, P. 329-343. 1993.

47. Feller W. An introduction to probability theory and its application. vol. 2, 2nd ed., New York: Wiley. 1966.

48. Ganesh A., O'Connell N., Wischik D. Big queues. - Lecture notes in mathematics, Springer, 2004. 260 p.

49. Ganesh A.J. Large deviations of the sojourn time for queues in series. Ann. Oper. Res. 79, 1998. P. 3-26.

50. Ganesh A.J., Anantharam V. Stationary tail probabilities in exponential server tandems with renewal arrivals. Queueing Systems. V. 22. 1996. P. 203-247.

51. Glynn P. W., Iglehart D. L. A joint central limit theorem for the sample mean and regenerative variance estimator // Annals of operation researh. 1987. Vol. 8. Pp. 41-55.

52. Glynn P. W., Iglehart D. L. Simulation methods for queues: an overview // Queueing systems. 1988. Vol. 3. Pp. 221-237.

53. Glynn P. W. Iglehart D. L. Conditions for applicability of the regeneration method // Managment Sci. 1993. Vol. 39. Pp. 1108-1111.

54. Glynn P. W., Whitt W. A central-limit-theorem version // Queueing systems. 1986. Pp. 191-215.

55. Glynn P. W. Whitt W. Sufficient conditions for functional-limit-theorem versions // Queueing systems. 1987. Pp. 279-287.

56. Glynn P. W., Whitt W. Limit theorems for cumulative processes // Stochastic Processes and their applications. 1993. Pp. 299-314.

57. Glynn P. W., Whitt W. Logarithmic asymptotics for steady-state tail probabilities in a single-server queue // Journal of Appl. Probab, 1994. Vol. 31. P. 131-156.

58. Kelly F. Notes on effective bandwidths // Stochastic Networks: Theory and Applications / Royal Statistical Society Lecture Notes Series, 4. — Oxford University Press, 1996. P. 141-168.

59. Kim J., Kim B. Tail asymptotics for the queue size distribution in the MAP/G/1 retrial queue // Queueing Syst. 2010. V. 66. P. 79-94.

60. Kim J., Kim B., Ko S.-S. Tail asymptotics for the queue size distribution in an M/G/1 retrial queue // J. Appl. Probab. 2007. V. 44. P. 1111-1118.

61. Kingman J. F. C. On the algebra of queues. J. Appl. Prob., vol. 3. P. 285-326, 1966.

62. Knessl C., Matkowsky B. J., Schuss Z., Tier C. An asymptotic theory of large deviations for Markov jump processes. SIAM J. Appl. Math., V. 46, P. 10061028. 1985.

63. König, D., Schmidt, V.: Stochastic Inequalities between Customer-Stationary and Time-Stationary Characteristics of Queueing Systems with Point Processes . J. Appl. Probab. 17, 768-777 (1980). doi: 10.2307/3212970

64. Lewis J. T., Russell R. An introduction to large deviation for teletraffic engineers. DIAS Technical Report DIAS-STP 97-16, 1997.

65. Miyazawa, M.: A Formal Approach to Queueing Processes in the Steady State and their Applications, J. Appl. Probab. 16, 332-346 (1979)

66. Miyazawa, M.: Stochastic Order Relations Among GI/G/1 Queues With a Common Traffic Intensity, J Operat. Res. Japan 19, 193-208 (1976)

67. Morozov, E., Delgado, R.: Stability analysis of regenerative queues. Automation and Remote control 70, 1977-1991 (2009). doi: 10.1134/S0005117909120066

68. Morozov, E., Steyaert B. Stability analysis of a two-station cascade queueing network // Annals of Operations Research. — 2013. — Vol. 202, no. 1. — P. 135-160.

69. Morozov E. Weak regeneration in modeling of queueing processes // Queueing Systems, 2004. Vol. 46. No. 3-4. P. 295-315.

70. Morozov E. A multiserver retrial queue: Regenerative stability analysis. Queueing Systems, 56 (2007), 157-168.

71. Morozov E., Aminova I. Steady-state simulation of some weak regenerative networks // European Transactions on Telecommunications (ETT), 2002. Vol. 13. No. 4. P. 409-418.

72. Morozov E., Rumyantsev A. A State-Dependent Control for Green Computing // Information Sciences and Systems 2015 Lecture Notes in Electrical Engineering. Springer International Publishing, 2015. P. 57-67.

73. E. Morozov, R. Delgado, Stability analysis of regenerative queues, Autom. Remote Control 70 (12) (2009) 1977-1991.

74. Morozov E., Tuan Phung-Duc. Stability analysis of a multiclass retrial system with classical retrial policy, Performance Evaluation 112 (2017) 15-26.

75. Evsey Morozov, Tuan Phung-Duc. Regenerative analysis of two-way communication orbit-queue with general service time. Proceedings of the conference QTNA, June 2018, Japan, Springer LNCS (accepted).

76. Müller, A., Stoyan D.: Comparison Methods for Stochastic Models and Risks. John Wiley & Sons, Hoboken, NJ, USA (2002)

77. Ney P., Nummelin E. Markov additive process II: Large deviations. Ann. Probab., V. 15. 1987.

78. Parekh S., Walrand J. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Autom. Contr., V. 1, P. 54-66, 1989.

79. Phung-Duc T., Wouter Rogiest, Yutaka Takahashi, Herwig Bruneel. Retrial queues with balanced call blending: analysis of single-server and multiserver model. Ann Oper Res (2016) 239:429-449, DOI 10.1007/s10479-014-1598-2

80. Rabinovitch P. Statistical estimation of effective bandwidth: M. Sc. thesis. — University of Cambridge, 2000. P. 1-75.

81. Rumyantsev, A., Morozov, E.: Stability criterion of a multiserver model with simultaneous service. Ann. Oper. Res. 252(1), 29-39 (2017). doi:10.1007/s10479-015-1917-2

82. Sadowsky J.S. A dependent data extension of Wald's identity and its application to sequential test performance computation. IEEE Trans. Inform. Theory, V. IT-35. P. 834-842, 1989.

83. J.S. Sadowsky (1995). The probability of large queue lengths and waiting times in a heterogeneous multiserver queue. Part II: Positive recurrence and logarithmic limits. Advances in Applied Probability 27, 567-583.

84. J.S. Sadowsky and W. Szpankowsky (1995) The probability of large queue lengths and waiting times in a heterogeneous multiserver queue. Part I: Tight limits. Adv. Appl. Probab. 27, 532-566.

85. Sadowsky J.S.(1991) Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue. IEEE Trans. Autom. Control 36(12), 1383-1394.

86. Sakurai H., Tuan Phung-Duc. Two-way communication retrial queues with multiple types of outgoing calls, TOP (2015) 23:466-492, DOI 10.1007/s11750-014-0349-5.

87. Schmeiser B. Batch size effects in the analysis of simulation output // Oper. Res., 1982. Vol. 30. P. 556-568.

88. Serfozo, R.: Introduction to Stochastic Networks. Springer-Verlag, New York (1999)

89. Shang W., Liu L., Li Q. Tail asymptotics for the queue length in a M/G/1 retrial queue. Queueing Systems. V. 52. 2006. P. 193-198.

90. Smith, W. L. Renewal theory and its remifications / W. L. Smith // Journal of the Royal Statistical Society. — 1958. — Vol. 20. — P. 243-302.

91. Song W. T. On the estimation of optimal batch sizes in the analysis of simulation output // European Journal of Operational Research, 1996. Vol. 88. No 2. P. 304-319.

92. Takahashi Y. Asymptotic exponentiality of the tail of the waiting time distribution in a PH/PH/c queue. Adv. Appl. Prob., V. 13, P. 619-630, 1981.

93. H. Thorisson (2000) Coupling, Stationarity, and Regeneration (Springer, NY).

94. H. Thorisson (1985) The queue GI/G/1: Finite moments of the cycle variables and uniform rates of convergence. Stochastic Processes and Applications 19, 85-99.

95. H. Thorisson (1985) The queue GI/G/k: Finite moments of the cycle variables and uniform rates of convergence. Stochastic Models applications 1, 221-238.

96. Vorobieva I., Morozov E., Pagano M., Procissi G. A New Regenerative Estimator for Effective Bandwidth Prediction // Proc. of AMICT'2007. — Petrozavodsk: Petrozavodsk State University, 2008. Vol. 9. P. 175-187.

97. Walrand J., Veciana G. Effective Bandwidths: Call Admission, Traffic Policing and Filtering for ATM Networks. Queueing Systems. V. 22. 1996. P. 203-247.

98. Whitt W., Abate J. Asymptotics for M/G/1 Low-Priority Waiting-Time Tail Probabilities. Proceedings of 34th Allerton Conference on Communication, Control and Computing, S. P. Meyn and W. K. Jenkins (eds.) 1996, pp. 923931.

99. W. Whitt, Comparing counting processes and queues, Advances in Applied Probability, 1981, v.13, 207-220.

100. Wolff, R.: Work-conserving priorities. J. Appl. Probab. 7, 327-337 (1970)

101. Wolff, R.: Poisson Arrivals See Time Averages. Oper. Res. 30 (2), 223-231 (1982)

Список публикаций по теме работы:

102. Калинина К. А. Программа для ЭВМ «Регенеративное оценивание эффективной пропускной способности узла инфо-коммуникационной сети». — Свидетельство о государственной регистрации программы для ЭВМ №2016612795 от 10.03.2016.

103. Калинина К.А., Морозов Е.В. О рандомизации в методе группового среднего при оценивании эффективной пропускной способности высокоответственных систем // Системы и средства информатики. 2017. Т. 27. № 4. С. 36-52.

104. А.С. Румянцев, К.А. Калинина, Т.Е. Морозова. Стохастическое моделирование вычислительного кластера с гистерезисным управлением скоростью обслуживания. Труды КарНЦ РАН. No 8. Сер. Математическое моделирование и информационные технологии. 2017. C. 76-85.

105. Borodina A., Kalinina K., Morozov E. On the accuracy of the effective bandwidth regenerative estimation, ICUMT, 2014, Saint-Petersburg, P. 652656.

106. Kalinina K., Morozov E., Rykov V. Effective bandwidth estimation in highly reliable regenerative networks // The Second International Symposium on Stochastic Models in Reliability Engineering, Life Science and Operations Management, Israel, 2016: Proceedings, P. 323-327.

107. Morozov E., Kalinina K. On the effective bandwidth estimation in communication network, 29th European Conference on Modelling and Simulation 2015: Proceedings, P. 423-429.

108. Morozov E., Rumyantsev A., Kalinina K. Inequalities for workload process in queues with NBU/NWU input. Man-Machine Interactions, Vol. 5. Advances in Intelligent Systems and Computing. Proceedings of International Conference on Man-Machine Interactions, Poland, Krakow, 3-6 October. 2017. Pp. 535544.

109. Rumyantsev A., Zueva P., Kalinina K., Golovin A. Evaluating a SingleServer Queue with Asynchronous Speed Scaling. Measurement, Modelling and Evaluation of Computing Systems, pp.157-172, 2018.

110. Калинина К. Об эффективной пропускной способности узлов коммуникационной сети, Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем: материалы Всероссийской конференции с международным участием.— Москва: РУДН, 2015, С. 24-26.

111. Kalinina K., Morozov E. Effective bandwidth estimation in the regenerative networks, Proceedings of the 18th international scientific conference DCCN-2015, Moscow, ICS RAN, 2015, P. 331-333.

112. Kalinina K. Effective bandwidth estimation in highly critical systems // 19th International Conference on distributed computer and communication networks (DCCN-2016), Moscow, Russia, 2016: Proceedings, P. 215-218.

113. Калинина К. Влияние случайного суммирования на регенеративную оценку эффективной пропускной способности узла сети // Расширенные тезисы IX международной Петрозаводской конференции «Вероятностные методы в дискретной математике», Петрозаводск, Россия, 2016, с.29-31.

114. Калинина К. О рандомизации в методах оценивания ЭПС в высокоответственных системах // Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь (DCCN-2017): материалы Двадцатой междунар. науч. конфер. Москва: М.: Техносфера, 2017. С. 407-410.

Приложение А Свидетельство о регистрации программы

Приложение Б

Программная реализация моделирования работы системы с повторными вызовами и оценивания вероятности большого уклонения на цикле

занятости

Система М/М/1 с постоянной интенсивностью повторных вызовов

lambda=2 mu=3

gamma=200

N=40 Q=1 h=0 Over=0

M=100000 while(h<=M){ S=rexp(1, mu) tau1=rexp(1, lambda) while(tau1>S){ S=rexp(1, mu) tau1=rexp(1, lambda)

h=h+1 }

orbit=1

tau=rexp(1, lambda) xi=rexp(1, gamma) Q=2

S=S-tau1

while(Q>0){

if(tau<xi){

if (tau>=S)

{S=rexp(1, mu) }

else {

orbit=orbit+1 Q=Q+1

if (Q>=N) {

Over=Over+1 break

}

S=S-tau }

xi=xi-tau

tau=rexp(1, lambda) }

else {

if(xi>=S) {

S=rexp(1, mu) orbit=orbit-1

Q=Q-1

tau=tau-xi

if (orbit!=0) xi=rexp(1,gamma) else if (S<=tau) Q=0 else {

orbit=1 Q=2

S=S-tau

xi=rexp(1,gamma) }

}

else {

S=S-xi tau=tau-xi

xi=rexp(1,gamma) }

}

}

h=h+1 }

Over

p=Over/M p

Система H/Weibull/1 с постоянной интенсивностью повторных вызовов

lambda=0.95 mu=2

gamma=30

N=35 Q=1 h=0 0ver=0

M=100000 while(h<=M){ S=rweibull(1, mu) tau1=rexp(1, lambda) while(tau1>S){ S=rweibull(1, mu) tau1=rexp(1, lambda)

h=h+1 }

orbit=1

tau=rexp(1, lambda) xi=rexp(1, gamma) Q=2

S=S-tau1

while(Q>0){

if(tau<xi){

if (tau>=S)

{S=rweibull(1, mu) }

else {

orbit=orbit+1 Q=Q+1

if (Q>=N) {

0ver=0ver+1

break }

S=S-tau }

xi=xi-tau

tau=rexp(1, lambda)

}

else {

if(xi>=S) {

S=rweibull(1, mu)

orbit=orbit-1

Q=Q-1

tau=tau-xi

if (orbit!=0) xi=rexp(1,gamma) else if (S<=tau) Q=0 else {

orbit=1 Q=2

S=S-tau

xi=rexp(1,gamma) }

}

else {

S=S-xi tau=tau-xi

xi=rexp(1,gamma) }

}

}

h=h+1 }

Over

p=Over/M p

Оценивание вероятности большого уклонения в системе М/С/1

require(stats)

lambda=2

mu=3

gamma=10

ro=lambda/mu

N=40 Q=1 h=0 Over=0

td=0 ta=0

M=1000000 while(h<=M){ orbit=0 td=0 ta=0 Q=0

S=rexp(1, mu) + rbinom(1, 1, ro)*rexp(1,gamma)

tau=rexp(1, lambda)

while(tau>S){

S=rexp(1, mu)

tau=rexp(1, lambda)

h=h+1 }

Q=1

td=S

ta=tau

while(Q>0){ if(ta<td){ Q=Q+1

orbit=orbit+1 if(Q>=N) { Over=Over+1 break

}

tau=rexp(1, lambda)

ta=ta+tau }

else{

Q=Q-1

if (orbit>0){

S=rexp(1, mu) + rbinom(1, 1, ro)*rexp(1,gamma) td=td+S

orbit=orbit-1 }

else Q=0

}

}

h=h+1 }

0ver

p=0ver/M p