Исследование систем массового обслуживания с параметрами регрессионного типа Леонтьев Николай Дмитриевич

Содержание к диссертации

Введение

1 Предварительные результаты 22

1.1 Модель дискретной авторегрессии 22

1.1.1 Определение 22

1.1.2 Стационарность 23

1.1.3 Корреляционные свойства 23

1.1.4 Модель дискретной авторегрессии первого порядка 24

1.1.5 Модель дискретной авторегрессии второго порядка

1.2 Факты из теории аналитических функций 26

1.3 Матрицы Копій 26

1.4 Классификация систем массового обслуживания 27

1.5 Система M\G\1 28

1.6 Система с обслуживанием авторегрессионного типа 29

1.7 Система Mx\G\1 32

1.8 Система DAR(1)\D\1 33

1.9 Система DAR(1)\D\c 35

1.10 Система DAR(2)\D\1 38

1.11 Система DAR(k)\D\1 39

2 Система с непрерывным временем и входящим потоком авторегрессионного типа 41

2.1 Описание системы 41

2.2 Основные результаты 41

2.3 Стационарный режим 49

2.4 Частный случай М = 2 50

3 Система с непрерывным временем, входящим потоком авторегрессионного типа и относительным приоритетом 62

3.1 Описание системы 62

3.2 Основные результаты 63

4 Системы с дискретным временем и входящим потоком авторегрессионного типа 74

4.1 Система DAR(1)\D\1 с обратной связью 74

4.2 Система DAR(2)D1 с обратной связью 77

5 Система с непрерывным временем и обслуживанием авторегрессионного типа з

5.1 Описание системы 82

5.2 Основные результаты 83

Заключение 91

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

Список рисунков 98

Список таблиц

• Модель дискретной авторегрессии первого порядка
• Система с обслуживанием авторегрессионного типа
• Стационарный режим
• Основные результаты

Введение к работе

Актуальность темы исследования

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

Способы передачи информации, используемые в современных телекоммуникационных сетях, можно условно разделить на два основных класса: способы, основанные на коммутации каналов (используемые, в частности, в аналоговых телефонных сетях), и способы, основанные на коммутации пакетов (используемые, в частности, в сети Интернет)¹. Рассмотрим подробнее второй класс способов. При коммутации пакетов передаваемые данные разбиваются на небольшие (до нескольких килобайт) части — пакеты. Каждый пакет оснащается заголовком, который содержит адрес узла-получателя и номер пакета. Пакеты передаются по сети независимо друг от друга. Коммутаторы такой сети имеют внутреннюю буферную память для временного хранения пакетов. Это позволяет сглаживать пульсации трафика на линиях связи между коммутаторами². Качество функционирования сети тесно связано с поведением этих буферов. К примеру, если буфер полностью занят, то поступающие пакеты информации могут теряться; могут возникать нежелательные задержки, и т. д.³

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

¹ Daigle J. N. Queueing Theory with Applications to Packet Telecommunication. Springer Science & Business Media, 2005.

²Коммутация пакетов // Википедия. [2012—2016]. Дата обновления: 09.02.2016. URL: (дата обращения: 05.03.2017).

^Bruneel Н., Fiems D., Walraevens J., and Wittevrongel S. Queueing Models for the Analysis of Communication Systems // TOP, 2014. Vol. 22. N. 2. P. 421-448.

могут быть зависимыми. Уход пакетов информации из буфера (процесс обслуживания) характеризуется распределением времён обслуживания, числом выходных каналов (обслуживающих устройств) и очерёдностью передачи пакетов (дисциплиной обслуживания). Обычно предполагается, что требования обслуживаются в порядке поступления (дисциплина обслуживания FCFS — First-Come-First-Served), однако в ряде приложений необходимо рассматривать другие дисциплины обслуживания, в том числе приоритетные. Емкость буфера обычно считается бесконечной, что существенно упрощает анализ соответствующих математических моделей. Это предположение допустимо в силу того, что в большинстве реальных систем связи ёмкость выбирается таким образом, чтобы сделать вероятность потери пакетов информации очень малой⁴.

В эмпирических работах, посвященных анализу трафика в сетях с коммутацией пакетов, показано, что размеры групп поступающих пакетов в ряде случаев оказываются коррелированными по времени⁵'⁶. Примером коррелированного потока данных является видео с переменным битрейтом (VBR). В VBR видео кадры генерируются в детерминированные моменты времени. Интервал времени между двумя кадрами для стандарта Н.261 составляет 1/24 секунды, а число бит в одном кадре является случайным. Сначала кодировщик генерирует один ключевой кадр (І-кадр), а последующие кадры кодируются как разностные кадры (Р-кадры)⁷. Кадры разбиваются на квадратные макроблоки, и тип ссылки для каждого из макроблоков определяется индивидуально, но с ограничением, заданным типом всего кадра. Ключевые кадры могут содержать только независимо сжатые макроблоки, а разностные — как независимо сжатые макроблоки, так и макроблоки со ссылкой на другой ключевой или разностный кадр⁸. Как следует из названия, разностные кадры несут информацию только об изменяющихся областях. Такой резким кодирования приводит к возникновению корреляции числа бит в последовательных Р-кадрах⁹.

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

⁴Bruneel Н., Fiems D., Walraevens J., and Wittevrongel S. Queueing Models for the Analysis of Communication Systems // TOP, 2014. Vol. 22. N. 2. P. 421-448.

⁶ Gusella R. Characterizing the Variability of Arrival Processes with Indexes of Dispersion // IEEE Journal on Selected Areas in Communications, 1991. Vol. 9. N. 2. P. 203-211.

^ePaxson V., Floyd S. Wide-area Traffic: The failure of Poisson modeling // IEEE/ACM Transactions on Networking (ToN), 1995. Vol. 3. N. 3. P. 226-244.

⁷Davis J., Chandra K., Thompson C. Nonlinear Time-Series Model for VBR Video Traffic // Local Computer Networks, 2000. LCN 2000. Proceedings. 25th Annual IEEE Conference on. IEEE, 2000. P. 678-683.

⁸Типы кадров // Википедия. [2007—2013]. Дата обновления: 25.11.2013. URL: (дата обращения: 05.03.2017).

⁹Frost V. S., Melamed В. Traffic Modeling for Telecommunications Networks // IEEE Communications Magazine, 1994. Vol. 32. N. 3. P. 70-81.

возникает корреляция между последовательно поступающими группами требований¹⁰:

