Примеры сетевых топологий
Элементарные свойства систем с большим числом состояний
Оставшаяся часть этого раздела будет посвящена анализу следующих трех проблем многих состояний.
Кратчайший путь
Исходные данные: Граф 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].
Работоспособность сети PERT: Если обрыв связи соответствует Te=0, а рабочее состояние связи соответствует Te=1 и каждый путь в G имеет идентичную длину n, тогда Rel2(G,s,t,p)=Pr[ФPERT=n].
Отсюда следует, что эти проблемы являются #P-полными для любого класса графа, для которого ассоциированная проблема надежности (s,t)-связности является #P-полной. (сюда входят и проблемы, которые удовлетворяют дополнительным требованиям соответствия PERT). Аналогичные рассуждения показывают, что вычисление E[Ф] является также #P-полным для этих классов графов.
Тип распределения, допустимый для случайных переменных связи, является критическим обстоятельством для эффективности вычислительных методов, обсуждаемых здесь, и, следовательно, необходимо рассмотреть базовые аспекты вычислительной эффективности при расчетах и манипулировании распределениями в процессе решения сетевых проблем. Следующие две операции играют главную роль в большинстве вычислительных схем расчета надежности сетей с большим числом состояний, а вычислительные трудности выполнения этих операций имеют первостепенную важность.
· свертка двух независимых случайных переменных Х1 и Х2, т.е. распределение их суммы Х1 + Х2;
· max (min) двух независимых случайных переменных Х1 и Х2, т.е. распределение max(Х1,Х2) или min(Х1,Х2).
Класс распределений связей для проблем сетей с большим числом состояний должен критически удовлетворять одному или более из следующих трех критериев, в зависимости от типа выполняемого анализа:
1. Вычисление данного значения интегральной функции распределения cdf (cumulative distribution function) элемента в фиксированном классе должно допускать расчет за полиномиальное время с нужным числом значащих цифр при заданной точности входного описания распределения.
2. Заданный набор распределений в классе и последовательность k операций min/max/свертки, выполняемых на основе этих распределений, распределение, полученное в результате последовательности операций должно принадлежать этому же классу, и далее, должно быть можно за полиномиальное время найти описание результирующих распределений при фиксированных исходных распределениях.
3. Ожидаемое значение, вариация или более общо любой специфицированный момент должны быть вычислимы (с точки зрения требуемой точности) в рамках полиномиальной оценки времени вычисления.
Обычно предполагается, что случайные величины имеют дискретное распределение, то есть, могут иметь конечное число значений. Хотя вычисление одной свертки или распределения min/max является элементарным, вычисление распределения для серии k таких операций считается #P-полным, даже если каждая исходная переменная имеет только два значения. Что необходимо, чтобы гарантировать эффективное вычисление свертки и min/max распределения, так это то, чтобы случайные переменные принимали последовательные значения {1, 2,…, xq} (или в более общем случае последовательные значения, кратные некоторому общему знаменателю) для всех ребер графа, для некоторого фиксированного q.
Существует два класса распределений с бесконечным числом состояний, которые относятся к наиболее известным и удовлетворяют сформулированным выше требованиям (1-3). Первое является дискретным и может быть описано как смесь геометрических распределений, имеющих форму pdf(probability distribution function)
для 0 < p < 1 и при соответствующем выборе значений aij. Существует также класс непрерывных распределений, которые имеют нужные свойства. Эти распределения могут быть описаны как “смесь Эрланговых” распределений (известных также как Coxian-распределения). Они являются аналогом “смеси геометрических” распределений, описанных выше. Они имеют форму cdf (cumulative distribution function):
при соответствующем выборе aij.
Дадим краткое описание методик основных оценок и ограничений для сетей с большим числом состояний. В большинстве случаев оказывается, что одна и та же техника используется для двух или более упомянутых выше проблем. Большинство методик имеют варианты для двоичных версий, которые представлены в разделах 3 и 4. Таким образом, мы организовали обсуждения методики, а не предмета, и следуем, когда возможно, формату для двоичной версии проблемы.Для большей части обсуждения мы концентрируемся на расчете Pr[Фіa] для конкретного системного значения функции Ф и специфической величины a.
