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

• Пузикова, Дарья Анатольевна
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Пузикова, Дарья Анатольевна

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

повторений

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

решение

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

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

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

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

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

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

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

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

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

ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВЫВОДЫ

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЯ

ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ

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, не зависящую от числа заявок на орбите. Чтобы не рассматривать два случая отдельно, часто обращаются к более общему случаю дисциплины повторений, а именно к так называемой линейной дисциплине. Она характеризуется тем, что интервалы времени между повторными попытками независимы и имеют экспоненциальное распределение с параметром и(п)8 + 771, где и{п) — единичная функция Хевисайда, а п — число заявок на орбите.

Отметим, что не для любой модели удается получить решение для линейной дисциплины. С этим связана необходимость отдельного рассмотрения классической и постоянной дисциплины повторений. Например, в работе [59] каждой из дисциплин осуществления повторений посвящен отдельный раздел. Заметим, что, если удается получить результаты для линейной дисциплины, то это дает возможность не рассматривать отдельно две другие дисциплины. Имея результаты для линейной дисциплины, мы можем, положив <5 = 0, получить результаты для классической дисциплины осуществления повторений. Аналогично, положив 7 = 0, мы автоматически получим все результаты для случая постоянной интенсивности суммарного потока с орбиты. Заметим, что система с линейной дисциплиной повторений рассматривается, например, в [44].

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

Также относительно дисциплины осуществления повторений важно заметить, что существуют системы, в которых используется некоторый механизм регулирования числа повторных попыток для каждой заявки. Для этого рассматривается набор вероятностей {Н^. ] > 1}, который носит название функции настойчивости. В таких системах повторная заявка после совершения .7-ой повторной попытки возвращается на орбиту с вероятностью Н^ и с дополнительной вероятностью 1 — Н^ покидает систему. Часто рассматривают случай, когда вероятность ухода заявки из системы не зависит от числа повторных попыток, то есть = Н2 = Щ = ... — р. Тогда говорят, что рассматривается система с р-настойчивыми повторными заявками. Еслир = 1, то требования называют абсолютно настойчивыми. Впервые такие модели для СМО с несколькими при-

борами были введены в [51]. Дальнейшее развитие этих моделей для однолинейных систем в предположении экспоненциального распределения времени обслуживания отражено в работе [61]. Для произвольного распределения времени обслуживания основные результаты для однолинейных систем были получены, например, в [75]. Для систем массового обслуживания с несколькими приборами эта модель рассматривается в работах [16, 52]. Также заметим, что иногда рассматриваются модели, в которых заявки после окончания обслуживания могут с некоторой положительной вероятностью вернутьсл на орбиту (см. [60]).

В большинстве работ по повторным заявкам орбита считается неограниченной. Однако имеется ряд работ, в которых предполагается, что размер (объем) орбиты (число заявок, которые могут совершать повторные попытки) ограничен некоторым числом s. При таком подходе число неизвестных в системе уравнений равновесия конечно, и для ее решения применяются стандартные методы линейной алгебры. В зарубежной литературе системы с ограниченной орбитой называют "truncated systemsВ книгах С.Н. Степанова [25] и Г.И. Фалина [58] подробно исследуется возможность аппроксимации СМО с неограниченной орбитой соответствующими моделями с конечной орбитой, и проводится анализ погрешностей, возникающих при таком подходе.

Остановимся подробнее на однолинейных СМО с повторными заявками. Наиболее полно изученной является система М/G/l с повторными заявками и различными дисциплинами осуществления повторений. Входящий в систему поток предполагается пуассонов-ским. Если заявка застала обслуживающий прибор занятым, она попадает на орбиту, с которой, в соответствии с рассматриваемой дисциплиной повторений, делает попытки попасть на обслуживающий прибор. Частный случай этой модели, а именно система М/М/1 с повторными заявками, впервые был рассмотрен в работе [51]. Первые результаты для системы М/G/l с повторными заявками и произвольным обслуживанием были получены в работе [63]. В дальнейшем для этой системы было получено стационарное распределение вероятностей состояний и были исследованы следующие временные характеристики ее работы: период занятости и свободный период для орбиты, виртуальное время ожидания для отдельной заявки, времена между выходами заявок из системы (в терминах ПЛС) и др.. Основные результаты, полученные к настоящему времени для си-

