Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.6 G-сети с несколькими классами положительных заявок и сигналов

Обобщениям -сетей на случай нескольких классов положительных заявок и сигналов был посвящен целый цикл работ [163,165,166, 168,186,187,197,203,204,220,248].

В [187,197,205] базовая G-сеть была обобщена на случай нескольких классов положительных и отрицательных заявок в предположении, что число классов обоих типов заявок одинаково. При этом в каждой из этих работ рассматриваются различные варианты, устанавливающие каким образом соотносится эффект отрицательных заявок с их типами. Так, в [205] предполагается, что отрицательные заявки фиксированного класса воздействуют только на положительные заявки того же класса. В [197] используется случайный выбор типа положительной заявки, т.е. если отрицательная заявка поступает в узел , в котором находится положительных заявок (без учета их типа), то с вероятностью будет уничтожена положительная заявка класса с. В [187] рассматривается G-сеть с различными дисциплинами: FIFO — обслуживание в порядке поступления, PS — разделение процессора и LIFO/PR — инверсионный порядок обслуживания с прерыванием обслуживания. Положительная заявка «на убой» выбирается в соответствии с установленной в узле дисциплиной обслуживания, при этом в узле отрицательная заявка класса может уничтожить положительную заявку класса к с вероятностью . В [203] результаты [187] были распространены на случай, когда имеется также несколько классов триггеров.

Остановимся кратко на основных результатах работы [203], в которой для G-сетей доказан в некотором смысле упрощенный аналог теоремы ВСМР со следующими дисциплинами обслуживания в однолинейных узлах (типами узлов в терминах теоремы ВСМР):

В целях сокращения мы не будем давать полное описание рассматриваемой G-сети и будем по возможности использовать материал предыдущих разделов.

Рассматривается сеть МО из М однолинейных узлов с накопителями неограниченной емкости. Извне (из узла 0) на сеть поступают R пуассоновских потоков положительных заявок интенсивности пуассоновских потоков сигналов интенсивности . Все поступающие в сеть потоки независимы между собой.

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

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

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

Положительная заявка класса к, закончив обслуживание в узле , с вероятностью переходит в узел к как положительная заявка класса I и с вероятностью как сигнал класса либо покидает сеть с вероятностью

Длительности обслуживания положительной заявки класса к в узле любого типа имеют экспоненциальное распределение с параметром

Будем предполагать, что для описанной G-сети выполняются следующие свойства.

Свойство 1. Для узлов Типа 1 (с дисциплиной FIFO) предполагается выполненным условие

Свойство 2. Для узла Типа 1 и сигнала класса таких, что

для любых выполняется условие

(5.53)

Это условие означает, что сигнал-триггер класса m при попытке перемещения положительной заявки из некоторого узла не «узнает» ее тип, т.е. он не различает положительные заявки по их типу.

Свойство 3. Для узла Типа 2 вероятность того, что некоторая положительная заявка будет выбрана в качестве мишени поступившим в узел сигналом, равна если в данном узле было с заявок (без учета их вида).

Заметим, что условие (5.52) и (5.53) для узла Типа 1 может быть заменено более ограничительным условием вида

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

для узлов Типа 1, 4

для узла Типа 2

Здесь для некоторого момента состояние узла : для узлов Типа 2 и 4 компонента вектора указывает класс заявки, стоящей в очереди узла на месте (порядок в очереди определяется дисциплинами FIFO и LIFO соответственно), а — число заявок в узле без учета их класса; для узла Типа и его компонента определяет число заявок в узле без учета их класса.

Обозначим через стационарную вероятность состояния к.

Теорема 7. Пусть для G-сети с несколькими классами положительных заявок и сигналов выполняются свойства 1-3.

Тогда, если система нелинейных уравнений

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

При этом величина зависит от типа узла и имеет следующий вид:

для узлов Типа 1:

для узлов Типа 2:

для узлов Типа 4:

и G — нормализующая константа.

Заметим, что условия гарантируют существование стационарного режима функционирования сети.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление