Марковские модели однолинейных систем обслуживания с накопителем конечной емкости тема диссертации и автореферата по ВАК РФ 05.13.17, доктор технических наук Нгуен Хунг Фонг

• Нгуен Хунг Фонг
• доктор технических наук
• 2001

Оглавление диссертации доктор технических наук Нгуен Хунг Фонг

Введение.

Глава 1. Приоритетные системы конечной емкости с марковскими потоками.

§ 1. Система МАРо/С2/1/т с относительным приоритетом.

1.1. Описание системы.

1.2. Вывод системы дифференциальных уравнений.

1.3. Решение системы уравнений.

1.4. Вычисление матричных экспоненциальных моментов

1.5. Вычисление стационарных вероятностей

1.6. Основные показатели производительности системы

1.7. Стационарные вероятности состояний системы в моменты поступления заявок или окончания их обслуживания

1.8. Стационарное распределение времени ожидания для приоритетных заявок при дисциплине ГСГЭ

1.9. Результаты численных исследований

§ 2. Система МАРо/С2/1/г с абсолютным приоритетом.

2.1. Система дифференциальных уравнений.

2.2. Решение системы уравнений.

2.3. Вычисление с тационарных вероятностей состояний системы.

2.4. Показатели производительности системы.

2.5. Стационарные вероятности состояний системы в моменты поступления заявок или окончания их обслуживания

2.6. Стационарное распределение времени ожидания для приоритетных заявок при дисциплине ГС Г Я

2.7. Результаты численных исследований

§ 3. Система обслуживания МАРч/Со/^/г с относительным приоритетом и марковскими потоками, зависящими от состояния очередей

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

3.2. Система дифференциальных уравнений.

3.3. Решение системы уравнений

3.4. Вычисление матричных экспоненциальных моментов.

3.5. Вычисление стационарных вероятностей

3.6. Показатели производительности системы

3.7. Стационарные вероятности состояний системы в моменты поступления заявок или окончания их обслуживания

3.8. Стационарное распределение времени ожидания для приоритетных заявок при дисциплине РСРБ . 104 Выводы

Глава 2. Системы со временем обслуживанием, зависящим от числа заявок в системе.

§ 1. СМО с одним марковским потоком.

1.1. Описание системы и линейчатый марковский процесс.

1.2. Система дифференциальных уравнений и её решение.

1.3. Показатели производительности системы

1.4. Стационарные вероятности состояний системы в моменты поступления заявок или окончания их обслуживания

1.5. Выходящий поток

1.6. Численное исследование

§ 2. Система с относительным приоритетом.

2.1. Описание системы и линейчатый марковский процесс.

2.2. Система дифференциальных уравнений и её решение

2.3. Вычисление матричных экспоненциальных моментов

2.4. Вычисление стационарных вероятностей

2.5. Основные показатели производительности системы

2.6. Стационарные вероятности состояний системы в моменты поступления заявок или окончания их обслуживания

2.7. Численное исследование

§ 3. Система с абсолютным приоритетом.

Выводы

Глава 3. Система обслуживания конечной емкости с групповым марковским потоком и полумарковским обслуживанием.

§ 1. Система ВМАР/SM/ 1/г. Первый подход.

1.1. Описание системы

1.2. Введение дополнительной переменной

1.3. Стационарные вероятности состояний системы

1.4. Вычисление вспомогательных матриц

§ 2. Система BMAP/SM/1/r. Альтернативный подход

2.1. Вложенная цепь Маркова. Матрица переходных вероятностей

2.2. Стационарные вероятности вложенной цепи Маркова

2.3. Стационарные вероятности линейчатого процесса

2.4. Показатели производительности системы

2.5. Численные примеры

§ 3. Гитерезисно-полосный механизм обслуживания в системе BMAP/SM/1/r с переключениями между режимами работы.

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

3.2. Дифферециальные уравнения равновесия

3.3. Решение систем дифферециальных уравнений

3.4. Стационарное распределение вероятностей состояний системы.

3.5. Вероятность потери.18

Выводы.

Глава 4. Системы с многомерным пуассоновским потоком и повторными заявками.

§ 1. Базовая многопотоковая СМО с повторными заявками

1.1. Описание системы

1.2. Система M к / G к/I/O/s с конечной орбитой

1.3. СМО Mk/Gk/1/0/oo с бесконечной орбитой

1.4. Маргинальное среднее число заявок на орбите

1.5. Численные примеры.

§ 2. Многопотоковая СМО с ненастойчивыми заявками

2.1. Случай конечной орбиты

2.2. Случай бесконечной орбиты

§ 3. Многопотоковая СМО с отключением прибора.

3.1. Случай конечной орбиты

3.2. Случай бесконечной орбиты

Выводы.

Глава 5. Системы с повторными заявками и приоритетным обслуживанием первичных заявок.

§ 1. Экспоненцжшьная система с повторными заявками и относительным приоритетом.

1.1. Описание системы

1.2. Система дифференциальных уравнений и её решение

1.3. Численные примеры

§ 2. СМО МАР/С/1/г с повторными заявками и приоритетным обслуживанием первичных заявок

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

2.2. Вспомогательные результаты

2.3. Вложенная цепь Маркова.

2.4. Стационарные распределения по времени

2.5. Программная реализация.

Выводы.

Глава 6. Системы с накопителем конечной емкости и повторными заявками.

§ 1. Система М/Я^^Д/г с одномерным пуассоновским потоком и повторными заявками.

1.1. Описание системы

1.2. Система дифференциальных уравнений

1.3. Вспомогательные функции и результаты

1.4. Решение системы дифференциальных уравнений

1.5. Численное исследование.

§ 2. Система М/НОк/1/г с многомерным пуассоновским потоком и повторными заявками.

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

2.2. Линейчатый марковский процесс и система дифференциальных уравнений

2.3. Решение системы дифференциальных уравнений

2.4. Средние длины очередей заявок различных типов

2.5. Численный анализ

Выводы.

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

§ 1. ОБЗОР ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМАТИКЕ ИССЛЕДОВАНИЯ

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

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

Интенсивные исследования различных систем и сетей массового обслуживания (СМО) и (СеМО) начались в начале 60-х годов и продолжаются в настоящее время [18, 21, 25, 42, 56, 57, 62-67, 70, 72-75, 78, 80, 85-90, 103, 105, 107, 114, 117, 146, 162, 169, 170, 186, 188, 189]. Большой вклад в развитие теоретических основ ТМО внесли советские и русские ученые: Хинчин А.Я., Гнеденко Б.В., Александров А.М., Башарин Г.П., Боровков A.A., Бочаров П.П., Вишневский

В.М., Жожикашвили В.А., Калашников В.В., Коваленко И.Н., Пе-чинкин А.В., Ушаков В.Г., Цыбаков B.C., Шнепс М.А., и др.

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

Вероятностно-аналитические модели описываются уравнениями, которые приближенно отражают стохастическое поведение систем. Для этих уравнений в одних случаях существуют точные решения, а в других случаях—лишь приближенные решения. Для решения этих уравнений часто прибегают к помощи численных методов. Главное достоинство аналитического подхода-—это сравнительная простота и несложная реализация на компьютере соответствующих расчетов для изучаемых систем. Тем самым, аналитический подход дает условия для численного эксперимента и нахождения л. оптимальных решений. Возможности применения СМО и СеМО в качестве аналитических моделей сетевых систем и их компонентов отражены в целом ряде монографий и обзоров [5-7, 11, 18, 20, 21, 42, 55, 64, 65, 73, 75, 76, 85, 89, 90] и др.

Имитационные модели отражают более адекватно реальные системы [55, 87]. Однако, из-за большой сложности построения имитирующей программы и трудности проверки ее корректности широкое применение имитации затруднено. Однако, в последнее время быстрое развитие вычислительных систем и появление мощных компьютеров дало новый импульс в развитии этого направления. Теоретические основы теории имитационного моделирования в советской/русской науке были разработаны Бусленко Н.В., Калашниковым В.В., Коваленко И.Н. и др. Результаты работ по этому, направлению отражены в монографиях и статьях [55, 67, 70, 84, 86, 87] и ДР

При аналитическом моделирования процессов очередей в реальных информационно-вычислительных системах и сетях во многих случаях важным фактором, который необходимо учитывать, является реальное ограничение на объем буферных накопителей. Это ограничение является довольно существенным для моделирования многих реальных систем и создает сложности для аналитического изучения. Это связано с невозможностью применения для моделей с конечными очередями метода производящих функций и других традиционных методов ТМО. Поэтому значительная часть публикаций, связанных с оценкой производительности сетевых систем, посвящена анализу СМО с неограниченными накопителями (см., например [56, 62, 78]). В некоторых случаях приближения такого рода дают вполне удовлетворительные результаты при решении реальных задач. Однако, в ряде случаев количественные оценки показателей производительности сетевых систем при замене в модели ограниченного буфера на неограниченный дают большие погрешности. Примеры, иллюстрирующие эту ситуацию, приводятся в [18, гл. 5], где показана резко выраженная зависимость вероятности потери системы с ограниченным накопителем от значения коэффициентов вариации интервалов между поступлениями заявок и длительностями их обслуживания.