стемы М/С/1 с повторными заявками, подробно описаны в книге [58].

Также рассматриваются обобщения классической модели М/С/1 с повторными заявками, а именно: система с групповым входящим потоком, система с заявками различных типов, система с р-настойчивыми требованиями, система с прерываниями, система с управлением потоком повторных вызовов, система с буфером для поступающих заявок, система с двумя способами коммуникации (см. [18]), система с отключениями прибора, система с ненадежным прибором.

Остановимся подробнее на однолинейных системах с повторными заявками, имеющих накопитель ограниченной емкости. Однолинейные системы с накопителем для первичных заявок изучались в работах [26, 56, 58, 72]. В системах такого типа поступившая заявка, заставшая обслуживающий прибор занятым, либо занимает место в накопителе, если он не полностью заполнен, либо попадает на орбиту, которая предполагается неограниченной. Заявки, попавшие в накопитель, будем называть первичными. Как только прибор освобождается, на него сразу же поступает заявка из первичной очереди, если в ней есть заявки. Заявки с орбиты пытаются попасть в зону обслуживания (либо на прибор, либо в накопитель). Если повторная заявка находит обслуживающий прибор занятым, а накопитель заполненным, она опять возвращается на орбиту. Точные результаты были получены только для случая наличия одного места для ожидания в предположении, что время обслуживания имеет экспоненциальное распределение.

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

Добавим, что системы с несколькими обслуживающими приборами и ограниченным накопителем исследованы в [25, 62, 72]. Аналогичная модель с неограниченным накопителем рассмотрена в [40]. В последнем случае организация повторного обслуживания подчиняется некоторому вероятностному механизму.

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

Однако пуассоновский поток и поток от конечного числа источников нагрузки не отражают весь спектр потоков, возникающих при моделированир! реальных объектов. Заметим, что имеется ряд работ, в которых входящий поток не принадлежит ни к одному из этих двух типов. Так, например, в [29] рассматривается система а/М/1 с рекуррентным входящим потоком, в которой время между поступлениями заявок внешнего потока имеет либо эрланговское, либо гиперэкспоненциальное распределение второго порядка. В работе [30] входящий поток предполагается потоком Кокса 2-го порядка. В этих работах получены производящие функции стационарного распределения состояний в виде гипергеометрических функций и основные показатели производительности систем.

Помимо модели М/С/1 с повторными заявками, для которой время обслуживания предполагается произвольным, имеется ряд работ, в которых предполагается, что функция распределения времени обслуживания принадлежит к некоторому определенному классу. Так, например, в работах [17, 19, 20] исследуется система М/Е/1 с повторными заявками, а в работе [38] — система М/Н^/Х с повторными заявками. Для обеих моделей получено стационарное распределение вероятностей состояний системы. Для второй модели также получено распределение времени ожидания начала обслуживания. В работе [20] дополнительно предполагается, что может иметь место конфликтная ситуация.

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

ных вероятностей состояний исходной системы. Заметим, что многофазное распределение времени обслуживания такого типа является частным случаем РН-распределения (все фазы соединены последовательно, и заявка может выйти с каждой фазы с некоторой положительной вероятностью).

Некоторым обобщением моделей, исследованных в [17, 19, 20, 25, 38], можно считать СМО М/РН/1 с неограниченной орбитой и распределением времени обслуживания фазового типа, рассмотренную в [54]. В этой работе получено стационарное совместное распределение числа заявок на орбите и фазы обслуживания, а также распределение времени ожидания начала обслуживания.

Обобщением моделей, рассмотренных в [17, 19, 20, 25, 29, 30, 38, 53] является СМО РН/ РН/1/0/з с повторными заяками и ограниченной орбитой, рассматриваемая во второй главе диссертации. Как уже было отмечено выше, символ РН обозначает распределение фазового типа, которое было введено М. Ньютсом [70]. Отметим, что СМО ограниченной емкости с ординарным фазовым потоком и фазовым обслуживанием неоднократно рассматривались в литературе [3, 4, 5, 12]. Однако аналогичные СМО с дополнительным предположением о наличии повторных заявок не были исследованы в известных автору работах.

