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

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

Теорема Бёрка (Burke)

Простейшая тандемная сеть

Фрагмент временной диаграммы простейшей тандемной сети

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

Фрагмент временной диаграммы для этой сети выглядит так, как это показано на рисунке сверху.

Пусть - плотность распределения вероятностей промежутков времени между последовательными требованиями на выходе, а - преобразование Лапласа . Когда требование покидает узел 1, возможно одно из двух событий:

(a) в очереди имеется хотя бы одно требование (узел 1 не пуст)

(b) в очереди нет требований (узел 1 пуст)

В первом случае - промежуток времени, через которое следующее требование покинет систему 1, распределен так же, как и время обслуживания:

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

Так как эти два промежутка времени распределены независимо, то плотность распределения вероятностей их суммы равна свертке плотностей распределения суммируемых величин. Соответственно преобразование Лапласа плотности распределения:

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

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

Учитывая, что время обслуживания – показательно распределенная случайная величина, то можно записать

и, окончательно, имеем:

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

Этот результат, в 1956 году установленный Бёрк, справедлив и для СМО типа M/M/m.

Теорема Джексона (Jackson)

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

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

N - число узлов сети;

- стационарная вероятность того, что требований находятся в системе M/ M/ m.

Открытые сети Джексона.

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

В узел поступает извне поток требований (трафик) из независимого пуассоновского источника с интенсивностью .

После обслуживания в узле требование переходит в узел с вероятностью .

Полная интенсивность трафика в узле можно определить так:

Используя обозначение

можно записать векторное уравнение:

Структурную схему узла можно представить в виде показанном на рисунке

где:

- вероятность того, что после обслуживания в узле требование поступит в узел;

- интенсивность внешнего потока требований;

- полная интенсивность потока требований в узле.

В 1967 году Гордон и Ньюэлл (Gordon W.J. Newell G. F.) опубликовали описание модели произвольной замкнутой Марковской сети. Фактически это было развитием частного случая, рассмотренного в 1963 году Джексоном.

В этой модели содержится К требований и не допускается поступление извне и уходы (то есть для всех i). Так как справедливо векторное уравнение:

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

В 1971 Мур (Moore F. R.) предложил использовать замкнутые Марковские сети для моделирования работы вычислительной системы с многими ресурсами, в котором каждый ресурс моделируется узлом сети.

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

Модель позволила предсказывать появление «узкого места» - это такой узел сети, в котором отношение , называемое относительным использование узла, имеет наибольшее значение. При некотором в узком месте образуется бесконечная очередь. Кроме того, Мур показал, что балансировка системы (то есть приведение всех к одному знаменателю) максимизирует .

Пример открытой сети.

Заметим, что вектор зависит от и не зависит от предположения о показательном распределении.

Разложение времени сетевой
задержки по каналам сети

g_jk– Трафик (traffic), поступающий в сеть из внешних источников для тех сообщений, которые возникают в узле j и предназначены для узла k.

Полный внешний трафик, поступающий в сеть, определим как:

, где N – число узлов.

Обозначим T – средняя задержка сообщения, Z_jk – задержка сообщения, которое возникло в j и предназначено для узла k.

Ясно, что эти две средние величины связаны равенством:

так как доля (g_jk/g) полного входящего трафика сообщений имеет в среднем задержку равную Z_jk.

Отметим, что последнее равенство представляет разложение сети по парам источник-адресат.

Обозначим через p_jk путь, по которому идут сообщения, возникающие в узле j и имеющие в качестве узла назначения узел k. Говорят, что i-ый канал (с пропускной способностью C_i) включен в путь p_jk, если сообщения, идущие по этому пути, проходят указанный канал (C_iÎp_jk).

Тогда среднее число сообщений в единицу времени, проходящих по i-му каналу связи равно:

Кроме того, заметим что Z_jk – сумма (T_i) средних задержек, испытываемых сообщением при передаче по различным каналам пути p_jk.

Следовательно:

Изменим теперь порядок суммирования (условие на i сменим на пару jk)

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

Используя известный результат исследований Джексона:

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

1/m - средняя длина сообщения,

1/mС_i– среднее время передачи сообщения по каналу С_i.

Можно провести расчет для случая непоказательных длин сообщений. Но при этом будет проявлена слишком большая смелость, так как для систем M/G/1 результат Джексона неприменим.

Однако это приближение приводит к модели, которая очень хорошо согласуется с моделированием на ЭВМ.

Пример:

m^-¹=i ^бит/_сообщ

g=32^сообщ/_сек

C₁=C_1-2=17^бит/_сек

C₂=C_2-3=22^бит/_сек

C₃=C_3-1=17^бит/_сек

C=56^бит/_сек

Топологию сети можно описать матрицей:

Отличный от нуля элемент указывает, что существует путь длиной в 1 из узла i в узел j.

Отличный от 0 элемент квадрата этой матрицы указывает число путей топологической длиной в 2 единицы из узла i в узел j.

Анализируя обе матрицы (st и st²) приходим к выводу:

Маршрут	Каналы
Маршрут	I	II	III
1-2	12
1-3	4	4
3-1			16
	16	4	16

l₁=16^сообщ/_сек

l₂=4^сообщ/_сек

l₃=16^сообщ/_сек

Тогда:

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

Определим n_jk – длину пути p_jk, как число каналов в этом пути, тогда средняя длина всех путей в сети:

Рассмотрим теперь полный трафик в сети. Вклад трафика (j-k) в полном трафике равен , т. к. сообщений в секунду пройдут n_jk участков при движении по сети. Следовательно:

Средняя длина пути выражается в виде:

Этот результат в 1964 г. получен Клейнроком (Kleinrock).

Выражая среднюю задержку сообщения Т через среднюю длину пути, получим:

Отношение вероятность использования i комната не зависит от нагрузки сети и является лишь функцией процедуре выбора маршрутов.

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

Нагрузку насыщения сети можно найти следующим образом:

1. Для некоторого значения нагрузки определить наибольшее отношение: .

2. Наименьшее значение нагрузки, при которой насыщается этот канал :

Эта двухпараметрическая упрощенная пороговая модель описывает поведение сети в первом приближении. Для рассмотренного примера:

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

Поэтому, при анализе сетей, весьма важной оказывается теорема Форда-Фалперсона о минимальном сечении и максимальном потоке, который сеть может переносить между данной парой узлов.

Задача выбора пропускных способностей каналов

Предположим, что заданы потоки и топология сети.

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

Для решения задачи будем варьировать пропускными способностями каналов , - стоимость пропускной способности для i-ого канала.

-среднее число бит в секунду, которые проходят по i-ому каналу, и, следовательно, любое реализуемое решение задачи должно быть таким, чтобы i-тый канал имел пропускную способность, не меньше указанной величины, т.е..

Для минимизации Т - времени пребывания требования в сети составим функцию Лагранжа:

Как обычно, используя метод Лагранжа, получаем следующую систему из М уравнений

Решая относительно , получим:

Определим b, составив ограничение путем перемножения на и суммировав по i:

Следовательно:

где - добавочная стоимость.

При таком наборе пропускных способностей каждый канал будет иметь, по крайней мере, пропускную способность и, кроме того, некоторую дополнительную пропускную способность.