Пионерские исследования по анализу СМО с ограниченными накопителями были выполнены Башариным Г.П. и Бочаровым П.П. и отражены в работах [14-17, 21, 26-28, 31]. Дальнейшие исследования систем обслуживания конечной емкости были продолжены в работах этих авторов, их учеников, а также в ряде работ других авторов [28-32, 39, 41, 42, 91, 92, 127, 151, 169, 170, 188] и др. В последние годы интерес к исследованию СМО с конечными накопителями стал еще более заметен в связи с появлением новых типов потоков— марковского потока (MAP—Markov Arrival Process) и марковского группового потока (ВМАР—Batch Markov Arrival Process), позволяющих строить более адекватные модели процессов очередей в современных информационно-вычислительных сетях [33, 34, 40, 43, 45-49,

51, 52, 60, 81, 111-113, 124, 125, 128, 130, 131, 133, 134, 141, 158]. Однако это направление исследований в ТМО еще не достаточно глубоко и полно изучено.

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

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

Остановимся теперь на основных работ, посвященных аналитическому исследованию однолинейных СМО с накопителем ограниченной емкости. Однако, мы вначале напомним модифицированные обозначения Кендалла и согласуем некоторые обозначения, которыми мы будем пользоваться в дальнейшем для описания исследуемых СМО. Используя эти обозначения, мы будем кодировать однофазную СМО в виде А/В/С¡Т)/¥, где символы А, В, С, Б, Е носят следующий смысл:

А, В обозначают тип входящего в систему потока и вид обслуживания заявок. В литературе чаще всего встречаются следующие коды: D—детерминированный поток или обслуживание, . М-пуассоновский поток или экспоненциальное обслуживание, . Е'-эрланговский поток или обслуживание, . Н-гиперэкспоненциальный поток или обслуживание, . РН-поток или обслуживание фазового типа, . MAP, ВМАР-марковский поток и груповой марковский поток, . GI, G-произвольный рекуррентный поток и произвольное рекуррентное обслуживание, . SM-полумарковский поток или обслуживание. В некоторых случах принимаются обозначения А к, В к, где индекс К показывает размерность многомерного потока или значение соответствующих параметров функций распределения (ФР) для потока или обслуживания.

С характеризует число приборов в системе. Конкретное значение числа приборов мы будем обозначать буквой с. В большинстве случаев указывается просто числовое значение с. Мы будем рассматривать однолинейные СМО, поэтому с = 1.

D—емкость накопителя системы. В данной работе D принимает ограниченное значение г (г < ос). В некоторых случах, когда речь идет о системах с повторными заявками, мы будем использовать расширенные коды r/s. Параметр s показывает максимальное число заявок в группе повторных заявок, называемой орбитой.

F—дисциплина обслуживания. Этот параметр указывается только в отдельных случах, когда имеется необходимость уточнить дисциплину выбора заявок на обслуживание. Обычно рассматриваются следующие дисциплины: FCFS (first come first served)—пришедший первым обслуживается первым, LCFS (last come first served)—пришедший последним обслуживается первым, RANDOM--случайный выбор на обслуживание. Для классификации приоритетных СМО будем использовать символ /• [15]. Здесь верхний индекс { обозначает дисциплину постановки заявок в очередь. Если г = 0, то заявка любого типа, поступающая на переполненную систему, теряется. Если { = 2, то при переполнении системы поступившая приоритетная заявка вытесняет из накопителя одну из неприоритетных заявок. Нижний индекс у обозначает дисциплину выбора заявок из очереди на обслуживание. В случае ] = 0 ни одному из типов заявок не дается преимущества; при ] = 1 приоритетные заявки имеют относительный приоритет (без прерывания обслуживания), а при j = 2— абсолютный приоритет (с прерыванием обслуживания).

Одним из важнейших направлений в ТМО является исследование приоритетных систем. Приоритетные модели являются более адекватными для многих практических систем, в которых требуется приоритетный механизм обслуживания. Так, например, принцип приоритетного обслуживания лежит в основе цифровых сетей с интеграцией служб, способных одновременно передавать разные типы сигналов: данные, речь, видеосигналы, и др. В частности, при аналитическом моделировании системы сигнализации N 7 [196], применяемой на различных типах цифровых сетей—телефонных сетях общего пользования, цифровых сетях с интеграцией служб, подвижных сетях, а также при реализации концепции интеллектуальных сетей [104], используются СМО с относительным приоритетом (без прерывания обслуживания) [19].

Приоритетным СМО с неограниченными накопителями посвящен ряд монографий [56, 62, 78]. Намного меньше число работ, посвященных приоритетным системам с ограниченными накопителями. Одна из первых работ по этим системам было выполнена Г.П. Башариным [15], в которой рассматривалась многолинейная СМО М2/М/с/г/Д° с общим ограниченным накопителем. Кроме того, в [15] рассмотрен также случай раздельных конечных накопик\ км1.

Хотя в этой работе объектом изучения является система с многими приборами нам важно отметить особую роль этой работы в развитии аналитического моделирования систем с ограниченным накопителем. В ней был впервые использован матрично-алгоритмический подход для вычисления стационарного двумерного распределения длин очередей в исследуемой СМО, получивший затем свое развитие в целом ряде других работ [18, 42, 92, 167, 188, 189], в том числе в работах автора [45-49, 52, 111, 128] и др.

Анализу однолинейных СМО конечной емкости с относительным приоритетом при общей очереди в литературе посвящен ряд работ [10, 26-28, 39, 45, 46, 49]. В работах [26-28, 39] анализировались СМО с пуассоновскими входящими потоками: в [39] рассматривалась система М2/ М2/1/г/ , в [26]—система М2/Е2/1/т/fi, в [27]—система M2/G2/l/i/f? и в [28]—система M2/G2/1/i/. Основными результатами этих работ являются рекуррентные формулы для расчета совместного стационарного распределения длин очередей. Анализ СМО с потоками фазового типа и относительным приоритетом можно найти в работе [10]. Однако исследуемая в этой работе СМО PH2/PH2/l/ri, r2/ff с потоками и временами обслуживания, характеризуемыми распределениями фазового типа (Piî-расиределениями), имеет раздельные накопители для каждого типа заявок. В работах [45, 46, 49] нами были изучены СМО MAP2/G2/l/r/fi с общим накопителем, марковскими потоками, произвольным обслуживанием и относительным приоритетом. В этих работах получены матрично-рекуррентиые алгоритмы расчета стационарного двумерного распределения состояний СМО в произвольные моменты времени и в моменты поступления заявок или их ухода. Получены также формулы расчета показателей производительности СМО и преобразование Лапласа-Стилтьеса (ПЛС) для стационарной ФР времени ожидания приоритетных заявок, принятых в систему и обслуживаемых по дисциплине FCFS.

Однолинейная СМО с общим накопителем конечной емкости и абсолютным приоритетом исследовалась в работах [9, 14, 29, 47, 48, 81]. В [14] для СМО М2/М2/1/г//£ были получены рекуррентные формулы, на основе которых рассчитывается стационарное двумерное распределение длин очередей. В [9] исследовалась СМО РЯ2/РЯ2/1/г//2°, в которой ФР, характеризующие входящие потоки заявок и длительности их обслуживания, являются РЯ-распределениями. Результатом этой работы является матрично-рекуррёнтный алгоритм для расчета стационарного распределения вероятностей состояний марковского процесса, описывающего функционирование СМО. В работе [29] был предложен унифицированный вычислительный алгоритм для определения стационарного распределения вероятностей состояний линейчатого марковского процесса, описывающего поведение СМО М2/С2/1/г для множества дисциплин обслуживания {Д0, , /|}. В работе [81] и в работах автора [47, 48] были предложены разные матричные алгоритмы расчета стационарного распределения состояний СМО МЛР2/6'2/1/г. Также получены такие же результаты, как и для СМО МАР2/С2/1/г с относительным приоритетом, но теперь для системы с абсолютным приоритетом.

Для систем, в которых параметры входящих потоков зависят от состояния очередей, результаты получены лишь для случая одного потока [30, 34, 202]. В работе [202] была изучена система М/й/1/г с входящим потоком, зависящим от состояния системы. В работе

30] рассматривалась СМО такого рода с потоком фазового типа, а в

34]—СМО с марковским потоком и произвольным обслуживанием.

