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

Леонтьев, Николай Дмитриевич

Исследование систем массового обслуживания с параметрами регрессионного типа тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат наук Леонтьев, Николай Дмитриевич

Леонтьев, Николай Дмитриевич
кандидат наук
2017

Специальность ВАК РФ01.01.05

Количество страниц 99

Леонтьев, Николай Дмитриевич. Исследование систем массового обслуживания с параметрами регрессионного типа: дис. кандидат наук: 01.01.05 - Теория вероятностей и математическая статистика. Москва. 2017. 99 с.

Оглавление диссертации кандидат наук Леонтьев, Николай Дмитриевич

Оглавление

Введение

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

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

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

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

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

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

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

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

1.3 Матрицы Коши

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

1.5 Система М|G|1

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

1.7 Система Мх|G|1

1.8 Система DAR(1)IDI1

1.9 Система DAR(1)lDlc

1.10 Система DAR(2)IDI1

1.11 Система DAR(k)IDl1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

Введение диссертации (часть автореферата) на тему «Исследование систем массового обслуживания с параметрами регрессионного типа»

Введение

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

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

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

Важную роль в моделировании и оценке качества функционирования телекоммуникационных систем играет теория массового обслуживания, В соответствующих моделях поток информации на буфер (входящий поток или поток требований) описывается при помощи задания распределения времени между последовательным поступлением групп пакетов {групп требований) и распределения размеров этих групп. Обычно предполагается, что размеры групп требований являются независимыми и одинаково распределёнными дискретными случайными величинами. Однако в ряде ситуаций необходимо рассматривать более сложные конструкции входящего потока — так называемые модели коррелированного входящего потока, в рамках которых размеры последовательно поступающих групп могут быть зависимыми, Уход пакетов информации из буфера (процесс обслуживания) характеризуется распределением времён обслуживания, числом выходных каналов ( обслуживающих устройств) и очерёдностью передачи пакетов (дисциплиной обслуживания). Обычно предполагается, что требования обслуживаются в порядке поступления (дисциплина обслуживания К( Т'Я — Гкв^Соте-Гкв^Зегуес!), однако в ряде приложений необходимо рассматривать другие дисциплины обслуживания, в том числе приоритетные. Емкость буфера обычно считается бесконечной, что существенно упрощает анализ соответствующих математических моделей. Это предположение допустимо в силу того, что в большинстве реальных систем связи ёмкость выбирается таким образом, чтобы сделать вероятность потери пакетов информации очень малой [13],

В эмпирических работах, посвященных анализу трафика в сетях с коммутацией пакетов, показано, что размеры групп поступающих пакетов в ряде случаев оказываются коррелированными по времени [27, 40], Примером коррелированного потока данных является видео с переменным битрейтом (УВЕ), В УВЕ видео кадры генерируются в детерминированные моменты времени. Интервал времени между двумя кадрами для стандарта 11.201 составляет 1/24 секунды, а число бит в одном кадре является случайным. Сначала кодировщик генерирует один ключевой кадр (1-кадр), а последующие кадры кодируются как разностные кадры (Р-кадры) [17]. Кадры разбиваются на квадратные макроблоки, и тип ссылки для каждого из макроблоков определяется индивидуально, но с ограничением, заданным типом всего кадра, Ключевые кадры могут содержать только независимо сжатые макроблоки, а разностные — как независимо сжатые макроблоки, так и макроблоки со ссылкой на другой ключевой или разностный кадр [44], Как следует из названия, разностные кадры несут информацию только об изменяющихся областях. Такой режим кодирования приводит к возникновению корреляции числа бит в последовательных Р-кадрах [24],

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

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

щего потока. Ещё один пример — так называемый составной входящий поток (train arrivals), который характеризуется тем, что ширина сессии для него составляет один пакет,

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

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

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

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

Основополагающей работой в области анализа временных рядов считается классическая книга Дж, Бокса и Г, Джепкипса [1], в которой был разработан систематический подход к анализу гауссовских временных рядов (GTS — Gaussian-based Time Series), Традиционные модели GTS используют в качестве входного сигнала белый гауссовский шум; в результате,

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

Изучению общих, негауссовских временных рядов посвящена обширная литература. Отметим книгу Д. Кокса и П. Льюиса [2], в которой разработан общий подход к их статистическому анализу, и статьи [26] и [37], где рассматриваются временные ряды, основанные на различных процессах инноваций.

Несмотря на относительную простоту и существующую успешную практику применения моделей временных рядов в различных областях анализа данных, подобные модели до недавнего времени не находили широкого применения в теории массового обслуживания. Тем не менее, стоит отметить ряд статей. В случае непрерывного времени, в работах [22] и [23] рассмотрена система обслуживания MAIM|1, в которой последовательность промежутков между поступлением требований подчинена модели скользящего среднего (МЛ — Moving Average), а длительности обслуживания имеют экспоненциальное распределение. Авторы рассмотрели случаи МА(1)ъ МА(2) и получили явные выражения для хвоста распределения длины очереди. Использованный в статьях подход может быть применён для анализа систем обслуживания с входящим потоком, задаваемым моделью скользящего среднего любого конечного порядка. В случае дискретного времени, в статье [28] рассмотрен дискретный аналог модели скользящего среднего. Так же, как и в упомянутых выше статьях, рассматривались случаи МА(1)ъ МА(2).

Авторегрессионные модели впервые были применены для описания трафика в телекоммуникационных сетях в статье [38], в которой рассматривалась передача видео. Там же показано, что параметры авторегрессионной модели можно достаточно легко вычислить, имея статистику по стационарному потоку данных. В работе [12] изучается время ожидания в системе обслуживания, входящий поток в которой описывается авторегрессионной моделью с гауссовскими инновациями. В статье [17] показано, что авторегрессионные модели временных рядов хорошо подходят для описания коррелированных потоков данных, таких как видео с переменным битрейтом (VBR), а в работе [14] авторегрессионные процессы используются также для моделирования беспроводного канала передачи данных.

В последние годы приобрело популярность использование моделей дискретной авторегрессии (DAE — Discrete AutoRegressive model) при анализе систем обслуживания. Класс моделей DAR(k) предложен в работе [31] как простой способ получения стационарной последовательности дискретных случайных величин с заданным распределением и задаваемой независимым образом корреляционной структурой. Процесс DAR(k) используется в большом числе работ как инструмент для описания входящего трафика в телекоммуникационных сетях. В качестве примеров приведём статью [21], где даётся анализ видеоконференц-трафика с переменным битрейтом (VBR) и моделирование его с помощью DAR(1) процесса, и статью

[41], где процесс ИАЯ(к) используется для моделирования видеотрафика. Модели ИАЯ(к) применяются также для решения задач из других областей, например, для анализа корреляционной структуры последовательностей ДНК [18, 19],

В большинстве работ по теории массового обслуживания рассматривается частный случай — модель дискретной авторегрессии первого порядка (ОАЯ(1)). В статьях [30] и [32] проведён анализ системы обслуживания ДАД(1)|Д|1, которая представляет собой систему с дискретным временем, в которой имеется одно обслуживающее устройство, входящий поток подчинён модели ИАЯ(1), а время обслуживания постоянно и составляет один квант времени. Авторы получили аналитические выражения для распределения длины очереди в стационарном режиме и ряда других характеристик. Статья [29] посвящена анализу времени ожидания для системы ДАД(1)|Д|1, В работе [34] основные характеристики функционирования системы ДАД(1)|Д|1 в стационарном режиме изучаются методом вложенных цепей Маркова, Статья [36] посвящена анализу хвостов распределения длины очереди и времени ожидания для системы ИАЯ(1)1 Д|1. В статье [15] изучена система 0АЯ(1)10|с с несколькими обслуживающими устройствами. Для моделей типа с к > 1 па сегодняшний день

получено лишь относительно небольшое число аналитических результатов. Отметим статью [39], в которой получены выражения для математического ожидания и дисперсии длины очереди для системы ДАД(2)|Д|1, и статью [35], поевящённую анализу хвостов распределения длины очереди и времени ожидания для общего случая Интересно отметить,

что похожие модели возникают и при описании зависимостей в последовательности времён ожидания в непрерывных моделях, В работе [11] рассмотрена система обслуживания типа М|С|1, в которой последовательность длительностей обслуживания внутри одного периода занятости подчинена непрерывному аналогу модели ИАЯ(1). В работе получены формулы для распределения длины очереди и времени ожидания в стационарном режиме. Более подробное описание постановок задач и основных результатов для систем обслуживания, основанных на моделях авторегрессионного типа, приведено в следующем разделе. Цели и задачи исследования

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

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

• Обобщить существующие результаты для систем обслуживания типа 0АЯ(к)1011 на случай обратной связи;

•

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

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

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

Теоретическая и практическая значимость

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

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

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

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

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

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

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

3, Рассмотрены системы массового обслуживания 0АК(1)1011 и 0АК(2)1011 с обратной связью. Проведён анализ функционирования систем в стационарном режиме; для системы 0АЯ(1)1011 с обратной связью получены формулы для распределения длины очереди, а для системы 0АЯ(2)1011 с обратной связью получено выражение для математического ожидания длины очереди,

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

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

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

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

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

Публикации

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

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

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

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

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

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

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

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

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

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

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

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

Определение. Пусть {Вп}пе. — последовательность независимых и одинаково распределённых случайных величин, принимающих неотрицательные целочисленные значения. Будем предполагать, что случайные величины Вп имеют два первых момента, Величины Ап подчиняются модели дискретной авторегрессии порядка к (ОАЯ(к)), если

Ап = (1 — ап)Ап-фп + апВп, п е

где {ап}п^1 — последовательность независимых случайных величин, имеющих распределение Бернулли с параметром р, 0 < р < 1, {Фп}пе1 ~ последовательность независимых случайных величин с распределением

Р(Фп = г) = Рг, г =1, 2,...,к;

последовательности [ап}пе., {Вп}пе. а {Фп}пе. независимы. Иначе говоря,

Вп с вероятностью р, Ап-1 с вероятноетыо (1 — р)^1, А„ = Ап-2 с вероятное тыо (1 — р)^2,

Ап-к с вероятное тыо (1 — р)^к.

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

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

Даётся общепринятая классификация систем массового обслуживания, предложенная Д. Кендаллом, и приводится обзор результатов для двух классических систем: М|С|1 и Мх |С|1, а также ряда систем с параметрами регресс ионного типа: ОАК(1)1ВЦ ПАН(1)1П1с, 0АК(2)1011 и более общей ИАН(к)1 И|1, а также системы типа М|С|1 с зависимыми временами обслуживания.

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

Рассматриваемая система обслуживания состоит из одного обслуживающего устройства, на которое поступает простейший поток групп требований с интенсивностью а; число мест для ожидания не ограничено, а длительность обслуживания требований имеет распре-

деление с плотностью Ь(х) и преобразованием Лапласа 3(в). Поступающие в систему группы требований могут иметь размер 1,..., М с вероятностями соответственно Н\,... ,Нм- При этом размер п-й поступившей в систему группы требований с вероятностью 0 < р < 1 равен размеру (п _ 1)-й, либо с дополнительной вероятностью 1 — р является независимой от него случайной величиной.

Определяются случайные процессы: Ь(Ь) — число требований в системе в момент ¿;

X(1) — время, прошедшее с начала обслуживания требования, находящегося на обелужива-

N(1) — размер последней поступившей в систему до момента Ь группы требований. Вводятся обозначения:

д

р (п, к, х, г) = — р (Ш) = п, N (г) = к, X (г) < х), х

р (п, к, г) = Р(Щ = п, N (г) = к)

те

к(г, к, х, в)=У^ гп I е-а1р (п,к,х, г)сИ, -о(к, в) = I е-а1Р (0,к, г)сИ

тете п

-(г, к, х, в) = гп /

п=1 {

при |г| < 1, Яе ( 5 ) > 0,

Доказывается следующая основная теорема, в которой даётся формула для определения к(х, к, х, в).

Теорема 2.2.1. Функция к (г ,к,х, з) при |г| < 1, к = 1,...,М, х > 0, И,е (в) > 0 определяется, по формуле

к(г, к, х, в) = (1 — В(х)) ^^ Сп(г, в)£-—_ еХр ^8 + а _ х^

п=1

где

м . х

Л П [К^ _ ра г1) м и ( \

Сп(г,8) = :--777Г -Г-7 Ъ

1 _ *-13 (5 + « _ ^ П (К(г) _ \(г)) ™=1 А"(г) _ ра^

3 = 1 V '

3=п

Ьт(г, в) = _(в + а)-о(т, в) + кт +

'\1(х),..., \м(г) определяются, из уравнения

м мм

П [ра^ _ X) + ^(1 _ р)Ыаг* Д (раг_ л) = 0

м

т

рк0(т, в)агт + (1 _ р) ^^ -0(п, з)ктаг

п=1

г=1 г=1 у=1

3=г

И

а ж0(1, в),... ,п0(М, в) — из системы,

м м

^ П — (—(5 + а)по(т, в) + Кт + \п(гп)ко(т, в)^ = 0,

т=1]=1

3=т

в которой гп = гп(з) — решение функционального уравнения

хп = @ (в + а — \п(гп)! .

Далее вводятся следующие обозначения:

р (п,г) = Р(Щ = п)

тете п

к,з) = ^ гп е-агР(п, к,

п=1 {

те „

п=1 о

о

те

п I „—зЬ ,

при | < 1, И,е (в) > 0, Выводится выражение для в):

, \ ^ , 4-1 1 — р (5 + а — хп(г))

п(г,8) = 2_^(в + а — \п(г)) 1---~ х

п=1

1 — х-1^ (з + а — \п(г))

м . Л

П — рагг) м , \ ( \\ ( \

х г=Л_^ — (в + а — Хп(г))по(т, в)

и (К(г) — хз(г)) ™=1 Лга(г) ра*

3 = 1 4 '

]=п

Заключительная часть раздела посвящена анализу стационарного режима функционирования системы,

те М

В предположении, что а^ЕН < 1, где /31 = —@'(0) = [ xdB(х), а ЕН = ^ пкп, опреде-

0 п=1

ляются функции

те

ъ(г) = V гп Иш Р(п,г),

^—' ^те

п=1

р0(т) = Иш Р(0,т,Ь).

Ь^те

И

Доказывается, что

М . X

м г / чч П (^(¿0 - м

^ 1 - р(а - \п(г)) =V / ^ Ро(т)

п=1 1 - *-1р(а - Хп^)) П (\п(г) - А3(г)) Хп(г) - Ра*

п -

3 = 1 '

3=п

Подробно рассматривается случай М = 2. Показывается, что в этом случае

к(г) = ---^-х

Ш - \2(г)

г(1 -3(а - \1(г))) г - 3(а - А1(г))

(а ^^ ((Ш -Щ?2 г - 3(а - А2(г))

х{ ^ 3(а ((Ш - раг 2)р0(1) + (Ш - раг )р0(2)) -

I г-р (а - А^г)) у 7

(Х2(г) - раг2)р0(1) + - раг)р0(2)^ |

Иш ЕОД = к'(1) = -*-(1 - К2) + а31(1 + Н2) + «232(1 + )) +

1 -р 2(1 -ар1(1 + П2))

а31 Ъ,2(1 - рЪ,2) р 1

1 -ар1(1 + 1%2) 1 -р 1 - р 1 -ар1(1 + 112)

оо

где р2 = 3''(0) = [ х2с1В (х). Проводится сравнение полученной формулы для длины очереди о

в стационарном режиме с соответствующим результатом для системы Мх |С|1: 'т 'пм р (л ар1 к2(1 - Р12)

■К (1) -к (1)|р=0 = --(1 - П2) +

1 -р 1 - ар1(1 + 12) 1 -р

а р1 1 2 1

1 -ар1(1 + 12) 1 -р 1 -ар1(1 + 12) 1

0(1)

1 -р 1 -ар1(1 + 1%2)

[(1 - 1%2)(1 - аР\) - ро(1)],

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

Список литературы диссертационного исследования кандидат наук Леонтьев, Николай Дмитриевич, 2017 год

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

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

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

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

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

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

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

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

[8] Матвеев В. Ф., Ушаков В. Г. Системы массового обслуживания. М,: МГУ, 1984.

[9] Привалов И. И. Введение в теорию функций комплексного переменного. М,: Физматгиз, 1960.

[10] Саати Т. Элементы теории массового обслуживания и её приложения. М,: Советское радио, 1965.

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

[12] Addie R. G., Zuckerman M. Performance Evaluation of a Single Server Autoregressive Queue // Australian Télécommunication Research, 1994. Vol. 28. N. 1. P. 25-32.

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

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

[15] Choi B. D., Kim B., 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.

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

[17] 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.

[18] Dehnert M., Helm W. E., Hutt M.-T. A Discrete Autoregressive Process as a Model for Short-Range Correlations in DNA Sequences // Phvsica A: Statistical Mechanics and its Applications, 2003. Vol. 327. N. 3. P. 535-553.

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

[20] Doetsch G. Introduction to the Theory and Application of the Laplace Transformation. Springer Verlag, 1974.

[21] 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.

[22] 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.

[23] 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.

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

[25] Gaver D. P. Imbedded Markov Chain Analysis of a Waiting-Line Process in Continuous Time // The Annals of Mathematical Statistics, 1959. P. 698-720.

[26] 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.

[27] 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.

[28] 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. 10751084.

[29] 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.

[30] 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.

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

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

[33] Kendall D. G. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain // The Annals of Mathematical Statistics, 1953. P. 338-354.

[34] Kim B., 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.

[35] Kim J., Kim B. Regularly Varying Tails in a Queue with Discrete Autoregressive Arrivals of Order p H Queueing Systems, 2007. Vol. 56. N. 2. P. 93-102.

[36] Kim B., 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.

[37] Lawranee A. J., Lewis P. A. W. An Exponential Moving Average Sequence and Point Process (EMA1) 11 Journal of Applied Probability, 1977. Vol. 14. N. 1. P. 98-113.

[38] Maglaris B., 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.

[39] 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.

[40] Paxson 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.

[41] Ryu В. К., 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,

[42] Schechter S. On the Inversion of Certain Matrices // Mathematical Tables and Other Aids to Computation, 1959. Vol. 13. N. 66. P. 73-77.

[43] Коммутация пакетов // Википедия. [2012—2016]. Дата обновления: 09.02.2016. URL: http://ru.wikipedia.org/?oldid=76343759 (дата обращения: 05.03.2017).

[44] Типы кадров // Википедия. [2007—2013]. Дата обновления: 25.11.2013. URL: http://ru.wikipedia.org/?oldid=59705795 (дата обращения: 05.03.2017).

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