eng
Содержание
Список обозначений и сокращений 7
Введение 10
1.
Системы поллинга. Основные понятия 14
1.1.
Классификация систем поллинга . . . . . . . . . . . . . . . . 14
1.2.
Основная модель поллинга . . . . . . . . . . . . . . . . . . . . 18
1.3.
Стационарный режим в системах поллинга . . . . . . . . . . 20
2.
Методы исследования систем поллинга 22
2.1.
Метод производящих функций . . . . . . . . . . . . . . . . . 22
2.1.1.
Шлюзовое обслуживание очередей . . . . . . . . . . . 23
2.1.2.
Исчерпывающее обслуживание очередей . . . . . . . . 28
2.2.
Метод ветвящихся процессов . . . . . . . . . . . . . . . . . . . 30
2.2.1.
Шлюзовая дисциплина обслуживания очередей . . . 31
2.2.2.
Применение метода ветвящихся процессов к обобщен-
ным моделям . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.3.
Вычисление моментов высших порядков для средних
времен ожидания . . . . . . . . . . . . . . . . . . . . . 38
2.2.4.
Метод ветвящихся процессов для систем в условиях
большой загрузки . . . . . . . . . . . . . . . . . . . . . 39
2.3.
Метод анализа средних . . . . . . . . . . . . . . . . . . . . . . 58
2.3.1.
Системы с исчерпывающим обслуживанием . . . . . . 60
2.3.2.
Системы со шлюзовым обслуживанием . . . . . . . . 63
2.3.3.
Системы со смешанным обслуживанием . . . . . . . . 65
2.3.4.
Системы с мгновенным переключением сервера меж-
ду очередями . . . . . . . . . . . . . . . . . . . . . . . . 66
2.4.
Дискретизация по времени посещения очередей . . . . . . . 66
2.4.1.
Исчерпывающая дисциплина обслуживания . . . . . . 674 Оглавление
2.4.2.
Время обслуживания очереди и время между посеще-
ниями очереди . . . . . . . . . . . . . . . . . . . . . . . 70
2.4.3.
Шлюзовая дисциплина обслуживания . . . . . . . . . 73
2.5.
Обобщенные марковские процессы в системах поллинга . . . 74
2.5.1.
Состояния системы в моменты опроса . . . . . . . . . 78
2.5.2.
Характеристики производительности системы в пере-
ходном режиме . . . . . . . . . . . . . . . . . . . . . . 82
2.5.3.
Стационарные характеристики производительности . 89
2.6.
Полиномиальное представление стационарных вероятностей
состояний системы . . . . . . . . . . . . . . . . . . . . . . . . . 92
2.7.
Законы псевдосохранения в системах поллинга . . . . . . . . 97
3.
Резервирование обслуживания в системах циклического
опроса 109
3.1.
Глобально-шлюзовое обслуживание . . . . . . . . . . . . . . . 110
3.1.1.
Время цикла . . . . . . . . . . . . . . . . . . . . . . . . 111
3.1.2.
Закон псевдосохранения . . . . . . . . . . . . . . . . . 113
3.1.3.
Среднее время ожидания . . . . . . . . . . . . . . . . . 114
3.1.4.
Сравнение со шлюзовым обслуживанием . . . . . . . 116
3.2.
Резервирование с множественным доступом . . . . . . . . . . 118
3.2.1.
Среднее время ожидания . . . . . . . . . . . . . . . . . 119
3.2.2.
Система с отсрочкой обслуживания . . . . . . . . . . 122
3.3.
Оптимальный порядок посещения очередей . . . . . . . . . . 128
3.3.1.
Глобально-шлюзовое обслуживание . . . . . . . . . . . 129
3.3.2.
Резервирование с множественным доступом . . . . . . 131
3.4.
Резервирование в системе с дискретным временем и ограни-
ченным обслуживанием . . . . . . . . . . . . . . . . . . . . . . 132
3.4.1.
Анализ системы с одной очередью . . . . . . . . . . . 134
3.4.2.
Анализ системы с несколькими очередями . . . . . . 138
3.5.
Система поллинга с адаптивным опросом очередей . . . . . 139
3.5.1.
Среднее время цикла и вероятность опроса очереди . 140
3.5.2.
Метод ветвящихся процессов . . . . . . . . . . . . . . 142
3.5.3.
Метод средних . . . . . . . . . . . . . . . . . . . . . . . 145
3.5.4.
Численный пример . . . . . . . . . . . . . . . . . . . . 146
4.
Системы поллинга с пороговыми дисциплинами обслужи-
вания 149
4.1.
Пороговая дисциплина с непрерывным опросом очередей . . 149
4.1.1.
Пороговая шлюзовая дисциплина . . . . . . . . . . . . 151
4.1.2.
Пороговая глобально-шлюзовая дисциплина . . . . . 159Оглавление 5
4.2.
Системы с пороговой исчерпывающей дисциплиной и про-
стоями сервера . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.2.1.
Стационарное распределение состояний системы и ха-
рактеристики производительности . . . . . . . . . . . 165
4.2.2.
Имитационная модель . . . . . . . . . . . . . . . . . . 172
4.3.
Системы поллинга с простоями и пороговой стратегией старта179
4.3.1.
Распределение длин очередей в моменты опроса . . . 181
4.3.2.
Средние времена ожидания . . . . . . . . . . . . . . . 185
4.3.3.
Случай симметричной системы . . . . . . . . . . . . . 191
4.3.4.
Оптимальный порядок посещения очередей . . . . . . 193
5.
Системы циклического опроса с ограниченным обслужива-
нием очередей 195
5.1.
Системы с k-ограниченным обслуживанием . . . . . . . . . . 196
5.1.1.
Метод средних . . . . . . . . . . . . . . . . . . . . . . . 197
5.1.2.
Приближенный метод анализа . . . . . . . . . . . . . . 208
5.1.3.
Полиномиальное представление стационарных веро-
ятностей состояний системы . . . . . . . . . . . . . . . 215
5.1.4.
Оптимизация k-ограниченных дисциплин обслужива-
ния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
5.1.5.
Вероятностно-ограниченное обслуживание очередей . 220
5.2.
Системы с ограниченным по времени обслуживанием очере-
дей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
5.2.1.
Метод производящих функций . . . . . . . . . . . . . 233
5.2.2.
Характеристики производительности . . . . . . . . . . 237
5.2.3.
Условия существования стационарного режима и за-
кон псевдосохранения . . . . . . . . . . . . . . . . . . . 241
6.
Приоритетные системы 244
6.1.
Система MN /GN /1 с абсолютным приоритетом . . . . . . . . 244
6.1.1.
Основная модель приоритетной системы . . . . . . . . 244
6.1.2.
Основные определения и обозначения . . . . . . . . . 246
6.1.3.
Распределение k-циклов переключения и k-циклов
обслуживания . . . . . . . . . . . . . . . . . . . . . . . 247
6.1.4.
Период занятости . . . . . . . . . . . . . . . . . . . . . 249
6.1.5.
Распределение длины очереди . . . . . . . . . . . . . . 253
6.1.6.
О вероятностях состояния сервера . . . . . . . . . . . 257
6.2.
Cистема MN /GN /1 со смешанным приоритетом . . . . . . . 267
6.2.1.
Описание системы. Постановка задачи . . . . . . . . . 267
6.2.2.
Определения, обозначения . . . . . . . . . . . . . . . . 2686 Оглавление
6.2.3.
Период занятости . . . . . . . . . . . . . . . . . . . . . 269
6.2.4.
Распределение длины очереди . . . . . . . . . . . . . . 272
7.
Оценка характеристик широкополосных беспроводных се-
тей с использованием стохастических моделей поллинга 276
7.1.
Состояние и перспективы развития широкополосных беспро-
водных сетей . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
7.2.
Уровень управления доступом к среде семейства протоколов
IEEE 802.11. Распределенная функция координации (DCF) . 281
7.3.
Централизованное управление в широкополосных беспровод-
ных сетях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
7.4.
Проблема ¾скрытых станций¿ в беспроводных широкополос-
ных региональных сетях передачи информации . . . . . . . . 291
7.5.
Адаптивный динамический поллинг в беспроводных сетях . 294
Литература 301
Введение
Конец XX и начало XXI веков ознаменовались бурным количествен-
ным и качественным ростом сетей передачи информации. Эта тенденция,
которая, очевидно, сохранится в ближайшие десятилетия, хорошо иллю-
стрируется беспрецендентным ростом сети Интернет, охватившей все стра-
ны мира. Локальные сети, являющиеся основой автоматизации деятельно-
сти отдельных предприятий и фирм, и распределенные сети, охватываю-
щие города, регионы и континенты, проникли во все сферы человеческой
деятельности, включая экономику, науку, культуру, образование, промыш-
ленность и государственное управление.
Современные сети обеспечивают пользователям широкий набор услуг,
таких, как электронная почта, передача факсимильных и голосовых сооб-
щений, работа с удаленными базами данных в реальном масштабе време-
ни, службы новостей и другие услуги. На базе сетей передачи информа-
ции реализуются: дистанционное обучение, телемедицина, телеконферен-
ции, электронные магазины, каталоги товаров и услуг, поисковые системы,
электронные СМИ и т. д. Быстрый рост числа компьютерных сетей, успе-
хи в развитии проводных и беспроводных средств связи сопровождают-
ся непрерывной сменой сетевых технологий, направленной на повышение
быстродействия и надежности сетей, возможности интегрированной пере-
дачи данных, голоса и видеоинформации.
В последние годы одним из основных направлений развития сетевой
индустрии становятся беспроводные сети передачи информации. Для стран,
в которых большая территория сочетается с невысокой плотностью населе-
ния, широкополосные беспроводные решения имеют особое значение, так
как позволяют экономично и оперативно создавать телекоммуникацион-
ную инфраструктуру на обширных территориях. Особенно важно это для
информатизации удаленных и сельских регионов Российской Федерации
и решения одной из важнейших проблем информационной безопасности
России - проблемы "информационного неравенства" российских регионов.
В ситуации, когда кабельная сеть недостаточно развита (что характерно
для России и многих других стран), применение беспроводной технологии
позволяет в кратчайшие сроки и с небольшими затратами объединить уда-
ленные локальные сети и рабочие станции в единую сеть передачи данных,
обеспечить удаленный стационарный доступ пользователей локальных се-
тей к сети Интернет. Бурное развитие сетей этого класса в России и во
всем мире, о котором часто говорят как о беспроводной революции в об-
ласти сетей передачи информации, потребовало дальнейшей разработки
теоретических основ проектирования беспроводных сетей.
Для оценки характеристик беспроводных сетей широко применяются
стохастические модели поллинга, которые исследовались с конца 50-х го-
дов прошлого века. Систематизация и обобщение теоретических резуль-
татов, полученных в данной области до 1985 г., проведены в монографии
Х. Такаги [88]. Дальнейшее развитие теоретических результатов в этом
направлении, опубликованных до 1995 г., нашло отражение в монографии
С. Борста [29]. Однако быстрое развитие телекоммуникационных систем
и сетей, в частности, систем сотовой связи и широкополосных беспровод-
ных сетей, потребовало разработки новых методов анализа и синтеза си-
стем поллинга. Поэтому в последнее десятилетие появилось значительное
количество работ по системам поллинга в этом направлении. Настоящая
монография посвящена обобщению и систематизации методов исследова-
ния стохастических моделей поллинга и применения их для исследования
широкополосных беспроводных сетей Wi-Fi и Wi-MAX с централизован-
ным механизмом управления. Монография является дальнейшим разви-
тием теоретических основ проектирования компьютерных сетей и может
рассматриваться как второй том книги [3].
Системы поллинга, или системы упорядоченного опроса, являются раз-
новидностью систем массового обслуживания с несколькими очередями
и общим обслуживающим прибором (сервером) или несколькими прибо-
рами. В каждую очередь поступает свой поток заявок. Обслуживающий
прибор по определенному правилу посещает очереди и обслуживает нахо-
дящиеся в них заявки. В самом общем виде системы поллинга сходны с
приоритетными системами массового обслуживания. Однако в приоритет-
ных системах заявки с более высоким приоритетом должны быть обслуже-
ны раньше заявок с низким приоритетом, тогда как в системах поллинга
сервер назначает приоритет очередям по определенному правилу.
Правило, следуя которому сервер выбирает очередь для обслужива-
ния, называется порядком обслуживания. Примерами такого правила мо-
гут служить циклический опрос очередей, когда сервер посещает очере-
ди от первой до последней и вновь возвращается к первой очереди, или
12 Введение
случайный порядок, при котором очередь на обслуживание выбирается
случайно.
Очереди системы поллинга обслуживаются согласно заданной дисци-
плине обслуживания. Она характеризуется числом заявок, которое может
обслужить сервер за одно посещение очереди. Наиболее распространенны-
ми дисциплинами обслуживания очередей являются исчерпывающая дис-
циплина, при которой сервер обслуживает заявки до тех пор, пока очередь
не опустеет, шлюзовая дисциплина, при которой сервер обслуживает лишь
те заявки, которые находились в очереди в момент подключения к ней
сервера, и ограниченная дисциплина, при которой число заявок, которое
может обслужить сервер, ограничено.
В самом общем случае система поллинга полностью описывается чис-
лом очередей и серверов, порядком опроса и дисциплинами обслуживания
очередей, параметрами входных потоков заявок, обслуживания и пере-
ключения сервера между очередями.
Классификация систем поллинга в зависимости от числа очередей и
порядка их опроса сервером, дисциплин обслуживания и других особен-
ностей систем изложена в главе 1. Рассмотрены вопросы существования
стационарного режима в системах поллинга.
В главе 2 изложены основные методы анализа систем циклического
опроса. Данные методы рассмотрены на примере исследования цикличе-
ских систем поллинга с исчерпывающим или шлюзовым обслуживанием.
Отыскивается распределение вложенной цепи Маркова, характеризующей
число заявок в очередях в моменты опроса, что дает возможность найти
среднее время ожидания в системе. Описан закон псевдосохранения для
некоторых систем поллинга, использование которого позволяет вычислить
средние времена пребывания заявки в системе.
В главе 3 рассмотрены схемы резервирования, в соответствии с которы-
ми определяется порядок или число заявок, подлежащих обслуживанию
в текущем или очередном цикле. Представлено исследование схем с ре-
зервированием числа заявок, которые могут быть обслужены в цикле, в
моменты начала цикла (так называемое глобально-шлюзовое обслужива-
ние) или в случайные моменты времени (резервирование с множественным
доступом). Получено правило выбора оптимальной схемы, минимизирую-
щей стоимость ожидания заявок в системе. Рассмотрена система поллинга
с ограниченным обслуживанием, причем число заявок, которое может об-
служить сервер в цикле, определяется длиной очереди в момент, когда
сервер ее покидает в прошлом цикле. Представлено исследование системы
с адаптивным механизмом опроса, при котором в цикле не опрашиваются
очереди, которые были пусты в момент опроса в предыдущем цикле.
Введение 13
В главе 4 рассматриваются модели поллинга, в которых обслуживание
происходит согласно пороговой дисциплине: очередь может быть обслу-
жена, если ее длина превышает заданный порог. Пороговые дисциплины
являются важной разновидностью введения приоритета между очередями
системы. Системы с такими дисциплинами широко используются для мо-
делирования широкополосных беспроводных сетей под управлением про-
токола IEEE 802.11x. Рассмотрены модели с непрерывным опросом очере-
дей и модели, в которых сервер прекращает обход очередей, если в системе
находится недостаточное число сообщений. Исследуется система с простоя-
ми сервера, когда возобновление работы начинается лишь после того, как
в системе накопилось нужное число заявок (так называемый пороговый
старт).
В главе 5 описаны модели с ограниченным обслуживанием очередей,
когда ограничено либо число заявок, которое может обслужить сервер
за одно посещение очереди, либо время пребывания сервера у очереди.
Рассмотрена задача оптимизации дисциплины обслуживания.
В главе 6 кратко рассмотрены приоритетные системы с абсолютным
или смешанным приоритетом и немгновенным переключением сервера меж-
ду потоками заявок разных приоритетов. Такие системы представляют со-
бой системы поллинга с приоритетным опросом. Затронуты вопросы нахо-
ждения распределения периодов занятости сервера обслуживанием заявок
одного приоритета, периода занятости системы, а также длины очереди
для каждого приоритета.
Глава 7 посвящена оценке характеристик широкополосных беспровод-
ных сетей с использованием стохастических моделей поллинга. Основное
внимание уделено моделированию беспроводных радиосетей под управле-
нием протокола централизованного управления PCF (point coordination
function), оценке производительности таких сетей, проведению сравнитель-
ного анализа и оптимальному выбору стратегий динамического опроса.
Авторы приносят благодарность профессору В.В. Рыкову за обсуж-
дение и советы, которые способствовали улучшению содержания книги,
профессорам О. Боксма (технологический университет Эйндховена, Ни-
дерланды), Ю. Ехиали (университет Тель-Авива, Израиль) и Г.К. Миш-
кою (Академия наук Молдовы) за предоставленные материалы по работам
в области систем поллинга и приоритетных систем, а также сотрудникам
лаборатории сетей передачи информации Института проблем передачи ин-
формации им. А.А. Харкевича РАН, участвовавших в подготовке и оформ-
лении рукописи.
ГЛАВА 1
Системы поллинга. Основные
понятия
1.1 Классификация систем поллинга
Системы упорядоченного опроса являются разновидностью систем
массового обслуживания с несколькими очередями и подразделяются на
два класса. Системы первого класса имеют несколько обслуживающих
приборов (серверов), и заявки, поступая в систему, выбирают сервер, на
котором они хотят получить обслуживание. Таким образом, у каждого
сервера образуется своя очередь, и заявки в таких системах являются ак-
тивными, а серверы пассивными. В системах второго класса (системы
поллинга) имеется общий для всех очередей сервер (или несколько серве-
ров), который по определенному правилу обходит очереди и обслуживает
находящиеся в них заявки.
Подходы к классификации систем поллинга описаны в различных ра-
ботах (см., например, [7], [29], [74]). В настоящей главе, следуя [7], при-
водится обобщенный подход к классификации систем поллинга по следу-
ющим критериям: число очередей, порядок опроса очередей, дисциплина
обслуживания очереди.
В зависимости от числа очередей системы поллинга бывают дискрет-
ными (число очередей конечно или счетно) и непрерывными (число оче-
редей или общее число мест для ожидания в системе более чем счетно).
В последнем случае рассматривают системы, в которых заявки распола-
гаются на окружности или в n-мерной области.
В данной книге мы рассматриваем лишь дискретные системы поллинга
с конечным числом очередей. О непрерывных системах поллинга можно
узнать из работ [20, 22, 52, 68, 87].
Классификация систем поллинга 15
Сведения из теории вероятностей, которые могут потребоваться при
чтении данной книги, можно почерпнуть из [3].
Дискретные системы поллинга характеризуются числом очередей, чис-
лом мест для ожидания, числом серверов, процессами поступления и об-
служивания заявок, длительностями переключения сервера между очере-
дями, порядком и дисциплиной обслуживания очередей, и, возможно, дру-
гими параметрами или конфигурацией системы. Предполагаем, что оче-
реди занумерованы от 1 до N, где N – число очередей в системе (N ≥ 2).
Очередь с номером i будем обозначать через Qi, i = 1,N.
Порядком опроса очередей называется правило, следуя которому, сер-
вер выбирает следующую очередь для обслуживания.
Среди видов порядка обслуживания выделяют
1. Циклический порядок: сервер посещает очереди в порядке Q1, Q2,
. . . , QN, Q1, Q2, . . . , QN, . . . . Такие системы поллинга называют
циклическими.
2. Периодический порядок: задается так называемая таблица поллинга
(T(1), T(2), . . . , T (M)) длины M (M ≥ N), T(i) ∈ {1, . . . , N}, i =
1,M. Cервер посещает очереди в порядке QT(1), QT(2), . . . , QT(M),
QT(1), QT(2), . . . , QT(M), . . . . При этом предполагается, что таблица
поллинга содержит номера всех очередей системы.
Частными случаями периодического порядка обхода очередей явля-
ются обход типа "звезда", когда очереди обслуживаются в порядке
Q1, Q2, Q1, Q3, . . . , Q1, QN), и элеваторный порядок обхода очере-
дей, при котором очереди обслуживаются от первой до последней, а
затем от последней очереди до первой.
3. Случайный порядок, при котором с вероятностью pi, i = 1,N, на
обслуживание выбирается очередь Qi, N
i=1 pi = 1. Возможен также
и другой вариант выбора очереди: с вероятностью pij , i, j = 1,N,
после посещения очереди Qi сервер переключается к Qj ,
N
j=1 pij = 1, i = 1,N.
4. Приоритетный порядок, при котором система имеет очереди разных
приоритетов и какая-либо очередь может быть обслужена, если более
приоритетные очереди не содержат заявок.
Описанные в литературе порядки опроса очередей можно условно раз-
делить на статические и динамические. При статическом порядке прави-
ло выбора очередей на обслуживание не меняется в ходе работы системы.
16 Глава 1. Системы поллинга. Основные понятия
Динамический порядок предполагает выбор очереди на обслуживание в
определенные моменты принятия решений на основе полной или частич-
ной информации о состоянии системы (например, обслуживание очередей
в цикле в порядке убывания их длин).
Дисциплиной обслуживания очереди называется число заявок, кото-
рое обслуживает сервер за одно посещение очереди. Внутри очереди заяв-
ки обслуживаются в порядке, определяемом дисциплиной обслуживания
заявок (например, заявки обслуживаются в порядке поступления в оче-
редь).
Среди дисциплин обслуживания очереди (предположим, что это оче-
редь Qi) выделяют
1. Исчерпывающую дисциплину, при которой сервер обслуживает заяв-
ки до тех пор, пока очередь не опустеет.
2. Шлюзовую дисциплину, при которой сервер обслуживает лишь те за-
явки, которые находились в очереди в момент опроса (момент завер-
шения подключения к ней сервера). Заявки, поступившие в очередь
после момента опроса, обслуживаются в следующем цикле. Если сер-
вер обслуживает только те заявки, которые находились в очереди в
момент начала цикла (момент опроса первой очереди), то говорят о
глобально-шлюзовой дисциплине.
3. li-ограниченную дисциплину, при которой число заявок, которое мо-
жет обслужить сервер, ограничено числом li, li ≥ 1. Среди огра-
ниченных дисциплин различают исчерпывающие и шлюзовые. При
ограниченной исчерпывающей дисциплине сервер обслуживает оче-
редь до тех пор, пока не произойдет одно из двух событий: либо будут
обслужены l заявок, либо очередь опустеет. Ограниченная шлюзовая
дисциплина предполагает обслуживание до тех пор, пока либо будут
обслужены l заявок, либо будут обслужены все заявки, которые на-
ходились в очереди в момент ее опроса. Частный случай li = 1 иногда
называют неисчерпывающим обслуживанием.
4. li-уменьшающую дисциплину, при которой сервер обслуживает за-
явки в очереди до тех пор, пока ее длина не станет на li меньше, чем
была в момент подключения сервера, либо пока очередь не опустеет,
li ≥ 1. При li = 1 эту дисциплину также называют полуисчерпываю-
щей.
Классификация систем поллинга 17
5. T-ограниченную дисциплину, при которой время пребывания сервера
у очереди ограничено. Эта дисциплина также может быть шлюзовой
или исчерпывающей.
6. Пороговую дисциплину, при которой сервер обслуживает очередь,
если число заявок в ней не меньше заданной величины (порога).
7. Случайную дисциплину, при которой число заявок, которое может
обслужить сервер, определяется значением дискретной случайной
величины ξi, имеющей закон распределения {ai
j, j ≥ 1}. Закон рас-
пределения может меняться при каждом посещении очереди. Значе-
ние случайной величины ξi разыгрывается при каждом опросе оче-
реди. Отметим некоторые случайные дисциплины:
(a) Биномиальная дисциплина, при которой случайная величина ξi
имеет биномиальное распределение с параметрами Xi и pi, где
Xi – число заявок в очереди Qi в момент опроса, pi – некоторое
число, 0 < pi ≤ 1. Для данной дисциплины aj
i = Cj
Xi
pj
i (1 −
pi)Xi−j , j = 1,Xi, aj
i = 0 для j > Xi;
(b) Дисциплина Бернулли, при которой первая заявка в очереди Qi
обслуживается с вероятностью 1, а каждая последующая – с за-
данной вероятностью pi. С вероятностью 1−pi сервер покидает
очередь. Для данной дисциплины aj
i = pj−1, j ≥ 1.
Если все очереди системы поллинга имеют дисциплины обслуживания
одного вида, будем говорить о системе поллинга с дисциплиной обслу-
живания данного вида (с исчерпывающей, l-ограниченной или другими
дисциплинами обслуживания). Если дисциплины обслуживания очередей
различны, то говорят о системе поллинга со смешанной дисциплиной об-
служивания.
Порядок обхода очередей и дисциплины их обслуживания составляют
политику обслуживания в системе поллинга – это правило выбора следу-
ющей заявки в системе на обслуживание.
Среди систем поллинга различают системы с дискретным временем
(время поделено на равные интервалы, называемые тактами дискретиза-
ции) и системы с непрерывным временем.
Если процессы, характеризующие очереди системы: процессы поступ-
ления и обслуживания заявок, процессы, определяющие длительности пе-
реключения сервера между очередями, и, возможно, другие процессы, со-
ответственно, являются стохастически эквивалентными для всех очередей,
18 Глава 1. Системы поллинга. Основные понятия
то система поллинга называется симметричной, или однородной систе-
мой. В противном случае система называется несимметричной, или неод-
нородной.
Если сервер не затрачивает время на переключение между очередями,
то будем говорить о системе с мгновенным переключением сервера между
очередями, в противном случае – о системе с немгновенным переключени-
ем сервера.
Если не оговорено иное, полагаем, что система поллинга является несим-
метричной, число ее очередей конечно, очереди имеют неограниченное
число мест для ожидания, переключение сервера между очередями нем-
гновенно. Если в очереди нет заявок, то сервер сразу же ее покидает.
Полагаем также, что внутри очереди заявки обслуживаются в порядке
поступления.
Целью большинства исследований систем поллинга является нахожде-
ние среднего времени ожидания в каждой из очередей системы. Однако
не всегда удается получить явные формулы для вычисления этих харак-
теристик, поэтому большое внимание уделяется нахождению приближен-
ных формул, а также уточнению уже полученных приближенных значе-
ний. Иногда задача нахождения средних времен ожидания сводится к на-
хождению взвешенной суммы этих характеристик. Под взвешенной сум-
мой средних времен ожидания понимается выражение
N i=1
ρiM[Wi], где Wi
– случайная величина, характеризующая время ожидания в очереди Qi,
M[Wi] – математическое ожидание, ρi = λibi – загрузка очереди Qi, λi –
интенсивность потока заявок, bi – среднее время обслуживания заявок в
очереди Qi, i = 1,N. Отметим, что согласно формуле Литтла, взвешенная
сумма средних времен ожидания представляет собой среднее количество
работы в системе в произвольный момент времени. Под количеством ра-
боты в некоторый момент времени понимается время, которое затратит
сервер на обслуживание заявок, находящихся в системе в этот момент.
1.2 Основная модель поллинга
Основная модель, которая является объектом исследования большин-
ства работ по системам поллинга, описывается следующим образом. Си-
стема имеет один сервер и N (N ≥ 2) очередей с неограниченным числом
мест для ожидания.
В i-ю очередь поступает стационарный пуассоновский поток заявок
с параметром λi. Времена обслуживания заявок в очереди Qi независи-
мы и одинаково распределены с функцией распределения Bi(t) со сред-
Основная модель поллинга 19
ним bi = ∞ 0
tdBi(t), вторым моментом b(2)
i и преобразованием Лапласа-
Стилтьеса (ПЛС) ˜Bi(x), i = 1,N. Полагаем, что потоки заявок и времена
обслуживания заявок независимы.
Следуя классификации Кендалла, такую систему называют системой
поллинга с очередями типа M/GI/1. Если времена обслуживания заявок
распределены экспоненциально или потоки заявок в очереди являются ре-
куррентными, то говорят о системах поллинга с очередями типа M/M/1
или G/G/1, соответственно.
Сервер посещает очереди, следуя определенному порядку опроса оче-
редей и обслуживая их в соответствии с выбранной дисциплиной. Время
подключения к очереди Qi, называемое временем переключения, имеет
функцию распределения Si(t) со средним si, вторым моментом s(2)
i и ПЛС
˜ Si(x), i, j = 1,N.
Обозначим через ρi = λibi загрузку очереди Qi, через ρ = N
i=1 ρi –
загрузку системы. Для систем с циклическим или периодическим опро-
сом очередей обозначим также через s и s(2) первый и второй моменты
совокупной длительности переключений сервера за один цикл,
s =
N
j=1
sj, s(2) = s2 +
N
j=1
(s(2)
j − s2j).
Будем говорить, что система массового обслуживания соответствует
i-й очереди системы поллинга, если поток заявок в эту систему являет-
ся стационарным пуассоновским с параметром λi, а время обслуживания
заявок имеет функцию распределения Bi(t). Система массового обслужи-
вания соответствует системе поллинга, если поток заявок в эту систему
является стационарным пуассоновским с параметром λ = N
i=1 λi, а время
обслуживания заявок имеет функцию распределения B(t) = N
i=1
λi
λ Bi(t).
Под моментом опроса (поллинга) понимается момент времени, когда
сервер принимает решение о том, сколько заявок в очереди он будет об-
служивать при этом посещении. Обычно за момент опроса принимается
момент, когда сервер завершил переключение к очереди и готов начать
ее обслуживание. Моментом опроса также иногда считают момент, когда
становится доступной информация о числе заявок в очереди.
Для систем поллинга с циклическим или периодическим опросом оче-
редей выделяют периоды времени, называемые циклами. Для цикличе-
ских систем – это время, затрачиваемое на опрос очередей от Q1 до QN.
Для систем с периодическим опросом – время, затрачиваемое на опрос
20 Глава 1. Системы поллинга. Основные понятия
очередей от QT(1) до QT(M). В работе некоторых систем поллинга выделя-
ют гамильтонов цикл – это время, за которое сервер посетит все очереди
системы, причем ровно один раз. При элеваторном опросе выделяют восхо-
дящий (опрос очередей от первой до последней) и нисходящий цикл (опрос
от последней до первой очереди).
Для систем с циклическим опросом и шлюзовым или исчерпывающим
обслуживанием среднее время цикла складывается из времени, когда сер-
вер обслуживает очереди (на это он тратит долю времени ρ), и время,
когда он переключается между очередями (на это он тратит в среднем
время s за цикл). Таким образом,
C = ρC + s,
отсюда получаем
C = s
1 − ρ
.
1.3 Стационарный режим в системах поллинга
Говорят, что в системе поллинга существует стационарный режим, если
длины всех очередей в моменты опроса имеют стационарное распределе-
ние и длина цикла имеет конечное математическое ожидание.
Для систем с циклическим опросом необходимые и достаточные усло-
вия существования стационарного режима имеют следующий вид:
• ρ < 1 для систем с исчерпывающим и шлюзовым обслуживанием
очередей;
• для ki-ограниченной дисциплины обслуживания –
ρ < 1 и λi <
ki(1 − ρi)
s
, i= 1,N.
При 1-ограниченном обслуживании эти условия принимают вид
ρ + λis < 1, i= 1,N.
• для системы с 1-уменьшающим обслуживанием –
ρ + λi(1 − ρi)s < 1, i= 1,N.
Стационарный режим 21
Необходимые и достаточные условия существования стационарного ре-
жима для систем с общими дисциплинами обслуживания и периодиче-
ским опросом очередей получено в работе [57]. В ней предложено опи-
сывать дисциплину обслуживания очереди тройкой случайных величин
(f(x), v(x), ϕ(x)), где x – число заявок в очереди в момент опроса, f(x) –
число заявок, которое будет обслужено при данном посещении очереди,
v(x) – длительность посещения очереди сервером, ϕ(x) – число заявок,
которое остается в очереди по завершении ее обслуживания. Необходимое
и достаточное условие существования стационарного режима в системах
поллинга имеет вид
ρ + λis/G∗i < 1, i= 1,N,
где G∗i – среднее максимальное число заявок, которые могут быть обслу-
жены в i-й очереди за один цикл. При этом дисциплина обслуживания
очередей должна удовлетворять следующим условиям:
• Дисциплина обслуживания не зависит от предыстории процесса об-
служивания, например, от числа обслуженных заявок или времени
их обслуживания.
• Выбор заявок на обслуживание не зависит от времени обслуживания
или возможных поступлений заявок в будущем.
• Очередь получает обслуживание с положительной вероятностью, ес-
ли в ней накопилось требуемое число заявок. Сервер, обращенный к
очереди, не простаивает (непрерывно обслуживает заявки). Если в
очереди нет заявок, он немедленно покидает ее.
• Дисциплина обслуживания (f(x), v(x), ϕ(x)) является стохастически
монотонной. Определение стохастической монотонности для случай-
ных векторов, называемой также монотонностью по распределению,
можно найти в работах [57, 86].
ГЛАВА 2
Методы исследования систем
поллинга
В главе изложены основные методы анализа систем циклического опро-
са. Данные методы рассмотрены на примере исследования циклических
систем поллинга с исчерпывающим или шлюзовым обслуживанием. Отыс-
кивается распределение цепи Маркова, характеризующей число заявок в
очередях в определенные моменты времени, вычисляется среднее число
заявок в очередях, что дает возможность найти время ожидания в систе-
ме. Рассмотрены свойства стохастического разложения времени занятости
сервера, а также закон псевдосохранения для некоторых систем поллинга,
использование которого позволяет вычислить средние времена пребыва-
ния сообщения в системе.
2.1 Метод производящих функций
Метод производящих функций широко используется для нахождения
распределения числа заявок в системе поллинга в моменты опроса очере-
дей. Рассмотрим его применение на примере системы поллинга с цикли-
ческим опросом и исчерпывающим или шлюзовым обслуживанием очере-
дей. Метод подробно описан в работе [99], где дополнительно изложены
основные методы и результаты исследования циклических систем с исчер-
пывающим, шлюзовым и глобально-шлюзовым обслуживанием очередей,
а также некоторых систем с нециклическим порядком обхода очередей.
Метод производящих функций 23
2.1.1 Шлюзовое обслуживание очередей
Рассмотрим основную систему поллинга, описанную в разделе 6.1.1, со
шлюзовым обслуживанием. Предположим, что система функционирует в
стационарном режиме. Обозначим через Xj
i число заявок в очереди Qj в
произвольный момент опроса очереди Qi, i, j = 1,N.
Обозначим также через Ai(T) – число заявок, поступивших в i-ю оче-
редь за время T (детерминированное или случайное), Bik – время обслу-
живания k-й заявки в i-й очереди, Si – время переключения сервера к i-й
очереди, i = 1,N.
При шлюзовом обслуживании очередей случайные величины Xj
i , i, j =
1,N, связаны между собой следующим образом:
Xj
i+1 =⎧⎨⎩
Xj
i + Aj Xi
i
k=1 Bik + Si+1 , j = i,
Ai Xi
i
k=1 Bik + Si+1 , j= i.
(2.1)
Отметим, что времена обслуживания заявок Bik, k = 1,Xi
i , независимы и
одинаково распределены с функцией распределения Bi(t), i = 1,N.
Пусть pi(r1, r2, . . . , rN) – стационарная вероятность того, что в произ-
вольный момент опроса i-й очереди j-я очередь содержит rj заявок, rj ≥ 0,
i, j = 1,N. Введем производящие функциии этих вероятностей
Gi(z) = Gi(z1, z2, · · · , zN) =
∞ r1=0
∞ r2=0
· · ·
∞ rN=0
pi(r1, r2, . . . , rN)zr1
1 · · · zrN
N .
Они также могут быть представлены как
Gi(z) = M⎡⎣
N
j=1
z
Xj
i
j⎤⎦
, i= 1,N,
где, напомним, M – математическое ожидание.
С помощью равенств (2.1) получаем
Gi+1(z) = M⎡⎣
N
j=1
z
Xj
i+1
j ⎤⎦
= MXi ⎡⎢⎢⎣
N
j=1
j =i
z
Xj
i
j M⎡⎣
N
j=1
z
Aj Xi
i
k=1 Bik
j Xi⎤⎦
⎤⎥⎥⎦
×
(2.2)
×M⎡⎣
N
j=1
zAj (Si+1)
j ⎤⎦
,
24 Глава 2. Методы исследования систем поллинга
где Xi = (X1
i ,X2
i , . . . , XN
i ),M[ · |Xi] – условное математическое ожидание.
Математическое ожидание случайной величины zAj (T)
j , где T – случай-
ная величина с функцией распределения D(T), определяется следующим
образом:
M zAj (T)
j = ∞
0
M zAj (t)
j dD(t) = ∞
0
∞ k=0
P(Aj(t) = k)zk
j dD(t) =
(2.3)
= ∞
0
∞ k=0
(λjt)k
k! e−λj tzk
j dD(t) = ∞
0
eλj t(1−zj ) dD(t) =
= ˜D(λj(1 − zj)),
где ˜D(w) – ПЛС функции распределения D(t).
Соответственно,
M⎡⎣
N
j=1
zAj (T)
j ⎤⎦
= ˜D
⎛⎝
N
j=1
λj(1 − zj)⎞⎠
.
Таким образом, из равенств (2.2)–(2.3) получаем соотношения для про-
изводящих функций Gi(z), i = 1,N,
Gi+1(z) = Gi⎛ ⎝z1, z2, . . . , zi−1, ˜Bi⎡⎣
N
j=1
λj(1 − zj)⎤⎦, zi+1, . . . , zN⎞⎠
× (2.4)
ט Si+1⎡⎣
N
j=1
λj(1 − zj)⎤⎦
, i= 1,N.
В (2.4) полагаем, что GN+1(z) = G1(z).
Среднее число заявок fi(j) = M[Xj
i ] в очереди Qj в опроса очереди Qi
определяется как
fi(j) = M(Xj
i ) = ∂Gi(z)
∂zj z=1
,
где 1 = (1, 1, . . . , 1).
Дифференцированием равенств (2.4) в точке z = 1 можно получить
систему уравнений для величин fi(j), i, j = 1,N. Запишем вначале урав-
нение для fi+1(j) при j = i. Обозначим через ν =
N j=1
λj(1 − zj), тогда из
Метод производящих функций 25
(2.4) имеем
fi+1(j) = d
dzj
Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN z=1
˜ Si+1(0)+
+Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN d
dzj
˜ Si+1(ν) z=1.
Далее,
fi+1(j) = ∂
∂zj
Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN + (2.5)
+ ∂
∂˜Bi
Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN d˜Bi(ν)
dν
∂ν
∂zj z=1
˜ Si+1(0)+
+Gi+1 z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN d ˜ Si+1(ν)
dν
∂ν
∂zj z=1
.
Заметим, что при z = 1: Gi(1) = 1, v(1) = 0, а ˜Bi(0) = ˜ Si(0) = 1. Также
d˜Bi(ν)
dν v=0
= − ∞
0
te−νtdBi(t) = −bi,
∂ν
∂zi z=1
= −λi, i= 1,N.
Тогда, с помощью последних равенств, соотношение (2.5) принимает
вид уравнения
fi+1(j) = fi(j) + λjbifi(i) + λjsi+1, j = i.
Cлучай i = j рассматривается аналогично.
Таким образом, получаем систему уравнений для средних длин очере-
дей системы в моменты опроса
fi+1(j) = fi(j) + λjbifi(i) + λjsi+1, j = i,
fi+1(i) = λibifi(i) + λisi+1, i= 1,N.
Решение этой системы может быть получено явно и имеет вид
fi(j) =⎧⎨⎩
λj i−1
k=j ρk
s
1−ρ + sk+1 , j = i,
λi
s
1−ρ, j= i.
Вторые моменты случайных величин Xj
i , i, j = 1,N, также могут быть
получены дифференцированием производящих функций Gi(z), i = 1,N,
fi(j, k) = M[Xj
i Xk
i ] = ∂2Gi(z)
∂zj∂zk z=1
,
fi(i, i) = M[Xi
i (Xi
i − 1)] = ∂2Gi(z)
∂z2
i z=1
.
26 Глава 2. Методы исследования систем поллинга
Система уравнений для вычисления fi(j, k), i, j, k = 1,N, имеет вид
fi+1(j, k) = λjλks(2)
i+1 + si+1λkfi(j) + si+1λjfi(k)+
+ fi(i)λjλk 2bisi+1
1 − ρi
+ b(2)
i
(1 − ρi)3 + bi
1 − ρi
(fi(i, i)λk + fi(i, k)λj)+
+ fi(j, k) + fi(i, i)λjλk bi
1 − ρi 2
, i = j, i = k,
fi+1(i, j) = λiλjs(2)
i+1 + si+1λi fi(j) + fi(i)λjbi
1 − ρi , i = j,
fi+1(i, i) = λ2i
s(2)
i+1, i, j, k = 1,N.
Метод производящих функций в некоторых случаях позволяет най-
ти ПЛС времени ожидания в очереди. Пусть Li – число заявок, которые
остаются в i-й очереди в момент ухода из нее заявки, i = 1,N. Обозначим
также через
¯L
i(z) = M[zLi] =
∞ k=0
Pi(k)zk
производящую функцию случайной величины Li, где Pi(k) – вероятность
того, что Li = k, k ≥ 0. Для рассматриваемой системы поллинга справед-
лив закон стационарной очереди Хинчина: стационарное распределение
числа заявок в системе в произвольный момент времени совпадает со ста-
ционарным распределением числа заявок в системе в моменты завершения
обслуживания. Следовательно, Li(z) представляет собой производящую
функцию числа заявок в i-й очереди в произвольный момент времени.
Пусть Ti – общее число заявок, обслуженных в i-й очереди за одно
посещение сервера, а Li(n), n = 1, Ti – последовательность случайных
величин, означающих число заявок в очереди непосредственно после n-
го момента завершения обслуживания в i-й очереди. Тогда производящая
функция случайной величины Li удовлетворяет равенству
¯L
i(z) =
M Ti
n=1 zLi(n) M[Ti] . (2.6)
Метод производящих функций 27
Поскольку Li(n) = Xi
i − n + A( n
k=1 Bik), равенство (2.6) принимает вид
¯L
i(z) =
1
M[Ti]
M⎡⎣
Ti n=1
z
Xi
i−n+A n k=1
Bik ⎤⎦ =
1
M[Ti]
M⎡ ⎣zXi
i
Ti n=1
z−n+A n k=1
Bik ⎤⎦ =
=
1
M[Ti]
M⎡ ⎣zXi
i
Ti n=1
z−ne−λ n k=1
Bik (1−z)⎤⎦
=
=
1
M[Ti]
M zXi
i
Ti n=1 ˜Bi(λi(1 − z))
z n =
=
1
M[Ti]
M⎡⎢⎣
zXi
i
˜B
i(λi(1 − z))
z
1 − ˜Bi(λi(1−z))
z Ti
1 −
˜B
i(λi(1−z))
z
⎤⎥⎦
.
Таким образом, получаем
¯L
i(z) =
˜B
i(λi(1 − z))
M[Ti](z − ˜Bi(λi(1 − z)))
M zXi
i−Ti(zTi−[˜Bi(λi(1−z))]Ti) .
Рассмотрим теперь распределение времени ожидания в i-й очереди.
Поскольку заявки, которые остаются в ней в момент завершения обслу-
живания, поступили за время пребывания (время ожидания плюс время
обслуживания) обслуженной заявки, то
¯L
i(z) =
∞ k=0
Pi(k)zk =
∞ k=0
zk ∞
0
e−λiw (λiw)k
k! dP (Wi ≤ w) =
= ˜Wi(λi(1 − z))˜Bi(λi(1 − z)),
откуда
˜W
i(w) =
¯L
i(1 − w/λi)
˜B
i(w)
. (2.7)
Для шлюзового обслуживания Xi
i = Ti, следовательно, [88],
¯L
i(z) =
˜B
i(λi(1 − z))
M[Ti] z − ˜Bi(λi(1 − z)) M zXi
i −M (˜Bi(λi(1 − z)))Xi
i .
(2.8)
28 Глава 2. Методы исследования систем поллинга
Среднее время ожидания в i-й очереди находится с помощью ПЛС
распределения времени ожидания как
M[Wi] = −
d
dw
˜W
i(w) w=0. (2.9)
Поскольку M[Ti] = M[Xi
i] = λiC, то с помощью (2.7) и (2.8), получаем
следующую формулу:
M[Wi] =
M[(Xi
i )2] −M[Xi
i ]
2λiM[Xi
i ]
(1 + ρi) =
(1 + ρi)fi(i, i)
2λ2i
C
, i= 1,N. (2.10)
2.1.2 Исчерпывающее обслуживание очередей
Рассмотрим теперь систему с исчерпывающим обслуживанием очере-
дей. Cлучайные величины Xj
i , i, j = 1,N, связаны между собой следую-
щим образом:
Xj
i+1 =⎧⎨⎩
Xj
i + Aj Xi
i
k=1 Θik + Si+1 , j = i,
Ai(Si+1), j= i,
(2.11)
где Θik – длительность периода занятости сервера в i-й очереди, порож-
денного k-й заявкой. Величины Θik независимы и одинаково распределе-
ны с ПЛС функции распределения ˜θi(w), которое находится как решение
функционального уравнения
˜θi(w) = ˜Bi(w + λi − λi ˜θi(w)).
Средняя длительность периода занятости сервера в i-й очереди определя-
ется как
θi = −˜θ (0) = bi
1 − ρi
.
Метод производящих функций 29
Как это сделано для шлюзового обслуживания, из равенств (2.11) по-
лучаем выражение для производящих функций Gi(z), i = 1,N,
Gi+1(z) = M⎡⎣
N
j=1
z
Xj
i+1
j ⎤⎦
= (2.12)
= M⎡⎢⎢⎣
N
j=1
j =i
z
Xj
i
j M⎡⎢⎢⎣
N
j=1
j =i
z
Aj Xi
i
k=1 Θik
j Xi⎤⎥⎥⎦
⎤⎥⎥⎦
M⎡⎢⎢⎣
N
j=1
j =i
zAj (Si+1)
j ⎤⎥⎥⎦
=
= Gi⎛⎜⎜⎝
z1, . . . , zi−1, ˜θi⎡⎢⎢⎣
N
j=1
j =i
λj(1 − zj)⎤⎥⎥⎦
, zi+1, . . . , zN⎞⎟⎟⎠
˜ Si+1⎡⎣
N
j=1
λj(1 − zj)⎤⎦
.
Система уравнений для средних длин очередей Xj
i , i, j = 1,N, состав-
ляется дифференцированием равенств (2.12) и имеет вид
fi+1(j) = fi(j) + λj
bi
1 − ρi
fi(i) + λjsi+1, j = i,
fi+1(i) = λisi+1, i= 1,N.
Ее решение может быть получено явно,
fi(j) =⎧⎨⎩
λj i−1
k=j+1 ρk
s
1−ρ + i−1
k=j sk+1 , j = i,
λi(1 − ρi) s
1−ρ, j= i.
(2.13)
Перейдем теперь к нахождению среднего времени ожидания в i-й оче-
реди. Используем те же рассуждения, что и в предыдущем разделе. При
исчерпывающем обслуживании среднее число заявок, обслуженных за од-
но посещение сервером очереди, есть величина
Ti = Xi
i + Ai⎛⎝
Xi
i k=1
Θik⎞⎠
,
таким образом,
M[Ti] = fi(i) + λifi(i)θi = fi(i)
1 − ρi
,
откуда с помощью (2.13) получаем, что M[Ti] = λiC, i = 1,N.
30 Глава 2. Методы исследования систем поллинга
Производящая фукнция числа заявок в i-й очереди в произвольный
момент времени определяется равенством, [88],
¯L
i =
1
λiC
˜B
i(λi(1 − z))
z − ˜Bi(λi(1 − z)) M zXi
i − 1 . (2.14)
Среднее число заявок в i-й очереди и среднее время ожидания в ней
находятся с помощью равенств (2.7), (2.9) и (2.14),
M[Li] = ρi + λ2i
b(2)
i
2(1 − ρi)
+ fi(i, i)
2λi(1 − ρi)C
,
M[Wi] = λib(2)
i
2(1 − ρi)
+ fi(i, i)
2λ2i
(1 − ρi)C
, i= 1,N. (2.15)
Величины fi(i, i), i = 1,N, могут быть вычислены как решение си-
стемы линейных уравнений, которая составляется дифференцированием
равенств (2.12).
2.2 Метод ветвящихся процессов
Метод ветвящихся процессов (иначе его называют методом потомков)
основан на вычислении числа потомков, которые порождаются в систе-
ме каждой заявкой. В данном разделе показано применение этого метода
для систем поллинга с фиксированным (циклическим или периодическим)
опросом очередей и шлюзовым или исчерпывающим обслуживанием, [67].
Этот метод предназначен для вычисления моментов времен ожидания.
Основные его преимущества состоят в следующем:
1. Среднее время ожидания в очереди вычисляется независимо от вре-
мен ожидания в других очередях. Поэтому метод предпочтителен,
если нет необходимости вычислять средние времена ожидания во
всех очередях, например, в системах с большим числом очередей со
сходными параметрами.
2. Метод может быть применен для анализа систем, которые могут
быть исследованы методом производящих функций (см. раздел 2.1).
3. Результаты, получаемые с помощью данного метода, создают пред-
посылки для оптимизации параметров системы.
Метод ветвящихся процессов 31
Рассмотрим систему с циклическим опросом, описанную в разделе 6.1.1.
Отнесем каждую заявку, поступающую в систему, к первичным заявкам,
если она поступила в момент, когда сервер не обслуживал заявки, или ко
вторичным заявкам, если она поступила в момент, когда сервер был занят
обслуживанием.
Пусть K – некоторая заявка. Тогда множеством сыновей заявки K
назовем множество заявок, поступивших за время ее обслуживания. Мно-
жеством потомков заявки K назовем множество, состоящее из K, ее
сыновей и потомков ее сыновей. Будем говорить, что заявка K принадле-
жит K, если K является потомком K.
Метод основан на том, что каждая заявка, присутствовавшая в оче-
реди Q1 в момент ее опроса, принадлежит лишь одной первичной заявке.
Рассматривается произвольная первичная заявка Ki, поступившая ранее в
очередь Qi, и вычисляется число ее потомков, находящихся в Q1 в момент
опроса этой очереди. Суммируя число потомков для каждой первичной за-
явки, находящейся в системе, получаем число заявок X1
1 в Q1 в момент ее
опроса (в этом смысле данный метод схож с нахождением распределения
длин очередей в моменты поллинга методом производящих функций).
Моментом наблюдения будем называть момент опроса очереди Q1.
Пусть Ri,0 – период обслуживания i-й очереди в цикле, предшествующем
моменту наблюдения, Ri,n – период обслуживания i-й очереди n+1 циклов
назад от момента наблюдения. Пусть также Ci,n – множество заявок, под-
лежащих обслуживанию в периоде обслуживания Ri,n, Li,n – случайная
величина, обозначающая число заявок в Q1, которые являются потомка-
ми Ci,n и присутствуют в Q1 в момент наблюдения. Величину Li,c также
можно интерпретировать как вклад заявок Ci,n в длину X1
1 очереди Q1
в момент наблюдения. Обозначим через Li,n(z) производящую функцию
для Li,n, Li,n(z) = M#zLi,n$. Введем также первые три момента случайной
величины Li,n: αi,n = M[Li,n], α(2)
i,n = M#(Li,n)2$ и α(3)
i,n = M[(Li,n)3].
Конец XX и начало XXI веков ознаменовались бурным количествен-
ным и качественным ростом сетей передачи информации. Эта тенденция,
которая, очевидно, сохранится в ближайшие десятилетия, хорошо иллю-
стрируется беспрецендентным ростом сети Интернет, охватившей все стра-
ны мира. Локальные сети, являющиеся основой автоматизации деятельно-
сти отдельных предприятий и фирм, и распределенные сети, охватываю-
щие города, регионы и континенты, проникли во все сферы человеческой
деятельности, включая экономику, науку, культуру, образование, промыш-
ленность и государственное управление.
Современные сети обеспечивают пользователям широкий набор услуг,
таких, как электронная почта, передача факсимильных и голосовых сооб-
щений, работа с удаленными базами данных в реальном масштабе време-
ни, службы новостей и другие услуги. На базе сетей передачи информа-
ции реализуются: дистанционное обучение, телемедицина, телеконферен-
ции, электронные магазины, каталоги товаров и услуг, поисковые системы,
электронные СМИ и т. д. Быстрый рост числа компьютерных сетей, успе-
хи в развитии проводных и беспроводных средств связи сопровождают-
ся непрерывной сменой сетевых технологий, направленной на повышение
быстродействия и надежности сетей, возможности интегрированной пере-
дачи данных, голоса и видеоинформации.
В последние годы одним из основных направлений развития сетевой
индустрии становятся беспроводные сети передачи информации. Для стран,
в которых большая территория сочетается с невысокой плотностью населе-
ния, широкополосные беспроводные решения имеют особое значение, так
как позволяют экономично и оперативно создавать телекоммуникацион-
ную инфраструктуру на обширных территориях. Особенно важно это для
информатизации удаленных и сельских регионов Российской Федерации
и решения одной из важнейших проблем информационной безопасности
России - проблемы "информационного неравенства" российских регионов.
В ситуации, когда кабельная сеть недостаточно развита (что характерно
для России и многих других стран), применение беспроводной технологии
позволяет в кратчайшие сроки и с небольшими затратами объединить уда-
ленные локальные сети и рабочие станции в единую сеть передачи данных,
обеспечить удаленный стационарный доступ пользователей локальных се-
тей к сети Интернет. Бурное развитие сетей этого класса в России и во
всем мире, о котором часто говорят как о беспроводной революции в об-
ласти сетей передачи информации, потребовало дальнейшей разработки
теоретических основ проектирования беспроводных сетей.
Для оценки характеристик беспроводных сетей широко применяются
стохастические модели поллинга, которые исследовались с конца 50-х го-
дов прошлого века. Систематизация и обобщение теоретических резуль-
татов, полученных в данной области до 1985 г., проведены в монографии
Х. Такаги [88]. Дальнейшее развитие теоретических результатов в этом
направлении, опубликованных до 1995 г., нашло отражение в монографии
С. Борста [29]. Однако быстрое развитие телекоммуникационных систем
и сетей, в частности, систем сотовой связи и широкополосных беспровод-
ных сетей, потребовало разработки новых методов анализа и синтеза си-
стем поллинга. Поэтому в последнее десятилетие появилось значительное
количество работ по системам поллинга в этом направлении. Настоящая
монография посвящена обобщению и систематизации методов исследова-
ния стохастических моделей поллинга и применения их для исследования
широкополосных беспроводных сетей Wi-Fi и Wi-MAX с централизован-
ным механизмом управления. Монография является дальнейшим разви-
тием теоретических основ проектирования компьютерных сетей и может
рассматриваться как второй том книги [3].
Системы поллинга, или системы упорядоченного опроса, являются раз-
новидностью систем массового обслуживания с несколькими очередями
и общим обслуживающим прибором (сервером) или несколькими прибо-
рами. В каждую очередь поступает свой поток заявок. Обслуживающий
прибор по определенному правилу посещает очереди и обслуживает нахо-
дящиеся в них заявки. В самом общем виде системы поллинга сходны с
приоритетными системами массового обслуживания. Однако в приоритет-
ных системах заявки с более высоким приоритетом должны быть обслуже-
ны раньше заявок с низким приоритетом, тогда как в системах поллинга
сервер назначает приоритет очередям по определенному правилу.
Правило, следуя которому сервер выбирает очередь для обслужива-
ния, называется порядком обслуживания. Примерами такого правила мо-
гут служить циклический опрос очередей, когда сервер посещает очере-
ди от первой до последней и вновь возвращается к первой очереди, или
12 Введение
случайный порядок, при котором очередь на обслуживание выбирается
случайно.
Очереди системы поллинга обслуживаются согласно заданной дисци-
плине обслуживания. Она характеризуется числом заявок, которое может
обслужить сервер за одно посещение очереди. Наиболее распространенны-
ми дисциплинами обслуживания очередей являются исчерпывающая дис-
циплина, при которой сервер обслуживает заявки до тех пор, пока очередь
не опустеет, шлюзовая дисциплина, при которой сервер обслуживает лишь
те заявки, которые находились в очереди в момент подключения к ней
сервера, и ограниченная дисциплина, при которой число заявок, которое
может обслужить сервер, ограничено.
В самом общем случае система поллинга полностью описывается чис-
лом очередей и серверов, порядком опроса и дисциплинами обслуживания
очередей, параметрами входных потоков заявок, обслуживания и пере-
ключения сервера между очередями.
Классификация систем поллинга в зависимости от числа очередей и
порядка их опроса сервером, дисциплин обслуживания и других особен-
ностей систем изложена в главе 1. Рассмотрены вопросы существования
стационарного режима в системах поллинга.
В главе 2 изложены основные методы анализа систем циклического
опроса. Данные методы рассмотрены на примере исследования цикличе-
ских систем поллинга с исчерпывающим или шлюзовым обслуживанием.
Отыскивается распределение вложенной цепи Маркова, характеризующей
число заявок в очередях в моменты опроса, что дает возможность найти
среднее время ожидания в системе. Описан закон псевдосохранения для
некоторых систем поллинга, использование которого позволяет вычислить
средние времена пребывания заявки в системе.
В главе 3 рассмотрены схемы резервирования, в соответствии с которы-
ми определяется порядок или число заявок, подлежащих обслуживанию
в текущем или очередном цикле. Представлено исследование схем с ре-
зервированием числа заявок, которые могут быть обслужены в цикле, в
моменты начала цикла (так называемое глобально-шлюзовое обслужива-
ние) или в случайные моменты времени (резервирование с множественным
доступом). Получено правило выбора оптимальной схемы, минимизирую-
щей стоимость ожидания заявок в системе. Рассмотрена система поллинга
с ограниченным обслуживанием, причем число заявок, которое может об-
служить сервер в цикле, определяется длиной очереди в момент, когда
сервер ее покидает в прошлом цикле. Представлено исследование системы
с адаптивным механизмом опроса, при котором в цикле не опрашиваются
очереди, которые были пусты в момент опроса в предыдущем цикле.
Введение 13
В главе 4 рассматриваются модели поллинга, в которых обслуживание
происходит согласно пороговой дисциплине: очередь может быть обслу-
жена, если ее длина превышает заданный порог. Пороговые дисциплины
являются важной разновидностью введения приоритета между очередями
системы. Системы с такими дисциплинами широко используются для мо-
делирования широкополосных беспроводных сетей под управлением про-
токола IEEE 802.11x. Рассмотрены модели с непрерывным опросом очере-
дей и модели, в которых сервер прекращает обход очередей, если в системе
находится недостаточное число сообщений. Исследуется система с простоя-
ми сервера, когда возобновление работы начинается лишь после того, как
в системе накопилось нужное число заявок (так называемый пороговый
старт).
В главе 5 описаны модели с ограниченным обслуживанием очередей,
когда ограничено либо число заявок, которое может обслужить сервер
за одно посещение очереди, либо время пребывания сервера у очереди.
Рассмотрена задача оптимизации дисциплины обслуживания.
В главе 6 кратко рассмотрены приоритетные системы с абсолютным
или смешанным приоритетом и немгновенным переключением сервера меж-
ду потоками заявок разных приоритетов. Такие системы представляют со-
бой системы поллинга с приоритетным опросом. Затронуты вопросы нахо-
ждения распределения периодов занятости сервера обслуживанием заявок
одного приоритета, периода занятости системы, а также длины очереди
для каждого приоритета.
Глава 7 посвящена оценке характеристик широкополосных беспровод-
ных сетей с использованием стохастических моделей поллинга. Основное
внимание уделено моделированию беспроводных радиосетей под управле-
нием протокола централизованного управления PCF (point coordination
function), оценке производительности таких сетей, проведению сравнитель-
ного анализа и оптимальному выбору стратегий динамического опроса.
Авторы приносят благодарность профессору В.В. Рыкову за обсуж-
дение и советы, которые способствовали улучшению содержания книги,
профессорам О. Боксма (технологический университет Эйндховена, Ни-
дерланды), Ю. Ехиали (университет Тель-Авива, Израиль) и Г.К. Миш-
кою (Академия наук Молдовы) за предоставленные материалы по работам
в области систем поллинга и приоритетных систем, а также сотрудникам
лаборатории сетей передачи информации Института проблем передачи ин-
формации им. А.А. Харкевича РАН, участвовавших в подготовке и оформ-
лении рукописи.
ГЛАВА 1
Системы поллинга. Основные
понятия
1.1 Классификация систем поллинга
Системы упорядоченного опроса являются разновидностью систем
массового обслуживания с несколькими очередями и подразделяются на
два класса. Системы первого класса имеют несколько обслуживающих
приборов (серверов), и заявки, поступая в систему, выбирают сервер, на
котором они хотят получить обслуживание. Таким образом, у каждого
сервера образуется своя очередь, и заявки в таких системах являются ак-
тивными, а серверы пассивными. В системах второго класса (системы
поллинга) имеется общий для всех очередей сервер (или несколько серве-
ров), который по определенному правилу обходит очереди и обслуживает
находящиеся в них заявки.
Подходы к классификации систем поллинга описаны в различных ра-
ботах (см., например, [7], [29], [74]). В настоящей главе, следуя [7], при-
водится обобщенный подход к классификации систем поллинга по следу-
ющим критериям: число очередей, порядок опроса очередей, дисциплина
обслуживания очереди.
В зависимости от числа очередей системы поллинга бывают дискрет-
ными (число очередей конечно или счетно) и непрерывными (число оче-
редей или общее число мест для ожидания в системе более чем счетно).
В последнем случае рассматривают системы, в которых заявки распола-
гаются на окружности или в n-мерной области.
В данной книге мы рассматриваем лишь дискретные системы поллинга
с конечным числом очередей. О непрерывных системах поллинга можно
узнать из работ [20, 22, 52, 68, 87].
Классификация систем поллинга 15
Сведения из теории вероятностей, которые могут потребоваться при
чтении данной книги, можно почерпнуть из [3].
Дискретные системы поллинга характеризуются числом очередей, чис-
лом мест для ожидания, числом серверов, процессами поступления и об-
служивания заявок, длительностями переключения сервера между очере-
дями, порядком и дисциплиной обслуживания очередей, и, возможно, дру-
гими параметрами или конфигурацией системы. Предполагаем, что оче-
реди занумерованы от 1 до N, где N – число очередей в системе (N ≥ 2).
Очередь с номером i будем обозначать через Qi, i = 1,N.
Порядком опроса очередей называется правило, следуя которому, сер-
вер выбирает следующую очередь для обслуживания.
Среди видов порядка обслуживания выделяют
1. Циклический порядок: сервер посещает очереди в порядке Q1, Q2,
. . . , QN, Q1, Q2, . . . , QN, . . . . Такие системы поллинга называют
циклическими.
2. Периодический порядок: задается так называемая таблица поллинга
(T(1), T(2), . . . , T (M)) длины M (M ≥ N), T(i) ∈ {1, . . . , N}, i =
1,M. Cервер посещает очереди в порядке QT(1), QT(2), . . . , QT(M),
QT(1), QT(2), . . . , QT(M), . . . . При этом предполагается, что таблица
поллинга содержит номера всех очередей системы.
Частными случаями периодического порядка обхода очередей явля-
ются обход типа "звезда", когда очереди обслуживаются в порядке
Q1, Q2, Q1, Q3, . . . , Q1, QN), и элеваторный порядок обхода очере-
дей, при котором очереди обслуживаются от первой до последней, а
затем от последней очереди до первой.
3. Случайный порядок, при котором с вероятностью pi, i = 1,N, на
обслуживание выбирается очередь Qi, N
i=1 pi = 1. Возможен также
и другой вариант выбора очереди: с вероятностью pij , i, j = 1,N,
после посещения очереди Qi сервер переключается к Qj ,
N
j=1 pij = 1, i = 1,N.
4. Приоритетный порядок, при котором система имеет очереди разных
приоритетов и какая-либо очередь может быть обслужена, если более
приоритетные очереди не содержат заявок.
Описанные в литературе порядки опроса очередей можно условно раз-
делить на статические и динамические. При статическом порядке прави-
ло выбора очередей на обслуживание не меняется в ходе работы системы.
16 Глава 1. Системы поллинга. Основные понятия
Динамический порядок предполагает выбор очереди на обслуживание в
определенные моменты принятия решений на основе полной или частич-
ной информации о состоянии системы (например, обслуживание очередей
в цикле в порядке убывания их длин).
Дисциплиной обслуживания очереди называется число заявок, кото-
рое обслуживает сервер за одно посещение очереди. Внутри очереди заяв-
ки обслуживаются в порядке, определяемом дисциплиной обслуживания
заявок (например, заявки обслуживаются в порядке поступления в оче-
редь).
Среди дисциплин обслуживания очереди (предположим, что это оче-
редь Qi) выделяют
1. Исчерпывающую дисциплину, при которой сервер обслуживает заяв-
ки до тех пор, пока очередь не опустеет.
2. Шлюзовую дисциплину, при которой сервер обслуживает лишь те за-
явки, которые находились в очереди в момент опроса (момент завер-
шения подключения к ней сервера). Заявки, поступившие в очередь
после момента опроса, обслуживаются в следующем цикле. Если сер-
вер обслуживает только те заявки, которые находились в очереди в
момент начала цикла (момент опроса первой очереди), то говорят о
глобально-шлюзовой дисциплине.
3. li-ограниченную дисциплину, при которой число заявок, которое мо-
жет обслужить сервер, ограничено числом li, li ≥ 1. Среди огра-
ниченных дисциплин различают исчерпывающие и шлюзовые. При
ограниченной исчерпывающей дисциплине сервер обслуживает оче-
редь до тех пор, пока не произойдет одно из двух событий: либо будут
обслужены l заявок, либо очередь опустеет. Ограниченная шлюзовая
дисциплина предполагает обслуживание до тех пор, пока либо будут
обслужены l заявок, либо будут обслужены все заявки, которые на-
ходились в очереди в момент ее опроса. Частный случай li = 1 иногда
называют неисчерпывающим обслуживанием.
4. li-уменьшающую дисциплину, при которой сервер обслуживает за-
явки в очереди до тех пор, пока ее длина не станет на li меньше, чем
была в момент подключения сервера, либо пока очередь не опустеет,
li ≥ 1. При li = 1 эту дисциплину также называют полуисчерпываю-
щей.
Классификация систем поллинга 17
5. T-ограниченную дисциплину, при которой время пребывания сервера
у очереди ограничено. Эта дисциплина также может быть шлюзовой
или исчерпывающей.
6. Пороговую дисциплину, при которой сервер обслуживает очередь,
если число заявок в ней не меньше заданной величины (порога).
7. Случайную дисциплину, при которой число заявок, которое может
обслужить сервер, определяется значением дискретной случайной
величины ξi, имеющей закон распределения {ai
j, j ≥ 1}. Закон рас-
пределения может меняться при каждом посещении очереди. Значе-
ние случайной величины ξi разыгрывается при каждом опросе оче-
реди. Отметим некоторые случайные дисциплины:
(a) Биномиальная дисциплина, при которой случайная величина ξi
имеет биномиальное распределение с параметрами Xi и pi, где
Xi – число заявок в очереди Qi в момент опроса, pi – некоторое
число, 0 < pi ≤ 1. Для данной дисциплины aj
i = Cj
Xi
pj
i (1 −
pi)Xi−j , j = 1,Xi, aj
i = 0 для j > Xi;
(b) Дисциплина Бернулли, при которой первая заявка в очереди Qi
обслуживается с вероятностью 1, а каждая последующая – с за-
данной вероятностью pi. С вероятностью 1−pi сервер покидает
очередь. Для данной дисциплины aj
i = pj−1, j ≥ 1.
Если все очереди системы поллинга имеют дисциплины обслуживания
одного вида, будем говорить о системе поллинга с дисциплиной обслу-
живания данного вида (с исчерпывающей, l-ограниченной или другими
дисциплинами обслуживания). Если дисциплины обслуживания очередей
различны, то говорят о системе поллинга со смешанной дисциплиной об-
служивания.
Порядок обхода очередей и дисциплины их обслуживания составляют
политику обслуживания в системе поллинга – это правило выбора следу-
ющей заявки в системе на обслуживание.
Среди систем поллинга различают системы с дискретным временем
(время поделено на равные интервалы, называемые тактами дискретиза-
ции) и системы с непрерывным временем.
Если процессы, характеризующие очереди системы: процессы поступ-
ления и обслуживания заявок, процессы, определяющие длительности пе-
реключения сервера между очередями, и, возможно, другие процессы, со-
ответственно, являются стохастически эквивалентными для всех очередей,
18 Глава 1. Системы поллинга. Основные понятия
то система поллинга называется симметричной, или однородной систе-
мой. В противном случае система называется несимметричной, или неод-
нородной.
Если сервер не затрачивает время на переключение между очередями,
то будем говорить о системе с мгновенным переключением сервера между
очередями, в противном случае – о системе с немгновенным переключени-
ем сервера.
Если не оговорено иное, полагаем, что система поллинга является несим-
метричной, число ее очередей конечно, очереди имеют неограниченное
число мест для ожидания, переключение сервера между очередями нем-
гновенно. Если в очереди нет заявок, то сервер сразу же ее покидает.
Полагаем также, что внутри очереди заявки обслуживаются в порядке
поступления.
Целью большинства исследований систем поллинга является нахожде-
ние среднего времени ожидания в каждой из очередей системы. Однако
не всегда удается получить явные формулы для вычисления этих харак-
теристик, поэтому большое внимание уделяется нахождению приближен-
ных формул, а также уточнению уже полученных приближенных значе-
ний. Иногда задача нахождения средних времен ожидания сводится к на-
хождению взвешенной суммы этих характеристик. Под взвешенной сум-
мой средних времен ожидания понимается выражение
N i=1
ρiM[Wi], где Wi
– случайная величина, характеризующая время ожидания в очереди Qi,
M[Wi] – математическое ожидание, ρi = λibi – загрузка очереди Qi, λi –
интенсивность потока заявок, bi – среднее время обслуживания заявок в
очереди Qi, i = 1,N. Отметим, что согласно формуле Литтла, взвешенная
сумма средних времен ожидания представляет собой среднее количество
работы в системе в произвольный момент времени. Под количеством ра-
боты в некоторый момент времени понимается время, которое затратит
сервер на обслуживание заявок, находящихся в системе в этот момент.
1.2 Основная модель поллинга
Основная модель, которая является объектом исследования большин-
ства работ по системам поллинга, описывается следующим образом. Си-
стема имеет один сервер и N (N ≥ 2) очередей с неограниченным числом
мест для ожидания.
В i-ю очередь поступает стационарный пуассоновский поток заявок
с параметром λi. Времена обслуживания заявок в очереди Qi независи-
мы и одинаково распределены с функцией распределения Bi(t) со сред-
Основная модель поллинга 19
ним bi = ∞ 0
tdBi(t), вторым моментом b(2)
i и преобразованием Лапласа-
Стилтьеса (ПЛС) ˜Bi(x), i = 1,N. Полагаем, что потоки заявок и времена
обслуживания заявок независимы.
Следуя классификации Кендалла, такую систему называют системой
поллинга с очередями типа M/GI/1. Если времена обслуживания заявок
распределены экспоненциально или потоки заявок в очереди являются ре-
куррентными, то говорят о системах поллинга с очередями типа M/M/1
или G/G/1, соответственно.
Сервер посещает очереди, следуя определенному порядку опроса оче-
редей и обслуживая их в соответствии с выбранной дисциплиной. Время
подключения к очереди Qi, называемое временем переключения, имеет
функцию распределения Si(t) со средним si, вторым моментом s(2)
i и ПЛС
˜ Si(x), i, j = 1,N.
Обозначим через ρi = λibi загрузку очереди Qi, через ρ = N
i=1 ρi –
загрузку системы. Для систем с циклическим или периодическим опро-
сом очередей обозначим также через s и s(2) первый и второй моменты
совокупной длительности переключений сервера за один цикл,
s =
N
j=1
sj, s(2) = s2 +
N
j=1
(s(2)
j − s2j).
Будем говорить, что система массового обслуживания соответствует
i-й очереди системы поллинга, если поток заявок в эту систему являет-
ся стационарным пуассоновским с параметром λi, а время обслуживания
заявок имеет функцию распределения Bi(t). Система массового обслужи-
вания соответствует системе поллинга, если поток заявок в эту систему
является стационарным пуассоновским с параметром λ = N
i=1 λi, а время
обслуживания заявок имеет функцию распределения B(t) = N
i=1
λi
λ Bi(t).
Под моментом опроса (поллинга) понимается момент времени, когда
сервер принимает решение о том, сколько заявок в очереди он будет об-
служивать при этом посещении. Обычно за момент опроса принимается
момент, когда сервер завершил переключение к очереди и готов начать
ее обслуживание. Моментом опроса также иногда считают момент, когда
становится доступной информация о числе заявок в очереди.
Для систем поллинга с циклическим или периодическим опросом оче-
редей выделяют периоды времени, называемые циклами. Для цикличе-
ских систем – это время, затрачиваемое на опрос очередей от Q1 до QN.
Для систем с периодическим опросом – время, затрачиваемое на опрос
20 Глава 1. Системы поллинга. Основные понятия
очередей от QT(1) до QT(M). В работе некоторых систем поллинга выделя-
ют гамильтонов цикл – это время, за которое сервер посетит все очереди
системы, причем ровно один раз. При элеваторном опросе выделяют восхо-
дящий (опрос очередей от первой до последней) и нисходящий цикл (опрос
от последней до первой очереди).
Для систем с циклическим опросом и шлюзовым или исчерпывающим
обслуживанием среднее время цикла складывается из времени, когда сер-
вер обслуживает очереди (на это он тратит долю времени ρ), и время,
когда он переключается между очередями (на это он тратит в среднем
время s за цикл). Таким образом,
C = ρC + s,
отсюда получаем
C = s
1 − ρ
.
1.3 Стационарный режим в системах поллинга
Говорят, что в системе поллинга существует стационарный режим, если
длины всех очередей в моменты опроса имеют стационарное распределе-
ние и длина цикла имеет конечное математическое ожидание.
Для систем с циклическим опросом необходимые и достаточные усло-
вия существования стационарного режима имеют следующий вид:
• ρ < 1 для систем с исчерпывающим и шлюзовым обслуживанием
очередей;
• для ki-ограниченной дисциплины обслуживания –
ρ < 1 и λi <
ki(1 − ρi)
s
, i= 1,N.
При 1-ограниченном обслуживании эти условия принимают вид
ρ + λis < 1, i= 1,N.
• для системы с 1-уменьшающим обслуживанием –
ρ + λi(1 − ρi)s < 1, i= 1,N.
Стационарный режим 21
Необходимые и достаточные условия существования стационарного ре-
жима для систем с общими дисциплинами обслуживания и периодиче-
ским опросом очередей получено в работе [57]. В ней предложено опи-
сывать дисциплину обслуживания очереди тройкой случайных величин
(f(x), v(x), ϕ(x)), где x – число заявок в очереди в момент опроса, f(x) –
число заявок, которое будет обслужено при данном посещении очереди,
v(x) – длительность посещения очереди сервером, ϕ(x) – число заявок,
которое остается в очереди по завершении ее обслуживания. Необходимое
и достаточное условие существования стационарного режима в системах
поллинга имеет вид
ρ + λis/G∗i < 1, i= 1,N,
где G∗i – среднее максимальное число заявок, которые могут быть обслу-
жены в i-й очереди за один цикл. При этом дисциплина обслуживания
очередей должна удовлетворять следующим условиям:
• Дисциплина обслуживания не зависит от предыстории процесса об-
служивания, например, от числа обслуженных заявок или времени
их обслуживания.
• Выбор заявок на обслуживание не зависит от времени обслуживания
или возможных поступлений заявок в будущем.
• Очередь получает обслуживание с положительной вероятностью, ес-
ли в ней накопилось требуемое число заявок. Сервер, обращенный к
очереди, не простаивает (непрерывно обслуживает заявки). Если в
очереди нет заявок, он немедленно покидает ее.
• Дисциплина обслуживания (f(x), v(x), ϕ(x)) является стохастически
монотонной. Определение стохастической монотонности для случай-
ных векторов, называемой также монотонностью по распределению,
можно найти в работах [57, 86].
ГЛАВА 2
Методы исследования систем
поллинга
В главе изложены основные методы анализа систем циклического опро-
са. Данные методы рассмотрены на примере исследования циклических
систем поллинга с исчерпывающим или шлюзовым обслуживанием. Отыс-
кивается распределение цепи Маркова, характеризующей число заявок в
очередях в определенные моменты времени, вычисляется среднее число
заявок в очередях, что дает возможность найти время ожидания в систе-
ме. Рассмотрены свойства стохастического разложения времени занятости
сервера, а также закон псевдосохранения для некоторых систем поллинга,
использование которого позволяет вычислить средние времена пребыва-
ния сообщения в системе.
2.1 Метод производящих функций
Метод производящих функций широко используется для нахождения
распределения числа заявок в системе поллинга в моменты опроса очере-
дей. Рассмотрим его применение на примере системы поллинга с цикли-
ческим опросом и исчерпывающим или шлюзовым обслуживанием очере-
дей. Метод подробно описан в работе [99], где дополнительно изложены
основные методы и результаты исследования циклических систем с исчер-
пывающим, шлюзовым и глобально-шлюзовым обслуживанием очередей,
а также некоторых систем с нециклическим порядком обхода очередей.
Метод производящих функций 23
2.1.1 Шлюзовое обслуживание очередей
Рассмотрим основную систему поллинга, описанную в разделе 6.1.1, со
шлюзовым обслуживанием. Предположим, что система функционирует в
стационарном режиме. Обозначим через Xj
i число заявок в очереди Qj в
произвольный момент опроса очереди Qi, i, j = 1,N.
Обозначим также через Ai(T) – число заявок, поступивших в i-ю оче-
редь за время T (детерминированное или случайное), Bik – время обслу-
живания k-й заявки в i-й очереди, Si – время переключения сервера к i-й
очереди, i = 1,N.
При шлюзовом обслуживании очередей случайные величины Xj
i , i, j =
1,N, связаны между собой следующим образом:
Xj
i+1 =⎧⎨⎩
Xj
i + Aj Xi
i
k=1 Bik + Si+1 , j = i,
Ai Xi
i
k=1 Bik + Si+1 , j= i.
(2.1)
Отметим, что времена обслуживания заявок Bik, k = 1,Xi
i , независимы и
одинаково распределены с функцией распределения Bi(t), i = 1,N.
Пусть pi(r1, r2, . . . , rN) – стационарная вероятность того, что в произ-
вольный момент опроса i-й очереди j-я очередь содержит rj заявок, rj ≥ 0,
i, j = 1,N. Введем производящие функциии этих вероятностей
Gi(z) = Gi(z1, z2, · · · , zN) =
∞ r1=0
∞ r2=0
· · ·
∞ rN=0
pi(r1, r2, . . . , rN)zr1
1 · · · zrN
N .
Они также могут быть представлены как
Gi(z) = M⎡⎣
N
j=1
z
Xj
i
j⎤⎦
, i= 1,N,
где, напомним, M – математическое ожидание.
С помощью равенств (2.1) получаем
Gi+1(z) = M⎡⎣
N
j=1
z
Xj
i+1
j ⎤⎦
= MXi ⎡⎢⎢⎣
N
j=1
j =i
z
Xj
i
j M⎡⎣
N
j=1
z
Aj Xi
i
k=1 Bik
j Xi⎤⎦
⎤⎥⎥⎦
×
(2.2)
×M⎡⎣
N
j=1
zAj (Si+1)
j ⎤⎦
,
24 Глава 2. Методы исследования систем поллинга
где Xi = (X1
i ,X2
i , . . . , XN
i ),M[ · |Xi] – условное математическое ожидание.
Математическое ожидание случайной величины zAj (T)
j , где T – случай-
ная величина с функцией распределения D(T), определяется следующим
образом:
M zAj (T)
j = ∞
0
M zAj (t)
j dD(t) = ∞
0
∞ k=0
P(Aj(t) = k)zk
j dD(t) =
(2.3)
= ∞
0
∞ k=0
(λjt)k
k! e−λj tzk
j dD(t) = ∞
0
eλj t(1−zj ) dD(t) =
= ˜D(λj(1 − zj)),
где ˜D(w) – ПЛС функции распределения D(t).
Соответственно,
M⎡⎣
N
j=1
zAj (T)
j ⎤⎦
= ˜D
⎛⎝
N
j=1
λj(1 − zj)⎞⎠
.
Таким образом, из равенств (2.2)–(2.3) получаем соотношения для про-
изводящих функций Gi(z), i = 1,N,
Gi+1(z) = Gi⎛ ⎝z1, z2, . . . , zi−1, ˜Bi⎡⎣
N
j=1
λj(1 − zj)⎤⎦, zi+1, . . . , zN⎞⎠
× (2.4)
ט Si+1⎡⎣
N
j=1
λj(1 − zj)⎤⎦
, i= 1,N.
В (2.4) полагаем, что GN+1(z) = G1(z).
Среднее число заявок fi(j) = M[Xj
i ] в очереди Qj в опроса очереди Qi
определяется как
fi(j) = M(Xj
i ) = ∂Gi(z)
∂zj z=1
,
где 1 = (1, 1, . . . , 1).
Дифференцированием равенств (2.4) в точке z = 1 можно получить
систему уравнений для величин fi(j), i, j = 1,N. Запишем вначале урав-
нение для fi+1(j) при j = i. Обозначим через ν =
N j=1
λj(1 − zj), тогда из
Метод производящих функций 25
(2.4) имеем
fi+1(j) = d
dzj
Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN z=1
˜ Si+1(0)+
+Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN d
dzj
˜ Si+1(ν) z=1.
Далее,
fi+1(j) = ∂
∂zj
Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN + (2.5)
+ ∂
∂˜Bi
Gi z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN d˜Bi(ν)
dν
∂ν
∂zj z=1
˜ Si+1(0)+
+Gi+1 z1, . . . , zi−1, ˜Bi(ν), zi+1, . . . , zN d ˜ Si+1(ν)
dν
∂ν
∂zj z=1
.
Заметим, что при z = 1: Gi(1) = 1, v(1) = 0, а ˜Bi(0) = ˜ Si(0) = 1. Также
d˜Bi(ν)
dν v=0
= − ∞
0
te−νtdBi(t) = −bi,
∂ν
∂zi z=1
= −λi, i= 1,N.
Тогда, с помощью последних равенств, соотношение (2.5) принимает
вид уравнения
fi+1(j) = fi(j) + λjbifi(i) + λjsi+1, j = i.
Cлучай i = j рассматривается аналогично.
Таким образом, получаем систему уравнений для средних длин очере-
дей системы в моменты опроса
fi+1(j) = fi(j) + λjbifi(i) + λjsi+1, j = i,
fi+1(i) = λibifi(i) + λisi+1, i= 1,N.
Решение этой системы может быть получено явно и имеет вид
fi(j) =⎧⎨⎩
λj i−1
k=j ρk
s
1−ρ + sk+1 , j = i,
λi
s
1−ρ, j= i.
Вторые моменты случайных величин Xj
i , i, j = 1,N, также могут быть
получены дифференцированием производящих функций Gi(z), i = 1,N,
fi(j, k) = M[Xj
i Xk
i ] = ∂2Gi(z)
∂zj∂zk z=1
,
fi(i, i) = M[Xi
i (Xi
i − 1)] = ∂2Gi(z)
∂z2
i z=1
.
26 Глава 2. Методы исследования систем поллинга
Система уравнений для вычисления fi(j, k), i, j, k = 1,N, имеет вид
fi+1(j, k) = λjλks(2)
i+1 + si+1λkfi(j) + si+1λjfi(k)+
+ fi(i)λjλk 2bisi+1
1 − ρi
+ b(2)
i
(1 − ρi)3 + bi
1 − ρi
(fi(i, i)λk + fi(i, k)λj)+
+ fi(j, k) + fi(i, i)λjλk bi
1 − ρi 2
, i = j, i = k,
fi+1(i, j) = λiλjs(2)
i+1 + si+1λi fi(j) + fi(i)λjbi
1 − ρi , i = j,
fi+1(i, i) = λ2i
s(2)
i+1, i, j, k = 1,N.
Метод производящих функций в некоторых случаях позволяет най-
ти ПЛС времени ожидания в очереди. Пусть Li – число заявок, которые
остаются в i-й очереди в момент ухода из нее заявки, i = 1,N. Обозначим
также через
¯L
i(z) = M[zLi] =
∞ k=0
Pi(k)zk
производящую функцию случайной величины Li, где Pi(k) – вероятность
того, что Li = k, k ≥ 0. Для рассматриваемой системы поллинга справед-
лив закон стационарной очереди Хинчина: стационарное распределение
числа заявок в системе в произвольный момент времени совпадает со ста-
ционарным распределением числа заявок в системе в моменты завершения
обслуживания. Следовательно, Li(z) представляет собой производящую
функцию числа заявок в i-й очереди в произвольный момент времени.
Пусть Ti – общее число заявок, обслуженных в i-й очереди за одно
посещение сервера, а Li(n), n = 1, Ti – последовательность случайных
величин, означающих число заявок в очереди непосредственно после n-
го момента завершения обслуживания в i-й очереди. Тогда производящая
функция случайной величины Li удовлетворяет равенству
¯L
i(z) =
M Ti
n=1 zLi(n) M[Ti] . (2.6)
Метод производящих функций 27
Поскольку Li(n) = Xi
i − n + A( n
k=1 Bik), равенство (2.6) принимает вид
¯L
i(z) =
1
M[Ti]
M⎡⎣
Ti n=1
z
Xi
i−n+A n k=1
Bik ⎤⎦ =
1
M[Ti]
M⎡ ⎣zXi
i
Ti n=1
z−n+A n k=1
Bik ⎤⎦ =
=
1
M[Ti]
M⎡ ⎣zXi
i
Ti n=1
z−ne−λ n k=1
Bik (1−z)⎤⎦
=
=
1
M[Ti]
M zXi
i
Ti n=1 ˜Bi(λi(1 − z))
z n =
=
1
M[Ti]
M⎡⎢⎣
zXi
i
˜B
i(λi(1 − z))
z
1 − ˜Bi(λi(1−z))
z Ti
1 −
˜B
i(λi(1−z))
z
⎤⎥⎦
.
Таким образом, получаем
¯L
i(z) =
˜B
i(λi(1 − z))
M[Ti](z − ˜Bi(λi(1 − z)))
M zXi
i−Ti(zTi−[˜Bi(λi(1−z))]Ti) .
Рассмотрим теперь распределение времени ожидания в i-й очереди.
Поскольку заявки, которые остаются в ней в момент завершения обслу-
живания, поступили за время пребывания (время ожидания плюс время
обслуживания) обслуженной заявки, то
¯L
i(z) =
∞ k=0
Pi(k)zk =
∞ k=0
zk ∞
0
e−λiw (λiw)k
k! dP (Wi ≤ w) =
= ˜Wi(λi(1 − z))˜Bi(λi(1 − z)),
откуда
˜W
i(w) =
¯L
i(1 − w/λi)
˜B
i(w)
. (2.7)
Для шлюзового обслуживания Xi
i = Ti, следовательно, [88],
¯L
i(z) =
˜B
i(λi(1 − z))
M[Ti] z − ˜Bi(λi(1 − z)) M zXi
i −M (˜Bi(λi(1 − z)))Xi
i .
(2.8)
28 Глава 2. Методы исследования систем поллинга
Среднее время ожидания в i-й очереди находится с помощью ПЛС
распределения времени ожидания как
M[Wi] = −
d
dw
˜W
i(w) w=0. (2.9)
Поскольку M[Ti] = M[Xi
i] = λiC, то с помощью (2.7) и (2.8), получаем
следующую формулу:
M[Wi] =
M[(Xi
i )2] −M[Xi
i ]
2λiM[Xi
i ]
(1 + ρi) =
(1 + ρi)fi(i, i)
2λ2i
C
, i= 1,N. (2.10)
2.1.2 Исчерпывающее обслуживание очередей
Рассмотрим теперь систему с исчерпывающим обслуживанием очере-
дей. Cлучайные величины Xj
i , i, j = 1,N, связаны между собой следую-
щим образом:
Xj
i+1 =⎧⎨⎩
Xj
i + Aj Xi
i
k=1 Θik + Si+1 , j = i,
Ai(Si+1), j= i,
(2.11)
где Θik – длительность периода занятости сервера в i-й очереди, порож-
денного k-й заявкой. Величины Θik независимы и одинаково распределе-
ны с ПЛС функции распределения ˜θi(w), которое находится как решение
функционального уравнения
˜θi(w) = ˜Bi(w + λi − λi ˜θi(w)).
Средняя длительность периода занятости сервера в i-й очереди определя-
ется как
θi = −˜θ (0) = bi
1 − ρi
.
Метод производящих функций 29
Как это сделано для шлюзового обслуживания, из равенств (2.11) по-
лучаем выражение для производящих функций Gi(z), i = 1,N,
Gi+1(z) = M⎡⎣
N
j=1
z
Xj
i+1
j ⎤⎦
= (2.12)
= M⎡⎢⎢⎣
N
j=1
j =i
z
Xj
i
j M⎡⎢⎢⎣
N
j=1
j =i
z
Aj Xi
i
k=1 Θik
j Xi⎤⎥⎥⎦
⎤⎥⎥⎦
M⎡⎢⎢⎣
N
j=1
j =i
zAj (Si+1)
j ⎤⎥⎥⎦
=
= Gi⎛⎜⎜⎝
z1, . . . , zi−1, ˜θi⎡⎢⎢⎣
N
j=1
j =i
λj(1 − zj)⎤⎥⎥⎦
, zi+1, . . . , zN⎞⎟⎟⎠
˜ Si+1⎡⎣
N
j=1
λj(1 − zj)⎤⎦
.
Система уравнений для средних длин очередей Xj
i , i, j = 1,N, состав-
ляется дифференцированием равенств (2.12) и имеет вид
fi+1(j) = fi(j) + λj
bi
1 − ρi
fi(i) + λjsi+1, j = i,
fi+1(i) = λisi+1, i= 1,N.
Ее решение может быть получено явно,
fi(j) =⎧⎨⎩
λj i−1
k=j+1 ρk
s
1−ρ + i−1
k=j sk+1 , j = i,
λi(1 − ρi) s
1−ρ, j= i.
(2.13)
Перейдем теперь к нахождению среднего времени ожидания в i-й оче-
реди. Используем те же рассуждения, что и в предыдущем разделе. При
исчерпывающем обслуживании среднее число заявок, обслуженных за од-
но посещение сервером очереди, есть величина
Ti = Xi
i + Ai⎛⎝
Xi
i k=1
Θik⎞⎠
,
таким образом,
M[Ti] = fi(i) + λifi(i)θi = fi(i)
1 − ρi
,
откуда с помощью (2.13) получаем, что M[Ti] = λiC, i = 1,N.
30 Глава 2. Методы исследования систем поллинга
Производящая фукнция числа заявок в i-й очереди в произвольный
момент времени определяется равенством, [88],
¯L
i =
1
λiC
˜B
i(λi(1 − z))
z − ˜Bi(λi(1 − z)) M zXi
i − 1 . (2.14)
Среднее число заявок в i-й очереди и среднее время ожидания в ней
находятся с помощью равенств (2.7), (2.9) и (2.14),
M[Li] = ρi + λ2i
b(2)
i
2(1 − ρi)
+ fi(i, i)
2λi(1 − ρi)C
,
M[Wi] = λib(2)
i
2(1 − ρi)
+ fi(i, i)
2λ2i
(1 − ρi)C
, i= 1,N. (2.15)
Величины fi(i, i), i = 1,N, могут быть вычислены как решение си-
стемы линейных уравнений, которая составляется дифференцированием
равенств (2.12).
2.2 Метод ветвящихся процессов
Метод ветвящихся процессов (иначе его называют методом потомков)
основан на вычислении числа потомков, которые порождаются в систе-
ме каждой заявкой. В данном разделе показано применение этого метода
для систем поллинга с фиксированным (циклическим или периодическим)
опросом очередей и шлюзовым или исчерпывающим обслуживанием, [67].
Этот метод предназначен для вычисления моментов времен ожидания.
Основные его преимущества состоят в следующем:
1. Среднее время ожидания в очереди вычисляется независимо от вре-
мен ожидания в других очередях. Поэтому метод предпочтителен,
если нет необходимости вычислять средние времена ожидания во
всех очередях, например, в системах с большим числом очередей со
сходными параметрами.
2. Метод может быть применен для анализа систем, которые могут
быть исследованы методом производящих функций (см. раздел 2.1).
3. Результаты, получаемые с помощью данного метода, создают пред-
посылки для оптимизации параметров системы.
Метод ветвящихся процессов 31
Рассмотрим систему с циклическим опросом, описанную в разделе 6.1.1.
Отнесем каждую заявку, поступающую в систему, к первичным заявкам,
если она поступила в момент, когда сервер не обслуживал заявки, или ко
вторичным заявкам, если она поступила в момент, когда сервер был занят
обслуживанием.
Пусть K – некоторая заявка. Тогда множеством сыновей заявки K
назовем множество заявок, поступивших за время ее обслуживания. Мно-
жеством потомков заявки K назовем множество, состоящее из K, ее
сыновей и потомков ее сыновей. Будем говорить, что заявка K принадле-
жит K, если K является потомком K.
Метод основан на том, что каждая заявка, присутствовавшая в оче-
реди Q1 в момент ее опроса, принадлежит лишь одной первичной заявке.
Рассматривается произвольная первичная заявка Ki, поступившая ранее в
очередь Qi, и вычисляется число ее потомков, находящихся в Q1 в момент
опроса этой очереди. Суммируя число потомков для каждой первичной за-
явки, находящейся в системе, получаем число заявок X1
1 в Q1 в момент ее
опроса (в этом смысле данный метод схож с нахождением распределения
длин очередей в моменты поллинга методом производящих функций).
Моментом наблюдения будем называть момент опроса очереди Q1.
Пусть Ri,0 – период обслуживания i-й очереди в цикле, предшествующем
моменту наблюдения, Ri,n – период обслуживания i-й очереди n+1 циклов
назад от момента наблюдения. Пусть также Ci,n – множество заявок, под-
лежащих обслуживанию в периоде обслуживания Ri,n, Li,n – случайная
величина, обозначающая число заявок в Q1, которые являются потомка-
ми Ci,n и присутствуют в Q1 в момент наблюдения. Величину Li,c также
можно интерпретировать как вклад заявок Ci,n в длину X1
1 очереди Q1
в момент наблюдения. Обозначим через Li,n(z) производящую функцию
для Li,n, Li,n(z) = M#zLi,n$. Введем также первые три момента случайной
величины Li,n: αi,n = M[Li,n], α(2)
i,n = M#(Li,n)2$ и α(3)
i,n = M[(Li,n)3].