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

5.4 Решение уравнений баланса для интенсивности потоков и устойчивости G-сетей

Системы уравнений баланса для интенсивностей потоков, циркулирующих в сети, для всех рассмотренных выше G-сетей являются нелинейным. Поэтому ключевым пунктом при нахождении многомерного стационарного распределения числа заявок в узлах сети (согласно теоремам 1-3) является исследование проблемы существования единственного положительного решения системы уравнений (5.23), (5.24); (5.28), (5.29) и (5.32), (5.33). Эта проблема не является тривиальной, и мы остановимся на ней более подробно.

В работе [199] существование и единственность положительного решения системы уравнений (5.23), (5.24) для интенсивностей потоков были обоснованы для базовой G-сети с матрицей переходных вероятностей специального вида. В частности, достаточным условием существования и единственности положительного решения системы уравнений (5.23), (5.24) является условие

Сеть, для которой выполняется условие (5.36), называется гиперустойчивой.

В [205] был предложен подход для решения нелинейной системы уравнений баланса для интенсивностей потоков вида (5.23), (5.24) для базовой G-сети общего вида. Затем этот подход был развит в [207] для G-сетей с сигналами и групповым удалением положительных заявок. Этот подход в определенной степени является более общим, и мы дадим здесь его краткое изложение, используя при этом результаты и обозначения раздела 5.3.2.

Предлагаемый в [207] метод решения нелинейной системы уравнений баланса для интенсивностей потоков основан на использовании теоремы Брауера о неподвижной точке.

Теорема 4. Если — полустохастическая неразложимая матрица, то решение , нелинейной системы уравнений (5.32) всегда существует.

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

Прежде всего перепишем уравнения (5.32) в несколько ином виде

где

Вводя векторы с координатами соответственно, а также диагональную матрицу G с диагональными элементами перепишем (5.36) в виде

Отсюда получаем, что

Введем вектор и векторную функцию

Заметим, что зависимость F от у выражается через матрицу G, которая зависит от . По теореме Брауера уравнение имеет неподвижную точку у. Эта неподвижная точка и дает решение системы уравнений (5.37):

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

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