В этих работах были получены матричные алгоритмы для вычисле ния стационарных вероятностей состояний, описывющих функционирование СМО марковского и линейчатого марковского процессов, и выведены соотношения для вычисления ряда показателей производительности этих систем. Полученные результаты [45, 46, 49] для

CMO MAP2/G2/l/r с относительным приоритетом в работах автора были обобщены для случая, когда входящий марковский поток зависит от состояний очередей [111, 112].

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

Более общим по сравнению с укзанными выше потоками является груповой марковский поток (ВMAP). CMO с групповым потоком часто встречаются при моделировании сетей связи с коммутацией пакетов. Например, сообщение, поступившее в главную ЭВМ для дальнейшей передачи в сеть, делится на пакеты фиксированной длины. Поскольку поступившее сообщение может иметь произвольную длину, возникает группа из случайного числа пакетов, которые одновременно поступают на связной контроллер, осуществляющий интерфейс между главной ЭВМ и сетью. Моделью этого контроллера может служить СМО с групповым входящим потоком заявок.

В литературе имеется большое количество работ, посвященных i системам с групповым потоком. Системы с групповым пуассонов-ским потоком заявок исследованы, в частности, в [1, 53, 54, 98, 140, 164, 174, 175, 180, 181, 185, 187, 191, 194, 207]. Случай, когда емкость накопителя ограничена, был рассмотрен в [53, 54, 164, 185,

187, 207]. В работе [185] исследована система ЪАХ/Ш/с/г (здесь верхний индекс X обозначает, что поток является групповым), в которой решена система уравнений равновесия (СУР) для стационарных вероятностей состояний СМО, найдены вероятности потери заявки и потери группы, интенсивности принятого потока, а также получена ФР времени ожидания заявок. В [187] рассмотрена система типа Mx/G/l/r вместе с двойственной системой GI/M^/l/r (верхний индекс Y обозначает групповое обслуживание), и для первой из них было получено распределение длины очереди по моментам окончания обслуживания, а для второй—-по моментам поступления заявок. В [164, 207] оценивается вероятность потери в СМО, при этом заметим, что полученные в этих работах приближенные результаты являются точными для систем Mx/G/l/r и Мх/М/c/r с произвольным размером группы в работе [207] и с фиксированным размером группы в работе [164]. СМО РНх/РН/1/г ограниченной емкости была изучена" в работах [53, 54], где были получены матричный алгоритм для расчета стационарных вероятностей состояний СМО и выражения для вычисления различных показателей ее производительности.

Следующим этапом в изучении групповых нерекуррентных потоков стал групповой марковский поток, эквивалентный потоку Ньют-са (или N-потоку), введенному ранее в работе [191] более сложным образом. Впервые система с входящим N-потоком была исследована в [194], где найдены стационарные распределения длины очереди и времени ожидания. В [180] впервые была рассмотрена СМО BMAP/G/1 с бесконечной очередью. Отметим, что вначале ВМАР считался обобщением N-потока и их эквивалентность была замечена лишь в [181]. Исследование ВМАР за последнее время можно V найти как и в иностранной [157, 165, 180-182, 184, 191, 192, 194], так и в советско/русской литератуте [35, 60, 61, 98, 101, 113, 131, 134, 152-158]. Разные модификации моделей неограниченных очередей с ВМАР-потоками изложены в монографии [60]: многолинейные

СМО, однолинейные СМО с повторными вызовами, нетерпеливыми запросами, альтернирующим входным потоком, катастрофическими опустошениями, прогулками прибора и др. СМО с конечной очередью и ВМАР-потоками были исследованы недавно [98, 157, 165]: в [98] рассмотрены СМО типа BMAP(n)/G/l/r, где входящий поток зависит от числа заявок в системе, а в [165] изучена вероятность потери для системы BMAP/G/1/N.

С другой стороны, СМО может быть сложной по структуре процесса обслуживания. Достаточно общим является полумарковское обслуживание. СМО с полу марковским обслуживанием впервые изучены в [189]. После введения этого типа обслуживания в литератере появились разные модели с полумарковским обслуживанием. Так, например, в [155] рассмотрены системы с повторными заявками и полумарковским обслуживанием, в [157] изучена СМО BMAP/SM/1/N с отрицательными заявками, а работы [156, 158] посвящены проблемам управления обслуживанием, Отметим здесь две ключевые "классические" модели с груповым марковским потоком и полумарковским обслуживанием. Первая из них— СМО BMAP/SM/1 бесконечной емкости детально рассматривалась в [184]. Вторая модель—СМО BMAP/SM/1/r конечной емкости была рассмотрена в работах автора [38, 131]. В этих работах предложены разные подходы для расчета стационарного распределения состояний системы как в произвольные моменты времени, так и для цепи Маркова, вложенной по моментам окончания обслуживания заявок. Получены расчетные алгоритмы, а также вероятность потери и другие показатели производительности системы.

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

В литературе имеется ряд работ, посвященных однолинейным СМО с временем обслуживания заявок, зависящим от состояния системы [2-5, 30, 51, 173, 200-202, 205]. В этих работах были изучены разные типы зависимости времен обслуживания от состояния системы. В [2-5] рассматривались предельные результаты для систем с неограниченными накопителями и зависимым обслуживанием. Работа [30] посвящена СМО PH/PH/1/r с входящим потоком и обслуживанием фазового типа, зависящими от состояния очереди, а также с учетом обратной связи на входе и выходе системы. В [173] изучалась СМО М/G/l бесконечной емкости, имеющая ФР времени обслуживания Bk(t) для случая, когда число заявок в системе в момент начала обслуживания равно /с, к < К, и B(t) для случая, когда к > К. Ряд результатов для СМО М/G/l бесконечной емкости для случая, когда ФР времени обслуживания зависит от длины очереди, получен в работах [200-202]. В [205] для СМО МАР/G/l бесконечной емкости рассматривался другой тип зависимости, когда время обслуживания зависит от состояния управляющего марковского процесса. В работе [51], автором была рассмотрена СМО MAP/G(k)/l/r с ФР времени обслуживания, зависящими от числа заявок, находящихся в системе в момент окончания обслуживания заявок. Для исследуемой системы были получены матричные рекуррентные формулы для расчета стационарного распределения вероятностей состояний системы и ряда ее характеристик.

Пороговой механизм обслуживания является важным средством для управления и оптимизации функционирования СМО. В работе [59] рассматривалась задача выбора оптимальной пороговой стратегии переключения скорости обслуживания заявок в двухскорост-ной ненадежной СМО М/G/1 неограниченной емкости, в которой ФР времени обслуживания для первой скорости является экспоненциальной, а для второй скорости имеет произвольный вид. В [151] подобная задача решалась для аналогичной СМО с групповым пуассоновским потоком. Здесь необходимо отметить, что простые пороги являются частным случаем зависимости между временами обслуживания и состоянием исследуемой в [51] системы. Полосно-гистерезисный механизм является более гибким и адекватным для управления процессом обслуживания СМО. В работе [168] исследуется полосно-гистерезисный механизм управления трафиком в АТМ-сетях. Этот механизм управления реализован в модели ММРР/М/1/К, где интенсивность обслуживания меняется в моменты поступлений или уходов заявок. Более адекватная ги-стерезисная модель была исследована в работе [158] для системы ВМАР/SM/1/N, где ФР времени обслуживания меняется только в моменты уходов заявок. Главным результатом [158] является алгоритм для расчета стационарного распределения состояний цепи Маркова, вложенной по моментам окончания обслуживания. Однако, в [158] не получен ряд других, важных характеристик качества функционирования системы. В частности, не получено стационарное V распределение очереди для произвольного момента времени. Приведенный в [158] алгоритм также не позволяет определить, например, вероятность потери—одну из важнейших характеристик производительности для СМО конечной емкости. В работе автора [113] была рассмотрена такая же система, как в [158], включая механизм переключения между режимами работ. Нами были получены матрично-рекуррентный алгоритм для расчета стационарного распределения состояний СМО в произвольные моменты времени. Получено также выражение для вычисления вероятности потери системы и других ее характеристик.

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

Наиболее полные обзоры результатов по исследованию СМО с повторными заявками представлены в монографии и обзорных статьях [105, 120, 161, 209]. Мы ограничимся здесь только обзором работ, посвященных однолинейным моделям повторных заявок. Первые теоретические результаты исследования этих систем изложены в работах [8, 176]. В этих работах авторы исследовали систему AÍ/G/1/0 с повторными заявками, и получили производящие функции для стационарного распределения длины очереди повторных заявок и выражение для средней длины очереди. Наиболее полный анализ системы М/С/1/0 с повторными заявками можно найти в монографии [162], в которой исследуется условие эргодичности, период занятости, ПЛС виртуального времени ожидания заявок и другие характеристики системы. Случай с групповым потоком рассматривался в [108, 209], в которых разными подходами было получено соч вместное распределение состояний прибора и числа заявок на орбите. Системы с ненастойчивыми повторными заявками исследовались в [69, 106, 145, 159, 197]. В [69, 145] предлагалось, что заявки уходят из системы (с орбиты) с некоторой постоянной интенсивностью. В