Преимущество РН-распределения заключается в том, что оно включает в себя в качестве частных случаев экспоненциальное, эр-ланговское, гиперэкспоненциальное, гиперэрланговское и некоторые другие распределения. Также заметим, что одним из методов анализа СМО (?//0г/1/г без повторных заявок является ее приближенный анализ на основании результатов для СМО с фазовым потоком и фазовым обслуживанием. Это связано с тем, что по двум моментам (среднее и коэффициент вариации) можно построить ([3, 13]) некоторое РН-распределение, которое будет являться приближением для произвольного рекуррентного потока (или рекуррентного обслуживания) с такими же соответствующими моментами. Заметим, что распределение Эрланга хорошо приближает распределения с коэффициентом вариации меньшим 1, а гиперэкспоненциальное распределение, в свою очередь, является хорошим приближением для распределений, имеющих коэффициент вариации превосходящий 1. Это идея может быть также взята за основу для приближенного анализа моделей с повторениями.

Как уже отмечалось выше, СМО РН/РН/1/г с накопителем

ограниченной емкости без повторных вызовов исследовалась в Используемый в [3, 12] подход был развит в главе 2 диссертационной работы для анализа однолинейной СМО с повторными заявками, характеризуемой распределениями фазового типа. Заметим, что СМО с фазовым потоком, фазовым обслуживанием и повторными заявками не исследовались в известных автору работах. Такие СМО можно использовать в качестве моделей для приближенного анализа локальных вычислительных сетей шинной топологии, имеющих общий моноканал передачи данных. Подробнее о моделировании таких сетей можно узнать из работ [30, 33, 36].

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

Однако в настоящее время большой интерес представляют модели, в которых одновременно с отключениями прибора предполагается наличие повторных заявок. Так, например, в работах [41, 65, 67, 68] изучаются системы в предположении наличия этих двух составляющих. Кратко остановимся на моделях, рассматриваемых в этих работах. Так, в работе [41] исследуется СМО М/С/1 с постоянной дисциплиной повторений и отключениями обслуживающего прибора. Дисциплина отключения является исчерпывающей, то есть прибор отключается только в том случае, если система пуста (прибор свободен и нет повторных заявок). Предполагается, что время отключения имеет экспоненциальное распределение, а время обслуживания распределено произвольно. Если за время отключения размер орбиты не меняется, то прибор опять отключается. В противоположной ситуации прибор выходит из состояния отключения и ждет прихода заявки. Проведен полный анализ этой системы, включающий в себя условие эргодичности, предельное поведение, стохастическое разложение для ряда характеристик и механизм оптимального управления.

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

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

(

Заметим, что иногда рассматриваются модели с другой природой отключений прибора. В этих моделях предполагается, что прибор может отключиться в то время, когда на нем происходит обслуживание заявки. Такие СМО принято называть системами с ненадежным прибором. СМО такого типа рассматривается, например, в [39].

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

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

Важно отметить, что СМО М/РН/1/г и РН/М/1/г с ограниченным накопителем и дисциплиной отключения со случайным механизмом, но без повторных заявок, были изучены в [12]. Использованный в [12] подход был развит в главе 3.

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

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

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

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

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

Целью диссертационной работы является

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

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

Научная новизна и результаты, выносимые на защиту, состоят в следующем:

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

на орбите. Также найдено необходимое и достаточное условие эрго-

/ 0

дичности процесса, описывающего функционирование исследуемои СМО.

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

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

3. На основе полученных теоретических результатов разработан комплекс программ для расчета показателей производительности однолинейных СМО с повторными заявками, рассмотренных в данной диссертационной работе.

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

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

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

Реализация результатов работы. Исследование систем массового обслуживания с повторными заявками проводилось в рамках НИР "Разработка математических методов и алгоритмов анализа цифровых сетей с интеграцией служб" (государственный регистрационный номер 01.960.0 09077), выполняемой в соответствии с планами РУДН, а также в рамках гранта INTAS № 96-0828 "Advances in Retrial Queues".

Апробация работы. Материалы диссертации докладывались на международных конференциях: "Distributed Computer Communi-

cation Networks. Theory and Applications" (Тель-Авив, 1997 г.), "First International Workshop on Retrial Queues" (Мадрид, 1998 г.), XIII и XIV Белорусских зимних школах-семинарах по теории массового обслуживания (Минск, 1997, 1998 гг.); на XXXIII и XXXV научных конференциях факультета физико-математических и естественных наук РУДН (Москва, 1997, 1999 гг.); на научном семинаре по теории массового обслуживания кафедры теории вероятностей и математической статистики РУДН.

Публикации. По материалам диссертации опубликовано 10 работ, из них 3 в центральной печати.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и двух приложений. Каждая глава состоит из параграфов, некоторые из которых подразделяются на пункты. Формулы нумеруются отдельно внутри каждого параграфа с указанием его номера. Если параграф подразделяется на пункты, то нумерация проводится отдельно в каждом пункте с указанием номера пункта и параграфа. Теоремы, рисунки и таблицы нумеруются отдельно внутри каждого параграфа с указанием его номера. При ссылке на формулы, теоремы и рисунки из другой главы указывается также номер главы.

В главе 1 рассматривается однолинейная СМО с накопителем конечной емкости с пуассоновским входящим потоком заявок и произвольным распределением времени их обслуживания. При переполнении системы поступающая заявка попадает на орбиту, размер которой предполагается неограниченным. С орбиты заявка может попасть только на свободный прибор. В модифицированных обозначениях Кендалла система кодируется как СМО MfG/1/r с повторными заявками. Подробное описание модели приводится в § 1. В § 2 проводится вывод системы дифференциальных уравнений с граничными условиями для стационарных вероятностей рассматриваемой СМО. В § 3 модель изучается в предположении независимого поведения заявок на орбите, которому соответствует классическая дисциплина повторений. В пункте 1 § 3 найдено стационарное распределение длины очереди заявок в накопителе и представлен рекуррентный алгоритм расчета факториальных моментов числа заявок на орбите. В пункте 2 § 3 получена формула для среднего числа заявок в системе безотносительно к их виду, которая является обобщением известной формулы Поллачека-Хинчина для системы M/G/1 без повторных заявок. В § 4 модель, описанная в § 1, исследуется

в предположении постоянной интенсивности потока с орбиты. В пункте 1 § 4 найдено стационарное распределение длины очереди заявок в накопителе. В пункте 2 § 4 получена формула для среднего числа заявок в системе в случае простоя прибора. Заметим, что эта характеристика необходима для получения числовых характеристик орбиты. Формула для среднего числа заявок в системе в целом безотносительно к их виду, полученная в пункте 3 § 4, может быть использована для расчета среднего числа заявок на орбите, так как стационарное распределение числа заявок в накопителе нам известно. В пункте 4 § 4 представлен алгоритм расчета дисперсии числа заявок на орбите. В § 5 с помощью построения цепи Маркова, вложенной по моментам окончания обслуживания, определяется достаточное условие для эргодичности процесса, описывающего функционирование рассматриваемой СМО. Это условие выражается в ограничении на загрузку системы р. В § 6 приводятся результаты численных исследований, их анализ и сравнение для различных дисциплин повторений. Результаты главы 1 достаточно полно представлены в работах [6, 7, 9, 10, 11, 46].

В главе 2 проводится анализ однолинейной СМО, на вход которой поступает рекуррентный поток заявок с ФР фазового типа. Заявка, заставшая прибор занятым, либо становится в очередь повторных заявок ограниченного размера 5, либо теряется, если в момент ее поступления число повторных заявок уже равно й. Эту очередь повторных заявок называют орбитой. С орбиты заявки делают попытки попасть на обслуживающий прибор, причем рассматривается линейная дисциплина повторений. ФР времени обслуживания, как первичных, так и повторных заявок, имеет фазовый тип. Такая система имеет кодировку РН/РН/1/0/в с повторными заявками. В § 1 проводится подробное описание модели. В § 2 выводятся уравнения равновесия для исследуемой СМО. В § 3 представлен матрично-реккурентный алгоритм расчета стационарного распределения вероятностей изучаемой СМО. В § 4 рассматриваются некоторые показатели производительности анализируемой СМО. В этом параграфе также получены соотношения между макрохарактеристиками системы, которые играют важную роль для контроля вычислений, производимых с помощью алгоритма из § 3. В § 5 полученные результаты обобщаются на случай, когда процесс генерации заявки или процесс обслуживания не является марковским. В § б получено стационарное распределение вероятностей для цепей Маркова, вло-

женных по моментам поступления заявок или окончания их обслуживания. Результаты численных исследований и их анализ для частных случаев рассматриваемой системы приведены в § 7. Также в этом параграфе изучаются вычислительные особенности алгоритма, изложенного в § 3. Результаты, полученные в главе 2, достаточно полно отражены в работах [2, 45, 47].

В третьей главе исследуется система, аналогичная системе, рассматриваемой в главе 2, с дополнительным предположением о возможности отключения прибора в случае полного опустошения системы. Напомним, что под полным опустошением понимается ситуация, когда обслуживающий прибор пуст и на орбите нет повторных заявок. Относительно времени отключения предполагается, что она, как и ФР времени генерации и обслуживания, имеет фазовый тип. Эта система в модифицированных обозначениях Кендалла имеет код РН/РН/1 /0/з с повторными заявками и отключениями прибора. В § 1 дано подробное описание модели. Так как модель, рассматриваемая в главе 3, полностью, за исключением возможности отключения прибора, идентична модели из главы 2. то остановимся только на описании механизма отключения. Дисциплина отключений состоит в следующем: 1).при полном опустошении системы прибор отключается с некоторой вероятностью 01 и с противоположной вероятностью в1 остается в состоянии ожидания заявки; 2)-если за время отключения в систему пришли заявки, прибор с вероятностью 1 выходит из состояния отключения; 3).если за время отключения в системе ничего не изменилось, то прибор с вероятностью в2 снова отключается и с противоположной вероятностью остается в состоянии ожидания заявки. В § 2 проводится вывод системы уравнений равновесия. Также в этом параграфе осуществляется переход к обозначениям, позволяющим записать эту систему в более простой форме, которая близка по записи к СУР для системы РЯ / РН/I/0/з с повторными заявками, но без отключений. В § 3 получено матричному лътипликативное решение СУР. Соотношения между макрохарактеристиками, используемые для контроля вычислений, производимых с помощью алгоритма из § 3, получены 3 § 4. Некоторые из показателей производительности д.:я исследуемой СМО также рассмотрены в этом параграфе. В § 5 происходит обобщение полученных результатов на случай, когда процесс генерации или процессы обслуживания и отключения (одновременно) не являются марковскими. В § б получены выражения 1ля стационарных распреде-