1. Рассмотрим так называемый сессионный входящий поток. Пусть существует бесконечная популяция пользователей, каждый из которых может начинать и заканчивать сессию. Во время сессии пользователь активен и посылает пакеты информации через систему связи. Каждый активный пользователь генерирует случайное, но строго положительное число пакетов в единицу (квант) времени. Легко видеть, что подобный сессионный механизм генерации пакетов приводит к возникновению корреляционной структуры входящего потока. Действительно, поскольку пакеты, отправленные в течение одной сессии, поступают во время последовательных квантов времени, постольку сессия длины п вносит вклад во входящий поток в течение п последовательных квантов времени, а это означает, что размер группы требований, прибывшей во время некоего кванта времени, зависит от размеров групп, прибывших в течение предыдущих квантов. Число последовательных квантов времени, в течение которых пользователь активен, называют длиной сессии, а число пакетов информации, генерируемых в единицу времени сессии, называют шириной сессии. Примером сессионного входящего потока служит процесс скачивания файла с веб-сервера. Веб-сервер — это компьютерная система, которая принимает запросы пользователей к веб-странице или файлу и отвечает отправкой запрашиваемого файла пользователю. Веб-сервер подключен к сети Интернет через шлюз, который содержит буфер для передачи в Интернет данных с сервера. Если определить скачивание файла пользователем как одну сессию, то можно описать трафик от сервера к буферу при помощи сессионного входящего потока. Другой пример сессионного входящего потока — отправка электронной почты. Если передачу электронного письма на почтовый сервер рассматривать как сессию, то трафик, поступающий на исходящий буфер, будет описываться при помощи сессионного входящего потока. Ещё один пример — так называемый составной входящий поток (train arrivals), который характеризуется тем, что ширина сессии для него составляет один пакет.

2. Другой класс моделей коррелированного входящего потока — двух-режимный (on/off-type) входящий поток, в котором конечное число пользователей генерирует один пакет за квант времени в режиме первого типа и ни одного в режиме второго типа. Продолжительности последовательных режимов первого и второго типов предполагаются

¹⁰Bruneel Н., Fiems D., Walraevens J., and Wittevrongel S. Queueing Models for the Analysis of Communication Systems // TOP, 2014. Vol. 22. N. 2. P. 421-448.

независимыми, однако могут иметь различные распределения. Основным отличием двухрежимной конструкции входящего потока от сессионной является ограничение на число пользователей, которые могут генерировать пакеты в течение кванта времени. Корреляционная структура потока для данной конструкции определяется как продолжительностью режимов первого и второго типов, так и тем, что число пользователей, переходящих из режима первого типа в режим второго типа (из режима второго типа в резким первого типа) в течение кванта времени зависит от того, сколько пользователей находились в режиме первого типа (в режиме второго типа) до его начала.

Резюмируя вышеизложенное, отметим, что для оценки функционирования буферов в телекоммуникационных сетях необходимо рассматривать подходящие модели входящего трафика. В частности, необходима разработка моделей, которые хорошо описывают коррелированные, прерывистые и неоднородные потоки данных, и в то же время поддаются изучению аналитическими методами. В центре внимания настоящей диссертации будут модели входящего потока, основанные на временных рядах. Преимуществом подобных моделей является то, что для ряда систем обслуживания с входящими потоками данного типа удаётся получить аналитические выражения для основных характеристик функционирования. Для сравнения, альтернативный подход к моделированию коррелированных входящих потоков — дискретные марковские потоки (D-BMAP — Discrete Batch Markovian Arrival Process), как правило, приводит к системам обслуживания, основные характеристики которых удаётся получить лишь с использованием численных методов¹¹. Этот подход в настоящей диссертации не рассматривается.

Степень изученности и проработанности проблемы

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

Основополагающей работой в области анализа временных рядов считается классическая книга Дж. Бокса и Г. Дженкинса¹³, в которой был разработан систематический подход к анализу гауссовских временных ря-

¹¹ Bruneel Н., Fiems D., Walraevens J., and Wittevrongel S. Queueing Models for the Analysis of Communication Systems // TOP, 2014. Vol. 22. N. 2. P. 421-448.

¹²Hwang G. U., Sohraby K. On the Exact Analysis of a Discrete-Time Queueing System with Autoregressive Inputs // Queueing Systems, 2003. Vol. 43. N. 1. P. 29-41.

¹³Бокс Дж.., Дзюенкинс Г. Анализ временных рядов: Прогноз и управление. М.: Мир, 1974.

дов (GTS — Gaussian-based Time Series). Традиционные модели GTS используют в качестве входного сигнала белый гауссовский шум; в результате, подобные модели обладают простыми аддитивными свойствами. Удобство подобных моделей заключается в их гибкости при задании различных корреляционных структур. Однако данные модели ограничиваются лишь гауссовскими маргинальными распределениями, что является неприемлемым для большинства приложений. В связи с этим, гауссовские модели используются, как правило, при асимптотическом подходе к анализу систем обслуживания¹⁴.

Изучению общих, негауссовских временных рядов посвящена обширная литература. Отметим книгу Д. Кокса и П. Льюиса¹⁵, в которой разработан общий подход к их статистическому анализу, и статьи П. Льюиса и др.¹⁶'¹⁷, где рассматриваются временные ряды, основанные на различных процессах инноваций.

Несмотря на относительную простоту и существующую успешную практику применения моделей временных рядов в различных областях анализа данных, подобные модели до недавнего времени не находили широкого применения в теории массового обслуживания. Тем не менее, стоит отметить ряд статей. В случае непрерывного времени, в работах П. Финча и др.¹⁸'¹⁹ рассмотрена система обслуживания МА|М|1, в которой последовательность промежутков между поступлением требований подчинена модели скользящего среднего (MA — Moving Average), а длительности обслуживания имеют экспоненциальное распределение. Авторы рассмотрели случаи МА{1) и МА{2) и получили явные выражения для хвоста распределения длины очереди. Использованный в статьях подход может быть применён для анализа систем обслуживания с входящим потоком, задаваемым моделью скользящего среднего любого конечного порядка. В случае дискретного времени, в статье Дж. Хе и К. Сохраби²⁰ рассмотрен дискретный

^1АНыапд G. U., Sohraby К. On the Exact Analysis of a Discrete-Time Queueing System with Auto-regressive Inputs // Queueing Systems, 2003. Vol. 43. N. 1. P. 29-41.

¹⁸Кокс Д., Льюис П. Статистический анализ последовательностей событий. М.: Мир, 1969.

¹⁶Gaver D. P., Lewis P. A. W. First-Order Autoregressive Gamma Sequences and Point Processes // Advances in Applied Probability, 1980. Vol. 12. N. 3. P. 727-745.

