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



/ <мшш»>

- - • "" / / ° 1 ' У I ч/ Ч/ * г

РОССИЙСКИМ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

На правах рукописи

Пузикова Дарья Анатольевна

УДК 519.21

АНАЛИЗ ОДНОЛИНЕЙНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С

ПОВТОРНЫМИ ЗАЯВКАМИ

(05.13.17 - теоретические основы информатики)

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель - д.т.н., профессор Бочаров П.П.

Москва -1999

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ................................................................................................................................................................5

ГЛАВА 1. СИСТЕМА МАЗЛ/г С ПОВТОРНЫМИ ЗАЯВКАМИ............................................................................................................................................24

§ 1. Описание системы......................................................................................................................24

§2. Система уравнений....................................................................................................................25

§ 3. Изучение системы в случае классической дисциплины

повторений................................................................................................................................................30

ЗЛ. Уравнения для факториальных моментов и их

решение ......................................................................................................................................................30

3.2. Среднее число заявок в системе..........................................................39

§4. Изучение системы в предположении постоянной

интенсивности потока с орбиты..........................................................................41

4.1. Стационарное распределение длины очереди первичных заявок........................................................................................................................41

4.2. Среднее число заявок в системе в случае простоя прибора........................................................................................................................................................45

4.3. Среднее число заявок в системе........................................................49

4.4. Дисперсия числа заявок на орбите..................................................52

§ 5. Условие эргодичности......................................................................................................56

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

ВЫВОДЫ..................................................................................... 64

ГЛАВА 2. АНАЛИЗ СИСТЕМЫ РН/РНЛ/О/б С ПОВТОРНЫМИ ЗАЯВКАМИ..................................................65

§ 1. Описание системы....................................................................................................................65

§2. Система уравнений равновесия..........................................................................66

§ 3. Анализ и решение уравнений равновесия........................................70

§ 4. Соотношения для макрохарактеристик и некоторые

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

§ 5. Обобщение нагрузки....................................................... 76

5.1 .Система ОРН/РНЛ/О/б с повторными заявками...... 76

5.2.Система РЬЩРНЛ/О/з с повторными заявками...... 78

§ 6. Стационарные вероятности состояний для вложенных

цепей Маркова ................................................................ 80

6.1. Стационарные вероятности по моментам поступлений ......................................................................... 80

6.2. Стационарные вероятности по моментам окончания обслуживания...................................................... 82

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

7.1. Изучение показателей качества работы конкретных систем.......................................................... 85

7.2. Изучение вычислительных особенностей алгоритма и программ..................................................... 98

ВЫВОДЫ .................................................................................. 102

ГЛАВА 3. АНАЛИЗ СИСТЕМЫ РН/РН/УО/б С ПОВТОРНЫМИ ЗАЯВКАМИ И ОТКЛЮЧЕНИЯМИ ПРИБОРА................................................................ 103

§ 1. Описание системы........................................................... 103

§2. Система уравнений равновесия...................................... 104

§ 3. Анализ и матрично-мультипликативное решение

уравнений равновесия.................................................... 112

§ 4. Некоторые показатели производительности и соотношения между макрохарактеристиками системы........... 117

§5. Обобщение марковской модели.................................... 119

