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


Группирование ребер


Пусть G=(V,E) является графом (или диграфом, или мультиграфом). Секция G содержит k графов G1,….,Gk с Gi=(V,Ei), где набор ребер Е поделен на k классов Е1,…,Еk. Группа ребер G из k графов G1,….,Gk получается путем выделения набора ребер Е в k+1 класс Е1,…,Еk, и определения Gi=(V,Ei). Главное, на что здесь следует обратить внимание, достаточно просто:

Лемма 4.1. Если G имеет группу ребер по k графам G1,….,Gk, а Rel является любой сопряженной мерой надежности, то

Неравенство в лемме 4.1 возникает из-за того, что существуют рабочие состояния G, в которых ни один Gi не работает. Сделаем несколько замечаний, чтобы применение леммы 4.1 было эффективным при получении нижней границы надежности. Рассмотрим группу ребер G из G1,….,Gk. Если любой Gi находится в нерабочем состоянии, когерентность (сцепление) гарантирует, что Rel(Gi)=0; в данном случае включение Gi в группу ребер не окажет влияния на ограничение и Gi может быть просто опущено. Таким образом, нам нужно в случае группы ребер заботиться только о работоспособных субграфах.

Нашей целью является получение эффективно вычислимых границ; следовательно, необходимо, чтобы мы вычисляли (или хотя бы устанавливали границы) Rel(Gi) для каждого Gi. Одним из таких решений, предложенных Полесски [V. P. Polesskii, “A lower boundary for the reliability of information networks”, Problems of Information Transmission, 7, (1971), 165-171], является алгоритм группирования ребер G с минипроходами. Надежность минипрохода легко вычисляется. Это дает решение, в котором мы формируем группу ребер G с максимально возможным числом минипроходов, а затем применяем лемму 4.1. Эта базовая стратегия активно использовалась.

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




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



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