лений цепей Маркова, вложенных по моментам поступления заявок или окончания их обслуживания. § 7 посвящен получению и анализу численных результатов. Результаты 3 главы достаточно подробно отражены в работе [1].

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

Заключение диссертации по теме «Теоретические основы информатики», Пузикова, Дарья Анатольевна

выводы

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

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

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

3. Найдены стационарные распределения вероятностей для цепей Маркова, вложенных по моментам поступления заявок или окончания их обслуживания.

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

ЗАКЛЮЧЕНИЕ

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

Проведенные исследования позволили получить ряд новых результатов, формулируемых ниже.

1. Для однолинейной СМО с накопителем ограниченной емкости с линейной дисциплиной повторений, пауссоновским входящим потоком, произвольным обслуживанием и относительным приоритетом при обслуживании первичных заявок найдено стационарное распределение числа заявок в накопителе и получен алгоритм расчета моментов числа повторных заявок на орбите. Получено также обобщение формулы Поллачека-Хинчина для среднего числа в системе в целом. Найдено необходимое и достаточное условие существования стационарного режима.

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

3. Составлен комплекс программ для расчета стационарных показателей производительности исследуемых в диссертации систем.

Список литературы диссертационного исследования кандидат физико-математических наук Пузикова, Дарья Анатольевна, 1999 год

