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

• Потахина Любовь Викторовна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Потахина Любовь Викторовна

Введение

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

1.1. Предварительные результаты

1.2. Процессы восстановления

1.3. Прошедшее и незавершенное время восстановления

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

Глава 2. Анализ моделей телекоммуникационных систем

2.1. Модель системы с оптическим буфером

2.2. Приоритетная система передачи данных по каналу, управляемому цепью Маркова

2.3. Системы с параметрами, зависящими от текущего состояния

2.4. Асимптотический анализ системы с конечным буфером и заявками случайного объема

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

моделей

3.1. Регенерация цепей Маркова, возвратных по Харрису

3.2. Жидкостной метод

3.3. Метод функций Ляпунова

Глава 4. Имитационное моделирование

4.1. Система с оптическим буфером

4.2. Приоритетная система передачи данных по каналу, управляемому цепью Маркова

4.3. Системы с параметрами, зависящими от текущего состояния

Заключение

Перечень сокращений и условных обозначений

Литература

Список иллюстраций

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

Введение

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

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

Степень разработанности. Методы теории восстановления и ее асимптотические результаты в полной мере изложены в источниках [10, 14, 83]. Также стоит отметить работы [56, 58, 66, 85], касающиеся анализа регенеративных систем и применимости регенеративного метода анализа стационарности.

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

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

1. Адаптация регенеративного метода для получения условий стационарности в моделях

— системы с оптическим буфером,

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

— систем, в которых параметры зависят от текущего состояния.

2. Асимптотический анализ характеристик модели с ограничением на суммарный объем заявок методами теории восстановления.

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

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

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

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

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

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

1. Достаточное условие стационарности модели системы с оптическим буфером.

2. Критерий стационарности модели приоритетной системы с каналом передачи, управляемым цепью Маркова.

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

4. Асимптотические соотношения для доли потерянного объема в модели с ограничением на суммарный объем ожидающих заявок.

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

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

1. Международный семинар "4th Nordic Triangular Seminar in Applied Stochastic" (Хельсинки, 6-8 марта 2013 г.);

2. Международный семинар "Networking games and management" (Петрозаводск, 23-25 июня 2013 г.);

3. Международная конференция "Distributed computer and communication networks (DCCN-2013): control, computation, communications" (Москва, 7-10 октября 2013 г.);

4. Международная научная конференция "Computer Networks (CN2014)" (Brunow, Польша, 23-27 июня 2014 г., по итогам конференции доклад был отмечен сертификатом с отличием);

5. Международная конференция "6th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT 2014)" (Санкт-Петербург, 6-8 октября 2014 г.);

6. Всероссийская конференция с международным участием "Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем (ИТТММ 2015)" (Москва, 20-24 апреля 2015 г.);

7. Международная научная конференция "Computer Networks (CN2015)" (Brunow, Польша, 16-19 июня 2015 г.);

8. Международная конференция "International Conference on Man-Machine Interactions (ICMMI 2015)" (The Beskids, Польша, 6-9 октября 2015 г.).

Работа выполнена при поддержке РФФИ (проекты 15-07-02341, 15-07-02354) и программы стратегического развития ПетрГУ на 2012-2016 годы.

Публикации. Материалы диссертации опубликованы в 11 работах, из них 2 статьи в рецензируемых журналах (входящих в БД Web of Science и РИНЦ) [51, 64], 4 статьи в сборниках трудов конференций (индексируемых в БД Scopus) [15, 61, 62, 65] и 5 тезисов докладов [6, 60, 63, 72, 73]. Подана заявка на регистрацию программы для ЭВМ [5].

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

Глава 1

Основные результаты теории восстановления

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

1.1. Предварительные результаты

Виды сходимости случайных величин. Пусть некоторая с. в. £ с ф. р. Р и семейство с. в. п > 1} с соответствующими ф. р. Рп заданы на вероятностном пространстве {П, р}. Последовательность {^п} сходится к £ с в. 1, если £п(ш) ^ при п ^ ж для всех ш, за исключением, возможно, ш Е А Е $ : Р(А) = 0. Последовательность с. в. п > 1} сходится слабо (или по распределению) к £ , если Рп(х) ^ Р(х) при п ^ ж в каждой точке непрерывности Р. Очевидно, сходимость с в. 1 влечет сходимость по распределению. (О видах сходимости с. в. см. [1, 2].)

Для любой последовательности н. о. р. с. в. {^п} будем называть типичным элементом данной последовательности такую с. в. £, что £ =31 £п . Поэтому всюду далее типичный элемент любой последовательности н. о. р. с. в. обозначается без индекса.

С. в. £ (и ее ф. р. Р) называется решетчатой с шагом решетки (1 > 0, если £ принимает значения из множества {0,^, 2(1,... } св. 1, и ё, является максимальным таким значением. Если не существует такого (1, то с. в. £ (и ф. р. Р) называется нерешетчатой. Целочисленная решетчатая с. в. £ называется периодической.

Случайные процессы. Семейство с. в. £ = Ь Е т}, заданное на

вероятностном пространстве {П, р}, называется случайным процессом. Про-

цесс рассматривается в непрерывном времени, если t = (-то, то) или t = [0, то) (обозначается (£)}) и в дискретном времени, если t = {..., -1,0,1,... } или t = {0,1,...} (обозначается {^п})- Для фиксированного ш £ величина £(w,i) представляет собой траекторию случайного процесса, а при фиксированном t £ t, £(w,t) есть с. в.

Стохастическая ограниченность. Последовательность с. в. {^n, п > 1} является стохастически ограниченной, если для любого £ > 0, существует константа D такая, что supnp(^n > D) < £ [10].

Равномерная интегрируемость. Последовательность с. в. {^n, п > 1} называется РИ, если

lim supe{|£n|; |£n| > N} = 0. (1.1)

Jy ^то п

Тогда, если ^ ^ при п ^ то, то [1]

e^n ^ e£, п ^ то. (1.2)

Отметим, что (1.2) имеет место, если верна

Теорема 1.1.1 (Лебега о мажорируемой сходимости [11]). Пусть с. в. {^п} и ^ таковы, что |£n| < e|^| < то и £п ^ ^ п. н. Тогда e|^| < то и

e^n ^ e^, п ^ то. (1.3)

Теорема 1.1.2 (Анскомб [35]). Пусть {^n, п > 1} - последовательность н. о. р. с. в. таких, что e^ = 0 и а2 := £ (0, то), а {Ж(t), t > 0} - семейство положительных целочисленных с. в. таких, что для некоторой постоянной в £ (0, то)

N(t)

—---У и с в. 1 при t ^ то.

Тогда

^N(t) £ ^N(t) £

^ ^ n(0,1) и ^ n(0,1) при t ^то.

a

у/Щ) aVet