106, 159] авторы изучали избыточную нагрузку системы. Системы с более сложными потоками и процессами обслуживания также вызывают интерес у многих исследователей. В [137] рассмотрена система РН/РН/1/0 с повторными завками, где входящий поток заявок и время обслуживания имеют распределения фазового типа. В [154, 155] проведены исследования системы с груповым марковским потоком, произвольным или полумарковским обслуживанием. Системы, рассматриваемые в [119, 121], имеют дополнительный поток отрицательных заявок.

Одной из проблем для СМО с повторными заявками, не изученных в должной мере до настоящего времени, является задача анализа СМО с несколькими типами заявок. Мы остановимся здесь на решении одной из таких задач для однолинейной СМО с многомерным пуассоновским потоком. Исследованию однолинейной СМО без накопителя с многомерным пуассоновским потоком и повторными заявками были посвящены публикации [12, 82, 132, 135, 136, 148, 160, 162, 178, 179, 193]. В [82] для такого рода СМО с экспоненциальной ФР Bj(x) времени обслуживания ¿-заявки, i = 1 ,К, была получена система уравнений порядка К для определения средних длин очередей для каждого типа заявок. Система с двумя пуассо-новскими потоками заявок и произвольными ФР Bi{x), i — 1,2, анализировалась в [179], где были получены явные формулы для средних длин очередей заявок обоих типов. Результаты [82] были обобщены в [160, 162] на случай произвольных ФР Бг(ж), г = l,il. В [132] были получены рекуррентные формулы для вычисления стационарного распределения состояний рассматриваемой в [160, 162] системы и среднего числа заявок каждого типа на орбите. В [135, 136] результаты работы [132] распространены на случай ненастойчивой модели, когда поступающая ¿-заявка, заставшая занятым обслуживающий прибор, с вероятностью Н{ > 0 присоединяется к орбите и с вероятностью 1 — Hi теряется. И, наконец, в [148, 193] результаты

132] обобщены на случай, когда допускается отключение прибора на случайное время после окончания обслуживания очередной заявки. Используемый автором в [12, 132, 135, 136, 148, 193] подход позволяет рассчитывать многомерное стационарное распределение длин очередей повторных заявок различных типов на основе стационарного распределения общей очереди повторных заявок в СМО с одним пуассоновским потоком.

Хотя в литературе имеется довольно много работ по анализу различных систем обслуживания с повторными заявками, однако большинство из них посвящено системам без накопителя. Эти модели не могут быть адекватными во многих практических случаях, когда до начала обслуживания заявки находятся случайное время в накопителе. Этот пробел связан со сложностью исследования моделей с ограниченным накопителем. До появления приведенных нами работ [36, 37, 43, 123, 126, 127] в литературе имелось совсем мало публикаций, где исследовались СМО с повторными заявками и накопителем для первичных заявок. Рассматривались лишь два типа СМО такого рода. В системе первого типа первичные заявки имеют относительный приоритет при обслуживании, т.е повторные заявки из орбиты могут попасть только на свободный прибор. В [129] была рассмотрена система М/С/Х/г с неограниченной орбитой и приоритетным обслуживанием первичных заявок. В [123] автором была исследована система М2/М/1/Г с двумя пуассоновскими потоками заявок, первый из которых является потоком первичных, а второй—потоком вторичных заявок. Первичные заявки поступают в накопитель конечной емкости. Вновь поступающая заявка первого типа теряется, если в накопителе нет свободных мест. Заявки второго потока прич ходят прямо на прибор и переходят на орбиту, если в момент поступления заявки прибор был занят. Оттуда каждая заявка независимо друг от друга начинает новые попытки вернуться на прибор. В [43] автором была рассмотрена система МАР/С/1/т\ подобная системе

129], но с марковским входящим потоком. Второй тип СМО с накопителем ограниченной емкости является более адекватной моделью реальных систем, с одной стороны, и более сложной для исследования, с другой стороны. Для систем такого типа повторные заявки возвращаются в очередь в накопителе, если в ней имеется свободное место в момент возвращения заявки, или на прибор, если в этот момент система пуста. В противном случае заявка возвращается на орбиту и делает новые попытки получить обслуживание. В [161, 195] для системы М/С/1 изучался случай, когда повторные заявки также возвращаются в накопитель, который имеет, однако, лишь емкость г = 1. В [36, 126] автором рассмотрена система М/С/1/г с повторными заявками. Входящий пуассоновский поток первичных заявок поступает в накопитель, а время обслуживания заявок распределено по произвольному закону. Были получены рекуррентный алгоритм для вычисления стационарного распределения состояний СМО и формулы для расчета различных показателей ее производительности. В [37, 127] полученные результаты обобщены автором на случай многомерного пуассоновского потока первичных заявок. Показано, что анализ модели с ограниченным накопителем и с многомерным пуассоновским потоком при произвольном обслуживании сводится к анализу модели с одним пуассоновским потоком, в которой вид заявки разыгрывается при выборе ее на обслуживание по полиномиальной схеме.

На этом мы завершим обзор литературы по исследуемой в диссертации проблеме, и перейдем к краткому изложению основных результатов диссертации.

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ. ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ

Диссертация состоит из введения, шести глав, списка литературы. Каждая глава состоит из параграфов, которые состоят еще из подпараграфов. Определения, теоремы, леммы, следствия, формулы, таблицы и рисунки нумеруются внутри каждого параграфа с указанием его номера. При ссылке на объект (определение, теорема, лемма, формула) из другой главы перед номером объекта поставлен номер главы.

Заключение диссертации по теме «Теоретические основы информатики», Нгуен Хунг Фонг

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

5 . Для СМО М2/М/1/Г с повторными заявками и относительным приоритетным обслуживанием первичных заявок получены рекуррентные формулы для расчета стационарного распределения состояний системы и приведены численные примеры.