ЛИТЕРАТУРА

1. Атенсиа И.. Бочаров П.П., Пузикова Д.А. Матрично- мультипликативное решение для однолинейной системы массового обслуживания с отключениями прибора, конечной очередью повторных заявок и распределениями фазового типа // Автоматика и телемеханика. -1999. (принято к печати)

2. Атенсиа И., Пузикова Д.А. Система РН/РН/ 1/0/з с обобщенной дисциплиной повторений // Тезисы докладов XXXV научной конференция факультета физ.-мат. и ест.наук, 24-28 мая 1999 г. - М.: Изд-во РУДН, 1999. (принято к печати).

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

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

5. Бочаров П.П., Ворннаритх Чхитх. Стационарные характеристики однолинейной системы массового обслуживания с заявками нескольких видов и отключениями прибора // Вестник РУДН. Серия "Прикладная математика и информатика". -1994.

1. -С. 45-63.

6. Бочаров П.П., Матюшенко С.И., Пузикова Д.А О системе М/Су1/г с постоянной интенсивностью потока повторных заявок и приоритетным обслуживанием первичных заявок // Тезисы докладов XIV Белорусской школы-семинара "Массовое обслуживание. Потоки, системы, сети", Минск, 27-29 января 1998 г. — Минск: Изд-во БГУ. -1998. -С. 37-40.