Теорема 1.1.3 (Тождество Вальда [14, 78]). Пусть {^п, п > 1} - н. о. р. с. в, а с. в. N принимает неотрицательные целые значения. Пусть событие {Ж > п — 1} измеримо относительно а-алгебры, порожденной с. в. . . . , для любого п =1, 2,... . Тогда, если Е|£| < ж и ЕЖ < ж, то

N

[Е = Е^ Е^. (1.4)

e

п=1

Усиленный закон больших чисел. Пусть {^п, п > 1} - н. о. р. с. в.

и e^ = а Е (—то, то). Тогда Zn = ^ + • • • + п > 1 описывает случайное

блуждание на R и справедлив УЗБЧ

%

— ^ а с в. 1. (1.5)

п

Заметим, что для любого t при п ^ то

п1 ¿. t

Zn ^ at св.1. (1.6)

п tn

Этот результат лежит в основе доказательства Функционального УЗБЧ [11]: для любого конечного Т при п ^ то

sup lZn(t) — ai| ^ 0. (1.7)

tE[0,T ]

Напомним формулировку классической ЦПТ [2].

Теорема 1.1.4 (ЦПТ). Пусть {^п, п > 1} - н. о. р. с. в. такие, что e^ = а, 0 < d := < то. Тогда

Sn := — ^ n(0,1), при п ^ то. (1.8)

'па

Класс распределений "новое лучше (хуже) старого". С. в. £ с ф. р.

F(х) ^и F(x) := 1 — F(х)^ принадлежит классу распределений "новое лучше старого" (New Better than Used, NBU), если

F(x + у) < F(x)F(y), x > 0, у > 0, (1.9)

или, что эквивалентно,

p (£ - у>хЦ>у) < p (£>х).

С. в. £ принадлежит классу распределений "новое хуже старого" (New Worse than Used, NWU), если

Выражения (1.9) и (1.10) означают, что на событии > у} перескок £ — у стохастически не больше (для КБи) или не меньше (для NWU) исходной с. в. £

1.2. Процессы восстановления

Рассмотрим случайные моменты времени 0 < Z0 < < Z2 < ..., в которые происходит некоторое событие. Число таких моментов в интервале (0,£] равно

Процесс Ь > 0} называется процессом восстановления (п. в.), если интервалы Хп := Zn — Zn—l, п > 2, являются н. о. р. с. в. и не зависят от интервала Х\ = Z\ — Z0, который может иметь другое распределение. Моменты {%п, п > 0} называются моментами восстановления (м. в.), а {Хп, п > 0} -интервалами восстановления (и. в.). П. в. является стационарным, если для любого I > 0

F(x + у) > F(x)F(y), х > 0, у > 0.

(1.10)

[69, 70].

00

Nt := ^ !{Zn < t} = inf{n : >г},г > 0.

(1.11)

(1.12)

Пусть Р - ф. р. с. в. X, а / - ее плотность. Тогда ф. р. Рп(Ь) := Р(^п < Ь) есть п-мерная свертка функции Р с собой. Функция

00

Н(¿) := ЕЩ = ^ г > 0, (1.13)

п=1

где Н(0) = 0, называется функцией восстановления и равна среднему числу восстановлений в интервале (0, £]. Справедлива следующая элементарная теорема восстановления [83]

, Н(г) 1

Ит —^ — -. (1.14)

¿—ж £ д

Определим функцию С как свертку функции восстановления с ограниченной вещественной функцией д, то есть

в(г) := н(г) * д(г) =