Для СМО МАР/(7/1/г с повторными заявками и относительным приоритетным обслуживанием первичных заявок получен матричный алгоритм, на основе которого вычисляется ряд стационарных характеристик системы: средняя длина свободного периода и периода занятости системы, а также маргинальные распределения чисел первичных и повторных заявок. Проведено численное исследование стационарных показателей производительности системы.

6 . Для СМО М/1№к/Х/г/з с повторными заявками и накопителем конечной емкости получен алгоритм для расчета стационарного распределения состояний системы, длины очереди в накопителе и числа заявок на орбите, Приведены численные примеры основных характеристик системы.

Рассмотрена также СМО Мк/НСк/Х/г/в с многомерным пуас-соновским потоком. Установлена простая связь стационарных вероятностей состояний системы с многомерным пуассоновским потоком с аналогичной системой с одним пуассоновским потоком, интенсивность которого является суммой интенсивностей компонент многомерного пуассоновского потока, а вид ФР времени обслуживания заявки определяется в момент начала ее обслуживания по полиномиальной схеме. Установлена также связь между средними значениями длин очередей для заявок каждого типа (в накопителе и на орбите) в системе с многомерным потоком и суммарными средними длинами очередей в системе с одним потоком. Проведен также численный анализ показателей производительности системы.

ЗАКЛЮЧЕНИЕ

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

1 . Для СМО МЛРг/С^А/7, с относительным/абсолютным приоритетами, включая систему с относительным приоритетом, когда параметры марковских потоков зависят от состояний очередей, выведены матричные алгоритмы для расчета стационарного распределения состояний системы в произвольные моменты времени и в моменты поступления заявок или окончания их обслуживания, получены выражения для основных показателей производительности системы, а также выражение для ПЛС для стационарной ФР времени ожидания для приоритетных заявок при обслуживании их в соответствии с дисциплиной РСР5. Проведено численное исследование показателей производительности системы для различных значений ее параметров.

2 . Для СМО МАР1в(к)11/г и МАР2/в2{п, ш)/1/г с относительным/абсолютным приоритетами, произвольным обслуживанием, зависящим от числа заявок в очереди, получены матричный алгоритм для расчета стационарного распределения состояний системы в произвольные моменты времени, а также в моменты поступления заявок или окончания их обслуживания, выведены формулы для основных показателей производительности и выражения для ПЛС для стационарной ФР интервала между выходами обслуженных заявок при дисциплине РСЕБ выбора на обслуживание. Проведено численное исследование показателей производительности системы.

3 . Для СМО ВМАР/ЗМ/1/г разработаны два алгоритма расчета стационарного распределения вероятностей состояний системы, как для произвольных моментов времени, так и для моментов ухода обслуженных заявок. Получены выражения для расчета ряда показателей производительности системы и проведено их численное исследование. Для СМО ВМАР/вМ/Х/г с гистерезисно-полосным механизмом управления обслуживанием и переключениями между режимами работы выведен матричный алгоритм для вычисления стационарного распределения состояний системы и получено выражение для вычисления вероятности потери заявки.

4 . Для СМО Мк/СА"/1/0/5 < с повторными заявками доказана теорема, позволяющая упростить анализ рассматриваемой системы с многомерным пуассоновским потоком и свести его к исследованию более простой системы с одним потоком заявок, выведен алгоритм для расчета стационарного распределения ее состояний для случая ограниченной орбиты и получена производящая функция для стационарного распределения общего числа заявок на орбите для случая бесконечной орбиты. Получена также формула для маргинального среднего числа заявок на орбите. Проведено численное исследование стационарных показателей производительности системы.

Список литературы диссертационного исследования доктор технических наук Нгуен Хунг Фонг, 2001 год

1. Абольников J1.M. Многоканальная система массового обслуживания с групповым поступлением // Техническая кибернетика. 1967. № 4. С. 39-48.

2. Абрамов В.М. Некоторые предельные теоремы для одноканаль-ной системы, интенсивность обслуживания которой зависит от длины очереди // Изв. АН СССР. Техническая кибернетика. 1981. № 5. С. 53-57.

3. Абрамов В.М. Предельные теоремы для некоторых совместных распределений одноканальной системы с интенсивностью обслуживания, зависящей от длины очереди, I // Изв. АН СССР. Техническая кибернетика. 1982. № 2. С. 135-138.

4. Абрамов В.М. Предельные теоремы для некоторых совместных распределений одноканальной системы с интенсивностью обслуживания, зависящей от длины очереди, II // Изв. АН СССР. Техническая кибернетика. 1984. № 2. С. 115-119.

5. Абрамов В.М. Исследование системы с обслуживанием, зависящим от длины очереди. Душанбе: Изд-во Донищ, 1991.

6. Авен О.И., Коган Я.А. Управление вычислительным процессом в ЭВМ. М.: Энергия, 1978.

7. Авен О.И., Турин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.

8. Александров A.M. О системе массового обслуживания с повторными требованиями // Изв. АН СССР. Техническая кибернетика. 1974. № 2. С. 86-89.

9. Альборес Ф.Х., Бочаров П.П. Об однолинейной системе обслуживания конечной емкости с распределениями фазового типа и абсолютным приоритетом // Автоматика и телемеханика. 1987. № 12. С. 93-103.

10. Алъборес Ф.Х., Бочаров П.П. Анализ двух ограниченных очередей с относительным приоритетом в однолинейной системе обслуживания с распределениями фазового типа // Автоматика и телемеханика. 1993. № 4. С. 96-107.

11. Артамонов Г. Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978.

12. Атенсиа И.М., Бочаров П.П., ДАпиче Ч., Фонг Н.Х. Однолинейная система массового обслуживания с многомерным пуассо-новским потоком и повторными заявками // Автоматика и телемеханика. 2000. № И. С. 123-138.

13. Базилевич Е.В., Прамнэк Г.Ф. Системы коммутации сообщений на базе техники ЭВМ. М.: Связь, 1971.

14. Башарин Г.П. Об обслуживании двух потоков на однолинейной системе с ограниченным числом мест для ожидания и абсолютным приоритетом // Изв. АН СССР. Техническая кибернетика. 1967. № 5. С. 31-49.

15. Башарин Г.П. Об обслуживании двух потоков с относительным приоритетом на полнодоступной системе с ограниченным числом мест для ожидания // Изв. АН СССР. Техническая кибернетика. 1967. № 2. С. 72-86.

16. Башарин Г. П. О пуассоновских обслуживающих системах с абсолютным приоритетом и обратной связью // В сб. "Массовое обслуживание в системах передачи информации". М.: Наука, 1969. С. 1-12.

17. Башарин Г. П. Один прибор с конечной очередью и заявки нескольких видов // Теория вероятностей и ее применения. 1965. № 10. Вып. 2. С. 282-296.

18. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989.

19. Башарин Г.П., Самуйлов К.Е. Об однофазной системе массового обслуживания с двумя типами заявок и относительным приоритетом // Изв. АН СССР. Техническая кибернетика. 1983. № 3. С. 48-55.

20. Башарин Г.П., Харкевич А.Д., Шнепс М.А. Массовое обслуживание в телефонии. М.: Наука, 1968.

21. Беллман Р. Введение в теорию матриц. М.: Физматгиз, 1969.

22. Боккер.П. ISDN. Цифровая сеть с интеграцией служб. М.: Радио и связь, 1991.

23. Боровков А.А. Вероятностные процессы в теории массового обслуживания. М.: Наука, 1972.

24. Бочаров П.П. Об обслуживании на однолинейной пуассоно-эрланговской системе с ограниченным числом мест для ожидания и относительным приоритетом // Проблемы передачи информации. 1969. Т. 5. Вып. 4. С. 50-58.

25. Бочаров П. П. Об однолинейной обслуживающей системе с ограниченным числом мест для ожидания с приоритетами // Проблемы передачи информации. 1970. Т. 6. Вып. 3. С. 70-77.

26. Бочаров П.П. О вычислении стационарных вероятностей в системе с относительным приоритетом и ограниченной очередью

27. Сборник научных работ аспирантов. М.: Изд-во УДН, 1970. Вып. 7. С. 3-9.

28. Бочаров П.П. Анализ системы il^/G^/l/r с относительными и абсолютными приоритетами // В сб. "Численные методы решения задач математической физики и теории систем". М.: Изд-во УДН, 1979. С. 32-43.

29. Бочаров П.П. О системе массового обслуживания ограниченной емкости с распределениями фазового типа, зависящими от состояния очереди // Автоматика и телемеханика. 1985. N® 10. С. 31-38.

30. Бочаров П. П. Однолинейные системы обслуживания конечной емкости. М.: Изд-во УДН, 1985.

31. Бочаров П. П. Разработка теоретических основ анализа очередей в сетевых системах с учетом ограниченности буферных накопителей // Дис. доктора тех. наук: 05.25.01. Москва, 1987.

32. Бочаров П. П. Анализ системы масссового обслуживания MAP/G/1/r конечной емкости // Вестник РУДН. Серия "Прикладная математика и информатика". 1995. № 1. С. 52-67.

33. Бочаров П. П. Анализ конечной очереди с марковским входящим потоком, зависящим от состояния системы, и произвольным обслуживанием // Автоматика и телемеханика. 1995. № 12. С. 60-70.

34. Бочаров П.П., Алъ-Натор С.В. Стационарные характеристики конечной очереди с групповым марковским потоком и произвольным обслуживанием // Вестник РУДН. Серия "Прикладная математика и информатика". 1995. ^ 1. С. 68-76.

35. Бочаров П.П., Д'Апиче Ч., Фонг Н.Х. Об обслуживании пуассо-новского потока на однолинейной системе с конечным накопителем и повторными заявками // Проблемы передачи информации. 2001. Т. 36. Вып. 3. С. 67-81.

36. Бочаров П.П., Д'Апиче Ч., Мандзо Р., Фонг Н.Х. Об обслуживании многомерного пуассоновского потока на одном приборе с конечным накопителем и повторными заявками // Проблемы передачи информации. 2001. Т. 37. Вып. 4.

37. Бочаров П.П., Д'Апиче Ч., Печинкин A.B., Фонг Н.Х. Система обслуживания конечной емкости с групповым потоком и полумарковским обслуживанием // Вестник РУДН. Серия "Прикладная математика и информатика". 2001. № 1. С. 64-79.

38. Бочаров П.П., Лысенкова В. Т. Об однолинейной системе с относительным приоритетом и ограниченным числом мест для ожидания // В сб. "Вероятностные задачи в структурно-сложных системах коммутации". М.: Наука, 1969. С. 59-65.

39. Бочаров П.П., Матюшенко С.И., Фонг Н.Х., Тхирау X. О зависимом обслуживании в системе MAPfG/1/r конечной емкости // Тезисы докладов XXXIV научной конференции факультета физико-математических и естественных наук РУДН. М.: Изд-во РУДН, 1998. С. 9-10.

40. Бочаров П.П., Павлова О.И., Пузикова Д.А. Система M/G/1/r с повторными заявками и приоритетным обслуживанием первичных заявок // Вестник РУДН. Серия "Прикладная математика и информатика". 1997. № 1. С. 37-51.

41. Бочаров П.П., Печинкин A.B. Теория массового обслуживания. М.: Изд-во РУДН, 1995.

42. Бочаров П.П., Печинкин A.B., Фонг Н.Х. Стационарные вероятности состояний системы MAP/G/l/r с повторными заявками и приоритетным обслуживанием первичных заявок // Автоматика и телемеханика. 2000. № 8. С. 68-78.

43. Бочаров П.П., Фонг Н.Х. Анализ системы массового обслуживания МАР2/G211А с относительным приоритетом // Вестник РУДН. Серия "Прикладная математика и информатика". 1996. № 2. С. 67-85.

44. Бочаров П.П., Фонг Н.Х. Анализ системы массового обслуживания МАР2/G2 /1 /г с абсолютным приоритетом // Автоматика и телемеханика. 1997. № 11. С. 102-117.

45. Бочаров П.П., Фонг Н.Х. О системе M/G/1/r с повторными заявками // Тезисы докладов Всероссийской научной конференции по проблемам математики, информатики, физики, химии и преподавания естественно-научных дисциплин. М.: Изд-во РУДН, 2000. С. 32.

46. Бочаров П.П., Хак Тх., Фонг Н.Х. Анализ конечной очереди с марковским потоком и произвольным обслуживанием, зависящим от числа заявок в системе // Автоматика и телемеханика. 1998. № 10. С. 64-75.

47. Бочаров П.П., Фонг Н.Х., Хак Тх. Анализ системы массового обслуживания МАРг/б^ДД с относительным приоритетом и обслуживанием, зависящим от длин очередей // Вестник РУДН. Серия "Прикладная математика и информатика". 1999. № 1. С. 92-109.

48. Бочаров П.П., Якушина (Аль-Натор) С.В. Стационарное распределение очереди в системе обслуживания конечной емкости с групповым потоком и временем обслуживания фазового типа // Автоматика и телемеханика. 1996. № 9. С. 106-119.

49. Бочаров П.П., Якушина (Аль-Натор) С.В. Анализ системы РН^/РНД/г с групповым поступлением // Тезисы докладов X Белорусской школы-семинара по теории массового обслуживания. Минск: Изд-во БГУ, 1994. С. 15-16.

50. Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем. М.: Советское радио, 1972.

51. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания. М.: Изд-во МГУ, 1973.

52. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1987.

53. Гришечкин С.А. Ветвящиеся процессы и системы с повторными вызовами или случайной дисциплиной // Теория вероятностей и ее применения. 1990. Т. 35. Вып. 1. С. 35-50.

54. Дудин А.Н. Оптимальное управление ненадежной двухскорост-ной системой массового обслуживания // Автоматика и телемеханика. 1985. № 9. С. 56-62.

55. Дудин А.Н., Клименок В. И. Системы массового обслуживания с коррелированными потоками. Минск.: Изд-во БГУ.

56. Дудин А.Н., Клименок В.И. О системе обслуживания BMAP/G/1 с альтернирующим режимом функционирования // Автоматика и телемеханика. 1999. JY2 10. С. 97-107.

57. Дэюейсуол Н. Очереди с приоритетами. М.: Мир, 1973.

58. Ершов В.А., Кузнецов H.A. Теоретические основы построения цифровой сети с интеграцией служб (ISDN). М.: Институт проблем передачи информации РАН, 1995.

59. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988.

60. Зелигер Н.Б., Чугреев О.С., Яновский Г.Г. Проектирование сетей и систем передачи дискретных сообщений. М.: Радио и связь, 1984.

61. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М.: Высшая школа, 1982.

62. Иглхарт Д.А., Шедлер Д.С. Регенеративное моделирование сетей массового обслуживания. М.: Радио и связь, 1984.

63. Ионин Г. Л. Однолинейная система с повторными вызовами // Тезисы докладов научно-технического совещания "Информационные сети и автоматическая коммутация". М.: Наука, 1971. С. 89-94.

64. Ионин Г.Л., Седол Я.Я. Исследование телефонных систем при повторных вызовах // Латвийский математический ежегодник. Рига, 1970. № 7. С. 71-83.

65. Калашников В. В. Качественный анализ поведения сложных систем методом пробных функций. М.: Наука, 1978.

66. Калашников К.К., Печинкин A.B. Дисциплина марковского обслуживания в системе с несколькими входящими потоками //

67. В сб. "Системный анализ и информатика". М.: Изд-во РУДН, 1992. С. 56-69.

68. Калашников В.В., Рачев С. Т. Математические методы построения стохастических моделей обслуживания. М.: Наука, 1988.

69. Клейнрок Л. Коммуникационные сети. М.: Наука, 1970.

70. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.

71. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.

72. Клепиков В.П., Марценицен С.И., Жевлюк К.С. Обработка сообщений в центре коммутации сообщений. М.: Радио и связь, 1984.

73. Клименок В. И. Оптимизация динамического управления режимом работы информационно-вычислительных систем с повторными вызовами // Автоматика и вычислительная техника. 1990. № 1. С. 25-30.

74. Климов Г. П. Стохастические системы обслуживания. М.: Наука, 1966.

75. Кокотушкин В.А., Михалев Д.Г. Обслуживание полнодоступным пучком нескольких потоков с относительным приоритетом на обслуживании и ограниченной общей очередью // Проблемы передачи информации. 1969. Т. 5. Вып. 2. С. 47-54.

76. Кокс Д.Р., Смит У.Л. Теория очередей. М.: Мир, 1966.

77. Коляденкова Л.Г., Печинкин A.B., Тришечкин С.И. Система МАР2/02 / 1/г с абсолютным приоритетом и общей очередью // Вестник РУДН. Серия "Прикладная математика и информатика". 2000. № 1. С. 72-90.

78. Корнышев Ю.Н. Однолинейная система с неоднородными повторными вызовами // В сб. "Теория телетрафика и сети с управляемыми элементами". М.: Наука, 1980. С. 113-122.

79. Корнышев Ю.Н. Однолинейная система с повторными вызовами и предварительным обслуживанием // Изв. АН СССР. Техническая кибернетика. 1977. № 2. С. 83-88.

80. Кузнецов Н.Ю. Конструктивный метод построения "исскуствен-ных" моментов регенерации // Труды семинара " Теория сложных систем и методы их моделирования". М.: ВНИИСИ, 1983. С. 15-22.

81. JIunaee В.В., Колин К.К. Серебровский Л.А. Математическое обеспечение управляющих ЦВМ. М.: Советское радио, 1972.

82. Лифшиц А.Л., Мальц Э.А. Статистическое моделирование систем массового обслуживания М.: Советское радио, 1978.

83. Манусевич B.C., Бусленко Н.П. Имитационное моделирование // В сб. "Методы развития теории телетрафика". М.: Наука, 1979.

84. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. М.: Изд-во МГУ, 1984.

85. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М.: Радио и связь, 1986.

86. Мизин И.А., Уринсон Л.С., Храмешин Г.К. Передача информации в сетях с коммутацией сообщений. М.: Связь, 1972.

87. Михалев Д. Г. Однолинейная система массового обслуживания с ограниченной очередью, многими входящими потоками и произвольными временем обслуживания // Проблемы передачи информации. 1970. Т. 6. Вып. 1. С. 87-96.

88. Наумов В.А. Численные методы анализа марковских систем. М.: Изд-во УДН, 1985.

89. Нетес В.А. Об оценке вероятности потери требования в системах массового обслуживания ограниченной емкости // Изв. АН СССР. Техническая кибернетика. 1988. № 3. С. 215-216.

90. Печинкин A.B. Система массового обслуживания с абсолютными приоритетами // Изв. АН СССР. Техническая кибернетика. 1983. № 6. С. 62-72.

91. Печинкин A.B. Система массового обслуживания с неординарным пуассоновским входящим потоком и относительными приоритетами // Техника средств связи. Серия "Системы связи". 1988. Вып. 6. С. ????

92. Печинкин A.B. Неординарный входящий поток в системах обслуживания с абсолютными приоритетами // Техника средств связи. Серия "Системы связи". 1990. Вып. 1. С. ???

93. Печинкин A.B. Система с абсолютными приоритетами и неординарным входящим потоком // Автоматика и телемеханика. 1990. № 10. С. 116-125.

94. Печинкин A.B. Однолинейная система обслуживания с марковским входящим потоком требований // Автоматика и телемеханика. 1996. № 4. С. 100-110.

95. Печинкин A.B. Стационарные вероятности состояний в системе с входящим потоком марковского типа, относительным приоритетом и раздельными очередями // Автоматика и телемеханика. 1998. № 1. С. 107-119.

96. Печинкин A.B. Стационарные вероятности состояний в системе с входящим потоком марковского типа, относительным приоритетом и общей очередью // Вестник МГТУ. Серия "Естественные науки". 1998. № 1(1). С. 5-18.

97. Печинкин A.B. Система BMAP/G/1/oo с дисциплиной преимущественного разделения прибора // Автоматика и телемеханика. 1999. № 10. С. 108-114.

98. Печинкин A.B. Система обслуживания с марковским входящим потоком и дисциплиной случайного выбора заявок из очереди // Автоматика и телемеханика. 2000. № 9. С. 90-96.

99. Рыков B.B. Управляемые системы массового обслуживания // Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М: ВИНИТИ. 1974. Т. 12. С. 143-157.

100. Самуилов К.Е. Система сигнализации N 7—ключевой элемент современных цифровых сетей связи // Сети. 1996. № 7. С. 1518.

101. Степанов С.Н. Численные методы расчета моделей с повторными вызовами. М.: Наука, 1983.

102. Степанов С.Н. Моменты избыточной нагрузки однолинейной системы с повторными вызовами // Изв. АН СССР. Техническая кибернетика. 1977. Т. 1. С. 88-93.

103. Тихоненко О.М. Модели массового обслуживания в системах обработки информации. Минск: Изд-во "Университетское", 1990.

104. Фалин Г.И. Груповое поступление требований в одноканальную систему с повторными вызовами // Украинский математический журнал. 1976. Т. 28, 4. С. 561-565.

105. Фалин Г.И. Однолинейная система с повторными вызовами // Изв. АН СССР. Техническая кибернетика. 1979. Т. 2. С. 107-114.

106. Фалин Г.И. О виртуальном времени ожидания в системах с повторными вызовами // Вестник МГУ. Математика и механика. 1988. Т. 6. С. 7-10.

107. Фонг Н.Х. О системе МAP2/G2/I/T с относительным приоритетом и с потоками, зависящими от состояния очередей // Тезисы докладов XXXIII научной конференции факультета физико-математических и естественных наук РУДН. М.: Изд-во РУДН, 1997. С. 99.

108. Фонг Н.Х. Исследование приоритетных систем массового обслуживания конечной емкости с марковскими потоками // Дис. канд. физ.-мат. наук: 05.13.17. Москва, 1997.

109. Фонг И.X. Гистерезисно-полосный контроль обслуживания в системах с групповым марковским потоком и полумарковским обслуживанием // Вестник РУДН. Серия "Прикладная математика и информатика". 2001. № 1. С. 90-101.

110. Хинчин А.Я. Работы по математической теории массового обслуживания. М.: Физматгиз, 1963.

111. Хомичков И.И. Производящие функции вероятностей состояний однолинейной системы с повторными вызовами / / Вести БГУ. Серия 1. 1987. Т. 1. С. 51-55.

112. Хомичков И.И. Система обслуживания с повторными вызовами, предварительным обслуживанием и блокировками // Изв. АН СССР. Техническая кибернетика. 1988. Т. 1. С. 188.

113. Шварц М. Сети связи. Протоколы, моделирование и анализ. М.: Наука, 1992.

114. Artalejo J.R. Explicit formulae for the characteristics of the M/H2/I retrial queue // J. of Operation Research Society. 1993. V. 44. JY® 3. P. 309-313.

115. Artalejo J.R. Retrial queues with negative arrivals // Proceedings of the International Conference on Stochastic Processes, Kerala, India, December 26-29, 1996, p. 159-167.

116. Artalejo J.R. Accessible bibliography on retrial queues // Math. Comput. Model. 1999. V. 30. P. 223-233.

117. Artalejo J.R., Gomez-Corral A. Generalized birth and death processes with applications to queues with repeated attempts and negative arrivals //OR Spektrum, Vol. 20, 1998, p. 5-14.

118. Atencia I., Bocharov P.P., Phong N.H. Analysis of a priority retrial queueing system // Proc. of Intern. Workshop on Distributed Computer Communication Networks. Moscow. June 16-19, 1998. P. 29-33.

119. Baiocchi A. Analysis of the loss probability of the MAP/G/1/K queue. Part I: Asymptotic Theory // Stoch. Models. 1994. V. 10. P. 867-893.

120. Baiocchi A., Blefari-Melezzi N. Analysis of the loss probability of the MAP/G/1/K queue. Part II: Approximations and numerical results // Stoch. Models. 1994. V. 10. P. 895-925.

121. Bocharov P.P., Pavlova О.I., Puzikova D.A. M/G/l/r retrial queueing systems with priority of primary customers // Mathematical and Computer Modelling. 1999. V. 30. P. 89-98.

122. Bocharov P.P., Pechinkin A. V. Application of branching processes to investigate the MAP/G/ljn queueing system with retrials // Proc. of Intern. Conf. "Distributed computer communication networks.

123. Theory and Applications". Tel-Aviv. November 9-13, 1999. P. 2026.

124. Bocharov P., Pechinkin A., Phong N., DApice C. On the BMAP/SM/l/r queueing system // Proc. of 9th IFIP Working Conf. on Performance Modelling and Evaluation of ATM h IP Networks. Budapest. June 27-29, 2001.

125. Bocharov P.P., Phong N.E. Retrial queues with several input flows // Intern. Conf. on Stochastic Proc. and their Appl. Cochin (India). December 17-20, 1999.

126. Bocharov P.P., Phong N.H. On the hysteresis threshold MAP/G/l/r queue // Proc. of 10th INFORMS Applied Probability Conf. Ulm (Germany). July 26-28, 1999. P. 218.

127. Bocharov P.P., Phong N.H. Analysis of BMAP/SM/l/r queue with hysteresis bandwidth mechanism // Proc. of Intern. Conf. on Control Problems. Moscow. June 29-July 2, 1999. P. 183-184.

128. Bocharov P.P., Phong N.H., Atencia I.M. Retrial queueing system with several input flows // Proc. of 4th Intern. Conf. on Oper. Res. La Habana. March 6-10. 2000. P. 17.

129. Bocharov P.P., Phong N.H., Atencia I.M. Retrial queueing system with several input flows // Investigación Operacional. 2001. № 2.

130. Bocharov P.P., Puzikova D.A. Matrix methods of analysis of queueing systems with limited retrial queue // Proc. of 1st Intern. Workshop on Retrial Queues. Madrid. September 22-24, 1998. P. 7-9.

131. Bretsnechneider G. Repeated calls with limited repetition probability // Proc. of 6th Intern. Teletraffic Congress. Munich. 1970. P. 434/1-434/5.

132. Brown P., Chemoil P., Delosme B. A congestion control policy for signalling networks // IEEE Intern. Conf. on Commun. 1985. P. 33-40.

133. Chaudhry M., Templeton J. A first course in bulk queues. New-York: John Wiley and Sons, 1983.

134. Choi B.D., Chang Y. MAPUMAP2/M/C retrial group of finite capacity and geometric loss // Math. Comput. Model. 1999. V. 30. P. 99-114.

135. Choi B.D., Han D.H., Falin G. On the virtual waiting time for an M/G/l retrial queue with two types of calls //J. Appl. Math, and Stoch. Anal. 1993. № 1. P. 11-23.

136. Choi B.D., Rhee K.H. The M/G/l retrial queue with retrial rate control policy // Probability in the Engineering and Informational Sciences. 1993. V. 7. P. 29-46.

137. Cinlar E. Introdution to stochastic processes. New Jersay: Prentice-Hall, 1975.

138. Cohen J. W. Basic problems of telephone traffic theory and the influence of repeated calls // Philips Telecommunication Review. 1957. V. 28, 2. P. 49-100.

139. Cooper R.B. Introduction to queueing theory. New York: North-Holland Publ., 1981.

140. DApice С., Manzo R., Phong N.H., Salerno S. Retrial queueing system with several input flows and with server vacations // Вестник РУДН. Серия "Прикладная математика и информатика". 2000. № 1. С. 60-71.

141. Diamond J.E., Alpha A.S. Matrix analytical methods for М/РН/1 retrial queues // Stochastic Models. 1995. V. 11. № 3. P. 447-470.

142. Diamond J.E., Alpha A.S. The МАР/РН/1 retrial queue // Commun. Statist. Stochastic Models. 1998. V. 14. № 3. P. 11511177.

143. Dudin A. Optimal control for an M x/G /1 queue with two operation modes // Probability in the Engineering and Informational Sciences. 1997. V. 11. P. 255-265.

144. Dudin A. Optimal multithreshold control for a ВМАР/G/1 queue with N service modes // Queueing Systems. 1998. V. 30. N. 3-4. P. 273-287.

145. Dudin A. A retrial BMAP/SM/1 models with impatient customers // Тезисы докладов XV Белорусской зимней школы-семинара по теории массового обслуживания "Массовое обслуживание. Потоки, системы, сети". Минск: Изд-во БГУ, 1999. С. 22-25.

146. Dudin A.N., Klimenok V.I. Queueing systems with BMAP/G/1 with repetead calls // Mathematical and Computer Modelling. 1999. V. 30. P. 115-128.

147. Dudin A.N., Klimenok V.I. A retrial BMAP/SM/1 system with linear repeated requests // Queueing Systems. 2000. V. 34. P. 47-66.

148. Dudin A.N., Klimenok V.I. Optimal multithreshold control for a BMAPn/SMn/1 retrial queue // Proc. of 1st Intern. Workshop on retrial queues. Madrid. September 22-24, 1998. P. 13-14.

149. Dudin A.N.; Nishimura S. Optimal hysteretic control for a ВМАР/SM/l/N queue with two operation modes // Mathematical Problems in Engineering. 2000, V. 5. P. 397-420.

150. Falin G.I. Single-line repeated orders queueing systems // Optimization. 1985. V. 17. 5. P. 685-691.

151. Falin G.I. On a multiclass batch arrival retrial queue // Adv. Appl. Prob. 1988. V. 20. P. 483-487.

152. Falin G.I. A survey of retrial queue // Queueing Systems. 1990. № 7. P. 127-168.

153. Falin G.I., Templeton J.G.C. Retrial queues. London: Chapman & Hall, 1997.

154. Farahmand K., Smith N.H. Retrial queues with recurrent demand option //J. Appl. Math, and Stoch. Anal. 1996. № 9. P. 221-228.

155. Gouweleeuw F. The loss probability in finite-buffer queues with batch arrivals and complete rejection // Probability in the Engineering and Informational Sciences. 1994. V. 8. P. 221-227.

156. Gouweleeuw F. The loss probability in a BMAP/G/1/N + 1 queue // Stochastic Models. 1996. V. 12. P. 473-492.

157. Graham A. Kronecker products and matrix calculus with applications. Chichester: Ellis Horwood, 1981.

158. Gün L. Experimental results on the matrix-analytical solution techniques — extensions and comparisions // Stochastic Models. 1989. V. 5(4). P. 669-682.

159. Halberstadt S., Kofman D. A dynamic bandwidth allocation mechanism for connectionless traffic on ATM networks // Proc. of XV Intern. Teletraffic Congres. 1997. P. 1281-1290.

160. Handbuch der Bedienungstheorie. I. Grundlagen und Methoden / Gnedenko B.W., Konig D. (red.). Berlin: Academie-Verlag, 1983.

161. Handbuch der Bedienungstheorie. II. Formeln und andere Ergebnisse / Gnedenko B.W., Konig D. (red.). Berlin: Academie-Verlag, 1984.

162. Hanschke T. Explicit formulas for the characteristics of the M\M\2\2 queue with repeated attempts //J. Appl. Prob. 1987. V. 24. P. 486-494.

163. Heffes H., Lucantoni D.M. A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance // IEEE J. Selected Areas in Comm. 1986. V. 4. № 6. P. 856-868.

164. Izydorczyk J. M/G/l queues with state dependent service times // Archiwum Informatyki Teoretycznej i Stosowanej. 1990. V. 2. 1-2. P. 19-26.

165. Kabak I. W. Blocking and delays in /M/c bulk arriving queueing systems // Oper. Res. 1968. V. 16. № 4. P. 830-840.

166. Kabak I. W. Blocking and delays in

167. M/c bulk arriving queueing systems // Management Sei. 1970. V. 17. № 1. P. 112-115.

168. Keilson J., Cozzonlino J., Young H. A service system with unfiled requests repeated 11 Oper. Res. 1968. V. 16. P. 1126-1137.

169. Khamisy A., Sidi M. Discrete-time priority queueing systems with two-state Markov modulated arrival process // Proc. of IEEE INFOCOM '91. Bal Harbour. Florida. 1991. P. 1456-1463.

170. Kurlani V.G. Expected waiting times in a multiclass batch arrival retrial queue //J. Appl. Prob. 1986. V. 23. P. 144-159.

171. Kidkarni V.G. On queueing systems with retrials //J. Appl. Prob. 1983. V. 20. P. 380-389.

172. Lucantoni D.M. New results on the single server queue with a batch Markovian arrival process // Stochastic Models. 1991. V. 7. P. 1-46.

173. Lucantoni D.M. The BMAP/G/1 queue: A tutorial // Models and techniques for performance evalution of computer and communication system. New-York.: Springer-Verlag, 1993. P. 330-358.

174. Lucantoni D.M., Choudhury G.L., Whitt W. The transient BMAP/G/1 queue // Stochastic Models. 1994. V. 10(1). P. 145182.

175. Lucantoni D.M., Meier-Hellstern K.S., Neuts M.F. A single-server queue with server vacations and a class of non-renewal arrival processes // Adv. Appl. Prob. 1990. V. 22. P. 676-705.

176. Lucantoni D.M., Neuts M.F. Some steady-state distributions for the MAP/SM/1 queue // Communications in Statistics-Stochastic Models. 1994, V. 10. P. 575-598.

177. Manfield D.R., Tran-Gia P. Analysis of a finite storage system with batch input arising out of message packetization // IEEE Trans. Commun. 1982. V. 30. № 3. P. 456-463.

178. Medhi J. Stochastic models in queueing theory. London: Acad. Press, 1981.

179. Miyazawa M. Complementary generating functions for Mx/GI/l/k and GI/MF/l/k queues and their applications to the comparision of loss probabilities //J. of Appl. Prob. 1990. V. 27. P. 684-692.

180. Neuts M.F. Matrix-geometric solutions in stochastic mo dels.-Baltimore and London: The Johns Hopkins Univ. Press. 1981.

181. Neuts M.F. Structured stochastic matrices of MjG/1 type and their applications. New York: Marcel Decker, 1989.

182. Neuts M.F. Models based on the Markovian arrival process // IEICE Transactions on Communications. E75-B. 1992. P. 1255-1265.

183. Neuts M.F. A versatile Markovian point process. // J. of Appl. Prob. 1979. V. 16. P. 764-779.

184. Nishimura S., Sato H. Eigenvalue expression for mean queue length of BMAP/G/1 queue // J. of Operational Research Society of Japan. 1997. V. 40. P. 122-132.

185. Phong N.H., DApiceManzo R., Salerno S. On a multiclass arrival retrial queue with server's vacations // Proc. of Intern. Conf. and Workshop on Stoch. Networks. Madison. June, 2000. P. 23.

186. Ramaswami V. The N/G/l queue and its detailed analysis. // Adv. Appl. Prob. 1980. V. 12. P. 222-261.

187. Ridout G.E. A study of retrial queueing systems with buffers // M.A.Sc. Thesis. Department of Industrial Engineering, University of Toronto, 1984.

188. Specification of signalling system N 7 CCITT // Blue Book. Fasc. YI.7. Geneva. 1989.

189. Stepanov S.N. The correlation function of a single-line queue with repeated attempts and its application to load measurement // Methods and Structures of Teletraffic Systems. Moscow, 1979.

190. Stepanov S.N. Optimal calculation of characteristics of models repeated calls //Proc. of 12th Intern. Teletraffic Congress. Torino. 1988.

191. Sugahara A., Takine T., Takahashi Y., Hasegawa T. Analysis of a non-preemtive priority queue with SPP arrivals of high class // Performance Evaluation. 1995. V. 21. P. 315-238.

192. Suzuki T. A queueing system with service depending on queue-length // Comment. Mat. Univ. St. Pauli. 1961. V. 10. N 10. P. 12621273.

193. Suzuki T. On a queueing process with service depending on queue-length // J. of Operation Research Society of Japan. 1962. V. 4. № 4. P. 147-169.

194. Takagi H. Analysis of finite-capacity M/G/l queue with a resume level // Performance Evaluation. 1985. № 5. P. 197-203.

195. Takagi H. Queueing analysis: A foundation of performance evaluation. Part 1. Vacations and priority systems. Amsterdam: North-Holland Publ., 1991.

196. Takine T. A non-preemptive priotiy MAP/G/1 queue with two classes of customers //J. Opns. Res. Soc. Japan. 1996. V. 39. № 2. P. 266-290.

197. Takine T., Hasegawa T. The workload in the MAP/G/1 queue with state-dependent services: its application to a queue with preemtive resume priority // Stoch. Mod. 1994. V. 10. P. 183-204.

198. Takine T., Matsumoto Y., Suda T., Hasegawa T. Mean waiting times in non-preemptive priotiy queues with Markovian arrival and i.i.d. service processes // Performance Evaluation. 1994. V. 20. P. 131-149.

199. Tijms H. Heuristics for finite-buffer queues // Probability in the Engineering and Informational Sciences. 1992. V. 6. P. 277-285.

200. Yang T., Posner M.J.M., Templeton J.G.C. The M\G\l retrial queue with nonpersistent customers // Queueing Systems. 1990. V. 7. P. 209-218.

201. Yang T., Templeton J.G.C. A survey on retrial queues // Queueing Systems. 1987. V. 2. P. 201-233.

202. Wei Q., Robles F., Chen K., Pujolle G. Some investigations on supporting IP traffic through ATM links with dynamic bandwidth allocation 11 Proc. of IFIP WATM'95, First Workshop on ATM Traffic Management. December 1995.