5.1. Система (^РН/РНЛ/О/б с повторными заявками и отключениями обслуживающего прибора..................... 120

5.2. Система РШ^РНЛ/О/б с повторными заявками и отключениями обслуживающего прибора..................... 122

§ 6. Стационарные вероятности состояний для вложенных

цепей Маркова..................................................................................................................................125

6.1. Стационарные вероятности по моментам поступлений ..................................................................................................................................125

6.2. Стационарные вероятности по моментам окончания обслуживания..............................................................................................................128

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

ВЫВОДЫ................................................................................... 145

ЗАКЛЮЧЕНИЕ..................................................................................................................................................146

ЛИТЕРАТУРА....................................................................................................................................................147

ПРИЛОЖЕНИЯ................................................................................................................................................154

ПРИЛОЖЕНИЕ 1............................................................................................................................................155

ПРИЛОЖЕНИЕ 2

159

ВВЕДЕНИЕ

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

Исследования математических моделей проектируемых и существующих сетей передачи данных, проводимые с целью определения и оптимизации их вероятностно-временных характеристик, являются неотъемлемым этапом современной технологии создания средств передачи информации. Зная эти характеристики, можно разработать оптимальный механизм управления передачей информационных потоков. Одним из наиболее мощных инструментов количественного анализа функционирования вычислительных ресурсов является аппарат теории сетей и систем массового обслуживания (СеМО и СМО). Применению этого аппарата к исследованию производительности сетей и систем связи посвящено большое количество работ [3, 15, 21, 25, 27, 34].

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

услышав короткие гудки, мы вешаем трубку и повторяем свою попытку через некоторое время. Кроме телефонных линий, эффект возникновения повторных требований характерен для вычислительных и телекоммуникационных сетей. Наиболее полный обзор результатов для СМО с повторными заявками, ставших уже в некотором роде классическими, содержится в работах Г.И. Фалина [56, 58] и и работе С.Н. Степанова [25]. Последние достижения для СМО с повторениями представлены на I международной конференции по этой проблеме, состоявшейся в Испании (г. Мадрид, 1998 год, [71]).

Для краткого описания СМО мы будем пользоваться в дальнейшем модифицированными обозначениями Кендалла. В этих обозначениях однофазные СМО могут быть представлены в виде А/В/с/г/в, где символом А кодируется поток заявок, входящий в систему, символом В — тип обслуживания заявок, с обозначает число обслуживающих приборов, г — число мест в накопителе перед приборами, а 5 — размер (объем) орбиты. Для обозначения типа входящего потока и обслуживания чаше всего встречаются следующие коды: М — пуассоновский поток или экспоненциальное обслуживание, В — детерминированный поток или одноименное обслуживание, Н — гиперэкспоненциальный поток или обслуживание, Е — эрланговский поток или обслуживание, РН — поток или обслуживание фазового типа, С1 — произвольный рекуррентный поток, С — призвольное рекуррентное обслуживание, МАР — марковский входящий поток. В некоторых моделях параметры г и к полагаются бесконечными, и тогда чаще всего они опускаются. Для распределений фазового типа иногда с помощью нижнего индекса указывается количество фаз (например, символ Н2 означает гиперэкспоненциальное распределение 2-го порядка). Если на месте символа А стоит несколько символов через запятую, то это означает, что в систему поступает несколько потоков заявок. В отдельных случаях дополнительно может указываться дисциплина обслуживания, то есть порядок поступления заявок из накопителя на приборы. В случае отсутствия особых указаний принимается, что заявка, первой поступившая в накопитель, первой поступает на освободившийся прибор. Заметим, что для систем с повторными заявками в дополнение к обозначениям Кендалла словами сообщается о наличии в системе повторных заявок ( например, СМО М/С/1 с повторными заявками). Отличительной особенностью систем с повторными заявками является то, что для них в названии иногда указывается тип дисциплины

осуществления повторений (например, СМО М/С/1 с повторными заявками и классической дисциплиной повторений).

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

По количеству обслуживающих приборов системы с повторными заявками делятся на системы, имеющие один прибор и системы, имеющие несколько обслуживающих приборов. Заметим, что модели с несколькими обслуживающими приборами и повторными заявками были впервые введены в [74]. Подробный обзор результатов для систем такого типа проводится в [58].

По количеству входящих потоков СМО с повторениями делятся на системы с одним поступающим потокоми системы с несколькими поступающими потоками. Системы с несколькими входящими потоками рассматриваются, например, в работах [48, 49]. Поток заявок является однородным, если все приходящие заявки имеют один тип и неоднороднымв противоположном случае. Тип заявки в свою очередь определяет функцию распределения (ФР) времени ее обслуживания и ФР времени между повторными попытками, совершаемыми этой заявкой. Обычно в качестве этих функций рассматриваются экспоненциальные ФР с различными параметрами, соответствующими типу заявки. Часто рассматривают системы, в которых интенсивность повторений не зависит от типа заявки.

По количеству одновременно поступающих заявок СМО делятся на системы с ординарными потоками и системы с групповыми потоками. В системе с ординарным потоком вероятность одновременного прихода нескольких заявок равна нулю, а в системе с групповым потоком заявки поступают группами. Большинство работ для моделей с повторными заявками посвящено системам с ординарным входящим потоком. Системы с групповым входящим потоком и повторными заявками изучаются, например, в работах [55, 65, 67].

Системы с неоднородным ординарным потоком рассматриваются, например, в [5, 58]. Системы с неоднородным групповым потоком рассматриваются, например, в [55, 65, 67]. Заметим, что в неоднородном потоке заявки могут иметь разный приоритет, и более приоритетная заявка, придя в систему и обнаружив на приборе

заявку более низкого приоритета, может прервать ее обслуживание. Именно такая ситуация рассматривается в работе [65].

В системах с двумя поступающими потоками и повторными за-явкаи обычно предполагается, что один поток является более приоритетным, чем другой. Заявки приоритетного потока, найдя прибор занятым, попадают в предназначенный для них накопитель, а заявки неприоритетного потока, обнаружив обслуживающий прибор занятым, должны покинуть зону обслуживания и повторить свою попытку позже. Заявки, имеющие более низкий приоритет, не могут получить обслуживание до тех пор, пока накопитель занят. Время обслуживания для заявок обоих типов обычно предполагается одинаковым. Система такого типа с одним обслуживающим прибором и ограниченным накопителем для приоритетных заявок рассматривается, например, в [50]. Система такого типа с несколькими приборами и неоганиченным накопителем для приоритетных заявок впервые была изучена в [56].

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

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

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

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

постоянной интенсивностью суммарного потока — коллективному. Линейная дисциплина является обобщением первых двух вариантов. Заметим, что такая классификация приводится в работе [44]. Рассмотрим подробнее каждый вариант поведения заявок на орбите.

Классическая дисциплина осуществления повторений характеризуется тем, что каждая повторная заявка независимо от других делает попытки занять обслуживающий прибор. Если в момент совершения попытки прибор оказывается занятым, повторная заявка возвращается на орбиту. Если заявка находит прибор свободным, она попадает на обслуживание. Длительности интервалов между повторными попытками для каждой заявки с орбиты представляют собой независимые в совокупности случайные величины, распределенные по экспоненциальному закону с параметром 7. Системы с такой дисциплиной повторений рассматриваются, например, в [38, 39, 42, 59].

Дисциплина с постоянной интенсивностью суммарного потока характеризуется тем, что повторные заявки осуществляют попытки попасть на прибор независимо друг от друга, но с интенсивностью обратно пропорциональной числу заявок на орбите. Иными словами, времена между повторными попытками для каждой заявки предполагаются независимыми, одинаково распределенными случайными величинами с параметром 6/п, п > 0, если орбита содержит п заявок. Коллективному поведению заявок на орбите можно дать и другую интерпретацию, а именно можно считать, что попытки по сути своей являются проверками обслуживающего прибора и осуществля-ютя централизованно. Если при проверке обнаружено, что прибор свободен, то на него сразу отправляется одна из заявок с орбиты: либо выбранная случайно, либо — по какому-либо иному принципу. Если прибор оказывается занятым, повторная попытка откладывается на случайное время, имеющее экспоненциальное распределение с параметром 6. Если орбита пуста, то проверки обслуживающего прибора не осуществляются. Модели с постоянной интенсивностью потока с орбиты используются для расчета характеристик локальных сетей шинной топологии, имеющих общий моноканал передачи данных. Системы с такой дисциплиной рассматриваются, например, в работах [17, 41, 44, 50, 60, 70].

Заметим, что в случае классической дисциплины, если орбита содержит п заявок, на прибор поступает поток повторных заявок интенсивности 7 п. В случае дисциплины с постоянной интенсивно-

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