7. Бочаров П.П., Матюшенко С.И., Пузикова Д.А. Система М/С/1/г с потоком повторных заявок постоянной суммарной интенсивности и приоритетным обслуживанием первичных заявок // Вестник РУДН. Серия "Прикладная математика и информатика". -1998. -№ 1. - С. 77-92.

8. Бочаров П.П., Наумов В.А. О некоторых системах массового обслуживания конечной емкости // Проблемы передачи информации. -1977. -Т. XIII. -Вып. 4. -С. 96-104.

9. Бочаров П.П., Павлова О.И., Пузикова Д.А. О некоторых результатах для системы массового обслуживания М/С/1/г // Тезисы докладов XXXIII научной конференции физ.-мат. и ест. наук, 20-24 мая 1997 г. — М.: Изд-во РУДН. -1997. -С. 12.

10. Бочаров П.П., Павлова О.И., Пузикова Д.А. Об одном обобщении формулы Поллачека-Хинчина для системы M/G/1/r с изменением типа повторных заявок // Тезисы докладов XIII Белорусской школы-семинара "Массовое обслуживание. Потоки, системы, сети", Минск, 3-5 февраля 1997 г. — Минск: Изд-во БГУ. -1997. -С. 19-20.

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

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

13. Бочаров П.П., Спесивое С.С. Таблицы стационарных характеристик однолинейной системы обслуживания конечной емкости. М.: Изд.-во РУДН, 1986.

14. Дьяконов В.П. Математическая система MAPLE V R3/R4/R5. М.: Изд-во Солон, 1998.

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

16. Зелинский А.М., Корнышев Ю.Н. Две модели системы с повторными вызовами // Электросвязь. -1978. 1. -С. 60-63.

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

18. Ионин Г.Л. Определение вероятностных характеристик однолинейной системы со сдвоенными соединениями и повторными вызовами //В кн. "Модели систем распределение информации и их анализ", М.: Наука. -1982. -С. 51-54.

19. Ионин Г.Л., Брезгунова Н.М. Однолинейная система с повторными вызовами в случае Г-распределения длительности обслуживания // Латв. мат. ежегодник. -1972. -Вып. 11. -С. 65-72.

20. Ионин Г.Л., Седол Я.Я., Кибилд A.B. Обобщенная модель массового обслуживания с повторными вызовами // Тезисы докладов третьего всесоюзного научно-технического совещания "Информационные сети и автоматическая коммутация" (ВСИС-3), Москва, 1975 г. — М.: Наука. - 1975. -С. 38-40.

21. Клейнрок Л. Вычислительные системы с очередями. М.: Маши-

ностроение, 1979.

22. Кнут Д. Искусство программирования для ЭВМ. т.2. М.: Наука, 1977.

23. Корнышев Ю.Н. Комплекты ожидания для перегруженных направлений // Электросвязь. -1974. 7. -С. 32-39.

24. Севастьянов Б.Г. Эргодическая теорема для марковских процессов и ее приложение к телефонным линиям с отказами // Теория вероятностей и ее применения. -1957. -Т.2. -Вып. 1. -С. 106-116.

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

26. Фалин Г.И. Вероятностная модель для исследования абонентских линий с комплектом ожидания // Теория вероятностей, теория случайных процессов и функциональный анализ. М.: Изд-во МГУ, 1985.

