Примеры сетевых топологий


Элементарные свойства систем с большим числом состояний


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

Кратчайший путь

Исходные данные: Граф G=(V,E) с вершинами s и t

Случайный параметр: Le= длина ребра е

Системная величина: ФPATH= кратчайший путь от s до t

Максимальный поток

Исходные данные: Ориентированный граф G=(V,E) с вершинами s и t

Случайный параметр: Ce=пропускная способность связи е

Системная величина: ФFLOW= максимальный поток (s,t) в G

Работоспособность сети PERT

Исходные данные:

Ориентированный граф без циклов G=(V,E) с исходящей вершиной s и входящей вершиной t

Случайный параметр:

Te = время завершения задания, ассоциированного с ребром е

Системная величина:

ФPERT= минимальное время завершения проекта, когда проект стартует в точке s и финиширует в t, и где никакое задание не может быть начато в вершине v, до тех пор, пока все задания, сопряженные с v, не будут завершены. Это условие можно переписать в виде: ФPERT= длине самого длинного пути с Te , представляющим длины ребер от s до t.

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

Все три перечисленные выше проблемы имеют специальный случай, который в точности соответствует метрике надежности связности Rel2(G,s,t,p), рассмотренной в разделе 1.3. В частности, каждый параметр связи принимает значения 0 или 1, соответствующие рабочему состоянию связи в двоичном представлении. Функция надежности (s,t)-связности имеет тогда следующую интерпретацию:

Кратчайший путь: Если обрыв связи соответствует Le=1, а рабочее состояние связи соответствует Le=0, тогда Rel2(G,s,t,p)=Pr[ФPATH=0].

Максимальный поток: Если отсутствие связи соответствует Се=0, а рабочее состояние - Се=1, тогда Rel2(G,s,t,p)=Pr[ФFLOW ?1].




Начало  Назад  Вперед



Книжный магазин