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

2.3.2 Теорема ВСМР

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

Уравнения глобального баланса для нахождения стационарного распределения вероятностей состояний сети записываются по аналогии с (2.18) в общем виде следующим образом:

для любого состояния , где - интенсивность выхода сети из состояния - интенсивность выхода сети из состояния в состояние . Отыскание стационарного распределения непосредственно из системы уравнений (2.36) представляет сложную задачу, поэтому обычно используется подход, связанный с получением уравнений локального баланса, техника составления которых для однородных замкнутых сетей была продемонстрирована в разделе 2.2. В данном случае суть составления уравнений локального баланса состоит в приравнивании интенсивности входа сети в состояние, при котором сообщение начинает обслуживаться с определенного этапа, к интенсивности выхода сети из этого состояния, при котором сообщение заканчивает этот этап обслуживания. С каждым сообщением связывается этап обслуживания. Если сообщение обслуживается, то этап определен, если оно стоит в очереди, то для дисциплины обслуживания LCFS - прерванный этап. При таком подходе каждое уравнение системы (2.36) можно представить в виде ряда уравнений локального баланса, выполнение которых, как уже отмечалось, является достаточным (но не необходимым) условием выполнения уравнений глобального баланса.

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

1) при поступлении сообщения класса в центр;

2) при уходе сообщения класса из центра;

3) при уходе сообщения класса из центра и при его последующем поступлении в центр в классе

Тогда стационарные вероятности состояний сети удовлетворяют системе уравнений глобального баланса

где предполагается, что все и для простоты введено обозначение .

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

Применяя принцип локального баланса к последнему выражению, имеем

Подставляя сюда для всех получаем окончательно две эквивалентные системы уравнений локального баланса [см. вывод уравнений (2.20)]:

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

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

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

Рассмотрим еще один пример составления уравнений локального баланса для замкнутой сети МО с двумя классами сообщений, представленной на рисунке 2.2.

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

Рис. 2.2

Уравнения локального баланса имеют вид:

Теперь все подготовлено для формулировки основной теоремы.

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

где

Стационарное распределение существует, если сходится ряд

где G - нормализующая константа.

Доказательство теоремы осуществляется подстановкой (2.38) в уравнение (2.36) или соответствующие уравнения локального баланса.

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

где нормализующая константа G и функция определяются так же, как и в (2.38), зависит от типа узла и имеет следующий вид:

если узел первого типа,

если узел второго или четвертого типа,

если узел третьего типа,

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

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