¹⁷Lawrance A. J., Lewis P. A. W. An Exponential Moving Average Sequence and Point Process (EMA1) // Journal of Applied Probability, 1977. Vol. 14. N. 1. P. 98-113.

¹⁸Finch P. D. The Single-Server Queueing System with Non-Recurrent Input-Process and Erlang Service Time // Journal of the Australian Mathematical Society, 1963. Vol. 3. N. 2. P. 220-236.

¹⁹Finch P. D., Pearce C. A Second Look at a Queueing System with Moving Average Input Process // Journal of the Australian Mathematical Society, 1965. Vol. 5. N. 1. P. 100-106.

²⁰He J., Sohraby K. A New Analysis Framework for Discrete Time Queueing Systems with General Stochastic Sources // INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE., 2001. Vol. 2. P. 1075-1084.

аналог модели скользящего среднего. Так же, как и в упомянутых выше статьях, рассматривались случаи МА{1) и МА(2).

Авторегрессионные модели впервые были применены для описания трафика в телекоммуникационных сетях в статье Б. Маглариса и др.²¹, в которой рассматривалась передача видео. Там же показано, что параметры авторегрессионной модели можно достаточно легко вычислить, имея статистику по стационарному потоку данных. В работе Р. Эдди и М. Цу-кермана²² изучается время ожидания в системе обслуживания, входящий поток в которой описывается авторегрессионной моделью с гауссовскими инновациями. В статье Дж. Дэвиса и др.²³ показано, что авторегрессионные модели временных рядов хорошо подходят для описания коррелированных потоков данных, таких как видео с переменным битрейтом (VBR), а в работе Т. Чен и Т. Чена²⁴ авторегрессионные процессы используются также для моделирования беспроводного канала передачи данных.

В последние годы приобрело популярность использование моделей дискретной авторегрессии (DAR — Discrete AutoRegressive model) при анализе систем обслуживания. Класс моделей DAR(k) предложен в работе П. Джейкобса и П. Льюиса²⁵ как простой способ получения стационарной последовательности дискретных случайных величин с заданным распределением и задаваемой независимым образом корреляционной структурой. Процесс DAR(k) используется в большом числе работ как инструмент для описания входящего трафика в телекоммуникационных сетях. В качестве примеров приведём статью А. Элвалида и др.²⁶, где даётся анализ видеоконференц-трафика с переменным битрейтом (VBR) и моделирование его с помощью DAR(\) процесса, и статью Б. Рю и А. Элвалида²⁷, где процесс DAR(k) используется для моделирования видеотрафика. Модели DAR(k) применяются также для решения задач из других областей,

²¹ Maglaris В., Anastassiou D., Sen P., Karlsson G., Robbins G. Performance Models
of Statistical Multiplexing in Packet Video Communications // IEEE Transactions on
Communications, 1988. Vol. 36. N. 7. P. 834-844.

²² Addie R. 67., Zuckerman M. Performance Evaluation of a Single Server Autoregressive
Queue // Australian Telecommunication Research, 1994. Vol. 28. N. 1. P. 25-32.

²³Davis J., Chandra K., Thompson C. Nonlinear Time-Series Model for VBR Video Traffic // Local Computer Networks, 2000. LCN 2000. Proceedings. 25th Annual IEEE Conference on. IEEE, 2000. P. 678-683.

²ⁱChen T. P., Chen T. Markov Modulated Autoregressive Processes for Traffic and Channel Modeling // International Packet-Video Workshop PV 2002, 2002.

²⁵Jacobs P. A., Lewis P. A. W. Discrete Time Series Generated by Mixtures. Ill: Autoregressive Processes (DAR(p)). — Monterey, California: Naval Postgraduate School, 1978.

²⁶Elwalid A., Heyman D., Laksman T. V., Mitra D., Weiss A. Fundamental Bounds and Approximations for ATM Multiplexers with Applications to Video Teleconferencing // IEEE Journal on Selected areas in Communications, 1995. Vol. 13. N. 6. P. 1004-1016.

²⁷Ryu В. K., Elwalid A. The Importance of Long-Range Dependence of VBR Video Traffic in ATM Traffic Engineering: Myths and Realities // ACM SIGCOMM Computer Communication Review, 1996. Vol. 26. N. 4. P. 3-14.

например, для анализа корреляционной структуры последовательностей ДНК²⁸-²⁹.

В большинстве работ по теории массового обслуживания рассматривается частный случай — модель дискретной авторегрессии первого порядка (DAR(1)). В статьях Г. Хвана и К. Сохраби ³⁰ и Ф. Камуна ³¹ проведён анализ системы обслуживания DAR(1)\D\1, которая представляет собой систему с дискретным временем, в которой имеется одно обслуживающее устройство, входящий поток подчинён модели DAR(1), а время обслуживания постоянно и составляет один квант времени. Авторы получили аналитические выражения для распределения длины очереди в стационарном режиме и ряда других характеристик. Статья Г. Хвана и др.³² посвящена анализу времени ожидания для системы DAR(1)\D\1. В работе Б. Кима и др.³³ основные характеристики функционирования системы DAR(1)\D\1 в стационарном режиме изучаются методом вложенных цепей Маркова. Статья Б. Кима и К. Сохраби³⁴ посвящена анализу хвостов распределения длины очереди и времени ожидания для системы DAR(1)\D\1. В статье Б. Чоя и др.³⁵ изучена система DAR(1)\D\c с несколькими обслуживающими устройствами. Для моделей типа DAR(k)\D\1 с к > 1 на сегодняшний день получено лишь относительно небольшое число аналитических результатов. Отметим статью Д. Мяо и X. Ли^зе, в которой получены выражения для математического ожидания и дисперсии длины очереди для системы

²⁸Dehnert М., Helm W. Е., Hutt М.-Т. A Discrete Autoregressive Process as a Model for Short-Range Correlations in DNA Sequences // Physica A: Statistical Mechanics and its Applications, 2003. Vol. 327. N. 3. P. 535-553.

²⁹Dehnert M., Helm W. E., Hutt M.-T. Information Theory Reveals Large-Scale Synchronisation of Statistical Correlations in Eucaryote Genomes // Gene, 2005. Vol. 345. N. 1. P. 81-90.

³⁰Hwang G. U., Sohraby K. On the Exact Analysis of a Discrete-Time Queueing System with Autoregressive Inputs // Queueing Systems, 2003. Vol. 43. N. 1. P. 29-41.

³¹ Kamoun F. The Discrete-Time Queue with Autoregressive Inputs Revisited // Queueing Systems, 2006. Vol. 54. N. 3. P. 185-192.