27. Флинт Д. Локальные сети ЭВМ: архитектура, принципы построения, реализации. М.: Финансы и статистика, 1986.

28. Хомичков И.И. Расчет характеристик модели локальной сети с протоколом доступа GSMA/CD // Конференция ученых социалистических стран "Локальные вычичслительные сети". Тезисы докладов. -1986. -Рига. -С. 150-155.

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

30. Хомичков И.И. Модель локальной сети со случайным множественным доступом // Автоматика и вычислительная техника. -1987. 1. -С. 58-62.

31. Хомичков И.И. Однолинейная система с повторными вызовами и входящим потоком Кокса 2 порядка // Вестник БГУ. Серия1. -1988. 3. -С. 70-71.

32. Хомичков И.И. Расчет характеристик системы массового обслуживания с повторными требованиями при сдвоенных соединениях // Автоматика и телемеханика. -1988. 4. -С. 77-84.

33. Хомичков И.И. Математические модели протоколов случайного доступа в сетях передачи данных. // Диссертация на соискание ученой степени доктора физико-математических наук. 05.13.16. -Минск. -1997.

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

35. Aleksandrov A.M. A queueing system with repeated orders // Engineering Cybernetics. -1974. -V. 12. 3. P. 1-4.

36. Almes G., Lazovska E. The behaviour of Ethernet-like computer communications networks // Proceedings of the 7-th Symposium on operation Systems Principes, ACM SIGCOMM. -1979. -P. 66-81.

37. Artalejo J.R. Information theoretic approximations for retrial queueing systems. // Proceeding of Trans. 11th Prague Conf. "Inf. Theory, Statist. Decis. Funct., Random Processes". -Prague. -1990. -P. 263-270.

38. Artalejo J.R. Explicit formulae for the Characteristics of the M/H2/l retrial Queue // Journal of the Operation Research Society. -1993. -V. 44. -P. 309-313.

39. Artalejo J.R. New results in retrial queueing systems with breakdown of the servers // Statistica Neerlandica. -1994. -V. 48. 1. -P. 2336.

40. Artalejo J.R. A queueing system with returning customers and waiting line // Operation Research Letters. -1995. 17. - P. 191-199.

41. Artalejo J.R. Analysis of an M/GJ1 queue with constant repeated attempts and server vacations // Сотр. Oper. Res. -1997. -V. 24.

6. -P. 493-504.

42. Artalejo J.R., Falin G.I. On the orbite characteristics of the M/GJ 1 retrial queue. // Naval Research Logistics. -1996. -V. 43. -P. 1147-1161.

43. Artalejo J.R., Gomez-Corral A. Information theoretic analysis for queueing systems with quasi-random Input // Mathl. Comput. Modelling. -1995. -V. 22. 3. -P. 65-76.

44. Artalejo J.R., Gomez-Corral A. Stochastic analysis of the departure and quasi-input processes in a versatile single-server queue // Journal of Applied Mathematics and Stochastic Analysis. -1996. -V. 9.

2. -P. 171-183.

45. Atencia I., Bocharov P.P., Puzikova D.A. Matrix- multiplicative solution for the PH/PH/1/0 queueing system with limited retrial queue // Вестник РУДН. Серия "Прикладная математика и информатика". -1999г. 1. (принято к печати)

46. Bocharov P.P., Pavlova O.I., Puzikova D.A. M/G/l/r retrial queueing system with nonpreemtive priority for primary customers // Distributed Computer Communication Networks. Theory and Application. Proc. of Internat. Conference "Distributed Computer Communication Networks. Theory and Applications", Tel-Aviv, November

47.

48.

49.

50.

51.

52.

53.

54,

55.

56,

57,

58,

59,

60

4-8, 1997. -P. 29-41.

Bocharov P.P., Puzikova D.A. Matrix methods of analysis of qu«:ue-ing systems with limited retrial queue. // Proc. of First Interriat. Workshop on Retrial Queues, Madrid, September 22-24, 1998. -P. 7-9.

Choi B.D., Choi K.B., Lee Y.W. M/G/l retrial queueing system with two type of call and finite capacity // Queueing systems. -1995. 19. -P. 215-229.

