В главе 1 излагаются основы классической теории телетрафика,
а в главах 2 и 3 — ее обобщение на мультисервисные модели Эрланга и Энгсета. <...> В главе 4 рассматриваются основы теории открытых и
замкнутых сетей массового обслуживания, а в главе 5 анализируются
модели буферизации в узле коммутации пакетов и фрагмента системы
спутниковой связи. <...> Классические моносервисные модели
Эрланга и Энгсета
§1.1 Первая модель Эрланга . <...> Биномиальное распределение числа занятых линий при 𝑁 6 𝑣. <...> Мультисервисная модель Эрланга
с явными потерями
§2.1 Пример мультиплексирования в АТМ . <...> Мультисервисные модели Энгсета
с явными потерями
§3.1 Две мультисервисные модели Энгсета . <...> Равновесное распределение числа заявок в
узлах сети Джексона. <...> Новые примеры анализа ВВХ
телекоммуникационных систем
215
§7.1 Немного об эволюции мобильных сетей . <...> При этом услуги, предоставляемые
в режиме реального времени (телефонный разговор, телевещание и т.д.) предъявляют гораздо более высокие требования к
качеству обслуживания, включая потери, задержки, джиттер и
другие ВВХ, чем передача данных (электронная почта, обмен
файлами и т.д.) <...> 15
математической ТТ, рассчитанного на широкий круг специалистов, и одновременно хорошим учебным пособием для старшекурсников технических университетов, могут служить вышедшая в 2000 г. книга В.С. Лагутина, С.Н. Степанова «Телетрафик
мультисервисных сетей связи» [12] и размещенное в Интернете
в 2002 г. и постоянно обновляющееся учебно-справочное пособие <...> Основоположником теории телетрафика является датский
ученый А.К. Эрланг (1878–1929 гг.) <...> Поэтому под понятием «телетрафик» понимают теперь не только классические телефонные и телеграфные сообщения, но и потоки сообщений в новых
информационно-вычислительных и телекоммуникационных сетях. <...> В связи с этим автор с 2000 г. читал студентам 1 и 2 курсов магистратуры кафедр «Системы телекоммуникаций» и «Информационные технологии» факультета физикоматематических и естественных <...>
Лекции_по_математической_теории_телетрафика.pdf
Г. П. Башарин
ЛЕКЦИИ
ПО МАТЕМАТИЧЕСКОЙ
ТЕОРИИ ТЕЛЕТРАФИКА
Издание третье, исправленное и дополненное
Рекомендовано
Учебно-методическим советом по прикладной
математике и информатике УМО
по классическому университетскому образованию
в качестве учебного пособия для студентов
высших учебных заведений, обучающихся
по специальности 010200 «Прикладная
математика и информатика» и по направлению
510200 «Прикладная математика
и информатика»
Москва
Российский университет дружбы народов
2009
Стр.1
ББК 22.1
Б 33
Утверждено
РИС Ученого совета
Российского университета
дружбы народов
Р е ц е н з е н т ы:
член-корр. РАН, зав. кафедрой АСВК ф-та ВМК МГУ Л.Н. Королев
д.ф.-м.н., профессор, зам. директора ИПИ РАН С.Я. Шоргин
Башарин Г. П.
Б 33 Лекции по математической теории телетрафика: Учеб.
пособие. Изд. 3-е, испр. и доп. — М.: РУДН, 2009. — 342 с.: ил.
ISBN 978-5-209-03058-4
В основу пособия положен двухсеместровый курс лекций для студентов
магистратуры направления «Прикладная математика и информатика»,
ориентированных на работу в области систем и сетей
телекоммуникаций, а также информационных технологий.
В главе 1 излагаются основы классической теории телетрафика,
а в главах 2 и 3 — ее обобщение на мультисервисные модели Эрланга
и Энгсета. В главе 4 рассматриваются основы теории открытых и
замкнутых сетей массового обслуживания, а в главе 5 анализируются
модели буферизации в узле коммутации пакетов и фрагмента системы
спутниковой связи. В главе 6 кратко изложены основные понятия и
методы управления доступом в мультисервисных сетях связи. В главе
7 предлагается несколько новейших моделей сетей сотовой и оптической
связи. Во всех главах приводятся эффективные алгоритмы расчета
показателей качества обслуживания. Пособие включает также три
справочно-математических и два учебно-методических приложения.
Для студентов, аспирантов, преподавателей ряда смежных специальностей,
а также специалистов исследовательских подразделений в
области телекоммуникационных и компьютерных систем и сетей.
ISBN 978-5-209-03058-4
c
ББК 22.1
○ Башарин Г. П., 2009
c
○ Российский университет дружбы народов, Издательство, 2009.
Стр.2
Оглавление
Предисловие
Список основных сокращений с указанием поясняющих
разделов
Глава 1. Классические моносервисные модели
Эрланга и Энгсета
11
19
23
§1.1 Первая модель Эрланга . . . . . . . . . . . . . . . . 23
1.1.1. Постановка задачи. . . . . . . . . . . . . . . 23
1.1.2. Построение процесса размножения и гибели. 25
1.1.3. Распределение и первая формула Эрланга. 28
§1.2 Нагрузка и ее характеристики . . . . . . . . . . . . 32
1.2.1. Предварительные замечания. . . . . . . . . 32
1.2.2. Определение и виды нагрузки. . . . . . . . 34
1.2.3. Остатистической оценке характеристик нагрузки.
. . . . . . . . . . . . . . . . . . . . . 36
1.2.4. Еще об интенсивности нагрузки. . . . . . . 38
1.2.5. Об измерении нагрузки в сетях с КК и КП 40
1.2.6. О порядке занятия свободных приборов. . . 43
§1.3 Модель Эрланга с ожиданием и блокировками . . 45
1.3.1. Постановка задачи. . . . . . . . . . . . . . . 45
1.3.2. Второе распределение Эрланга. . . . . . . . 46
1.3.3. Оценка интенсивности принятой нагрузки
и вторая формула Эрланга. . . . . . . . . . 52
§1.4 Модель Энгсета . . . . . . . . . . . . . . . . . . . . 54
1.4.1. Описание модели Энгсета. . . . . . . . . . . 54
1.4.2. Построение процесса размножения и гибели. 54
1.4.3. Распределение Энгсета числа занятых линий
для случая N > v. . . . . . . . . . . . . 57
1.4.4. Биномиальное распределение числа занятых
линий при N v. . . . . . . . . . . . . 60
3
Стр.3
1.4.5. Связь между вероятностями блокировок по
времени, по вызовам и по нагрузке. . . . . 63
§1.5 Новая модель Энгсетовского типа . . . . . . . . . . 66
1.5.1. Оптический коммутатор. . . . . . . . . . . . 66
1.5.2. Математическая модель ОК с КП. . . . . . 67
§1.6 Методические комментарии . . . . . . . . . . . . . 72
Глава 2. Мультисервисная модель Эрланга
с явными потерями
75
§2.1 Пример мультиплексирования в АТМ . . . . . . . 75
§2.2 Основные параметры мультисервисной
модели Эрланга . . . . . . . . . . . . . . . . . . . . 77
§2.3 Пространство состояний системы . . . . . . . . . . 79
§2.4 Теорема о равновесном распределении . . . . . . . 82
§2.5 Вероятность потерь и другие
макрохарактеристики . . . . . . . . . . . . . . . . . 87
§2.6 Рекуррентный алгоритм вычисления
макрохарактеристик . . . . . . . . . . . . . . . . . . 89
§2.7 Однородные мультисервисные СМО (b = 1) . . . . 93
§2.8 Методические комментарии . . . . . . . . . . . . . 95
Глава 3. Мультисервисные модели Энгсета
с явными потерями
98
§3.1 Две мультисервисные модели Энгсета . . . . . . . 98
§3.2 Основные предположения и параметры для двух
мультисервисных моделей энгсетовского типа . . . 100
§3.3 Пространство состояний . . . . . . . . . . . . . . . 102
3.3.1. Мультисервисная модель типа Энгсет-1. . . 102
3.3.2. Мультисервисная модель типа Энгсет-2. . . 103
§3.4 Теоремы о равновесном распределении . . . . . . . 104
§3.5 Рекуррентный алгоритм вычисления
макрохарактеристик . . . . . . . . . . . . . . . . . . 107
§3.6 Методические комментарии . . . . . . . . . . . . . 112
4
Стр.4
Глава 4. Сети массового обслуживания
114
§4.1 Немного истории . . . . . . . . . . . . . . . . . . . . 114
§4.2 Описание модели . . . . . . . . . . . . . . . . . . . 117
4.2.1. Узел. . . . . . . . . . . . . . . . . . . . . . . 117
4.2.2. Сеть. . . . . . . . . . . . . . . . . . . . . . . 118
4.2.3. Входящий поток в открытой сети. . . . . . 119
4.2.4. Маршруты заявок. . . . . . . . . . . . . . . 119
§4.3 Открытые однородные экспоненциальные
сети (сети Джексона) . . . . . . . . . . . . . . . . . 122
4.3.1. Параметры сети Джексона. . . . . . . . . . 122
4.3.2. Быстродействие узла и длительность обслуживания.
. . . . . . . . . . . . . . . . . . 124
4.3.3. Условие отсутствия перегрузок в сети. . . . 125
4.3.4. Интенсивность потоков в сети Джексона. . 126
4.3.5. Анализ частот посещения заявкой узлов сети
Джексона. . . . . . . . . . . . . . . . . . . 130
4.3.6. Равновесное распределение числа заявок в
узлах сети Джексона. . . . . . . . . . . . . . 136
§4.4 Замкнутые однородные экспоненциальные сети . . 144
4.4.1. Постановка задачи. . . . . . . . . . . . . . . 144
4.4.2. Равновесное распределение числа заявок в
узлах. . . . . . . . . . . . . . . . . . . . . . . 148
§4.5 Рекуррентные алгоритмы вычисления
характеристик замкнутой сети . . . . . . . . . . . . 152
4.5.1. Свойства нормирующей константы. . . . . . 152
4.5.2. Вычисление нормирующей константы методом
Бузена. . . . . . . . . . . . . . . . . . 156
4.5.3. Характеристики производительности узлов
замкнутой сети. . . . . . . . . . . . . . . . . 161
§4.6 Методические комментарии . . . . . . . . . . . . . 167
Глава 5. Примеры анализа некоторых
телекоммуникационных систем сложной
структуры
169
§5.1 Постановка задачи . . . . . . . . . . . . . . . . . . 169
5
Стр.5
§5.2 Математическая модель буферизации в узле
коммутации пакетов . . . . . . . . . . . . . . . . . . 171
§5.3 Математическая модель фрагмента системы
спутниковой связи . . . . . . . . . . . . . . . . . . . 177
5.3.1. Введение. . . . . . . . . . . . . . . . . . . . . 177
5.3.2. Построение модели фрагмента системы спутниковой
связи. . . . . . . . . . . . . . . . . . 179
5.3.3. Математическая модель фрагмента ССС. . 182
5.3.4. Равновесное распределение дляСМО⟨︀S2,A5⟩︀.183
5.3.5. Вероятности потерь и другие макрохарактеристики.
. . . . . . . . . . . . . . . . . . . 188
§5.4 Методические комментарии . . . . . . . . . . . . . 191
Глава 6. Управление доступом для мультисервисных
СМО
192
§6.1 Стратегии доступа. Основные определения . . . . 193
§6.2 Управление доступом и мультипликативность . . 197
6.2.1. СУГБ. . . . . . . . . . . . . . . . . . . . . . . 197
6.2.2. СУЧБ. . . . . . . . . . . . . . . . . . . . . . 199
§6.3 Координатно-выпуклые стратегии . . . . . . . . . 202
6.3.1. Координатно-выпуклое множество. . . . . . 202
6.3.2. Основные примеры координатно-выпуклых
стратегий. . . . . . . . . . . . . . . . . . . . 203
§6.4 Об оптимизации стратегии доступа . . . . . . . . . 207
6.4.1. Постановка задачи. . . . . . . . . . . . . . . 207
6.4.2. Система с общей памятью и выделенными
приборами. . . . . . . . . . . . . . . . . . . . 208
6.4.3. Система без мест для ожидания. . . . . . . 210
6.4.4. Экстремальный трафик. . . . . . . . . . . . 211
§6.5 Методические комментарии . . . . . . . . . . . . . 213
Глава 7. Новые примеры анализа ВВХ
телекоммуникационных систем
215
§7.1 Немного об эволюции мобильных сетей . . . . . . 215
§7.2 Анализ фрагмента иерархической сети сотовой связи217
6
Стр.6
7.2.1. Введение. . . . . . . . . . . . . . . . . . . . . 217
7.2.2. Модель кластера двухуровневой ССПС. . . 221
7.2.3. Вывод условий мультипликативности. . . . 224
7.2.4. Анализ основных ВВХ. . . . . . . . . . . . . 233
§7.3 Анализ ВВХ микросоты с двумя типами каналов
и учетом мобильности абонентов . . . . . . . . . . 234
7.3.1. Введение. . . . . . . . . . . . . . . . . . . . . 234
7.3.2. Построение математической модели . . . . 234
7.3.3. Вывод СУГБ. . . . . . . . . . . . . . . . . . 236
7.3.4. Вывод одномерных распределений. . . . . . 240
7.3.5. Эквивалентная физическая модель. . . . . 243
7.3.6. Рекуррентный алгоритм. . . . . . . . . . . . 245
7.3.7. Оптимизация числа каналов. . . . . . . . . 246
§7.4 Анализ производительности фрагмента сотовой
сети с учетом перекрытия зон радиосвязи . . . . . 248
7.4.1. Введение. . . . . . . . . . . . . . . . . . . . . 248
7.4.2. Математическая модель. . . . . . . . . . . . 249
7.4.3. Решение СУЛБ. . . . . . . . . . . . . . . . . 255
7.4.4. Параметры производительности системы. . 256
7.4.5. Численный анализ. . . . . . . . . . . . . . . 257
§7.5 Математическая модель оптической сети с маршрутизацией
по длине волны . . . . . . . . . . . . . 260
7.5.1. Введение. . . . . . . . . . . . . . . . . . . . . 260
7.5.2. Сети с маршрутизацией по длине волны. . 261
7.5.3. Задача маршрутизации и назначения длин
волн. . . . . . . . . . . . . . . . . . . . . . . 262
7.5.4. Предположения и обозначения. . . . . . . . 264
7.5.5. Пространство состояний и равновесное распределение.
. . . . . . . . . . . . . . . . . . . 268
7.5.6. Приближенный анализ. . . . . . . . . . . . . 271
§7.6 Итоговые научно-методические комментарии . . . 278
7.6.1. Оптические коммутаторы и оптические сети.278
7.6.2. Об основных направлениях исследований
по ТТ на кафедре СТ. . . . . . . . . . . . . 280
7
Стр.7
Приложение А. Скачкообразные марковские
процессы
284
А.1 Определение и основные характеристики
однородного МП . . . . . . . . . . . . . . . . . . . . 284
А.2 Конструктивное описание скачкообразного МП . . 290
А.3 Система уравнений равновесия и равновесное
распределение для ступенчатого МП . . . . . . . . 292
Приложение Б. Процессы размножения и гибели 296
Б.1 Постановка задачи . . . . . . . . . . . . . . . . . . 296
Б.2 Матрицы A и Q . . . . . . . . . . . . . . . . . . . . 297
Б.3 Локальный баланс и равновесное
распределение . . . . . . . . . . . . . . . . . . . . . 298
Б.4 Процесс чистого размножения . . . . . . . . . . . . 302
Приложение В. Обратимые марковские процессы и
критерий Колмогорова
304
В.1 Определение и свойства обратимого марковского
процесса . . . . . . . . . . . . . . . . . . . . . . . . . 304
В.2 Критерий Колмогорова . . . . . . . . . . . . . . . . 306
В.3 Примеры . . . . . . . . . . . . . . . . . . . . . . . . 307
В.4 Если критерий Колмогорова не выполняется . . . 312
Приложение Г. Практические задания для самостоятельной
работы
315
Приложение Д. Программа экзамена по курсу МТТ
для студентов магистратуры
Вместо заключения
Литература
323
327
336
8
Стр.8