³²Hwang G. U., Choi B. D., and Kim J.-K. The Waiting Time Analysis of a Discrete-Time Queue with Arrivals as an Autoregressive Process of Order 1 // Journal of Applied Probability, 2002. Vol. 39. No. 3. P. 619-629.

^S3Kim В., Chang Y., Kim Y. C, Choi B. D. A Queueing System with Discrete Autoregressive Arrivals // Performance Evaluation, 2007. Vol. 64. N. 2. P. 148-161.

^siKim В., Sohraby K. Tail Behavior of the Queue Size and Waiting Time in a Queue with Discrete Autoregressive Arrivals // Advances in Applied Probability, 2006. Vol. 38. N. 4. P. 1116-1131.

³⁶ Choi B. D., Kim В., Hwang G. U., and Kim J.-K. The Analysis of a Multiserver Queue Fed by a Discrete Autoregressive Process of Order 1 // Operations Research Letters, 2004. Vol. 32. N. 1. P. 85-93.

³⁶Miao D. W. C, Lee H. C. Second-Order Performance Analysis of Discrete-Time Queues Bed by DAR (2) Sources with a Focus on the Marginal Effect of the Additional Traffic Parameter // Applied Stochastic Models in Business and Industry, 2013. Vol. 29. No. 1. P. 45-60.

DAR(2)\D\1, и статью Дж. Ким и Б. Кима³⁷, посвященную анализу хвостов распределения длины очереди и времени ожидания для общего случая DAR(k)\D\l. Интересно отметить, что похожие модели возникают и при описании зависимостей в последовательности времён ожидания в непрерывных моделях. В работе В. Г. Ушакова и И. Г. Харитонцевой³⁸ рассмотрена система обслуживания типа M|G|1, в которой последовательность длительностей обслуживания внутри одного периода занятости подчинена непрерывному аналогу модели DAR(l). В работе получены формулы для распределения длины очереди и времени ожидания в стационарном режиме.

Цели и задачи исследования

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

Построить и исследовать модель системы массового обслуживания с непрерывным временем и входящим потоком авторегрессионного типа;

Обобщить модель на случай системы с относительным приоритетом;

Обобщить существующие результаты для систем обслуживания типа .DAR(A;)|.D|1 на случай обратной связи;

Провести анализ нестационарного режима функционирования системы массового обслуживания с обслуживанием регрессионного типа.

Научная новизна

Все основные результаты диссертации являются новыми. Теоретическая и практическая значимость

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

Использованные подходы и методы

³⁷Kim J., Кіт В. Regularly Varying Tails in a Queue with Discrete Autoregressive Arrivals of Order p // Queueing Systems, 2007. Vol. 56. N. 2. P. 93-102.

³⁸ Ушаков В. Г., Харитонцева И. Г. О системе с зависимыми временами обслуживания // Математическое моделирование и цифровая обработка информации. М.: МИЭТ, 1990. С. 154-163.

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

Положения, выносимые на защиту

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

3. Построена модель системы массового обслуживания типа M|G|1 с групповым поступлением требований, в которой последовательность размеров групп поступающих требований подчинена модели дискретной авторегрессии первого порядка. Проведён анализ нестационарного режима функционирования системы; получены соотношения, позволяющие найти распределение длины очереди в произвольный момент времени, а также ряд вспомогательных характеристик. Исследован стационарный резким функционирования системы; получены выражения для распределения и математического ожидания длины очереди.

4. Построено обобщение модели на случай системы с относительным приоритетом. Исследован нестационарный режим функционирования системы; получены соотношения, позволяющие найти распределение длины очереди в произвольный момент времени.

5. Рассмотрены системы массового обслуживания DAR(l)\D\l и DAR(2)\D\l с обратной связью. Проведён анализ функционирования систем в стационарном режиме; для системы DAR(l)\D\l с обратной связью получены формулы для распределения длины очереди, а для системы DAR(2)\D\l с обратной связью получено выражение для математического ожидания длины очереди.

6. Рассмотрена система массового обслуживания типа M|G|1, в которой времена обслуживания подчинены процессу регрессионного типа. Проведён анализ нестационарного режима функционирования системы, получены формулы для распределения длины очереди в произвольный момент времени.

Достоверность результатов

Достоверность результатов обеспечивается корректными доказательствами всех приведённых в работе утверждений.

Апробация работы

Результаты диссертации докладывались на семинарах "Аналитические методы в теории массового обслуживания" и "Теория риска и смежные вопросы" (неоднократно) кафедры математической статистики ВМК МГУ, а также на XXXIII международном семинаре по проблемам устойчивости стохастических моделей в г. Светлогорске Калининградской области.

Публикации

В основу диссертационной работы легли следующие статьи, опубликованные в журналах, рекомендованных ВАК:

7. Леонтьев Н. Д. Анализ нестационарного режима функционирования системы с зависимыми временами обслуживания // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика, 2013. N. 2. С. 20-25.

8. Леонтьев Н. Д., Ушаков В. Г. Анализ системы обслуживания с входящим потоком авторегрессионного типа // Информатика и её применения, 2014. Т. 8. Вып. 3. С. 39-44.

9. Леонтьев Н. Д., Ушаков В. Г. Исследование систем обслуживания с дискретным временем, входящим потоком авторегрессионного типа и обратной связью // Системы и средства информатики, 2015. Т. 25. N. 2. С. 60-70.

10. Леонтьев Н. Д. Анализ стационарного режима функционирования системы массового обслуживания с входящим потоком авторегрессионного типа // Вестник ТвГУ. Серия: Прикладная математика. 2016. N. 2. С. 39-48.

11. Леонтьев Н. Д., Ушаков В. Г. Анализ системы обслуживания с входящим потоком авторегрессионного типа и относительным приоритетом // Информатика и её применения, 2016. Т. 10. Вып. 3. С. 15-22.

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

Структура и объём

Диссертация состоит из введения, пяти разделов, заключения и списка литературы. Первый раздел содержит предварительные результаты, а разделы со второго по пятый составляют основную часть работы. Полный объём диссертации составляет 99 страниц. Список литературы содержит 44 наименования.

Модель дискретной авторегрессии первого порядка