Choi B.D., Han D.H., Falin G. On the virtual waiting time for an M/G/l retrial queue with two type of calls // Journal of Applied Mathematical Stochastic Analysis. -1993. -№ 6. -P. 11-24. Choi B.D., Shin Y.W., Ahn W.C. Retrial queues with collision arising from unslotted CSMA/CD protocol // Queueing Systems. -1092. -V.ll. -№4. -P. 335-356.

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

Deul N. Stationary conditions for multi-server queueing systems with repeated calls // Journal of Information Processing and Cybernetics. -1982. -V. 18. -№10-11. -P. 587-594.

Diamond J.E., Alfa A.S. Matrix analytical method for M/PH/1 retrial queues // Stochastic Models. -1995. 11. -P. 447-470. Doshi B. T. Single-server queues with vacations. // Stochastic Analysis of Computer and Communications Systems. Amsterdam: H. Takagi, Elsevier, 1990.

Falin G.I. On a multiclass batch arrival retrial queue // Advanced Applied Probability. -1988. 20. -P. 483-487. Falin G.I. A survey of retrial queues // Queueing Systems. -1090. 7. -P. 127-168.

Falin G.I., Artalejo J.R. A finite source retrial queue // European Journal of Operation Research. -1998. 108. -P. 409-424. Falin G.I., Templeton J.G.G. Retrial Queues. London: Chapman & Hall, 1997.

Farahmand K., Smith N.H. Retrial queues with recurrent demand option // Journal of Applied Mathematics and Stochastic Analysis. -1996. -V.9 2. -P. 221-228.

Farahmand K. Single line queue with recurrent repeated demands // Queueing Systems. -1996. -V. 22. -P. 425-435.

61.

62.

63.

64.

65.

66.

67.

68.

69.

70

71

72,

73

74

75,

Hanschke T. A model for planning switching networks // Operation Research Proceedings. -Springer. -Berlin. -1984. -P. 555-562. Hashida O., Kawashima K. Buffer behaviour with repeated calls // Electronics and Comunications in Japan. -V. 62-B. № 3. -P. 27-35. Keilson J., Cozzolino J., Young H. A service system with unfilled request repeated // Operation Research. -1968. -№16. -P. 11261137.

Kulkarni V.G., Choi B.D. Retrial queues with server subject to breakdowns and repairs // Queueing Systems. -V. 7. -№2. -P. 191-208.

Langaris C., Moutzoukis E. A retrial queue with structured batch arrivals, priorities and server vacations // Queueing System. -1995. № 20. -P. 341-368.

Liang H.M., Kulkarni V.G. Monotonocity properties of single-server retrial queues // Communications in statistics. Stochastic Models. -1993. -V. 9. 3. -P. 373-400.

Moutzoukis E.,Langaris C. Non-preemptive priorities and vacations in multiclass retrial queueing system // Stochastic Models. -1996. 3. -P. 455-472.

Li H., Yang T. A single-server retrial queue with server vacations and finite number of input sources // European Journal of Operational Research. -1995. -V. 85. -P. 149-160.

Neuts M.F. Matrix-Geometric Solution in Stochastic Models: An Algorithmic Approach. Baltimore and London: The Johns Hopkins Univ. Press, 1981. ,

Newts M.F., Ramalhoto M.F. A service model in which the server is required to search for customers // Journal of Applied Probability. -1984. -V. 21. 1. -P. 157-166.

Proceedings of the First International Workshop on Retrial Queues, Madrid, 1998.

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

Teghem J. Control of the service process in a queueing system // European Journal of Operation Research. -1986. 23. - P. 141158.

Wilkinson R.I. Theories for tall traffic engineering in the USA // Bell. Syst. Techn. Journal. -1956. -V. 35. 2. -P. 421-507. Yang T.,Posner M.J.M., Templeton J.G.C. The M/G/l retrial

queue with nonpersistent customers // Queueing Systems. -1990.

2. -P. 209-218.

76. Yang T., Posner M.J.M., Templeton J.G.C., Li H. An approximation method for M/G/l retrial queue with general retrial times. // European Journal of Operation Research. -1994. 76. -P. 552-562.

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