Автоматика и телемеханика, № 5, 2011
© 2011 г. В.И. КЛИМЕНОК, д-р физ.-мат. наук, О.С. ТАРАМИН
(Белорусский государственный университет, Минск)
ДВУХФАЗНАЯ СИСТЕМА в1/РН/1 —> •/РН/1/0 С ПОТЕРЯМИ
Найдено стационарное распределение и характеристики производительности двухфазной системы массового обслуживания с рекуррентным входящим потоком. Обслуживающие устройства на обеих фазах однолинейные. Времена обслуживания имеют распределения фазового типа. На первой фазе имеется бесконечный буфер. Промежуточный буфер отсутствует. В случае занятости прибора второй фазы в момент окончания обслуживания запроса на первой фазе этот запрос уходит из системы недообслуженным (теряется).
1. Введение
Двухфазные системы массового обслуживания (СМО) являются простейшим примером сетей массового обслуживания, состоящих из двух последовательно расположенных узлов. Такие системы могут быть использованы для моделирования реальных сетей и их фрагментов, а также для проверки алгоритмов декомпозиции сетей общего вида, см. [1—3]. В случае, когда оба узла являются системами М/М/1, они образуют элементарную сеть Джексона. В этом случае совместное распределение длин очередей в узлах имеет форму произведения. В случае более сложных двухфазных СМО нахождение совместного стационарного распределения состояний узлов часто представляет собой непростую в математическом плане задачу, которая во многих случаях не поддается аналитическому решению. В частности, задача значительно усложняется при отказе от предположения об экспоненциальном характере входящего потока и распределения времен обслуживания в узлах тандема. Особенно сложной она становится в случае немарковских систем, когда входящий поток и (или) процессы обслуживания в узлах не могут быть описаны марковскими процессами.
Обширный обзор ранних статей по многофазным СМО приведен в [4]. Большинство из этих статей посвящено экспоненциальным системам. В последнее десятилетие значительные результаты были достигнуты в исследовании тандемных СМО с групповым марковским потоком (Batch Markovian Arrival Process, общепринятая аббревиатура В MAP) (см., например, [5]), который можно рассматривать как обобщение стационарного пуассоновского потока на случай коррелированного взрывного трафика, присущего реальным сетям. Тандемные системы с марковским входящим потоком рассматривались, например, в [6-10]. Хотя такие системы являются сложными и достаточно общими моделями двухузловых сетей массового обслуживания, однако они не могут использоваться для моделирования сетей либо их фрагментов с немарковскими потоками, например потоками, у которых интервалы между поступлениями запросов имеют детерминированное, равномерное, логнормальное распределения, распределение Вейбулла и т.д.
По сведениям авторов, существует сравнительно небольшое число работ, посвященных аналитическим методам исследования тандемных СМО с немарковскими потоками. В [11] рассмотрена многофазная система без ожидания и промежуточных буферов, с произвольным распределением интервалов между поступлениями запросов во входящем потоке и экспоненциальным распределением времен обслуживания
в узлах. В работах Б. Ави-Итсхака (см., например, [12]) и соавторов рассматриваются системы с произвольным входящим потоком, детерминированными временами обслуживания и блокировками, в статье Ч. Кнессела [13] - СМО с детерминированным входящим потоком, экспоненциально распределенными временами обслуживания и ожиданием на каждой фазе. В работах Ч. Кнессела и Ч. Тиэра (см., например, [14]) рассматриваются двухфазные СМО с рекуррентным потоком, бесконечными буферами и экспоненциальным распределением времен обслуживания. Авторы исследуют совместное распределение длин очередей в условиях большой загрузки при помощи диффузионной аппроксимации. Следует отметить, что исследования, основанные на диффузионной аппроксимации, занимают значительное место в литературе, посвященной немарковским двухфазным СМО. Соответствующие ссылки можно найти в [13, 14].
В данной статье находится стационарное распределение двухфазной СМО с рекуррентным потоком и фазовым распределением времен обслуживания на обоих приборах с использованием матрично-аналитических методов. Первая фаза рассматриваемой СМО представлена системой GI/РН/1, на второй фазе находится один обслуживающий прибор. Промежуточный буфер между фазами отсутствует. Коллизии, связанные с ситуацией, когда запрос, обслужившийся на первой фазе, застает второй прибор занятым, разрешаются путем ухода недообслуженного запроса из системы. Рассматриваемая модель является достаточно общей по характеру используемых распределений. Рекуррентный поток предполагает произвольное распределение интервалов между поступлениями заявок. Класс распределений фазового типа (PH - Phase-type distribution) включает в себя многие традиционно используемые в теории массового обслуживания распределения и всюду плотен в классе всех распределений на неотрицательной полуоси. Вследствие этого произвольное распределение теоретически может быть с любой точностью аппроксимировано распределением фазового типа. Насколько нам известно, в литературе нет аналитических результатов для рассматриваемой модели СМО даже в случае экспоненциально распределенных времен обслуживания на обоих приборах.
Нетрудно видеть, что маргинальное стационарное распределение числа запросов на первой фазе рассматриваемой СМО находится легко, так как ее функционирование не зависит от второй фазы и может быть найдено как соответствующее распределение в системе GI/РН/1. Но задача нахождения распределения вероятностей состояний второй фазы или совместного распределения фаз гораздо сложнее. Вместе с тем, только зная совместное распределение состояний процессов обслуживания на обеих фазах, можно вычислить главную характеристику рассматриваемой СМО - вероятность потери запроса после первой фазы. Как будет видно из дальнейшего, эта вероятность может быть найдена, если известно совместное распределение числа запросов на первой фазе и состояний процессов обслуживания в моменты поступления запросов в систему. Поэтому первым шагом в исследовании является построение вложенной по моментам поступления запросов цепи Маркова и нахождение ее стационарного распределения. На основе этого распределения далее находятся совместное распределение состояний обеих фаз в произвольные моменты времени и различные характеристики производительности системы, включая вероятность потерь, преобразование Лапласа-Стилтьеса времени пребывания в системе произвольного запроса, совместное распределение состояний приборов в произвольный момент времени и т.д.
2. Математическая модель
Рассматривается двухфазная СМО, первая фаза которой представлена однолинейной СМО с ожиданием. Времена между поступлением запросов на первую фазу
являются независимыми случайными величинами с общим распределением А(£),
оо
имеющим конечный первый момент ах = / £<А(£).
0
После обслуживания на первой фазе запрос поступает на вторую фазу, которая представляет собой однолинейную систему без буфера. Если запрос закончил обслуживание на первой фазе и застал прибор второй фазы занятым, то он уходит из системы недообслуженным (теряется). Времена обслуживания запросов на обеих фазах имеют распределения фазового типа. Время обслуживания, имеющее распределение фазового типа с неприводимым представлением (3,5*), можно интерпретировать как время, в течение которого управляющий марковский процесс то4, £ ^ 0, с конечным пространством состояний {1,..., М, М + 1} достигнет единственного поглощающего состояния М +1 при условии, что начальное состояние этого процесса выбирается в множестве {1,..., М} согласно стохастическому вектору-строке /3. Интенсивности переходов процесса то4, £ ^ 0, в множестве состояний {1,...,М} определяются субгенератором $ (квадратной матрицей порядка М с отрицательными диагональными элементами и неотрицательными недиагональными элементами), а интенсивности переходов в поглощающее состояние определяются элементами вектор-столбца 50 = — 5*е с неотрицательными элементами, среди которых есть хотя бы один положительный. Здесь и далее е - вектор-столбец, состоящий из единиц. Более подробную информацию о распределении фазового типа можно найти, например, в [15, 16].
Полагаем, что процесс обслуживания на г-м, г = 1, 2, приборе имеет фазовое распределение с неприводимым представлением (3г, $г) и управляется цепью Маркова то^г), £ ^ 0, с пространством состояний {1,..., Мг, Мг + 1}, где состояние Мг + 1 является поглощающим. Среднее время обслуживания на г-м приборе вычисляется
по формуле Ь^ = 3г(—$г)-1е, интенсивность обслуживания равна = (Ь^)-1, г = 1, 2.
3. Стационарное распределение вложенной цепи Маркова
Пусть £п - момент поступления п-го запроса на первую фазу, гп - число запросов на этой фазе в момент времени £п — 0, тоПХ) - состояние РД-процесса обслуживания на первом приборе в момент £п, п ^ 1. Как было отмечено выше, процесс {гп,тоП1)}, п ^ 1, является цепью Маркова с известным стационарным распределением. Если предположить, что для первого в периоде занятости запроса первоначальная фаза обслуживания устанавливается в соответствии с вектором 31 в момент окончания предыдущего периода занятости, то эта цепь Маркова имеет пространство состояний {(г, /7? 1), г ^ 0, т\ = 1,М\\, а ее стационарное распределение имеет матрично-геометрический вид, см. [16]. Однако таким образом построенная цепь не несет информации о процессе обслуживания на второй фазе и не позволяет вычислить важнейшие характеристики производительности рассматриваемой системы.
Таким образом, возникает вопрос: "каким образом построить вложенную цепь Маркова?" Ясно, что нужный процесс должен учитывать не только число запросов
на первой фазе и состояние процесса обслуживания на этой фазе, но и состояние
(2)
процесса обслуживания на второй фазе. Пусть топ - состояние РД-процесса обслуживания на втором приборе в момент £п. Введем дополнительную компоненту топ2) в рассмотренный выше процесс {гп,топ1)}, п ^ 1, предполагая, что эта компонента принимает значения в множестве {1, . . . , М2,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.