Настоящий раздел содержит обзор предварительных результатов. В подразделе 1.1 определяется модель дискретной авторегрессии; обсуждается вопрос стационарности случайного процесса, задаваемого этой моделью, и его корреляционные свойства. Подробно рассматриваются свойства модели дискретной авторегрессии первого и второго порядка. Подразделы 1.1.1-1.1.3 изложены по [31], подраздел 1.1.4 — по [30], а подраздел 1.1.5 — по [39]. В подразделе 1.2 приводятся факты из теории аналитических функций, используемые в основной части диссертации. Формулировки теоремы единственности аналитической функции и теоремы Рупіє изложены по книге [9], а абелевой теоремы для преобразования Лапласа — по книге [20]. В подразделе 1.3, следуя статье [42], излагаются элементы теории матриц Копій. В подразделе 1.4 вводится общепринятая классификация систем массового обслуживания. Последующие подразделы посвящены изложению известных результатов для различных систем массового обслуживания: системы MG1 (подраздел 1.5, следуя [8]), системы типа MG1 с зависимыми временами обслуживания (подраздел 1.6, следуя [11]), системы Mx\G\1 (подраздел 1.7, следуя [10] и [25]), системы DAR(1)\D\1 (подраздел 1.8; часть подраздела, посвященная анализу длины очереди, приводится по [30] и [32], а часть, посвященная анализу времени ожидания — по [29]), системы DAR(1)\D\c (подраздел 1.9, следуя [15]), системы DAR(2)D1 (подраздел 1.10, следуя [39]) и системы DAR(k)\D\1 (подраздел 1.11, следуя [35]).

Пусть {Вп\пЄі — последовательность независимых и одинаково распределённых случайных величин, принимающих неотрицательные целочисленные значения. В дальнейшем будем предполагать, что случайные величины Вп имеют два первых момента. Величины Ап подчиняются модели дискретной авторегрессии порядка к (DAR(k)), если Ап = (1 - ап)Ап_Фп + апВп, п Є Z, (1-1-1) где {an}nez — последовательность независимых случайных величин, имеющих распределение Бернулли с параметром р, 0 р 1, {п}пєі, последовательность независимых случайных величин с распределением Р(п = і) = &, і =1,2,...,к; последовательности {an}nez, {Вп}пЄІі и {Ф„}гаЄй независимы. Иначе говоря, Вп с вероятностью р, An_i с вероятностью (1 — р) рі, А„. = Ап_2 с вероятностью (1 — р)(/?2, Ап_к с вероятностью (1 — р) рк. 1.1.2 Стационарность

Пусть 7г — распределение величин „. Можно показать, что существует начальное распределение для вектора (A-k+i, A_i,A0) такое, что последовательность {Ап} будет стационарной с маргинальным распределением п.

Обозначим r{m) = corr(Ara+m, Ап). Легко видеть, что COV(AH-I, Ап) = Е[Ап+1Ап] - ЕАп+1ЕАп = = Е[(1 — ап+і)Ап+і_фп+1Ап] + Щап+іВп+іАп] — ЕАп+іЕАп = = (1 - p) iEA2n + (1 - р) 2Е[Ап_1Ап] + ... + (1 - р) ркЕ[Ап_к+1Ап]+ + рЕВп+1ЕАп - ЕАп+1ЕАп = (1 - p) icov(An, Ап)+ + (1 - p)tp2cov(An_i, Ап) + ... + (1 - p)tpkcov(An_k+i, Ап). Отсюда г(1) = (1 - р) р!г(0) + (1 - р) р2г(1) + ... + (1 - р) кг(к - 1). Действуя аналогичным образом, можно получить систему уравнений Юла-Уокера: г(0) = 1, г(1) = (1 - р) іг(О) + (1 - р)(р2г(1) + . г(2) = (1 - р) іг(І) + (1 - р) г(О) + . .. + (1 -р)іркг{к- 1), .. + (1-р)(ркг(к-2), г(к) = (1 - р) ріг(к - 1) + (1 - р)р2г(к - 2) + ... + (1 - р) ркг(0), и, для / 1, r(fc + /) = (!- p) ir(fc + /-!) + (!- p) 2r{k + / - 2) + ... + (1 - p) pkr(l). 1.1.4 Модель дискретной авторегрессии первого порядка Рассмотрим важный частный случай — модель дискретной авторегрессии первого порядка. Пусть {-Е га}га о — последовательность независимых и одинаково распределённых случайных величин, принимающих неотрицательные целочисленные значения. Модель дискретной авторегрессии первого порядка (DAR(1)) определяется при помощи уравнения регрессии, а именно для п 0 Л) = в0, Ап+1 = (1 - ап+і)Ап + ап+гВп+1, п 0, (1-1.2) где {o!ri}ra i — независимые случайные величины, имеющие распределение Бернулли с параметром р, 0 р 1; последовательности {о;га}га і и {Вп}п 0 независимы. Заметим, что уравнение регрессии (1.1.2) неформально может быть записано следующим образом Ап-\-\ = Вп+і с вероятностью р, Ап с вероятностью 1 — р. Используя уравнения Юла-Уокера, выведенные выше, легко получить выражение для автокорреляционной функции последовательности {Ап}п 0: г (га) = сотт(Ап+т,Ап) = (1 - р)т для га = 0,1, 2,... 1.1.5 Модель дискретной авторегрессии второго порядка Рассмотрим ещё один частный случай — модель дискретной авторегрессии второго порядка. Пусть {Вп}пе% — последовательность независимых и одинаково распределённых случайных величин, принимающих неотрицательные целочисленные значения. Модель дискретной авторегрессии второго порядка (DAR(2)) определяется при помощи уравнения регрессии Ап = (1 - ап)Ап_Фп + апВп, п Є Z, (1.1.3) где {«и}nez — последовательность независимых случайных величин, имеющих распределение Бернулли с параметром р, 0 р 1, {Фп}п& — последовательность независимых случайных величин с распределением Р(Фп = г) = ірі, г = 1,2,и(/?1 + (/?2 = 1; последовательности {n}nez, {ri}raez и {Ф„}гаЄй независимы. Другими словами, п определяется как

Очевидно, что (1) является частным случаем (2) при 2 = 0. Изучим более подробно, как введение дополнительного параметра влияет на характеристики модели. Из уравнений Юла-Уокера следует, что автокорреляционная функция последовательности {п} имеет вид Обозначим () = ()/( — 1) для 1. Величина 1 — () называется темпом затухания автокорреляционной функции. Легко видеть, что для модели {1) {) = 1 — . Нас будет интересовать предельное значение темпа затухания, поэтому введём ещё одно обозначение: (оо) = Игл (). Тогда асимптотический темп затухания будет определяться

Утверждение 2 демонстрирует, что автокорреляционная функция модели (2) имеет, как правило, более медленный темп затухания, чем (1). Первый пункт утверждения даёт достаточное условие, выполнение которого обеспечивает более медленный темп затухания автокорреляционной функции модели (2) по сравнению с (1) для случая 2 оо. Во втором пункте утверждается, что при — оо автокорреляционная функция модели (2) имеет более медленный темп затухания, чем (1), для всех значений 2-Другими словами, начиная с некоторого выполнено () ()\ 2=о , это означает, что () имеет более тяжёлый хвост для модели (2), чем для (1). 1.2 Факты из теории аналитических функций

Система с обслуживанием авторегрессионного типа

Рассмотрим одноканальную систему обслуживания, в которую поступают два потока требований. Первый поток — пуассоновский с интенсивностью а\, а второй поток является пуассоновским потоком групп требований. Интенсивность поступления групп требований равна а2. Группа состоит из случайного числа требований и содержит к требований с вероятностью hk, к = 1,..., М. Между размерами двух последовательно поступающих групп требований имеется следующая зависимость: размер п-й поступающей группы требований либо с вероятностью 0 р 1 равен размеру п — 1-й группы, либо с вероятностью 1 — р является независимой от него случайной величиной. Требования из первого потока имеют относительный приоритет по отношению к требованиям из второго потока. Иными словами, требования из второго потока могут поступать на обслуживание только при отсутствии в очереди требований из первого потока. Будем считать, что число мест для ожидания не ограничено, а длительность обслуживания требований г-го потока имеет функцию распределения ВІ(Х) с плотностью bi(x) и преобразованием Лапласа /5j(s).

Определим следующие случайные процессы: I{t) — номер потока, требование из которого обслуживается в момент t; Li(t) — число требований г-го потока в системе в момент времени t;

X{t) — время, прошедшее с начала обслуживания требования, находящегося на обслуживании в момент t5; N(t) — размер последней поступившей в систему до момента t группы требований 2-го потока. Положим д Pi(nun2, к, х, t) = Q P(Ht) = г, Lxit) = щ, L2(t) = п2, N(t) = к, X(t) х), Р(0, к, t) = P(Li(t) = 0, L2(t) = 0, N(t) = к). 5В случае, когда система свободна, можно для определенности положить I(t) = 0 и X(t) = 0. Обозначим

Формулы для определения 7Ti(zi, z2, к, х, s) и их вывод содержатся в следующей основной теореме. [7] Функции щ(гі, z2, k, х, s) при \z\\ 1, \z2\ 1, k = 1,..., M, x 0, Re (s) 0 определяются no следующим формулам:

Это линейная система дифференциальных уравнений первого порядка с постоянными коэффициентами. Принимая во внимание результат леммы, приведенной ниже, решение системы можно записать в виде м TTi(z1,z2,k,x,s) = 2Ci n(z1, z2, s)ukn(z2) exp(-(s + - a1z1 + a2 - Xn(z2))x), (3.2.20) n=l где Xk(z2) = Xk(z1,z2,s) + (s + ai - a1z1 + a2), к = 1,...,M; X\(zi, z2, s),..., \M(Z\, Z2, S) — собственные значения матрицы системы, а u\{z2) = (un(z2),... ,uMi(z2))T,... ,UM(Z2) = (uiM(z2),... ,UMM(Z2))T — соответствующие собственные векторы. Заметим, что матрицы систем дифференциальных уравнений для 7Ti(zi,z2,k,x,s) и 7r2(zi, z2, к,х, s) одинаковы, а следовательно, собственные значения и собственные векторы в записи решений совпадают.

Обе части уравнения являются аналитическими в области \z\\ 1 функциями. Имеем, с учётом леммы, \/3i(s + аг - axzx + а2 - K(z2))\ /Зі(Re (s + аг - axzx + a2 - Ara(z2))) /3i(Re(s)) 1 = zi при \z\\ = 1. В силу теоремы Рупіє отсюда следует, что функциональное уравнение (3.2.26) имеет единственное решение z\ = ziyU(z2,s), причем функция ziyU(z2,s) является аналитической в области \z2\ 1 х Re (s) 0.

Подставляя z\ = Z\,n[z2)s) в уравнение (3.2.25), получим C\n(zhn(z2, s),z2, s) (і - z2l(32{s + аг - a1zhn(z2, s) + a2 - \n{z2))\ = M _ Y[{K{z2) -pa2zl2) M , , , , _ i=\ V 0m\Zl,n{Z2, S) Z2, S) ( M „ „ 1 T ,_ ч „„ _m [A.Z.Zf) П (K(z2) - х3Ы) m=l ХпЫ 2ZT 3 =1 откуда C2tn\Z\tn\Z2, s), z2, s) 1 - z2 1/32(s + ai - aizhn(z2, s) + a2 - \n{z2)) M _ mK(z2) - pa2zl) M i=\ ST Om{Zitn{Z2, S), Z2, S) ilto-«-i K(z2)-pa2zip 3 =1 Заметим, что TT2(ZI, z2,k,x, s), а значит и C2;ra(zi, z2, s), не зависит от z\. Из этого факта вытекает, что можно записать C2yn\Zl, z2,s) = 1 - z2 1/32(s + ai - aizi n(z2, s) + a2- \n{z2)) M _ Y[(K(z2) -pa24) M , ( ( л л .i=l V Om{Zl,n{Z2,S),Z2,S) , . 3 =1 Подставляя (3.2.28) в (3.2.25), будем иметв Ci,n(zi,z2, s) (і - z±ll3i{s + ai- aizi + a2 - Ara(z2))J = M _ Y[(\n(z2) - pa2z\) M , M EfT-; -(&m( l 2,s) П (А„Ы - ХІШ) m=l ХпЫ 2ZT i=i 1 - Z21/32(s + ax- axzx + a2 - Xn(z2)) 1 - Z2l(52{s + ai- aizhn(z2, s) + a2- \n{z2)) TO ЄСТВ Cl,n{Zl, z2, s) -i Ara z2 - pa2z \ 1 - z1 lf3i(s + ai - a\Z\ + a2 - \n(z2)) M 1 . m-i K(z2) - pa2z V m П {Ki{z2) - PCl2Zl2) M bm(zi,n(z2, s),z2, s) , (3.2.29) U(Uz2)-\M))m=lXn{z2) 2zn2 3 =1 1 - z2 1/32(s + ai - axzx + a2 - \n(z2)) -bm(zhn(z2,s),z2,s) 1 - z2 1/32(s + ai- ciizhn(z2, s) + a2- \n(z2)) Остается найти тг0(т, s), m = 1,..., M. Рассмотрим уравнение z2 = /32(s + ai- aizhn(z2, s) + a2- \n{z2)). (3.2.30) Обе части уравнения являются аналитическими в области \z2\ 1 функциями. Имеем, с учётом леммы, /52(s + аг - aizi n(z2, s) + а2 - Xn(z2))\ /32(Re (s + ai- aizhn(z2, s) + a2 - \n{z2))) /52(Re(s)) 1 = \z2\ при \z2\ = 1. В силу теоремы Рупіє отсюда следует, что функциональное уравнение (3.2.30) имеет единственное решение z2 = z2tn(s), причем функция z2tn(s) является аналитической в области Re (s) 0.

Стационарный режим

Рассмотрим систему массового обслуживания, в которой в течение интервала (п - 1, тт.) обслуживается одно требование и поступает Ап требований. Будем считать, что Ап подчиняется модели дискретной авторегрессии первого порядка (см. подраздел 1.1.4). Обозначим (3(z) производящую функцию случайной величины Ап, т. е. (3(z) = EzAn, а также Ъ\ = ЕАп, &2 = ЕА . Также предположим, что каждое обслуживание может с вероятностью q О оказаться "неудачным", вследствие чего обслуженное требование возвращается обратно в очередь.

Обозначим Ln число требований в системе в момент п. Эволюция Ln задаётся уравнением Ьп+1 = max(Lra - fn+1, 0) + Ап+1, где {fn}n i — последовательность независимых бернуллиевских случайных величин с параметром 1 - q. Можно показать, что последовательность {(Ln, An)}n i является цепью Маркова. Для \z\ 1, \w\ 1 обозначим Lpn(z,w) совместную производящую функцию вектора (Аг Ап): Lpn(z,w) = Е [zL"wAn] . Будем считать, что Ъ\ 1 — q. При этом условии можно осуществить предельный переход: tp(z,w) = lim tpn(z,w). -ормула для определения tp(z,w) и её вывод содержатся в п— оо следующей теореме. Теорема 4.1.1. В предположении Ъ\ 1 - q для z таких, что \z\ 1 и (1 -p)\q+ 1, и w таких, что \w\ I, справедливо p(z,w) = (1-q-h) (і --) х (л \и f \ , І і , ( , 1 Ч\ (l-p)hi(z)+ph2(z,l) (1 - p)ln(z) + р [ 1+ [q+-) , x_q, h2(z,w) где h1(z) = Y,(±-p)n( i+ -) , п=0 \ Z / ОО , -. ч п „-п V - / Доказательство. Выпишем ipn+i(z,w): pn+1(z,w) = Е [ZLn+1WAn+1 ] = Е [zx(tI1-/„+1,0) w l-Q„+1)4„+an+1B„+1 = = РЕ max(L„-/„+1)0) w S„+1j + (1 - р)Е max(L„-/„+1)0) w „j _ Преобразуем первое слагаемое: g Г тах(п-/п+ь0Ь \Bn+i" _ j max(Ln-/n+i,0)Е( гу)Бп+1 = = {gEzL" + (1 - Ez111 "1 0) } E(zw)B"+1 = = {qEzL" + (1 - q)E - (l{L„=o} + 1{L„ O} )]} E(zW) = = {gEzL" + (l-q) ( El{Ln=0} + E [ "" {L o} ])} E(zw)B = = jgEzL" + (l-q) (ЕІ{ЬП=0} + ( EzL" - El{Ln=0} )) } x xE(zw)B = {(Q+ ]--) VzL" + (l-q) (l- M El{Ln=0} x xEH 1 = {(? + - ) z !) + (!- 9) f1 - I) P(Ln = 0)\p(zw). Второе слагаемое7: E max(L„-/„+1)0) w „j = gE [ «( )A,] + (X - g)E max(Ln-l,0) ( )A,] = = gE [zL"(zW)A"] + (1 - q)E [z n-i,o){zw)An ( 1{Ln=Q} + i{Ln 0} )] = = qE [zL-(zw)A-] + (l-q) ( El{Ln=0} + E [zL"-\zw)A"l{Ln 0} ]) = = qE [zL"(zw)A"] +{l-q) ( El{Ln=0} + ± ( E [zL"(zW) ] - El{Ln=0} ) ) = = (9 + - ) E l + (1 - 9) (l - I) El{Ln=0} = = U + Ц- ) (fn(z, zw) + (l-q)(l- -\ P(Ln = 0). 7Здесь мы воспользовались тем, что Ln = 0 влечет Ап = 0. Тем самым Prn-i(z, w) = р { [ q + ]- Л pn(z, 1) + (1 - q) (і - Ч P(Ln = 0) } (3{zw)+ +(1 -P) { [ q+ -1) Mz,zw) + (l-q) (l- ] P(Ln = 0) } = = (l-p)(l-q) (l--z)P(Ln = 0)-+p[(l-q)[l- )p(Ln = 0)+ (q+ -A tpn(z, 1) ) P(zw)+ +(i -p) (q + ) Pn(z, zw). При условии Ъ\ 1 - q можно осуществить предельный переход: p(z,w) = (l-p)(l-q) (l- \l0+ +Р ( (1 -q)U- A lo+ (q+ 1--\ ф, 1)) P(zw)+ +(i -р) \ q + ) p(z,zw), где /о = Игл P(L„ = 0). Для z таких, что (1 - p)\q + —f-\ 1, уравнение можно переписать в виде p(z,w) = (1 -р)(1 -q)(l- ) l0h1(z)+ +Р ( (1 - Q) ( 1 - I) k + (q + - ) ( , 1) ) /i2(z, w), (4.1.1) где n=0 h2(z,w) = J2 -p)n(q + -1) P(zn+lw). n=0 \ Z J Подставив в (4.1.1) w = 1, получим , n (1 -P)(I - q) ( 1 - i) /ofei( ) +P(1 - g) ( 1 - Й W , 1) V[Z,) l-p(q+ )h2(z,l) Перепишем полученное выражение: (p(z, l)(z-p(qz + l- q) h2(z, 1)) = (1 - p)(l - q) (z - 1) /0M )+ + p(l-g)(z-l)/0/i2 ,l). (4.1.2) Дифференцируя (4.1.2) по z и подставляя в полученное выражение z = 1, получим /о = 1 - -г— Ъ\. Тем самым и 1—q ( лл (л .ч Л 1 1-р )fei )+ph2 (z, 1) \ ZJ i-p{q + -f)h2(z,i) Наконец, подставив (4.1.3) в (4.1.1), после некоторых преобразований получим: (4.1.3) ip{z,w) = (1 -q-bi) ( 1 - - I х (л \и f \ , и,! , 1-я\ (l-p)hi(z)+ph2(z,l) / 1-P« + T ,1) Теорема доказана. Следствие 4.1.1. Мы получили выражение для производящей функции длины очереди в стационарном режиме: lim EzLn = p(z, 1) = (1 - f - 1\ (l-p)/n(z)+p/i2(z,l) 9 Ч z) l-p(q+l- )h2(z,l) (4.1.4) Подставляя в (4-1-4) 9 = 0, получим аналогичный результат для системы без обратной связи: lim Е = (1 - 6,) f 1 - -) -P)Mz)+ph2(z,l) n oo z) l-fh2(z,l) (4.1.5)

Следствие 4.1.2. Дифференцируя (4-1-2), можно получить выражение для математического ожидания длины очереди в стационарном режиме: lim EL„ = - q - 6i p 62-262 + b! , (l-p)62 (l-p)(l-q)b1 p (4.1.6) Аналогичный результат для системы без обратной связи примет вид lim ELK I-61 62-262 + 6! , (1-р)62 (l-p)6i Р Р (4.1.7) Отметим, что (4.1.5) и (4.1.7) соответствуют результатам статьи [2].

Рассмотрим теперь систему массового обслуживания типа DAR(2)D1, то есть систему, в которой входящий поток групп требований, задаваемый последовательностью Ап, подчиняется модели дискретной авторегрессии второго порядка (см. подраздел 1.1.5). В остальном рассматриваемая система аналогична изученной выше. Нашей задачей будет нахождение математического ожидания длины очереди в стационарном режиме8.

Обозначим Ln число требований в системе в момент п. Эволюция Ln задаётся уравнением Ьп+1 = max(Lra - fn+1, 0) + Ап+1 = Ln - Un+i + An+1, (4-2.1) где {fn}n i — последовательноств независимых бернуллиевских случайнвіх величин с параметром 1 - q, Un+l = l{Ln 0}l{/n+1 o}. Будем считатв, что Ъ\ 1 - q. Сделаем дополнителвное предположение Р(Ап = 1) = 0, которое позволит нам получитв необходимые резулвтатві в явном виде. Докажем сначала следующее вспомогателвное утверждение.

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

Обозначим L(ip2) математическое ожидание длины очереди в стационарном режиме как функцию от р2 Следствие 1.10.1. Функция L(tp2) обладает следующими свойствами: L является вогнутой функцией ір2, достигающей максимума при р2 1. Если р 1 b2 , тпо L достигает максимума при р 2 таком, что 0 р2 1. В этом случае L(tp2) является возрастающей функцией на отрезке [О, ]. Формула для второго момента длины очереди в стационарном режиме даётся в следующей теореме.

Теорема 1.10.2. В предположении Р(Ап = 1) = 0 математическое ожидание квадрата длины очереди в стационарном режиме определяется по формуле

Рассматривается система массового обслуживания с дискретным временем, в которой в течение интервала (п — 1, тт.) обслуживается одно требование и поступает Ап требований, причём Ап подчиняется модели дискретной авторегрессии порядка к. Предполагается, что требования, поступившие в течение разных интервалов, обслуживаются в порядке поступления; требования, поступившие в течение одного интервала обслуживаются в случайном порядке. Мы также предполагаем, что последовательность {Ап} является стационарной и р = ЕАп 1.

Дадим несколько определений. Будем называть интервал с номером п ведущим, если ап = 1. Предположим, что интервал п является ведущим и п т. Будем говорить, что интервал п ведёт интервал га, если Ап определяет Ат из уравнения регрессии. Более формально, интервал п ведёт интервал га, если существует / 0 и целые числа п0, щ,..., щ такие, что п = щ п\ ... щ = га и выполнено аПі = 0 и ФПі = щ — Щ-і, і = 1,..., п. Очевидно, что ведущий интервал ведёт самого себя. С каждым ведущим интервалом можно связать набор всех интервалов, которые он ведёт. Этот набор мы будет называть 1-набором.

Определение. Распределение случайной величины V имеет правильно меняющийся хвост порядка —7 (т 0), если P(V х) x (F(x) при х — со, где F{x) — медленно меняющаяся функция, т. е. F{x) измерима по Лебегу, Зжо 0 : F(x) 0 Ух XQ И lim JL XJ = 1 для всех Л 0. F(Xx) F(x) Всюду далее запись f{x) д{х) при х — оо эквивалентна следующему предельному соотношению: lim ЦЩ = 1.

Теорема 1.11.1. Пусть /3 0. Предполагается, что распределение входящего потока имеет правильно меняющийся хвост порядка —/3 — 1, то есть Р(Вп х) x l3 1F(x) при х — оо для некоторой медленно меняющейся функции F(-). Тогда время ожидания W произвольного требования и длина очереди L в произвольный момент времени имеют правильно меняющиеся хвосты порядка —/3:

Следствие 1.11.1. Рассмотрим систему обслуживания Geox\D\l, в которой требования прибывают в соответствии с групповым потоком Бернулли, а время ожидания составляет один интервал. Если число требований, прибывающих за один интервал, В, имеет правильно меняющийся хвост порядка —/3 — 1, то есть Р(В х) x l3 1F(x) при х — оо для некоторой медленно меняющейся функции F(-), то время ожидания произвольного требования и длина очереди в произвольный момент времени имеют правильно меняющиеся хвосты порядка —/3: гдер = ЕВ. 2 Система с непрерывным временем и входящим потоком авторегрессионного типа

Настоящий раздел посвящен анализу системы обслуживания с непрерывным временем и входящим потоком авторегрессионного типа. Основные результаты для нестационарного режима опубликованы в статье [5], а для стационарного режима — в статье [4].

Рассмотрим систему обслуживания, состоящую из одного обслуживающего устройства, на которое поступает простейший поток групп требований с интенсивностью . Будем считать, что число мест для ожидания не ограничено, а длительность обслуживания требований имеет распределение с плотностью {) и преобразованием Лапласа (). Поступающие в систему группы требований могут иметь размер 1,..., с вероятностями соответственно \,..., м- При этом размер й поступившей в систему группы требований с вероятностью О 1 равен размеру ( — 1)-й, либо с дополнительной вероятностью 1 — является независимой от него случайной величиной.

Определим следующие случайные процессы: {) — число требований в системе в момент ; {) — время, прошедшее с начала обслуживания требования, находящегося на обслуживании в момент ; () — размер последней поступившей в систему до момента группы требований.

Формула для определения (,,,) и её вывод содержатся в следующей основной теореме. 3В случае, когда система свободна, можно для определенности положить X(t) = 0.