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

5.7 Другие модели и методы анализа G-сетей

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

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

относительно неизвестных . При выполнении этого условия инвариантная мера представляется в мультипликативной форме:

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

В [219,220] также допускается отрицательная длина очереди для базовой G-сети и вводятся зависимости интенсивностей обслуживания и переходных вероятностей от состояний сети, а в [221] предполагается возможность группового обслуживания.

Мы уже отмечали, что в ряде работ понятие сигнала отождествляется с понятием триггера в смысле, введеннном Геленбе в работах [196,207]. Так, в [220] рассматривается G-сеть, в которой так называемые эффективные сигналы типа 0 играют роль триггера. В определенной степени смешение понятие сигнала и триггера присутствует в работах [163,165-169]. В этих работах вводятся сигналы, которые могут циркулировать по сети.

В [163] для G-сети с несколькими классами положительных заявок и сигналами-триггерами вводится задержка сигналов (обслуживание, активизация в смысле раздела 5.5) в узле на случайное время. Маршрутизация положительных заявок и сигналов по сети соответствует описанию, сделанному в разделе 5.5 (естественно, с учетом того, что в [163] рассматривается несколько классов положительных заявок). Время обслуживания для каждого типа положительных заявок распределено либо экспоненциально, либо по произвольному закону, но лишь для специальных случаев симметричных дисциплин обслуживания (например, дисциплины разделения процессора или дисциплины LCFS/PR). Для анализа сети используется подход, предложенный в [168] для анализа базовой G-сети. В этом подходе имеются два ключевых этапа. На первом этапе доказывается, что изолированный узел удовлетворяет так называемому условию квазиобратимости (для изолированного узла в равновесном режиме будущие поступления положительных заявок и сигналов, текущее состояние сети и прошлые процессы выхода из узла положительных заявок и сигналов должны быть независимы). На втором этапе используется подход, предложенный в [296], позволяющий распространить результаты для изолированных узлов на сеть в целом. Для стационарного распределения вероятностей состояний сети, которые совпадают с состояниями множества X, определяемого формулой (5.38), в [163] получено мультипликативное представление, однако, как было замечено в разделе 5.5, формула (3) в [163] для маргинальных распределений состояний узлов сети некорректна. (По-видимому, ошибка в этой формуле не носит принципиального характера и может быть исправлена).

В [167] результаты для рассмотренной в [163] G-сети с мгновенной активизацией сигналов обобщаются на случай, когда переходные вероятности для положительных заявок и сигналов зависят от предыстории сети. Для анализа сети используется подход работ [163,168]. При этом рассматривается два случая. В первом из них предполагается, что переходная вероятность заявки заданного типа, выходящей из узла после окончания обслуживания по причине прерывания ее обслуживания поступившим в узел сигналом, зависит от количества времени, которое уже было затрачено на обслуживание данной заявки.

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

В [99] подход, использующий понятие квазиобратимости ([235]), был использован для анализа базовой G-сети с обходами узлов. В [99] предполагается, что положительная заявка, направленная в узел , с вероятностью где — число положительных заявок в узле , присоединяется к очереди этого узла, а с дополнительной вероятностью считается мгновенно обслуженной в этом узле и обходит его. Приведем ниже основной результат работы [99].

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

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

где

Теорема 8. Если существует единственное положительное решение , системы уравнений (5.61), (5.62) такое, что выполняется условие

то марковский процесс эргодичен и его стационарное распределение представляется в мультипликативной форме:

где

где определяются формулой (5.62), a

В [70] рассматривается G-сеть, являющаяся комбинацией двух непересекающихся подсетей: базовой G-сети и сети с обходами. При этом для подсети с обходами рассматриваются два случая; экспоненциальное время обслуживания в узлах при дисциплине обслуживания FCFS или общее распределение времени обслуживания при дисциплине обслуживания FCFS/PR. Для обоих случаев получено мультипликативное представление стационарного распределения вероятностей состояний сети, при этом для дисциплины FCFS/PR это распределение зависит только от первых моментов времени обслуживания в узлах сети.

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