д(г — и^Н (и) (1.15)

о

(при I < 0 полагаем д(р) = 0, С(Ъ) = 0). Известно, что функция С является единственным решением следующего уравнения восстановления [14]:

О

С(1) = д(г) +

— и^р(и), г > 0, (1.16)

причем функция д считается известной.

Следующая Ключевая теорема восстановления [83] является одной из основных в теории восстановления.

Теорема 1.2.1. Пусть функция д в (1.16) является непосредственно интегрируемой по Риману (см. [10, 14]), ф- р. ^ - нерешетчатая и ц, < ж. Тогда

ж

С(1) = Н(!) * д(1) — 1

еХ

д(и)(1и, £ — ж. (1.17)

о

Теорема 1.2.2 (ЦПТ для процесса восстановления). Пусть X = 1/ЕХ. Тогда

К — М

/йЖ3

^ N(0,1), г —у ж. (1.18)

Поясним кратко ее вывод. По классической ЦПТ для достаточно большого п имеем

гп — пц, — xzNt — щ ,, п . -^^ ~ —t ._ = —, t « n(0,1), (1.19)

где п заменено на ^ по теореме Анскомба (1.1.2). Заметим, что ZNt ~ Ь, —n(0,1)

=^ n(0,1) и \fN~t ~ в силу (1.12). Отсюда и из (1.19) следует

(1.18).

1.3. Прошедшее и незавершенное время восстановления

Для каждого Ь определим прошедшее время текущего и. в. А1 и незавершенное время текущего и. в. (перескок) В1 соответственно, как

Аг = Ь — ZNt—l, Вг = ZNt — t,

и тогда ^ = А1 + ^ есть и. в., накрывающий момент времени £ [10].

Отметим, что п. в. стационарен (то есть (1.11) выполнено), если распределение времени перескока ^ не зависит от £, то есть если (марковский) процесс {В^ стационарен. Заметим, что

{Вг < £} = { м. в. в интервале (£,£ + £] } = {Аг+^ < £}.

Кроме того,

р(Д > = х) = р№ > ж + у1Х1 >х) = Р(*+.у). (1.20)

Ь (х)

Лемма 1.3.1. Верны следующие утверждения:

(г) Если стационарен, то {В^ тоже стационарен.

(гг) Если А1 имеет распределение Р0, то В1 распределено так же, причем р(л >х,Вг >у) = Ро(х + у).

Доказательство. (1): следует непосредственно из (1.20), откуда видно, что распределение ^ является функцией А^. (п): Если имеет распределение то из (1.20) следует

00

Р(Л >х,Вг >у) =

+ у) (, , 1

00

Ё(Х + у) =

1

М

р(х )<1г = Г0(х + у),

х+у

откуда получаем (при х = 0), что ^ имеет распределение Р0.

□

Запишем ф. р. для накрывающего интервала

00

р(^ < =

к=1

Р(£ — х<и < х)Р(гк е (1и) =

х

1{х > г — и}[г(х) — ^(г — и)](1Н(и).

Тогда из Ключевой теоремы восстановления следует, что

Ит P(LÍ < х) = -

[^ (х) — ^ (и)](1и = 1

м

иГ ((1и),

(1.21)

где в последнем равенстве используется интегрирование по частям. Аналогично запишем ф. р. для перескока В¿:

Р(Вг < ж) =

[^ (£ — и + ж) — ^ (£ — (и).

(1.22)

Применяя Ключевую теорему восстановления, получаем

Ит Р(Вг < ж)

1

М

[^ (и + х) — ^

где

(X)

00

00

(и + х) — Р (и)]йи =

Р(Х > и)(1и —

р(Х >и + х)(1и =

р(Х > и)(1и.

Таким образом, ф. р. Р0 для стационарного ^ (и Д) имеет вид

^о(ж) := Нш Р(Д < ж)

1

М

(1 — ^ (и))^

(1.23)

и обладает плотностью ^0(ж) = Р(х)/^.

Обозначим Н(г,х) := Р(Д < ж). В силу (1.23)

Нш Н(£, ж)

1

М

[1 — ^(й)] ¿5.

(1.24)

Распределение в (1.24) имеет конечное м. о. в том и только том случае, когда Р имеет дисперсию. Можно показать [10], что в случае д = ж при любом х

Н(£, х) ^ 0, £ ^ ж,

(1.25)

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

Пусть ЕА2 < ж и существуют пределы при Ь ^ ж

Аг ^ ^оо, Вг ^ Вы, Ьг ^ Ьж.

(1.26)

Обозначим X(и) := X — и. Тогда в силу Теоремы 1.4.1, трактуя {А^ и {В^

как регенерирующие процессы, получаем

-х

е/о x(и)(1и ех2

еЛж = еБж = ^ = е^, Е[Аж}2 =

'00

еХ

2д

еХ 3 3д '

откуда

= еЛ«, + е^ =

ех2 м

(1.27)

(1.28)

Выражения (1.27) и (1.28) являются одной из форм парадокса времени восстановления [26].

В силу (1.23) и (1.21) моменты порядка р > 0 имеют вид

е( ВЖ) = ^—1(р + 1)—1 е(ХР+1), е(£Ж) = д—1е(ХР+1) (1.29)

и конечны, когда е(ХР+1) < ж.

Заметим, что ZNt = £ + Применяя к этому равенству операцию м. о. и тождество Вальда (1.4), получаем

+ е о

е % = цн(¿), н(¿) = - + —-. (1.30)

Более того, так как

Нт ЕВ- = — = ^, (1.31)

-—ж

то

Ч Ъ ЕХ2 н(¿) = - + + о(1), г — ж. 2

Более точное выражение для верхней границы дает следующая лемма [14].

Лемма 1.3.2. [Неравенство Лордена] Для любого Ь

е В- < еХ2/11. (1.32)

Доказательство. Из полуаддитивности функции восстановления следует, что Н(Ь + в) — Н(в) < Н(¿). Из (1.30) следует

е в- + е ва = д[я(¿) + н(й)] —г — з> дн(г + з) — г — з = ев-+3.

Заменяя + на , получим

е В- < е В8 + е В-—8 < т£{е В8 + е В-—8 : 0 < в < ¿/2} <

-/2 о

22 < - [е В8 + е В-—8]йз = -

е В8йз. (1.33)

Это дает следующее равенство:

1 ^ 1

В ¿8 = ^ X* — ^ В*. (1.34)

п=1

Применяя операцию м. о. к обоим частям (1.34), получим г

ЕВ^в = 1 е^еХ2 — 1 еВ* = 1Н (¿)еХ2 — 1 еВ* 2 2 2 2

= ^ + еВ^)еХ2/^ — 1 еВ*. (1.35)

22

Обозначим а = еВ^, тогда еВ* > а, и из (1.33) и (1.35) получаем

га < (г + а)ЕХ2/^ — а2,

то есть

а2 + а(г — еХ2/д) — г еХ2/¡I < 0. (1.36)

Правая часть (1.36) - это квадратное уравнение относительно а с корнями —£ и еХ2/д. Значит — г < а < еХ2/д. □

Теперь на основании Леммы 1.3.2 и (1.30) получаем верхнюю границу для функции восстановления:

/, г ех 2

н(г) < - + . (1.37)

д д2

Кроме того, ниже используется обобщенное неравенство Лордена [24]: для любого р > 0 верно

е(В[) < 0 + 2)е(Вж). (1.38)

Дальнейшие результаты в этом направлении см. в [24, 39, 43, 46, 50].

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

Вещественный случайный процесс X = {X (£), £ > 0}, определенный на вероятностном пространстве {П, Г, р}, называется регенерирующим, если суще-

ствует последовательность случайных моментов 0 < Z0 < Z1 < ... такая, что случайные элементы

Сп := {X(7,п + ¿) : 0 < г <Zn+1 _ Zn}, п > 1,

(1.39)

называемые циклами регенерации (ц. р.), являются н. о. р. и не зависят от начального цикла С0 := {X(£) : 0 < £ < Zo}. Моменты {Zn} называются моментами регенерации (м. р.). Обозначим длины ц. р. через Тп = Zn _ Zn_l, п > 0. Если еТ < ж, то процесс называется положительно возвратным, по аналогии с неприводимыми ЦМ, для которых положительная возвратность означает конечность среднего числа шагов до возвращения в любое фиксированное состояние [94]. Если цикл С0 имеет распределение, отличное от последующих циклов, то процесс X называется регенерирующим процессом с задержкой. В этом случае для положительной возвратности требуется дополнительное условие Z0 < ж св. 1.

Отметим, что м. р. образуют вложенный процесс восстановления и N1 равно числу регенераций до момента £. Запишем

X(зЦв = ВД + VI + • • • + У^ + Д*, г> 0,

(1.40)

где

шш (г, г0)

X(й)^, Дг :=

ВД := X(8)й8, Уп : =

о

Легко видеть, что У0(Ь) ^ Уо^0) < ж при Ь ^ ж. Пусть

г г

X (8)(18.

У0 := тах

0<г <г0

Уп := тах

гп— 1 <г <%п

г

п-1

X (в^в

где с. в. {Уп} являются н. о. р. Отметим, что

Уп = тах | Дг |, п > 1.

гп-1<г <гп

X (вЦв

п 1,

(1.41)

Следующая теорема играет важную роль при анализе регенерирующих процессов [14].

Теорема 1.4.1. Пусть еТ < то, е|У | < то, еУ < то и У0 < то св. 1. Тогда

г0 X Шв еУ

^——-->-— св. 1. (1.42)

г ет v ;

Доказательство. Поскольку {У,} являются н. о. р. с. в., то по УЗБЧ

£1=1 Ъ £1=1 Уг ^ еУ

— = ---> ==, г — то.

г щ г ет

В силу (1.41), при 0

А, - % Ъ (1.43)

г - щ г 1 ;

Из (1.12) следует, что — 1/еТ Е (0, то). Далее, при еУ < то, с в. 1 верно

Уп £п=1 к ^п-1 К:

— 0 г — то. п п п

Значит А,/Ь — 0 при Ь — то. Кроме того, очевидно, что У0(г)/г — 0 св. 1 при г — то. Из этого и (1.40) следует, что (1.42) верно. □

Случайный процесс С = {£(£),£ > 0} называется процессом накопления, если:

(1) приращения {Ап := С(^п) — С^п—1), п > 1} являются н. о. р. с. в.;

(2) процесс С с в. 1 имеет ограниченную вариацию на каждом конечном интер-

вале [0, £], то есть для любого разбиения {хп} : 0 = х1 < < • • • < zп = £

п—1

г=1

< то с в. 1;

(3) приращения {Ап := С(^п) — С(^п—1)} процесса С(£) := /0 (м)| являются н. о. р. с. в.

Процессы накопления тесно связаны с регенерирующими процессами [82]. Одним из типичных примеров процесса накопления является интеграл от измеримой функции / регенерирующего процесса {X (£)} [4], то есть

е(*) =

$\х(з)№, г > 0.

В этом случае, если еТ < то и еА < то, то по Теореме 1.4.1,

ет еа

— — — с в. 1. (1.44)

г ет v '

1.4.1. Регенеративный анализ стационарности

Данный раздел посвящен методу анализа стационарности систем обслуживания, обладающих свойством регенерации [17, 41, 59]. Это означает, что траектория случайного процесса, описывающего поведение системы, разбивается на н. о. р. ц. р. в м. р., которые образуют вложенный п. в. Здесь и далее термин система будет означать модель рассматриваемой системы обслуживания [40].

Как и в [58], рассмотрим систему С1 /С/1, в которую заявки поступают в моменты {Ьп} через н. о. р. интервалы тп = Ьп+1 — 1п, п > 0, причем ет Е (0, то). Пусть {Бп, п > 0} - н. о. р. времена обслуживания, Е (0, то). Определим процесс величины очереди V = {и(£)}, где V(£) - число заявок в системе в момент I, а ип = V(£—), п > 0 - число заявок в момент прихода заявки п. Считаем, что в системе задана некоторая дисциплина обслуживания заявок. Так же определим процесс загрузки системы W = {Ж(£)}, где W(^ - незавершенное время обслуживания всех заявок, находящихся в системе в момент £ (при отсутствии поступления новых заявок), и пусть Wп = W(£—). Напомним рекурсию Линдли, определяющую последовательность времен ожидания обслуживания заявок в системе:

^п+1 = (Жп + Зп — Тп)+, п > 0. (1.45)

Поскольку {Wk = 0} = {щ = 0} (поступление заявки в пустую систему), то вложенные последовательности {Wn} и {ип} (в дискретном времени) регенерируют одновременно в моменты

0п+1 = тт{& > вп : Wк = 0}, п > 0, 6>0 = 0, (1.46)

причем тт 0 = ж. Моменты регенерации для процессов V и W в непрерывном времени определяются следующим образом:

Zn+l = т1п{^ >Zn ^(Ц)=0}, п > 0, Zo = (1.47)

Очевидно Z1 = т0 + • • • + тв1—1. Тогда из тождества Вальда (1.4) следует

еТ = ете 3, (1.48)

где 3 и Т есть типичные длины ц. р. в дискретном и непрерывном времени соответственно, то есть 3 =вг вп _ @п—1 и Т Zn _ Zn_1 при п > 1.

Для процессов в дискретном времени рассмотрим незавершенное время регенерации в момент п

3 (п) = тт{_ п : _ п > 0}.

В силу (1.25) ^при £ = п и Вг = 3(пверна следующая асимптотика величины 3 (п): независимо от начального значения 91

3(п) ф ж тогда и только тогда е3 = ж.

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

Основная идея регенеративного метода анализа стационарности стоит в том, что при любом 1

3(п) ф ж влечет е3 < ж. (1.49)

Тогда из (1.48) следует eT < ж, и процесс W является положительно возвратным.

Отметим, что запись ß(п) ф ж эквивалентна тому, что существуют константы х0 > 0, £ > 0 и последовательность пг ^ ж такие, что

inf p(ß(пг) < хо) > е. (1.50)

Для доказательства существования стационарного распределения важен следующий результат [14].

Теорема 1.4.2. Если с. в. ß является непериодической и Eß < ж, тогда существует стационарное распределение процесса {Wn}. Аналогичное утверждение верно и для процесса в непрерывном времени, если ß - нерешетчатая.

Отметим, что процесс {Wn} является примером процесса накопления (подробнее см. [4]). Так как Дп = W(Zn+1) — W(Zn) = 0 и еД = 0, то в силу (1.44)

lim ^ = 0 св.1. (1.51)

t ^ж t

Опишем основные шаги применения регенеративного метода к анализу процесса {Wn}. Необходимо показать, что

(1) Доказать отрицательный снос процесса {Wn} вне ограниченного множества

A = [0, D]:

e(Wn+i — Wn|Wn = х) < 0 при х £ A.

(2) Доказать, что

p( Wn регенерирует за конечное время | Wn £ A) > 0.

(3) Из шагов (1), (2) следует, что ß(п) ф ж и, значит, eß < ж.

Заключительный шаг анализа заключается в доказательстве непериодичности длины цикла регенерации (для дискретного времени) или его нерешетчатости (для процесса в непрерывном времени).

Следующие определения необходимы для дальнейшего анализа. Будем называть систему стационарной тогда и только тогда, когда соответствующий процесс восстановления ¡3 является положительно возвратным. В случае, если ЕД = то, система может быть слабо или строго нестационарной. Система называется слабо нестационарной, если W(^ ^ то и V(£) ^ то. Будем называть систему строго нестационарной, если W(^ — то и V(£) — то св. 1. (Терминологию см. в [55, 66].)

Глава 2

Анализ моделей телекоммуникационных систем

В данной главе в разделах 2.1 - 2.3 приведены достаточные условия стационарности некоторых новых моделей телекоммуникационных систем, полученные на основе описанного выше регенеративного метода. Кроме того в разделе 2.4 описано применение результатов теории восстановления для асимптотического анализа характеристик системы с конечным буфером и заявками случайного объема.

2.1. Модель системы с оптическим буфером

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

Рассмотрим сеть с оптической коммутацией пакетов, в которой данные (заявки) перемещаются от источника к пункту назначения в форме света (то есть без преобразования в электрический сигнал в промежуточных пунктах). Для буферизации оптических сигналов используется счетное множество A = {Z0, Z\, Z2,... }, каждый элемент которого соответствует длине некоторой оптоволоконной линии задержки (ОЛЗ) [22, 76]. Будем считать, что на обслуживающем устройстве (сервере) реализована дисциплина FIFO и каждая требующая буферизации заявка отправляется на ОЛЗ так, что к моменту завершения прохождения заявки по линии, сервер обработает накопленную до ее прихода загрузку и будет готов начать обслуживание данной заявки. В общем случае поступающая в сеть заявка будет ожидать обслуживания дольше, чем в случае классической системы с бесконечным буфером, поскольку времена ожидания выбираются из множества A (это подробнее поясняется ниже). В данном разделе рассматриваются системы с множеством ОЛЗ со случайными длинами,

согласно работе [64]. (Системы, в которых A содержит ОЛЗ с детерминированными длинами, проанализированы в работах [61, 85, 86].)

Определим длину n-й линии как Zn := Ai+- • -+ДП, Z0 := 0, где {Дп, п > 1} есть неотрицательные н. о. р. с. в. Будем предполагать, что с. в. Д нерешетчатая. (В общем случае можно предположить, что Zn = а0 + Д1 + • • • + Дп, где а0 = const - заданная минимальная задержка. Но дальнейшие рассуждения не зависят от этого предположения.) Будем говорить, что Zn содержит п элементарных звеньев с типичной длиной Д. При такой интерпретации фактическая длина необходимой случайной линии априори не известна и зависит от реализаций с. в. {Дп}.

Пусть в момент прихода n-й заявки загрузка в системе равна Wn = х. Тогда, чтобы данной заявке гарантировать задержку не менее заданного порога х, необходимо иметь

N(х) = inf{п > 0 : Zn > х} (2.1)

элементарных звеньев. Заметим, что {N(х),х > 0} является п. в., порожденным случайным блужданием {Zn}. Тогда фактическая (случайная) задержка заявки (или ее время ожидания) определяется как Zn(х) или, что эквивалентно,

ZN (х) = inf {Zn Е A : Zn - ж > 0}. (2.2)

n>0

Положим Zn(0) = N(0) = Z0 = 0 для х < 0, что соответствует случаю неожидающей заявки. Для каждого х > 0 определим перескок п. в. через х как

Д(х) = Zn(х) - х. (2.3)

По определению, Д(х) > 0 для любого х > 0 и Д(^) = 0 для любого к > 0. Далее предположим, что для некоторого е0 > 0

0 < еД2+£0 < то. (2.4)

Ввиду еД < ж, для любого £0 > 0 существуют константы И < ж, 5* > 0 такие, что

р(6* < Д < И) > 1 _ ¿0. (2.5)

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

. . еД2 еД2 , ,

Д* := еД , Д0 := 2еД. (2.6)

Отметим, что Д0 = еД(ж) (см. 1.27), а из неравенства Лордена (1.32) следует, что для всех х > 0

еД(х) < Д*. (2.7)

Пусть времена между приходами заявок есть н. о. р. с. в. {ть} с ф. р. , а времена обслуживания заявок - н. о. р. с. в. {5^} с ф. р. ^, причем соответствует времени между приходами к и к+1 заявки, а - времени обслуживания к-й заявки. Определим и := 5 — г и пусть ¥ц(х) = Р(и < х), х £ (_ж, +ж). Заметим, что ввиду независимости г и 5 распределение и имеет вид:

00

(х) =

^ (х + у)Рт (йу).

Пусть Wk определяет оставшуюся загрузку в системе в момент прихода заявки к, то есть это время, необходимое для завершения работы, накопленной в системе (в оптическом буфере и на сервере) до прихода заявки к. Определим процесс загрузки W = {Wk, к > 0} и сконструируем м. р. {вп} процесса W стандартным образом как в (1.46). Будем рассматривать регенеририующий процесс W без задержки, в котором точка 0 является м. р. и 3 - длина типичного ц. р.

Список литературы диссертационного исследования кандидат наук Потахина Любовь Викторовна, 2015 год

Литература

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

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

3. Боровков, А. А. Эргодичность и устойчивость случайных процессов / А. А. Боровков. — М.: Эдиториал УРСС, 1999. — 440 с.

4. Некрасова, Р. С. Регенеративный метод и его применение в анализе систем обслуживания / Р. С. Некрасова, Е. В. Морозов. — Петрозаводск: Издательство ПетрГУ, 2013. — 76 с.

5. Потахина, Л. В. Программа для ЭВМ "Вычисление времени ожидания заявки в модели приоритетной системы, управляемой цепью Маркова".— Номер и дата поступления заявки в Федеральный институт промышленной собственности: №2015618491 от 08.09.2015.

6. Потахина, Л. В. Регенеративный метод в анализе стационарности телекоммуникационных систем / Л. В. Потахина // Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем: материалы Всероссийской конференции с международным участием. — М.: РУДН, 2015. — С. 50-52.

7. Рыбко, А. Н. Об эргодичности случайных процессов, описывающих функционирование открытых сетей массового обслуживания / А. Н. Рыбко, А. Л. Столяр // Проблемы передачи информации. — 1992.— Т. 28, № 3. — С. 3-26.

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

9. Тихоненко, О. М. Определение характеристик систем обслуживания с ограниченной памятью / О. М. Тихоненко // Автоматика и телемеханика. — 1997. —Vol. 6. — P. 105-110.

10. Феллер, В. Введение в теорию вероятностей и ее приложения / В. Феллер. — М.: Мир, 1967. — Т. II. — 765 с.

11. Ширяев, А. Н. Вероятность / А. Н. Ширяев. — М.: МЦНМО, 2004. — В 2-х книгах.

12. Aalto, S. Flow-level stability and performance of channel-aware priority-based schedulers / S. Aalto, P. Lassila // Proceedings of 6th EURO-NF Conference on Next Generation Internet, 2010.— 2010.

13. Alonso, M. Power saving in regular interconnection networks. / M. Alonso, et al. // Parallel Computing. — 2010. — Vol. 36, no. 12. — P. 696-712.

14. Asmussen, S. Applied Probability and Queues / S. Asmussen. — 2 edition. — Springer-Verlag, NY, 2003. — 438 p.

15. Asymptotic analysis of queueing systems with finite buffer space / E. Morozov, R. Nekrasova, L. Potakhina, O. Tikhonenko // Communications in Computer and Information Science. — 2014. — Vol. 431. — P. 223-232.

16. Athreya, K. B. A new approach to the limit theory of recurrent markov chains / K. B. Athreya, P. Ney // Transactions of the American Mathematical Society. — 1978. — Vol. 245. — P. 493-501.

17. Avrachenkov, K. Stability analysis of GI/GI/c/K retrial queue with constant retrial rate / K. Avrachenkov, E. Morozov // Mathematical Methods of Operations Research. — 2014. — Vol. 79. — P. 273—291.

18. Ayesta, U. A modeling framework for optimizing the flow-level scheduling with time-varying channels / U. Ayesta, M. Erausquin, P. Jacko // Performance Evaluation.—2010. —Vol. 67, no. 11. —P. 1014-1029.

19. Bonald, T. A score-based opportunistic scheduler for fading radio channels / T. Bonald // Proceedings of European Wireless. — 2004. — P. 283-292.

20. Borst, S. User-level performance of channel-aware scheduling algorithms in wireless data networks / S. Borst // IEEE/ACM Transactions on Networking.— 2005. — Vol. 13, no. 3. — P. 636-647.

21. Bremaud, P. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues / P. Bremaud. — Springer-Verlag New York, 1998. — 445 p.

22. Callegati, F. Optical buffers for variable length packets / F. Callegati // IEEE Communications Letters. — 2000. — Vol. 4, no. 9. — P. 292-294.

23. CDMA/HDR: a bandwidth-efficient high-speed wireless data service for nomadic users / P. Bender, P. Black, M. Grob et al. // IEEE Communications Magazine. — 2000. — Vol. 38, no. 7. — P. 70-77.

24. Chang, J. Inequalities for the overshoot / J. Chang // Annals of Applied Probability. — 1994. — Vol. 4, no. 4. — P. 1223-1233.

25. Chernova, N. A polling system whose stability region depends on the whole distribution of service times / N. Chernova, S. Foss, B. Kim // Operations Research Letters. — 2013. — Vol. 41, no. 2. — P. 188—-190.

26. Cooper, R. B. Some reflections of the renewal theory. paradox in queueing theory / R. B. Cooper, S.-C. Niu, M. M. Srinivasan // Journal of Applied Mathematics and Stochastic Analysis. — 1998. — Vol. 11, no. 3. — P. 355-368.

27. Czachorski, T. Queue with limited volume, a diffusion approximation approach / T. Czachorski, T. Nycz, F. Pekergin // Lecture Notes in Electrical Engineering. — 2010. — Vol. 62. — P. 71-74.

28. Dai, J. A fluid limit model criterion for instability of multiclass queueing networks / J. Dai // Annals of Applied Probability.— 1996.— Vol. 6, no. 3. — P. 751-757.

29. Dai, J. G. On positive harris recurrence of multiclass queueing network: A unified approach via fluid limit models / J. G. Dai // The Annals of Applied Probability. — 1995. — Vol. 5, no. 1. — P. 49-77.

30. Delgado, R. Stability analysis of cascade networks via fluid models / R. Delgado, E. Morozov // Performance Evaluation. — 2014. — Vol. 82. — P. 39—-54.

31. Down, D. A survey of markovian methods for stability of networks / D. Down, S. Meyn // Lecture Notes in Control and Information Sciences. — 2005. — Vol. 199. — P. 490-504.

32. Foss, S. On the stability of a partially accessible multi-station queue with state-dependent routing / S. Foss, N. Chernova // Queueing Systems. — 1998. — Vol. 29, no. 1. — P. 55-73.

33. Gandhi, A. Optimal power allocation in server farms. / A. Gandhi, et al. // ACM SIGMETRICS Performance Evaluation Review.— 2009.— Vol. 37, no. 1. — P. 157-168.

34. Glynn, P. Wide-sense regeneration for harris recurrent markov processes: An open problem / P. Glynn // Queueing Systems: Theory and Applications. — 2011. — Vol. 68, no. 3-4. — P. 305-311.

35. Gut, A. Anscombe's theorem 60 years later / A. Gut // Department of Mathematics Uppsala University, Research Report. — 2011. — Vol. 14.

36. Ibm energyscale for power7 processor-based systems. — http://www-03.ibm. com/systems/power/hardware/whitepapers/energyscale7.html.

37. Intel turboboost technology.— http://www.intel.ru/content/www/ru/ru/ architecture-and-technology/turbo-boost/turbo-boost-technology. html.

38. Jacko, P. Value of information in optimal flow-level scheduling of users with markovian time-varying channels / P. Jacko // Performance Evaluation. — 2011. —Vol. 68, no. 11.—P. 1022-1036.

39. Jewell, W. S. A curious renewal process average / W. S. Jewell // Stochastic processes and their Applications. — 1981. — Vol. 11. — P. 293-295.

40. Kaj, I. Stochastic Modeling in Broadband Communications Systems / I. Kaj.— Society for Industrial and Applied Mathematics, Philadelphia PH, 2002. — 177 p.

41. Kalashnikov, V. V. Regenerative queueing processes and their qualitative and quantitative analysis / V. V. Kalashnikov // Queueing Systems.— 1990.— Vol. 6, no. 1. — P. 113-136.

42. Kallenberg, O. Foundations of Modern Probability / O. Kallenberg. — Springer-Verlag New York, 1997. — 638 p.

43. Kamps, U. On a renewal process average / U. Kamps // Stochastic Processes and their Applications. — 1996. — Vol. 62. — P. 347-349.

44. Kelly, F. P. Loss networks / F. P. Kelly // Annals of Applied Probability. — 1991. —Vol. 1. — P. 319-378.

45. Knopp, R. Information capacity and power control in single-cell multiuser communications / R. Knopp, P. Humblet // Proceedings of IEEE International Conference on Communications. — 1995.— P. 331-335.

46. Kremers, W. An extension and implications of the inspection paradox / W. Kremers // Statistics & Probability Letters. — 1988. — Vol. 6. — P. 269-273.

47. Kushner, H. Convergence of proportional-fair sharing algorithms under general conditions / H. Kushner, P. Whiting // IEEE Transactions on Wireless Communications. — 2004. — Vol. 3. — P. 1250-1259.

48. Liu, S. Scheduling in multichannel wireless networks with flow-level dynamics / S. Liu, L. Ying, R. Srikant // ACM SIGMETRICS Performance Evaluation Review - Performance. — 2010. — Vol. 38, no. 1. — P. 191-202.

49. Location-assisted clustering and scheduling for coordinated homogeneous and heterogeneous cellular networks / M. Eslami, R. C. Elliott, W. A. Krzymien, M. Al-Shalash // Transactions on Emerging Telecommunications Technologies. — 2013. — Vol. 24, no. 1. — P. 84-101.

50. Lorden, G. On excess over the boundary / G. Lorden // The Annals of Mathematical Statistics. — 1970. — Vol. 41, no. 2. — P. 520-527.

51. Maximal flow-level stability of best-rate schedulers in heterogeneous wireless systems / P. Jacko, E. Morozov, L. Potakhina, I.M. Verloop // Transactions on Emerging Telecommunications Technologies. — 2015. — DOI: 10.1002/ett.2930.

52. Meyn, S. Markov Chains and Stochastic Stability / S. Meyn, R. Tweedie. — Springer-Verlag New York, 1993. — Online ISBN: 978-1-4471-3267-7.

53. Morozov, E. The tightness in the ergodic analysis of regenerative queueing processes / E. Morozov // Queueing Systems. — 1997. — Vol. 27. — P. 179-203.

54. Morozov, E. Fluid approach in stability analysis of multiclass communication networks / E. Morozov // FDPW'2001-2002 Petrozavodsk University Press. — 2002. —Vol. 4. — P. 20-41.

55. Morozov, E. Weak regeneration in modeling of queueing processes / E. Morozov // Queueing Systems. — 2004. — Vol. 47. — P. 295-315.

56. Morozov, E. A multiserver retrial queue: regenerative stability analysis / E. Morozov // Queueing Systems. — 2007. — Vol. 56. — P. 157-168.

57. Morozov, E. Stability analysis of a general state-dependent multiserver queue / E. Morozov // Journal of Mathematical Sciences. — 2014.— Vol. 200, no. 4.— P. 462-472.

58. Morozov, E. Stability analysis of regenerative queueing systems / E. Morozov, R. Delgado // Automation and Remote control. — 2009.— Vol. 70, no. 12.— P. 1977-1991.

59. Morozov, E. Stability analysis of multiserver discrete-time queueing systems with renewal-type server interruptions / E. Morozov, D. Fiems, H. Bruneel // Performance Evaluation. — 2011. — Vol. 68. — P. 1261—-1275.

60. Morozov, E. Asymptotic analysis of a queuing system with finite buffer space / E. Morozov, R. Nekrasova, L. Potakhina // Distributed Computer and Communication Networks: Control, Computation, Communications (DCCN-2013). — Moscow: JCS "TECHNOSPHERA", 2013. — P. 345-347.

61. Morozov, E. An application of the inspection paradox in stability analysis of optical systems / E. Morozov, L. Potakhina // Proceedings of ICUMT 2014: The 6th International Congress on Ultra Modern Telecommunications and Control systems and Workshops, Saint-Petersburg. — 2014.— P. 622-625.

62. Morozov, E. Asymptotically work-conserving disciplines in communication systems / E. Morozov, L. Potakhina // Communications in Computer and Information Science. — 2015. — Vol. 522. — P. 326-335.

63. Morozov, E. A refined stability condition for a queue with equidistant optical buffers / E. Morozov, L. Potakhina, K. De Turck // Distributed Computer and Communication Networks: Control, Computation, Communications (DCC-N-2013). — Moscow: JCS "TECHNOSPHERA", 2013. — P. 456-458.

64. Morozov, E. Stability analysis of an optical system with random delay lines lengths / E. Morozov, L. Potakhina, K. De Turck // Informatics and Applications. — 2014. — Vol. 1, no. 1. — P. 127-134.

65. Morozov, E. Stability analysis and simulation of a state-dependent transmission rate system / E. Morozov, L. Potakhina, A. Rumyantsev // Man-Machine Interactions 4, Advances in Intelligent Systems and Computing 391.— 2015.— DOI: 10.1007/978-3-319-23437-3_57.

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

67. Morozov, E. V. Coupling and monotonicity of queueing processes / E. V. Morozov. — Петрозаводск: Издательство ПетрГУ, 2013. — 72 p.

68. Morozov, E. V. On the estimation of the overflow probability in regenerative

finite buffer queueing systems / E. V. Morozov, R. S. Nekrasova // Informatics and their applications. — 2012. — Vol. 6, no. 3. — P. 391-399. — (in Russian).

69. Müller, A. Comparison Methods for Stochastic Models and Risks / A. Müller, D. Stoyan. — John Wiley & Sons, 2002. — 350 p.

70. Nofal, Z. M. On the class of new better than used of life distributions / Z. M. No-fal //Applied Mathematical Sciences. — 2012. — Vol. 6, no. 137. — P. 6809-6817.

71. Nummelin, E. Regeneration in tandem queues / E. Nummelin // Advances in Applied Probability. — 1981. — Vol. 13. — P. 221-230.

72. Potakhina, L. An application of the inspection paradox to stability analysis of some telecommunication systems / L. Potakhina, E. Morozov, K. De Tur-ck // International workshop "Networking games and management". — 2013. — P. 76-78.

73. Potakhina, L. Inspection paradox: an application to loss and optical queues / L. Potakhina, E. Morozov, K. De Turck // XXXI International Seminar on Stability Problems for Stochastic Models (ISSPSM'2013). — Moscow: IPI RAN, 2013. — P. 52-54.

74. Queues with workload-dependent arrival and service rates / R. Bekker, S. C. Borst, O. J. Boxma, O. Kella // Queueing Systems. — 2004. — Vol. 46.— P. 537-556.

75. R foundation for statistical computing.— ISBN3-900051-07-0. http://www. R-project.org/.

76. Rogiest, W. Stability analysis of a two-stage optical buffer / W. Rogiest, H. Bruneel // Proceedings of ICNAAM 2014. — 2014. — P. 1-4.

77. Scheduling in a random environment: Stability and asymptotic optimality / U. Ayesta, M. Erausquin, M. Jonckheere, I. M. Verloop // IEEE Transactions on Networking. — 2013. — Vol. 21. — P. 258-271.

78. Serfozo, R. Basics of Applied Stochastic Processes / R. Serfozo. — Springer, 2009. — 443 p.

79. Sigman, K. Queues as harris recurrent markov chains / K. Sigman // Queueing Systems. — 1988. — Vol. 3. — P. 179-198.

80. Sigman, K. Regeneration in tandem queues with multiserver stations / K. Sigman // Journal of Applied Probability. — 1988. — Vol. 25, no. 2. — P. 391-403.

81. Sigman, K. A review of regenerative processes / K. Sigman, R. Wolff // Society for Industrial and Applied Mathematics. — 1993. — Vol. 35, no. 2. — P. 269-288.

82. Smith, W. Regenerative stochastic processes / W. Smith // Proc. of the Royal Society. Series A. — 1955. — Vol. 232. — P. 6-31.

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

84. Stability of flow-level scheduling with markovian time-varying channels / J. Kim, B. Kim, J. Kim, Y. Han Bae // Performance Evaluation. — 2013. — Vol. 70.— P. 148-159.

85. Stability of multiwavelength optical buffers with delay-oriented scheduling / E. Morozov, W. Rogiest, K. De Turck, D. Fiems // Transactions on Emerging Telecommunications Technologies. — 2012. — Vol. 23, no. 3. — P. 217-226.

86. Stability of single-wavelength optical buffers / W. Rogiest, E. Morozov, D. Fiems et al. // European Transactions on Telecommunications.— 2010.— Vol. 21, no. 3. — P. 202-212.

87. Tanenbaum, A. S. Computer Networks / A. S. Tanenbaum, D. J. Wetherall. — 5 edition. — Pearson, 2010. — 960 p.

88. Thorisson, H. Coupling, Stationarity, and Regeneration / H. Thorisson. — Springer, 2000. — 517 p.

89. Tikhonenko, O. Computer systems probability analysis / O. Tikhonenko // Akademicka Oficyna Wydawnicza EXIT, Warsaw. — 2006. — (in Polish).

90. Tikhonenko, O. M. The problem of determination of the summarized messages volume in queueing systems and its applications / O. M. Tikhonenko // Journal of Information Processing and Cybernetics. — 1987. — Vol. 32, no. 7. — P. 339-352.

91. Tikhonenko, O. M. Queuing system with processor sharing and limited resources / O. M. Tikhonenko // Automation and Remote Control. — 2010.— Vol. 71, no. 5. — P. 803—815.

92. Tsafrir, D. Modeling user runtime estimates. job scheduling strategies for parallel processing / D. Tsafrir, Y. Etsion, D. G. Feitelson // Lecture Notes in Computer Science. — 2005. — Vol. 3834. — P. 1-35.

93. Whitt, W. Blocking when service is required from several facilities simultaneously / W. Whitt // AT&T Technical Journal.— 1985.— Vol. 64, no. 8.— P. 1807-1856.

94. Wolff, R. W. Stochastic Modeling and the Theory of Queues / R. W. Wolff. — Prentice-Hall, 1989. — 560 p.

95. Wolff, R. W. Losses per cycle in a single-server queue / R. W. Wolff // Journal of Applied Probability. — 2002. — Vol. 39, no. 4. — P. 905-909.

Список иллюстраций

2.1 Динамика процесса BR-загрузки......................................38

2.2 Теряемый объем Vn как интервал, накрывающий порог M..........60

4.1 Динамика процесса W : А — ехр (3), До = 0.333 ....................77

4.2 Динамика процесса W : А — uni f([0, 0.8]), Д0 = 0.267 ............77

4.3 Динамика процесса W : А — Pareto(l, 4), Д0 = 0.75................78

4.4 Динамика процесса W : s(1) — ехр (7), s(2) — ехр (5)....................80

4.5 Динамика процесса W : s(1) — Weibul 1(7, 2), s(2) — Weibul 1(7,1.1). 80

4.6 Динамика процесса W : s(1) — Pareto(4,3.5), s(2) — Par eto(4, 5). . 81

4.7 Зависимость e(X) от p: s(1) — ехр(7), s(2) — ехр(5)..................82

4.8 Зависимость e(X) от p: s(1) — Weibul 1(7, 2), s(2) — Weibul 1(7,1.1). 82

4.9 Зависимость e(X) от p: s(1) — Pareto(4,3.5), s(2) — Pareto(4, 5). . 83

4.10 Зависимость e(X) от p: r(1) = r(2) и s(1), s(2) — ехр(5)..............84

4.11 Динамика процесса W : S — ехр (1)....................................85

4.12 Динамика процесса W : S — Pareto(1, 2)..............................85

4.13 Динамика процесса и: S — ехр(1)......................................86

4.14 Динамика процесса и: S — Pareto(1, 2)................................86

4.15 Динамика процесса и: s — Weibul 1(7, 1.1)..............................88

4.16 Динамика процесса v: s — Weibul 1(7, 1.1)............................88

4.17 Динамика процесса v: s — Pareto(4, 5)................................89

4.18 Динамика процесса и: s — Pareto(4, 5)................................90