1. Введение

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

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

И если требование надежности определить как работоспособность всех элементов, надежность Интернета окажется равной нулю, ведь всегда найдется неисправный или отключенный узел или рабочая станция. Если же определить надежность системы, как возможность коммуникации между, скажем, 1000 каких-либо узлов или рабочих станций, то надежность Интернет окажется практически равной единице. Понятно, что если ваша рабочая станция не попадет в число этих 1000 узлов, вы вряд ли согласитесь с утверждением абсолютной надежности. Понятно поэтому, что оба определения совершенно неприемлемы. Не нужно думать, что случай оценки надежности локальной сети, содержащей, например, 100 рабочих станций много проще.

Здесь нужно будет определить, что такое отказ. Современная персональная ЭВМ достаточно сложный прибор, содержащий несколько внешних устройств, один или более процессоров, определенный набор внешних устройств, оперативную память, сетевой интерфейс, ОС и т.д. Что следует считать отказом рабочей станции? Выход из строя источника питания, повисание ОС, разрушение системного диска, отказ сетевой карты и пр. или что-то еще, например, ошибка в прикладной программе или выдергивание уборщицей кабеля из розетки. Надо сразу сказать, что однозначного ответа на этот вопрос нет, все зависит от обстоятельств.

Прежде чем переходить к теоретической части, рассмотренной в указанной в подзаголовке статье, посмотрим, что можно сделать для улучшения надежности сети с практической точки зрения. Конечно, этому будет способствовать использование RAID-систем жестких дисков, катастрофоустойчивой системы дублирования резервных копий дисков в удаленных узлах, размещенных в разных зданиях и т.д.. Но не следует снимать со счетов дублирование базовых серверов: DNS, NTP (если они нужны), почтовых серверов, серверов баз данных и пр. Внутри локальной сети повышению надежности может способствовать применение протокола STP, который может автоматически обеспечить обход отказавшего участка LAN (если применение динамического протокола внутренней маршрутизации невозможно или нежелательно, например, по соображениям безопасности). Во многих случаях крайне важно задублировать шлюз сети, ведущий в Интернет, так как его отказ оставит всех пользователей сети без связи. Компания CISCO и многие другие фирмы разработали протоколыезервирования маршрутизаторов. В этих протоколах два или более устройств совместно используют виртуальные IP и МАС-адреса, которые указаны в сетевом сегменте для шлюза по умолчанию. Для реализации такой схемы существует три протокола:

• HSRP (Hot Standby Router Protocol - протокол горячего резервирования маршрутизаторов) компании CISCO
• IPSTB (IP Standby Protocol) компании DEC
• VIRP (Virtual Router Redundancy Protocol - протокол избыточного виртуального маршрутизатора)

Компания CISCO поддерживает только протокол HSRP. В этом протоколе один из маршрутизаторов является основным (primary), а второй резервным (standby). После ввода этого протокола в строй все запросы и весь трафик шлюза облуживаются основным маршрутизатором. Дублирующий маршрутизатор остается пассивным до выхода основного из строя (решение не самое дешевое, если учесть стоимость маршрутизатора, даже если дублирующий прибор проще и дешевле основного).

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

Выход из строя рабочей станции (терминальный узел) создает проблемы ее пользователю, остальные пользователи Интернет, скорее всего этого не заметят, отказ сервера скажется на работе всех его клиентов, в том числе и удаленных. Выход же из строя маршрутизатора (если это транзитный узел) может оказать влияние на работу целого региона. Отсюда видно, что отдельные узлы могут по-разному влиять на работу сети в целом. Даже в классе серверов можно выделить группы разного влияния на уровень надежности. Например, отказ сервера IN-ADDR.ARPA практически парализует работу программ traceroute . Еще худшее воздействие окажет выход из строя регионального сервера DNS. Именно по этой причине такие серверы обычно дублируются (даже в локальных сетях). Существуют и другие серверы, которые влияют на реализацию определенных сетевых функций (почтовые серверы, серверы баз данных в системах платежей, серверы центров сертификации и пр.). Отсюда видно, что влияние на надежность сети может оказывать не только оборудование или ОС, но и прикладные программы.

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

Если мы рассмотрим в качестве примера полный граф с четырьмя узлами, размещенными в вершинах квадрата (6 ребер), то расчет связности такой сети будет включать комбинаторику перебора ребер и учет распределения вероятности обрыва каждой из связей. Нетрудно понять, что если попытаться проанализировать надежность структурированной локальной сети с сотней ЭВМ, задача окажется на многие порядки сложней, я уже не говорю об Интернете в целом. Обычно множественность в таких задачах равна N! (где N - число узлов в графе связей). В любом случае в качестве исходных данных должны использоваться значения надежности отдельных узлов и каналов, вычисленные или измеренные с учетом тех факторов, влияние которых вы хотите учесть. Во многих случаях бывает нужно сделать предположение относительно распределения вероятности отказа рассматриваемых сетевых элементов. Кроме того, надо решить, какая оценка вам нужна: для работы сети в среднем или для функционирования в экстремальных условиях. Ради упрощения проблемы часто делается предположение об идентичности распределений и даже равенстве вероятности отказа для всех узлов. Понятно, что такие предположения делают полученный результат весьма приблизительным. По этой причине даже оценки границ надежности довольно часто корректны лишь по порядку величины. Во многих случаях, когда требуется получить оценку надежности конкретной сети, неплохие результаты может дать расчет по методу Монте-Карло (см. главу 5 данной статьи).

По этой причине, прежде чем писать и запускать программу расчета надежности сети надо научиться оценивать - а хватит ли имеющихся вычислительных ресурсов для решения поставленной задачи в текущем тысячелетии. Для этого существует математические методы оценки сложности алгоритмов [А. V. AHO, J. D.Ullman, “Foundation of Computer Science”, Computer Science Press, 1992, или V.V. Leeuwen, “Algorithms and Complexity”, The MIT Cambridge, Massachusetts, Elsevier Science Publishers, 1990]. Из-за сложности прямых вычислений многие исследователи ограничиваются лишь оценкой возможных границ надежности. На практике, даже используя самые производительные вычислительные системы, можно оценить надежность сети с ограниченным числом узлов. Для больших сетей доступными являются лишь оценки нижней или верхней границы надежности.

За отправную точку примем сеть G =(V,E), в которой V - набор узлов или вершин графа сети, а Е - набор неориентированных ребер или набор ориентированных дуг. Большинство исследований по сетевой надежности посвящены к-терминальным мерам. Пусть имеется набор из К узлов и узел sÎ K(k=|K|). Задана сеть G, и все дуги графа, описывающего сеть, имеют вероятность надежности р. Тогда к-терминальная мера надежности определяется как (Pr - вероятность):

Rel(G,s,K,p)=Pr[существует хотя бы один работающий путь от s до каждого узла из набора К]

То есть, надежность сети с графом G для набора узлов К и выбранного узла s при вероятности иметь надежную связь для всех ребер графа p равна вероятности того, что узел s имеет хотя бы один доступный путь до каждого из узлов К. Обычно эта величина соответствует определенному временному интервалу.

Существует два важных частных случая мер: 2-терминальная мера с |К|=2 и всетерминальная мера, где К=V. Эти меры принято обозначать Rel₂(G,s,p) и Rel_А(G,s,p), соответственно (Rel - надежность).

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

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

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

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

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

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

1.1. Области применения

1.1.1. Сети с коммутацией пакетов, уровень опорной сети.

Первые сети с коммутацией пакетов были разработаны в 1960х. Их создали с целью поделить высокоскоростные каналы между большим количеством пользователей. Трафик, порождаемый одним пользователем, имеет много всплесков и пауз. Трафик нескольких пользователей можно динамически разнести по времени и передавать по одному соединению. ARPANET была первой крупной сетью с коммутацией пакетов. Большая часть исследований в области сетевой надежности до и после 1970 велась именно для ARPANET. На рис. 1 представлена схема ARPANET по состоянию на 1979 год. Надежность ARPANET в основном рассматривалась с точки зрения связанности сети. Считалось, что сеть функционирует, если она остается связанной, т.е. пока каждый из пользователей специфицированного субнабора связан друг с другом. Такой подход был оправдан, так как в ARPANET использовалась динамическая маршрутизация, так что данные могли быть направлены в обход отказавших узлов. Хотя данные и могли быть направлены по другому маршруту, в сети могли возникнуть перегрузки и задержки, вызванные падением общей пропускной способности сети.

При сравнении ARPANET с коммерческими опорными сетями с коммутацией пакетов, используемыми в 1980-х годах, такими как Telnet и Tymnet ясно, что коммерческие сети много компактнее. Как следствие, вероятность нарушения связанности в коммерческих сетях много меньше, но, как правило, загрузка каналов там достаточно высока. Отсюда напрашивается вывод, что следует более детально подходить к вычислению параметров сетевой надежности и учитывать перегрузки и пропускную способность сети. Будем считать, что сеть работоспособна, если она связанна и параметры сетевой работоспособности, коими могут быть средние задержки, не превышают заданных пределов.

Сегодня сеть ArpaNet может показаться топологически достаточно простой, но даже для такой сети расчет надежности отнюдь не простая задача даже при оценке простой связности.

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

1.1.2. Опорный уровень в сетях с коммутацией каналов.

На сегодняшний день крупнейшие телекоммуникационные сети являются сетями с коммутацией каналов, которые образуют всемирные телефонные сети общего назначения. В таких сетях пара пользователей занимает канал на время разговора. Отказ в работе некоторых сетевых компонентов снижает полную пропускную способность сети, и сокращается максимально возможное количество соединений. Это неблагоприятно сказывается на пользователях, возрастает вероятность того, что, когда человек захочет позвонить, линия будет занята. Это явление называется - «блокировкой вызова». В случае повреждения узлов в сети с коммутацией пакетов может увеличиться задержка передачи данных, но блокировки вызова не произойдет. Конечно для обоих типов сетей, если отсутствует связанность сети между двумя пользователями, они не смогут друг с другом общаться. В ранних работах по сетевой надежности предлагались модели сети с коммутацией каналов, где сетевые каналы считались неисправными, если они оказались блокированными.

Рис. 1. Arpanet 1979 год

1.1.3. Связные сети

Особый случай сетей с коммутацией каналов возникает при проектировании связных сетей в параллельных вычислительных архитектурах для объединения параллельных процессоров и памяти. Модели, основанные на связанности сети, одинаково применимы и к отказам по причине перегрузок, и к отказам в работе сетевых узлов. Эквивалентом производительности системы считается среднее значение параметра связанности сети между ее входной и выходной точками.

1.1.4. Локальные оптоволоконные сети для передачи голоса

Оптические кабели - одно из последних достижений современной технологии. Телекоммуникационные сети всего мира переводятся на использование этой техники (смотри, например, T. Flanagan, “Fiber Network Survivability” IEEE Communication Magazine 28 (1990) 46-53). В оптоволоконных каналах данные транспортируются при помощи световых волн, передаваемых по волокнам кварца. Основным преимуществом оптической среды передачи по сравнению с передачей по медным кабелям является существенный рост пропускной способности и снижение уровня шумов. Именно по этой причине многие телефонные сети общего пользования осуществляют быстрый переход на оптику. Как, однако, оказалось, в проблематике надежности сетей существуют более важные проблемы и именно их следует изучать. А именно: пропускная способность оптоволоконных сетей чрезвычайно высока, поэтому структура таких сетей в отличие от обычных имеет более распределенный характер. Старые сети были более разветвленными и имели большое число связей, вопрос сетевой надежности стоял не так остро. При проектировании современных сетей следует серьезно отнестись к проблеме сетевой надежности, т.к. перебои в работе даже одного из оптических каналов могут вызвать разрыв сети.

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

1.1.5. Архитектуры переключателей и компьютеров, устойчивые к сбоям.

Компьютерная система называется устойчивой к сбоям, если при отказе одного из ее компонентов, она продолжает функционировать. В 1970-х годах такие компьютеры использовались в качестве переключателей в опорных телекоммуникационных сетях. И сегодня они широко используются во многих приложениях. Позже были разработаны параллельные вычислительные архитектуры. С целью повышения производительности параллельные ЭВМ собирались из множества однотипных элементов. Однако параллельные архитектуры имеют также и повышенные характеристики надежности. Обычно такие отказоустойчивые и параллельные компьютерные системы при анализе надежности моделировались как сети. Поскольку большая часть исследований по оценке сетевой надежности велась для сетей передачи данных, основной упор делался на алгоритмы анализа топологии сетей. Стимулом работ по сетевой надежности послужили компьютерные архитектуры, в основе работы которых лежат сильно структурированные сети, сопряженные с определенными архитектурами ЭВМ. Обычно используются меры, базирующиеся на связанности сети. Однако особенно в случае параллельных ЭВМ с большим количеством процессоров должны рассматриваться параметры надежности, которые учитывают соображения пропускной способности.

1.1.6. Прочие применения

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

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

1.1.7. Причины возникновения сбоев.

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

1.2. Основные определения

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

Для модели с двумя состояниями вероятность работоспособности компонента или, проще надежность, можно понимать по-разному. Наиболее распространенными являются формулировки:

1. доступность компонента
2. надежность компонента

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

Cреднее время до отказа

среднее время до отказа + среднее время восстановления.

Определение надежности компонента не учитывает время восстановления. Специфицируется промежуток времени t, а надежность компонента определяется как вероятность того, что за это время t компонент останется в рабочем состоянии. Допускаются также иные трактовки для вероятности того, что компонент работает. Конечно, интерпретация уровня надежности компонента определяет в свою очередь интерпретацию мер сетевой надежности. В оставшейся части статьи мы будем использовать вероятность работоспособности или надежности и не будем пытаться это как-либо интерпретировать.

За отправную точку примем сеть G=(V,E), в которой V - набор узлов или вершин, а Е - набор неориентированных ребер или набор ориентированных дуг. При изучении моделей связанности для каждого еÎЕ мы определяем надежность е (р_е) как Pr[e работает]. При изучении простых моделей потоков (кратчайших путей), мы ассоциируем пропускную способность с_е(расстояние d_е) с каждым еÎЕ. Мы интерпретируем р_е, как вероятность того, что е работает и имеет пропускную способность с_е (расстояние d_е), а 1-р_е, как вероятность того, что е не работает и имеет пропускную способность 0 (расстояние равно бесконечности). При изучении моделей потоков (кратчайших путей) с множеством состояний мы ассоциируем распределение пропускной способности {c_е,i, p_е,i} (распределение расстояний {d_е,i, p_е,i}) для еÎЕ. Здесь p_е,i - вероятность того, что е будет иметь пропускную способность c_е,i (расстояние d_е,i).

Иногда, при изучении сетевой надежности, бывает удобно переходить к обобщенным случаям и рассматривать когерентные двоичные системы. Стохастическая бинарная система SBS (stochastic binary system) - представляет собой систему, которая отказывает случайным образом в результате случайного выхода из строя ее компонента. Каждый компонент из набора сетевых компонентов T может принимать одно из двух значений: работает, не работает. Структура системы описывается функцией ψ (S), определенной для SÍT.

ψ (S)=

Функция SBS является когерентной, если ψ(Т)=1, ψ(0)=0 и выполняется условие ψ(S΄)≥ψ(S) для S΄ÉS. Последнее свойство означает, что выход из строя любого из компонентов может только повредить работе системы. Представляет интерес задача вычисления выражения:

Rel(SBS,p)=Pr[ψ(S)=1, где S - набор работающих компонентов],

если известен вид распределения ψ(). Иногда мы рассматриваем задачи надежности, где р_е=p для всех е, в этих случаях мы заменяем p на p в представленной выше нотации. Для произвольной стохастической когерентной двоичной системы (SCBS - stochastic coherent binary system) определим набор путей как набор компонентов, работоспособность которых означает работу системы в целом. Назовем минипроходом - минимальный набор путей, обеспечивающих работоспособность системы. Аналогично определим набор разрезов, как набор компонентов, чей отказ вызовет отказ системы, а миниразрезом назовем минимальный набор таких разрезов.

1.3. Меры сетевой надежности

Сетевые меры надежности, которые мы изучаем, являются либо вероятностями определенных случайных событий, либо ожидаемыми значениями случайных переменных, которые зависят от структуры сети, расстояний и пропускной способности, ассоциированными с членами Е и вероятностями соответствующих событий. Большинство исследований по сетевой надежности, также как и большая часть нашей статьи посвящены к-терминальным мерам (см. раздел 1).

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

• Pr[Ф≥a] или Pr[Ф£a], вероятность достижения порогового значения, и
• Ex[Ф], ожидаемое значение для величины Ф

Пусть заданы два терминала s и t, и распределение пропускной способности (расстояния дуги), определяем Ф_FLOW как величину max(s,t)-потока, а Ф_PATH как величину наикратчайшего пути (s,t). Рассмотрим следующие меры производительности:

FT(G,s,t,{с_е,i, p_е,i },f_thresh) = Pr[Ф_FLOW≥ f_thresh]

ST(G,s,t,{d_е,i, p_е,i}, l_thresh) = Pr[Ф_PATH £l_thresh]

FE(G,s,t,{с_е,i, p_е,i }) = Ex[Ф_FLOW]

SE(G,s,t,{d_е,i, p_е,i }) = Ex[Ф_PATH]

Для этих мер, s относится к исходному узлу, а t - к терминальному.

2. Вычислительная сложность и соотношение проблем

Начинаем с обсуждения различий между ориентированной и неориентированной задачами и влиянием отказов узлов в параграфах 2.1 и 2.2 соответственно. После чего рассмотрим проблему вычислительной сложности.

2.1. Ориентированные и неориентированные сети.

Общий метод преобразования неориентированного ребра в пару противоположно ориентированных ребер проиллюстрирован на рис. 2. Этот подход широко применяется в задачах сетевой надежности.

Теорема 2.1. Пусть дан неориентированный граф G=(V,E), заданы вероятности разрыва ребер, их функция распределение по длинам {l_е,i, p_е,i } или по пропускной способности {с_е,i, p_е,i}. Применяя схему на рисунке 2 к каждому ребру исходного графа, получен ориентированный граф G¢=(V,A), надежность ориентированных дуг равна p_a, а распределение по длинам {l_a,i, p_a,i} или по пропускной способности {с_a,i, p_a,i}. Если эти параметры окажутся равными соответствующим параметрам неориентированного графа, тогда справедливо:

Rel(G,s,K,p) = Rel(G¢,s,K,{p_a})

FT(G,s,t,{с_е,i},{ p_е,i},f_thresh) = FT(G¢,s,t,{с_a,i}, {p_a,i},f_thresh)

ST(G,s,t,{d_е,i }, { p_е,i},l_thresh) = FT(G¢,s,t,{d_a,i}, {p_a,i},l_thresh)

FE(G,s,t,{с_е,i}, {p_е,i }) = FT(G¢,s,t,{с_a,i}, {p_a,i})

SE(G,s,t,{d_е,i}, {p_е,i}) = FT(G¢,s,t,{d_a,i}, {p_a,i})

Рис. 2. Преобразование неориентированных графов в диграфы.

Рассмотренное преобразование идентично тем преобразованиям, что применяются для сетевых потоков. Теорема 2.1 дает нам право трактовать состояния антипараллельной пары дуг, как пару независящих друг от друга случайных величин, в то время как их состояния не являются независимыми. Полученные соотношения могут не выполняться, если рассматривать более сложные меры работоспособности.

2.2. Отказы узлов

Во многих приложениях могут отказывать как дуги, так и узлы. Следовательно, приходится изучать модели, способные реагировать и на отказы узлов и на обрывы дуг. К счастью, для случая ориентированных сетей с помощью преобразования, показанного на рисунке 3, задачу с ненадежными ребрами и узлами можно свести к задаче с абсолютно надежными узлами и ненадежными ребрами. Преобразование используется для мер Rel(), FT(), ST(), FE() и SE(), где в каждом случае дуга, которая замещает узлы, наследует характеристики соответствующих узлов. При осуществлении преобразования для терминального узла i узел-заменитель i₁ не должен быть терминальным, а узел-заменитель i₂ должен быть терминальным. При выполнении этого преобразования для исходящего узла i нужно, чтобы i₁ был исходящим, а i₂ - таковым не был.

Рис. 3. Замена ненадежного узла.

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

2.3. Введение к сложности анализа надежности.

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

Чтобы наиболее простым образом свести задачи анализа надежности к более знакомым комбинаторным проблемам, рассмотрим частный случай задачи анализа надежности, которая возникает, когда все индивидуальные компоненты надежности равны, т.е. p_i для всех i. В этом случае Rel(SBS,p) можно записать в виде полинома по степеням p:

Rel(SBS,p)=

Этот полином является полиномом надежности. Задача по его вычислению называется задачей анализа функциональной надежности, где в качестве входных данных используется представление SBS, а на выходе получается вектор {F_i}.

Общий член в полиноме надежности F_ip^m-i(1-p)ⁱ представляет собой вероятность того, что работает ровно m-i компонентов сети и функционирует система в целом. Таким образом, можно интерпретировать F_i так:

F_i=|{S:|S|=i и ψ(T-S)=1}|.

Отсюда видно, что проблема определения коэффициентов F_i является задачей подсчета. Результатом задачи по распознавания гамильтоновых контуров может быть либо “Да”, если в графе содержатся контуры, либо “Нет”, а результатом задачи подсчета гамильтоновых контуров в графе является число таких контуров. NP и NP-полный являются классами задач распознавания. Классы, соответствующие задачам подсчета, обозначаются #P и #P-полный. Очевидно, что любая задача подсчета, по крайней мере, не проще чем соответствующая ей задача распознавания. Например, если известно число гамильтоновых контуров в графе, то не составит труда ответить на вопрос - «Число гамильтоновых контуров больше нуля?». Получается, что любая разновидность задачи подсчета из NP-полного класса часто является #P-полной. С другой стороны, существуют примеры задач распознавания, у которых время решения является полиномиальным, а их счетные аналоги относятся к NP-полному классу. Например, задача поиска точного соответствия в двудольном графе имеет полиномиальное время решения, а задача поиска точного числа полных соответствий в двудольном графе является #P-полной. Чтобы не усложнять этот обзор, мы не будем подробней вдаваться в проблему сложности, а будем указывать, относится ли она к полиномиальному классу или классу NP сложности.

Многие практические приложения требуют использования моделей с разной надежностью компонентов. В таких моделях все вероятности являются рациональными числами. Мы формулируем проблему анализа рациональной надежности следующим образом. В качестве входной информации используется представление и для каждого компонента i пара целых чисел a_i, b_i. На выходе получается пара целых чисел a и b таких, что a/b = Rel(SBS,{a_i/b_i}).

Мы начинаем с установления того, что, если конкретный анализ функциональной надежности является NP-сложными, тогда соответствующий анализ рациональной надежности является NP-сложными.

Утверждение 2.2. Для любой задачи анализа рациональной надежности r-Rel и соответствующей ей задачи анализа функциональной надежности, f-Rel за полиномиальное время может быть сведена к r-Rel.

Доказательство: В f-Rel входит представление функции SBS. На выходе необходимо получить набор коэффициентов {F_i} полинома надежности. Чтобы преобразовать f-Rel в r-Rel выберем m+1 рациональное значение вероятности 0 < p₀ < p₁ < ... < p_m < 1. Для j= 0,1,…,m обозначим решения соответствующей задачи анализа рациональной надежности как r_j = Rel(SBS,p_j), где все компоненты надежности установлены равными p_j. Теперь мы можем записать систему уравнений:

для j = 0,1,…,m.

Решив m+1 задачу анализа рациональной надежности, найдем p_j и r_j. Получим систему из m+1 линейного уравнения с m+1 неизвестными F_i. Коэффициенты матрицы имеют свойство матрицы Вандермонде и, следовательно, является невырожденной, таким образом, можно вычислить значения F_i.

Исследуем более детально вид полинома надежности для функций SCBS. Если задана SCBS, мы определяем значения:

m = число компонентов в системе

с = мощность набора минимального разреза

n_c = число наборов разрезов с минимальной мощностью

l = мощность минимального набора путей.

n_l = число наборов путей с минимальной мощностью

Заметим сразу, что коэффициенты полинома надежности обладают следующими свойствами:

, для i =0,1,…,m

, для i< c,

, для i=c,

F_i=n_l для i=m-l,

F_i=0 для i>m-l

Эти свойства означают, что, вычисляя полином надежности, мы легко определяем важные свойства SCBS функции. Например, исследовав полином надежности, мы сможем определить размер набора разрезов с минимальной мощностью. Таким образом, если задача распознавания набора разрезов с минимальной мощностью имеет сложность NP, то задача вычисления полинома надежности тоже имеет сложность NP. Из цепочки наших рассуждений следует:

Теорема 2.3. Для любой SCBS, если выполняется одно из следующих пяти условий, то задачи анализа функциональной и рациональной надежности являются NP сложными:

1. Задача распознавания минимального набора путей имеет сложность NP.
2. Задача подсчета минимального набора путей имеет сложность NP
3. Задача распознавания минимального набора разрезов имеет сложность NP
4. Задача подсчета минимального набора разрезов имеет сложность NP
5. Задача нахождения общих коэффициентов в полиноме надежности имеет сложность NP.

Доказательство: Результат анализа функциональной надежности следует из того, что выходные значения каждой из пяти задач могут быть получены из полинома надежности. Результат для проблемы рациональной надежности следует из утверждения 2.2. Применим построенную нами систему к задаче исследования сетевой надежности.

2.4. Сложность анализа сетевой надежности.

Приведем результаты, полученные для сложности анализа сетевой надежности в трех частных задачах: k-терминальной 2-терминальной и всетерминальной.

2.4.1. k терминалов

Набор путей с минимальной мощностью для k-терминальной меры является деревом Штейнера с минимальной мощностью. Известно, что задача распознавания является NP сложной для ориентированных и неориентированных сетей. Из теоремы 2.3 следует, что анализ функциональной и рациональной надежности для задачи анализа имеют NP сложность. Валиант [L.G.Valiant, “The complexity the enumeration and reliability problems”, SIAM, J. Computing, 8 (1979), 410-421] приводит альтернативное доказательство, заключающееся в демонстрации того, что вычисление SN(K)=∑ F_i = |{S : S соответствует субграфу, который содержит путь до каждого узла в К}|, имеет сложность NP. Здесь K является набором терминалов.

2.4.2. 2 терминала

Задачи распознавания минимального набора путей и разрезов, сопряженные с 2-терминальной мерой, являются проблемами кратчайшего пути и минимального разреза, соответственно. Известны полиномиальные алгоритмы для обеих этих задач. Валиант впервые показал, что задачи анализа надежности в случае 2-терминальной меры имеют сложность NP. Его результаты, которые мы описываем, являются хорошей иллюстрацией методик, используемых в данной области. Доказательство, приведенное ниже, зиждется на сведении проблемы вычисления SN(K) к задаче анализа 2-терминальной рациональной надежности:

Пусть дан граф G = (N,A) с исходным узлом s и набором терминальных вершин K. Построим граф G´, добавив к исходному графу узел t и дуги (u,t) для каждого uÎK. Присвоим вероятность отказа 1-p всем ребрам (u,t), а всем дугам исходной сети присвоим вероятность отказа 0,5. Заметим, что если все дуги из А имеют одинаковую вероятность отказа, равную 0,5, то все случайные состояния дуг из А, будет иметь вероятность (1/2)^|A|. Если через A_i обозначить число субграфов в G, в которых s соединена ровно с i узлами из K, то можно записать Pr[Rel(G`;s,t)]=∑_i∑ _SÍK,|S|=iPr[существует рабочий путь от s к S, но не работают остальные K-S узлов, а (u,t) работают для всех uÎS] = 2^-|E|∑A_i(1-pⁱ). Сделав оценку такой надежности для |K| различных значений p, мы можем записать систему из |K| уравнений с |K| неизвестными величинами A_i. Отсюда мы можем найти A_i. Сведение завершено, т.к. A_|K|=SN(K). Такое сведение показывает, что сложность рациональной задачи соответствует NP. Немногим сложнее доказать, что задача функциональной надежности имеет сложность NP.

2.4.3. Всетерминальная мера

Для ориентированной всетерминальной меры проблемы с наборами путей и разрезов с минимальной мощностью, являются задачами поиска минимального покрывающего дерева и минимального s-ориентированного разреза, соответственно.

Обе эти задачи решаются за полиномиальное время. Задача подсчета минимального s-ориентированных разрезов имеет сложность NP. А это, в свою очередь означает, что связанная с этим задача надежности имеет сложность NP. Для случая неориентированной меры задачи по распознаванию и подсчету минимального набора путей и разрезов имеют полиномиальную сложность. Однако задача вычисления общего члена в полиноме надежности имеет сложность NP потому, что задачи анализа надежности для неориентированного случая имеют сложность NP.

В свете этих негативных результатов, большинство исследований имело целью анализ структурированных сети. Самый широкий класс сетей, для которых можно выполнить вычисления за полиномиальное время, базируется на последовательно-параллельных графах и определенных обобщениях. Последние исследования посвящены сложности анализа надежности структурированных сетей, в частности это касается ориентированных ациклических и планарных сетей. Прован (J.S.Provan, “The complexity of reliability computations in planar and acyclic graphs”, SIAM, J. Computings 8 (1986), 694-702 ) показал, что неориентированная 2-терминальная проблема надежности имеет сложность NP в планарных нециклических сетях, имеющих степени узлов не выше трех.

Результаты данного раздела указывают на то, что полиномиальные алгоритмы для сетевой надежности существуют только для маленького класса сетей. Благодаря этому факту большое число исследований было посвящено изучению ограничений сетевой надежности, и подходов основанных на методе Монте-Карло.

3. Точное вычисление надежности

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

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

3.1. Преобразования и сокращения

Ребро или дуга, которые не входят ни в один из минимальных наборов путей называется нерелевантным: работоспособность таких нерелевантных ребер не влияет на работу или отказ сети. Самым простым способом упрощающего преобразования графа является удаление нерелевантных ребер. По определению, такое преобразование не меняет меру надежности. Чтобы преобразование имело практическое применение для сети, время его эффективной реализации должно быть полиномиальным. Для все-, k- и 2-терминальных мер надежности петли всегда являются нерелевантными. А для k- и 2-терминальных мер надежности, нерелевантными являются также все ребра, не имеющие терминального окончания. Такие ребра легко находить и удалять. В случае ориентированных задач надежности поиск нерелевантных дуг отнюдь не простая задача. Было показано, что задача нахождения нерелевантных дуг в случае (s,t)-связанности имеет сложность NP, в то время как общая неориентированная задача допускает эффективное решение.

Сосредоточимся сначала на неориентированных задачах. Ребро или дуга, входящие во все минипути, является обязательным. После удаления всех нерелевантных ребер, каждое оставшееся соединение (набор разрезов ребер с мощностью 1) является обязательным. Пусть G=(V,E) с набором терминалов KÍV, и ребро eÎE имеет вероятность функционирования p_e. Стягивание G●e , ребра e={x,y} из G получается путем удаления e, которое определяет x и y, и превращая результирующий узел в терминал всякий раз, когда K1{x,y}≠0. Надежность Rel(G) графа G удовлетворяет соотношению Rel(G)=p_eRel(G●e), когда e является обязательным ребром. Таким образом, отображение G в G●e является преобразованием, сохраняющим меру надежности, с мультипликативным коэффициентом p_e.

Два ребра e и f, имеющие одни и те же концы, являются параллельными. Так как любой минимальный путь содержит, по крайне мере, одно из двух таких ребер, а замена e на f будет естественным взаимно однозначным соответствием между минимальными наборами проходов, содержащих е, и минимальных путей с ребром f. Замена e и f на одно ребро g с коэффициентом p=1-(1-p_e)(1-p_j) не изменит общую меру надежности. Это называется параллельным сокращением графа. Понятие параллельного сокращения можно обобщить на случай, когда e и f сами являются заменителями ребер.

Два ребра e={x,y} и f={y,z} называются последовательными, когда y является узлом степени 2. В этом случае любой миниразрез содержит либо ребро е, либо f. Замена e на f является естественной для миниразрезов, содержащих e и f, соответственно. Таким образом, преобразование, сохраняющее меру надежности, получается путем удаления узла y и ребер e, f и добавления ребра g = {x,z} с надежностью p_g=p_ep_f при условии, что y не является терминальной вершиной. Это называется последовательной редукцией. В более общем случае, когда два ребра являются дополнениями, могут быть использованы аналогичные преобразования.

Последовательную редукцию нельзя применять к терминальным узлам графа со степенью 2. Однако, в случае, когда x, y, z являются терминалами, некоторое структурное замещение с сохранением меры надежности возможно. Коэффициент такого преобразования будет равен 1-(1-p_e)(1-p_f), если надежность нового ребра g определяется вероятностью p_g=p_ep_f/(1-(1-p_e)(1-p_f)). Это называется редукцией второй степени. Остается рассмотреть случаи, когда y является терминалом, а x или z - нет.

В сущности, каждое упрощение может рассматриваться, как замещение некоторой субсети субсетью, которая имеет эквивалентные характеристики надежности, или характеристики, которые масштабируют исходную меру надежности определенным образом. Принимая это во внимание, рассмотрим сеть G=(V,E) с набором терминальных узлов KÍV. Полученная из G подсеть H=(W,F) является s-связанной, если существует такой набор АÍW, с |A|£s, для которого каждое ребро графа G с одним концом в точке V\W и другим концом в W, имеет оконечную точка в А. Другими словами только узлы из А связывают подсеть с оставшейся сетью. Общий класс упрощений возникает из изучения s-связанных субграфов для малых s, и замещения каждого из них на более простые s-связанные графы.

1-связные субсети соединены с остальной сетью через один узел разреза. Если 1-связная субсеть не содержит терминалов, все ее ребра являются нерелевантными. С другой стороны, если субсеть, и остальная сеть содержат терминалы, сам узел разреза может рассматриваться как терминал, так как он связан с терминалами в любом минипути. Таким образом, добавляем узел разреза в качестве терминала. Затем сеть может быть разделена на две субсети H и G\(W-A), а мера надежности равна произведению мер этих двух объектов. Это обобщает понятие преобразования на процедуры, которые разделяет сеть на две или более субсети.

Для субсетей, объединенных в двух точках, мы рассматриваем замещение субсети как определение эквивалентного ребра. Если Н является субсетью, соединенной через {x,y}, и Н не содержит терминалов, то мы можем определить 2-терминальную надежность Н от х до у и заместить Н ребром {x,y}, чья вероятность работоспособности равна найденной 2-терминальной надежности. Когда Н содержит терминалы, ситуация более сложна, так как недостаточно знать, что х достижимо со стороны у, нужно также знать, могут ли все внутренние терминалы связаться с х или у или с обоими из них. Несмотря на это, разработаны преобразования, при которых ребрам присваивается несколько значений вероятности, а не только вероятность работоспособности. Число величин, которые нужно поддерживать, не зависит от размера сети, но растет экспоненциально с увеличением числа подсоединенных узлов.

3.2. Эффективные алгоритмы для ограниченных классов

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

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

Для k-терминальной надежности параллельно-последовательных графов существует два алгоритма с линейным временем работы. Сатайанарайана и Вуд [A.Satyanarayana and R.K.Wood “A linear time algorithm for computing k-terminal reliability in serial-parallel networks”, SIAM, J. Computing 14 (1985), 818-832] использовали последовательную, параллельную и двухступенчатую редукцию совместно с редукциями двухсвязных сетей, называемых также преобразованиями многогранник-цепочка, чтобы свести последовательно-параллельную терминальную сеть к одновершинному графу.

Когда две субсети сопряжены с s узлами, надежность их объединения может быть полностью определена из значений для каждой субсети. Это может быть фактически выполнено посредством алгоритма динамического программирования, чье время работы линейно по отношению к числу вершин, но экспоненциально относительно числа точек соединения. Метод Уолда и Кольбурна использует тот факт, что последовательно-параллельные графы могут быть рекурсивно разъединены с помощью парных разрезов в вершинах - то есть, последовательно параллельные графы имеют ширину дерева равную двум. Расширение алгоритма с линейным временем на деревья любой ширины является непосредственным, за исключением трудности распознавания сетей с заданной шириной дерева.

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

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

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

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

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

3.3. Методы, базирующиеся на состояниях

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

Состояние сети G=(V,E) определяется субнабором SÍE работоспособных ребер. Концептуально простейшим точным алгоритмом является полный подсчет состояний. Пусть O является набором всех рабочих состояний. Тогда

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

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

Rel(G)=p_eRel(G×e)+(1-p_e)Rel(G-e)

для любого ребра е из G. Факторизация продолжается до тех пор, пока не будут подсчитаны все состояния. Однако некоторые простые наблюдения могут дать определенные улучшения. Когда G - е не работает, любая последовательность сокращений и удалений приводит к неработающему состоянию сети, и по этой причине нет нужды факторизовать G - е. Более того, хотя мы можем не иметь возможности упростить G с помощью преобразования, сохраняющего надежность, мы можем упростить G×e или G - e.

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

Ниже мы определяем метод факторизации более явно:

procedure factor (graph G)

используем преобразования, сохраняющие надежность G, следующим образом

удаляем нерелевантные ребра

стягиваем необходимые ребра

используем последовательные редуцирования

используем параллельные редуцирования

используем 2-ступенчатые редуцирования

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

если G имеет только один оставшийся терминал, return(mult)

в противном случае

выбираем ребро е из G

return(mult*(factor(G ×e)+factor(G-e)))

end (конец)

Дальнейшие улучшения возможны путем разделения графа на двухсвязные или трехсвязные компоненты на каждом этапе.

3.4. Методы, базирующиеся на маршрутах и разрезах

Когда базовые редуцирования выполнены, для завершения вычислений можно применить полный подсчет состояний. Если только редуцирования не приводят к существенному уменьшению размера графа, такая схема непрактична. Несмотря на это, можно сформировать все минимальные пути сети и, следовательно, метод, использующий минимальные маршруты, будет работать. Предположим тогда, что минимальные пути P₁,…,P_h графа G посчитаны. Пусть E_i является случаем, когда все ребра минимаршрута P_i работоспособны. Тогда надежность равна вероятности того, что произошло одно (или более) событий {E_i}. К сожалению, {E_i} не являются независимыми и, следовательно, мы не можем просто суммировать вероятности их реализации. Точнее Pr[E₁ или E₂] равна Pr[E₁] + Pr[E₂] - Pr[E₁ и E₂]. Теперь Rel(G) = Pr[E₁ или E₂ или … или E_s], и, следовательно,

(1)

где E_I является событием, когда все пути P_i c iÎI находятся в рабочем состоянии. Это является стандартным расширением включения-исключения.

Имея список минимальных путей, вычисляется вероятность для каждого реализованного субнабора минимальных путей. Чтобы вычислить надежность, необходимо только определить выше представленную сумму. Выполняя это, следите, чтобы нечетные минипути давали вклад с плюсом, а четные - с минусом. Это сводит нашу проблему к определению набора всех минимаршрутов. Наивная реализация этого подхода фактически хуже, чем полный подсчет состояний. Число наборов путей h может быть показательной функцией n и, следовательно, только формирование минипутей требует экспоненциального времени. Однако более серьезным недостатком является то, что генерирование всех субнаборов наивным способом занимает 2^h времени, которое предоставляет нам дважды экспоненциальный алгоритм вычисления надежности.

Приняв меры, можно избежать двойного экспоненциального поведения. Каждый субнабор минипутей соответствует субграфу, ребра которого являются объединением наборов ребер минипутей. Учитывая это, i-структура субграфа является набором i минипутей, чье объединение является субграфом. Структура является нечетной, когда i нечетно, и четным, когда i четно. Граф, имеющий структуру, является К-субграфом. Каждая нечетная структура субграфа вносит положительный вклад в надежность, а каждая четная структура дает негативный вклад. Знаковая доминантность G с терминальным набором вершин К, sdom(G,K), равна числу нечетных структур G минус число четных структур G. Доминантность dom(G,K) равна абсолютному значению знаковой доминантности. Мы обычно пишем sdom(G), а подразумеваем dom(G) с терминальным набором К. С учетом этих определений Сатианарайана и Прабхокар существенно упростили выражение для надежности:

,

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

Первой целью является определение того, какие состояния имеют знаковую доминантность равную нулю, и могут, следовательно, игнорироваться в выражении для надежности. Учитывая это, состояние (субграф) является релевантным, если он не содержит нерелевантных дуг. Субграф, содержащий нерелевантные дуги, не имеет каких-либо структур и, следовательно, имеет нулевую знаковую доминантность. Таким образом, мы ограничиваем наше рассмотрение только релевантными субграфами. Среди релевантных субграфов многие имеют нулевую знаковую доминантность: точнее циклические субграфы (субграфы с ориентированными циклами). Более того, нециклические релевантные диграфы с m дугами и n узлами имеют знаковую доминантность sdom(G)=(-1)^m-n+1.

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

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

Предположим, что у нас есть перечень минипроходов P₁,…,P_h и пусть E_i является случаем, когда все ребра/дуги минипрохода P_i являются работоспособными. Как было замечено, события {E_i} не являются независимыми. Мы рассматриваем стратегию формирования набора независимых событий. Пусть обозначает дополнение события E_i. Теперь определим событие D₁=E₁, и вообще, . События D_i являются независимыми, и, поэтому часто называются событиями “независимого произведения”. Более того, Rel(G)=. При использовании этого подхода нужно получить формулу для Pr[D_i] в терминах состояний ребер/дуг. Каждое событие E_i может быть записано в виде булевого выражения, которое является произведением состояний ребер/дуг минимаршрута P_i. Следовательно, D_i может быть также записано в виде булева выражения. По этой причине алгоритмы, которые используют независимые произведения, называются иногда методами “булевой алгебры”.

Существует большое разнообразие методов булевой алгебры. Во-первых, заметим, что выражение для события D_i является комплексным булевым выражением, включающим дополнения событий E_i, а не только состояния ребер и дополнения состояний ребер. Вычисление D_i требует упрощения булевого выражения к такому виду, который включает только состояния ребер и их дополнения. Большинство методов связано первоначально с эффективностью этого упрощения и с получением результирующих выражений, которые настолько малы насколько возможно. Во-вторых, чтобы облегчить упрощение, большинство методов использует некоторую простую стратегию для упорядочения кратчайших проходов прежде чем определять события {D_i}. Конкретные, определенные события сильно зависят от выбранного порядка минипроходов. Типовой эвристикой здесь является упорядочение кратчайших проходов путем помещения в начало проходов с меньшим числом ребер/дуг. Несмотря на эти эвристические улучшения, вообще не существует известной полиномиальной границы для длины упрощенного булевого выражения Rel(G) через число минипроходов.

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

Кольбурн и Пулейбланк [S.J.Colbourn and W.R. Pulleyblank, “Matroid Steiner problems< , the Tutte polynomial and network reliability” J. Combinatorial theory B41 (1989), 20-31] сформулировали алгоритм упорядочения минипроходов для проблем k-терминальной надежности, где число членов не превышает числа деревьев связи. Однако это число может превышать число минипроходов при экспоненциальном факторе.

Каждый алгоритм, упомянутый здесь, в худшем случае требует экспоненциального времени реализации вне зависимости оттого, вычисляет ли он число состояний, минипроходов или миниразрезов. Полный граф с n узлами, например, имеет 2^n-1 миниразрезов, n^n-2 деревьев связи и состояний. Если экспоненциальные алгоритмы оказываются наилучшими, можно надеяться, что разумно рассмотреть алгоритмы, которые используют относительно малое число состояний. Из многих алгоритмов, упомянутых здесь, три метода наиболее достойны внимания.

Методы, основанные на доминантности, гарантируют, что будут просматриваться только релевантные состояния и, таким образом, достигается улучшение в отношении почти всех других методов включения-исключения. Методы, базирующиеся на факторизации (для неориентированного случая), также генерируют только релевантные состояния. Подход Сатайанарайана-Чанга реализует наилучшее возможное время вычисления, используя последовательные и параллельные сокращения. Фактически, во всетерминальном случае, так как число деревьев связи превышает доминантность, алгоритм улучшает все методы, основанные на минипроходах. Наконец, методы, основанные на независимых произведениях, хотя и сопряжены с трудностями анализа, дают два важных алгоритма: алгоритм Болла-Немхаузера для вычисления всетерминальной надежности за полиномиальное время при заданном числе минипроходов, и алгоритм Прована-Болла, который вычисляет двухтерминальную надежность за полиномиальное время при заданном числе миниразрезов.

Этот полезный механизм измерения сложности в терминах числа минипроходов, миниразрезов или релевантных состояний позволяет видеть, что отобранные методы в действительности лучше остальных алгоритмов оценки сетевой надежности.

4. Границы сетевой надежности

Существенно, то, что проблемы надежности, представляющие интерес, являются #P-полными, и, следовательно тот факт, что описанные точные алгоритмы совершенно неэффективны не вызывают удивления. Несмотря на это при оценке сетевой надежности абсолютно необходимо, чтобы работа завершалась за “разумное” время. Конфликтные требования быстрого вычисления при высокой точности приводят к разнообразной коллекции методов установления мер надежности.

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

Проведение связи между методами Монте-Карло и методиками ограничений, возможно, вводит в заблуждение, так как многие методы Монте-Карло используют ограничения как средство определения размера пространства выборки. Мы сначала рассмотрим случай, когда все ребра работают независимо с одной и той же известной вероятностью. Затем мы рассмотрим вариант, когда ребра работают независимо с произвольными (но все же известными) вероятностями.

4.1. Равные вероятности отказа ребер

В этом разделе мы работаем с ограничениями, которые верны, когда каждое ребро имеет одну и ту же вероятность работоспособности р; в этом случае, как мы видели, надежность может быть выражена в виде полинома от р. Субграф с рабочими ребрами Е’ÍE возникает с вероятностью p^|E’|(1-p)^|E-E’|. Следовательно, вероятность получения субграфа зависит только от числа ребер, которые он содержит. Тогда пусть N_i обозначает число рабочих субграфов с i ребрами. Вероятность работы сети обозначим Rel(G,p) или просто Rel(p) и тогда

Таким образом, вероятность является полиномом по р, который называется полиномом надежности. Это формулировка в терминах наборов маршрутов. Другая формулировка получается из рассмотрения наборов разрезов. Пусть С_i равно числу i-реберных наборов разрезов (оставляющим m-i рабочих ребер), тогда

Еще одна формулировка, вероятно наиболее общая, получается путем рассмотрения дополнений наборов маршрутов. Пусть F_i обозначает число наборов с i ребрами, для которых остальные m-i ребер образуют набор маршрутов. Тогда

4.1.1. Базовые наблюдения

Первой целью введения полинома надежности является компактное представление информации о надежности, чтобы сравнивать топологических кандидатов. Кельманс [A.K.Kel’mans “The graph with the maximum probability of remaining connected depends on the edge-removal probability”, Graph theory newsletter, 9 (1979) 2-3; “On graph with randomly deleted edges”, Acta Math. Acad. Sci. Hung, 37 (1981), 77-78] доказал, что для заданного числа вершин и ребер, в определенных случаях не существует графа, который является наиболее надежным для всех вероятностей работоспособности ребер. Таким образом, надежность является больше чем просто параметр графа; она в действительности является функцией надежностей каналов (связей).

4.1.2. Точное вычисление некоторых коэффициентов

В разделе 2.3 мы показали, что возможность вычисления размера набора проходов l с минимальной мощностью и размера с набора разрезов с минимальной мощностью делает возможным точное определение числа коэффициентов. Когда l эффективно вычислимо, дальнейшая информация может быть часто получена с помощью вычисления N_l. В k-терминальной проблеме это по правде безнадежно, так как нужно подсчитать минимальное число деревьев Штайнера, что является #P-сложной задачей. В двух других случаях, однако, эффективные алгоритмы существуют.

Во всетерминальной проблеме N_i.равно числу деревьев связи. Кирхофф в 1847 разработал элегантный метод подсчета деревьев связи; он был разработан в форме, удобной для реализации на ЭВМ. В двухтерминальной проблеме N_i равно числу наикратчайших s,t-проходов. Болл и Провен разработали эффективную стратегию для вычисления этого числа. Было установлено, что для любого фиксированного k³ 0, набор проходов размера l+k в двухтерминальной проблеме может быть эффективно вычислен.

Эффективный алгоритм для вычисления с дает нам возможность также определить точно число дополнительных коэффициентов. Эта проблема легко решаема во всех трех случаях, представляющих интерес, с использованием идентичного метода в каждом из случаев. Теорема Менгера гарантирует, что минимальный s,t-разрез имеет в точности размер с, когда максимальное число s,t-проходов с разъединенными ребрами равно с. Эта проблема легко адаптируется для задачи сетевых потоков со всеми ребрами, имеющими полосу (пропускную способность) равную 1.

Имея вычисленное с, было бы интересно вычислить C_c, число наборов разрезов минимальной мощности. Прован и Болл показали, что в двухтерминальном случае вычисление лишь этого коэффициента является #P-сложным; так как k-терминальная проблема включает в себя двухтерминальную проблему. Однако для всетерминальной проблемы был разработан метод эффективного вычисления C_c. Ломоносов и Полесски [М.V.Lomonosov and V.P.Polesskii, “Lower bound of network reliability”, Problems of Information Transmission, 8 (1972), 118-123] показали, что каждый n-узловой граф G имеет . Кроме того, замечено, что для любого i и любого ребра е графа G C_i(G)=C_i(G ×e)+C_i-1(G-e). Эти два факта были использованы, чтобы разработать эффективный метод для подсчета наборов разрезов размера c+k для любого фиксированного k ³ 0.

4.1.3. Простые ограничения

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

Rel_A(p)»N_n-1p^n-1(1-p)^m-n+1

а когда р близко к 1,

Rel_A(p) »1-С_сp^m-c(1-p)^c

В заданном определении полинома надежности точная формулировка аппроксимации Кельмана верна для всех значений р:

N_n-1p^n-1(1-p)^m-n+1£Rel_A(p) £1 - C_cp^m-c(1-p)^c

Таким образом, аппроксимации Кельмана могут рассматриваться как абсолютные ограничения на полином надежности. Существенным наблюдением здесь является то, что для крайних значений р любой член, содержащий N_n-1 или член, включающий C_c, доминирует над остальными членами. Мы знаем, что N_i+C_m-I= и, следовательно, мы имеем .

Это наблюдение подводит нас к простому набору ограничений:

В нижней границе каждый “неизвестный” N_i аппроксимируется нулем; известные коэффициенты равны для i < n-1 (нуль) i=n-1 (число деревьев связи), i=m-c (m-c-реберный субграф, чьи компоненты не равны минимальной мощности набора разрезов), и i > m-c (все возможные i-ребра субграфов). В верхней границе “неизвестный” N_i аппроксимируется . Расширение для k-терминальной надежности достаточно прямолинейно: просто всюду подставляем l вместо n-1. Нижняя граница, несмотря на это, оказывается недооценивающей N_l как 0; верхняя граница получается просто путем использования недооценки для самого l.

Эти ограничения крайне слабы и предоставляют полезную информацию, только когда р лежит вблизи 0 или 1.

4.1.4. Когерентность

Ограничение неизвестного N_i сильно зависит от знания комбинаторной структуры набора работающих субграфов. Большинство проблем надежности, представляющих для нас интерес, имеют свойство когерентности. Имея это в виду, рассмотрим набор D={D₁, D₂,D₃,…,D_r}, в котором каждый D_i является набором ребер, для которого E - D_i является рабочим. Набор D имеет набор для каждого работающего субграфа, в который входят ребра, не перечисленные в работающем субграфе. Определив так D, мы сформировали наследственное семейство наборов (или комплекс), называемый F-комплексом (то есть, если SÎD и S’ ÍS, тогда S’Î D. Тот факт, что сформированное семейство наборов является наследственным, означает, что оно имеет свойство когерентности. Не является совпадением и тот факт, что F_i, определенное ранее, в точности равно числу наборов мощности i в D. Фактически полином надежности для наследственного семейства D полностью определяется его F-вектором (F₀,F₁,…,F_d), где d=m-1.

Ключом к использованию когерентности при нахождении ограничений является следующее. Рассмотрим все i-наборы в семействе наследования D. Так как семейство является наследственным, в коллекции i-наборов должно быть несколько i-1-наборов; минимальное число таких индуцированных наборов является нижней границей для F_i-1. Минимизация F_i-1 как функции F_i является известной проблемой в теории экстремальных наборов. Здесь имеет место неравенство .

Теорема Спернера может использоваться при небольших вычислительных усилиях для улучшения простых ограничений. Мы предполагаем, что доступны l, c, F_m-1 и F_c. Тогда

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

Одним из таких методов является улучшение теоремы Спернера. Теорема Крускала-Катона помещает нижнюю границу на F_i-1, заданное F_i; соответственно, она помещает верхнюю границу на F_i, заданное F_i-1. Форма границы здесь имеет малую важность, за исключением того, что x^j/i может быть эффективно вычислено, и что всякий раз, когда x³y, x^j/i ³ y^j/i. Напомним, что F_с равно . Для всетерминальной надежности мы можем вычислить F_с точно; в остальных двух случаях мы не можем надеяться вычислить F_с, но мы можем легко вычислить F_с-1. Предположим, что мы можем вычислить эффективно последовательность коэффициентов F₀,F₁,…,F_s. Тогда теорема Крускала-Катона дает нам верхнюю границу для F_s+1. Затем, задав значение верхней границы для F_s+1, мы идем тем же путем, чтобы получить верхние ограничения для F_s+2, F_s+3 и так далее.

Нижние границы получаются симметрично. Мы эффективно вычисляем некоторую последовательность коэффициентов F_m-l, F_m-l+1,…,F_m. Для всетерминальной и двухтерминальной надежности F_m-l равно числу деревьев связи и кратчайших путей, соответственно. В k-терминальной проблеме, для того чтобы вычислить эту последовательность, мы можем задать, например, l=k-1. В любом случае пусть d=m-l. При известном F_d, теорема Крускала-Катона выдает нижнюю границу для F_d-1, а именно .

4.1.5. Оболочечность

У нас нет надежды без дополнительной информации улучшить ограничения Крускал-Катона. Такая дополнительная информация может быть получена разными путями. Одним из таких путей мог бы быть эффективный алгоритм вычисления (или установления более жестких границ) одного или более неизвестных F_i. Другим - может быть выявление того, что конкретное наследственное семейство, имеет некоторую специальную комбинаторную структуру. Этот последний подход является многообещающим, так как, несмотря на то, что компоненты наборов маршрутов в когерентных системах образуют наследственные семейства, не все наследственные семейства образуются таким путем.

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

Прован и Биллера доказали важный результат, связанный со структурой матроидов, который (вместе с другими результатами) накладывает ограничения на их F-векторы. Они показали, что матроиды являются “оболочечными” комплексами. Важность результата Прован-Биллера в исследованиях надежности заключается в том, что они предлагают возможность использования оболочечности для улучшения ограничений Крускал-Катона. Конечно, это требует введения структурной теоремы для оболочечных систем. Интервал [L,U] является семейством субнаборов {S:LÍSÍU}. Часть интервала комплекса является набором разъединенных интервалов, для которых каждый набор в комплексе принадлежит строго одному интервалу. Комплекс разделим, если он имеет секции интервалов [L_i,U_i], 1 £i £ J с U_i в качестве базы для всех i. Оболочечные комплексы всегда являются разделимыми.

Рассмотрим оболочечный комплекс с b базами. Пусть {[L_i,U_i]|1 £i £ b} является секцией интервала для этого комплекса. [L_i,U_i] является компактной записью для всех наборов в интервале. Вероятность того, что какой-то из этих наборов реализуется, равна тогда p^m-|U_i|(1-p)^|L_i|. Другими словами, ребра |L_i| должны отказать, а ребра m-U_i должны работать. Состояние остальных ребер не играет никакой роли. Каждый U_i является базой в комплексе; следовательно, мощности всех U_i равны (ранг d базы). Однако ранги L_i не являются идентичными; мы, следовательно, определяем H_i=|{L_j:1£j £ b,|L_j|=i}|. Это дает увеличение Н-вектора (Н₀,…,Н_d). Коэффициенты H_i определяют интервалы в секции, чей младший набор имеет ранг i.

Это предлагает еще одну форму полинома надежности:

Здесь l - мощность набора маршрутов с минимальной мощностью (дерево связей), а d=m-l является рангом базы. Более конкретно, в графе с n-вершинами и m-ребрами i=n-1, а d=m-n+1.

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

Рассмотрим наборы ранга k в комплексе. Они подсчитываются с помощью F_k. Теперь любой интервал [L_i,U_i] отвечает за определенные наборы. Пусть r является рангом L_i. Если r > k, интервал отвечает за 0 наборов в F_k; однако, если r£ k, он отвечает за наборы . Отсюда мы нашли, что . Приравнивание форм F-вектора и Н-вектора полинома надежности дает выражение для H_i в терминах F-вектора, а именно

Это выражение позволяет нам эффективно вычислить Н₀,…,Н_s. Другой очевидный, но полезный факт заключается в том, что .

Стенли получил нижнюю границу для Н_i-1, заданном Н_i, которая вообще является жесткой для оболочечных комплексов. Это, в свою очередь дает верхнюю границу для Н_i, заданном Н_i-1. Для наших целей важны три вещи. Прежде всего, для k ³ j³ i, x^<k/i> = x^<j/i><k/j>. Во-вторых, при заданных x, j и i мы можем эффективно вычислить x^<j/i>. В-третьих, всякий раз, когда x³y, x^<j/i> ³y^<j/i>.

Теорема Стенли может быть использована для получения эффективно вычисляемых ограничений полинома надежности. Задав префикс (F₀,…,F_s) F-вектора, мы можем эффективно вычислить префикс (Н₀,…,Н_s) Н-вектора.

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

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

Ставим в соответствие каждому Н_i “корзину”. Теперь предположим, что мы имеем F_d “мячей”. Наша задача заключается в том, чтобы поместить все мячи в корзины, так чтобы номера мячей в i-ой корзине, удовлетворяли условию .

Как следует распределить мячи так, чтобы максимизировать или минимизировать полином надежности? Эти распределения, когда будут найдены, дадут верхнее и нижнее ограничение полинома надежности. Тщательно рассмотрим сумму полиномов надежности: . Так как 0<р<1, сумма больше, когда коэффициенты нижнего порядка больше. Фактически для двух Н-векторов (Н₀,…,Н_d) и (J₀,…,J_d) всякий раз, когда для всех i, полином надежности Н_i доминирует над полиномом надежности для J_i.

Это последнее простое наблюдение предлагает методику получения ограничений. В практической модели верхняя граница получается путем помещения мячей в самую левую корзину (с корзинами пронумерованными 0,…,d слева направо); аналогично, нижняя граница получается помещением мячей в самую правую корзину. Мы делали это размещение не без ограничений, так как мы заранее знали содержимое корзин 0,…,s.

Теперь мы формируем коэффициенты для полинома верхней границы и для полинома нижней границы, используя префикс (Н₀,…,Н_s) и F_d. Шаги включают в себя:

1. Для i=0,…,s устанавливаем =Н_i=
2. Для i=

В каждом ограничении мы определяем число мячей в каждой корзине от 0 до d по порядку. Как мы заметили, содержимое корзин 0,…,s известно. Для последующих корзин верхняя граница определяется следующим образом. Число мячей, которые могут попасть в текущую корзину, ограничено теоремой Стенли, и лимитируется также тем фактом, что существует фиксированное число мячей, подлежащих распределению. Если осталось больше мячей, чем мы можем поместить в текущую корзину, мы кладем столько, сколько сможем. Если все может быть помещено в текущую корзину, мы делаем это; в этом случае все мячи оказались распределены, а остальные корзины пусты. Нижняя граница определяется путем помещения минимально возможного числа мячей.

Метод приводит к очень мощному набору ограничений, границам Болл-Провена:

В отличие от ограничений Крускала-Катона в случае ограничений Болла-Прована обычно не имеет место неравенство .

4.1.6. Многогранные комплексы и матроидные порты

В случае проблемы достижимости Прован [J.S.Provan, “Polyhedral combinatorics and network reliability”, Math. Oper. Res., 11 (1986) 36-61] замечает, что F-комплекс является “многогранным комплексом” и использует теорему Биллеры и Ли, чтобы получить эффективно вычисляемые ограничения надежности, которые жестче для многогранных комплексов.

Структура матроида для всетерминальной проблемы и многогранная структура достижимости позволяют получить существенное улучшение по сравнению с ограничениями Крускала-Катона для общей когерентной проблемы надежности. Пусть для связного графа с n вершинами, имеющего k терминалов, и набор ребер Е, |E|=m, F является его F-комплексом. Блокирующий комплекс F* из F является {E\S:SÎ2^E\F }. F-вектор (F₀,...,F_m) из F и F-вектор удовлетворяет условию для 0 £ i £ m. Чари показал, что субкомплекс F^(m-n+1), полученный путем удаления всех наборов из F с мощностью, превосходящей m-n+1, является оболочечным комплексом. Следовательно, задав ограничение на отдельный коэффициент F_m-n+1, можно применить стратегию Балл-Прована к этой k-терминальной проблеме, для того чтобы ограничить (F₀,…,F_m-n+1). Что можно сказать об остальных коэффициентах? Чари далее доказал, что F*^(n-2), полученный из F* путем удаления всех наборов с мощностью, превосходящей n-2, также является оболочечным. Следовательно, границы Балл-Прована могут быть применены снова для ограничения (F*₀,…,F*_n-1) или эквивалентно ограничить (F_m,…,F_m-n+2).

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

4.1.7. Стандартная форма

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

Мы видели ранее, что один или более полезных точных алгоритмов используют теорию доминирования. Мы вернемся немного к этой теории, чтобы разработать интерпретацию коэффициентов в полиноме надежности. В развитие идеи доминирования следующим образом определена i-четность P_i(G). Пусть все S_i являются i-реберными субграфами графа G. Тогда P_i(G)=. Сатянарайана и Кхалил [A.Satyanarayana and Z.Khalil, “On an invariant of graphs and the reliability polynomial” SIAM J. Alg. Desc. Meth, 7 (1986), 399-403] установили, что P_i(G)=P_i-1(G×e)+ P_i-1(G-e).

При получении значения надежности через наборы маршрутов каждое образование рассматривается только один раз. Пусть {G₁,…,G_t} обозначает все K-субграфы графа G, Rel_k(G)=. Следовательно, когда все вероятности для ребер равны, мы получаем другую форму полинома, стандартная форма:

Другими словами, четности являются просто коэффициентами этого полинома надежности (Р-вектор).

Описание Р-векторов, базирующееся на полиномах надежности, широко не изучалось. Р-вектор для полинома всетерминальной надежности удовлетворяет неравенству для каждого i. О Р-векторе в настоящее время мало что известно. Легко видеть, что P_i =0 для i<n-1 и что Р_n-1 равно числу деревьев связи в сети. Однако по существу ничего не известно об остальных коэффициентах в Р-векторе (за исключением, конечно, тех соотношений, которые связаны с эквивалентностью Н- и F-векторов).

4.2. Вероятности отказов произвольных ребер

Когда ребра отказывают с разными вероятностями, F -комплекс содержит всю информацию о надежности, предоставив рабочие вероятности для каждого ребра. Однако F-вектор и полином надежности здесь более не применимы. Это ведет к нескольким методикам использования структуры сети для получения ограничений.

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

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

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

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

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

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

Ничего не стоит также, чтобы любая группа ребер работоспособных субграфов G₁,….,G_k, для которых легко вычислить Rel(G_i), предоставляла возможность эффективного вычисления нижней границы. Это приводит к задачам, таким как группирование ребер для последовательно-параллельных графов, или к частичным k-деревьям при фиксированном k. Этот последний подход, кажется, еще не изучен в литературе, следовательно, мы сосредоточимся на формировании групп ребер с минипроходами.

Используя теорему Таттла и Нэш-Вильямса, Полесски заметил, что граф с n вершинами и с-связанными ребрами имеет, по крайней мере, деревьев связи с разъединенными ребрами. Следовательно, когда вероятности работоспособности всех ребер равны р, всетерминальная надежность графа равна, по крайней мере, 1-(1-p^n-1)^[c/2]. Когда вероятности для ребер не равны, граница Полесски естественным образом расширяется. Применение леммы 4.1 позволяет получить нижнюю границу все-терминальной надежности. Естественно, чтобы получить наилучшее ограничение на основе леммы 4.1, захочется иметь не только большое число минипроходов с разделенными ребрами, но также потребовать, чтобы эти минипроходы были надежны. Алгоритм Эдмондса не обязательно выдает набор деревьев связи, предоставляющий наилучшее ограничение при группировании ребер, использующем минипроходы. Фактически, проблема сложности нахождения набора деревьев связи, приводящих к наилучшим ограничениям при группировании ребер, остается открытой.

Для двухтерминальной надежности минипроходы являются лишь s,t-проходами. Теорема Менгера утверждает, что максимальное число s,t-проходов с разделенными ребрами равно мощности минимального s,t-разреза. Таким образом, используя методики сетевых потоков, можно найти максимум группирования ребер. Проблема нахождения наилучшего группирования ребер, даже если все вероятности работоспособности ребер равны, является сложной из-за того факта, что минипроходы демонстрируют большую вариацию мощности.

Обратимся к k-терминальной надежности, где ситуация не столь удовлетворительна. Здесь минипутем является субдерево, в котором каждый листик представляет собой терминал, т.е. дерево Штайнера. Оказалось, что никакой эвристики для нахождения “хороших” групп ребер для деревьев Штайнера не найдено.

До этого момента мы рассматривали нижние границы, базируясь на методике группирования ребер в рамках минипроходов. Теперь обратимся к верхним границам. Не удивительно, что лемма 4.1 имеет “дуальный” вид для верхних границ при замене набора проходов на набор разрезов:

Лемма 4.2. Пусть G=(V,E) является графом (или диграфом, или мультиграфом). Пусть Rel является когерентной мерой надежности. Пусть С₁,…,С_s является группой ребер G набора разрезов. Тогда

где р_е - вероятность работоспособности ребра е.

Лемма 4.2 дает верхнюю границу, так как отказ для любого разреза при группировании ребер вызывает отказ G, но отказ G может случиться, даже когда ни один из наборов разрезов в группе не дает отказа.

Нахождение максимального набора разрезов, разъединяющих ребра, достаточно прямолинейно - просто следует пометить каждый узел его расстоянием от s. Если t получает метку l, формируем набор разрезов С_i, содержащий все ребра между вершинами, помеченными i-1 и вершинами, помеченными i для 1 £ i £ l. В результате получается l s,t-разрезов, разъединяющих ребра. Нахождение ”хороших” наборов разрезов для определения верхних границ методом группирования ребер оказывается более сложным, чем для нижних границ. В последнее время Вагнер [D.K.Wagner, “Disjoint (s,t)-cuts in a network”, Networks 20, (1990), 361-372] предложил алгоритм с полиномиальным временем для нахождения набора s,t-разрезов, разъединяющих ребра, с минимальной стоимостью при максимальной мощности.

Обратившись к верхним границам все- и k-терминальной надежности с привлечением группирования ребер миниразрезами, мы сталкиваемся с главной трудностью: даже для всетерминальной надежности нахождение максимальной группировки посредством миниразрезов является NP-трудным. Таким образом, верхняя граница всетерминальной надежности может быть получена путем использования ограничения группирования дуг для достижимости.

Выделяются два потенциальных метода улучшения стратегии группирования ребер. Первый - заключается в рассмотрении более надежных субграфов для группировки; второй - связан c расширением рассматриваемых наборов проходов и разрезов с целью разрешения некоторых пересечений ребер (таким образом, теряя независимость наборов ребер в группировке). Мы рассматриваем второе расширение, которое используется более активно в следующем подразделе. Для первого метода оказалось выполнено мало работы. Используя эффективный точный алгоритм для достижимости в случае бесцикловых ориентированных графов, Раманатхан и Кольбурн [A.Ramanathan, and C.J.Colbourn, “Bounds on all-terminal reliability via arc packing”, Ars Combinatoria 23A, (1987), 91-94] получили улучшения верхних границ достижимости, а также всетерминальных верхних границ надежности. Однако использование группирования ребер с привлечение не минимальных проходов или набора разрезов не развивается, частично из-за нехватки точных алгоритмов для ограниченных классов, частично по причине трудности нахождения подходящей группы ребер.

4.2.2. Непересекающиеся разрезы

Использование набора проходов и разрезов с разъединенными ребрами до сих пор мотивировалось первоначально необходимостью вычислить вероятность того, что один набор проходов работает (как в лемме 4.1) или что один набор разрезов приводит к отказу (как в лемме 4.2). Разработан метод, который позволяет наборам разрезов иметь общие ребра, сохраняя эффективность вычисления вероятности того, что один из наборов разрезов приводит к отказу. Для графа G=(V,E) секция (А,В) из V образует набор разрезов, содержащий все ребра, имеющие один конец в А, а другой в В. Два таких набора разрезов (А,В) и () являются непересекающимися, если, по крайней мере, один из АÇВ, АÇ, ÇВ и является пустым. Коллекция разрезов является непересекающейся или ламинарной, если каждый из двух наборов в коллекции являются непересекающимися. В n-узловом графе с k терминалами набор непересекающихся разрезов содержит по большей части n-1+k-2 £ 2n-3 непересекающихся разрезов. Базис разрезов n-вершинного графа является набором из n-1 разреза С₁,…,С_n-1, для которых каждый разрез может быть записан как сумма по модулю 2 этих n-1 разрезов. Ломоносов и Полесски показали, что для любого базиса разрезов С₁,…,С_n-1 всетеринальное значение надежности удовлетворяет равенству

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

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

4.2.3. Преобразования и аппроксимация графов

Мы имели до сих пор два метода расширения стратегии группирования ребер: группирование не минимальных проходов или разрезов и смягченные требования разделения ребер. В этом подразделе мы рассматриваем третье расширение, которое является, может быть менее прямым, чем предыдущие два.

Мы видели, что преобразования могут быть использованы, чтобы “упростить” сеть и уменьшить время, необходимое для точных алгоритмов. Такие преобразования сохраняют значение меры надежности. Другие преобразования сети могут иметь свойство, гарантирующее, что мера надежности не увеличится. Эти D-преобразования сохраняют нижние границы меры надежности (то есть, вычисление нижней границы после использования такого преобразования выдает то же значение нижней границы надежности, что и до преобразования). Аналогично, I-преобразования гарантируют неуменьшение меры надежности, и, следовательно, сохранение верхней границы.

Тривиальное D-преобразование ликвидирует ребро или дугу сети; оно следует принципам когерентности и статической независимости, так что мера надежности не может увеличиться после такого удаления. Аналогично, операция расщепления узла х на два узла х₁ и х₂, и замещение каждого ребра {y,x} на {y,x₁} или {y,x₂} не может увеличить надежность. Эти тривиальные преобразования имеют заметные последствия. Было показано, что нижняя граница при группировании ребер для двухтерминальной надежности может быть получена с помощью использования лишь удаления ребер и расщепления узлов (удалить все ребра, которые не работают для обеспечения проходов в группе и расщепить нетерминальные узлы, соответствующим образом, чтобы было более одного прохода в группе). Результатом этих преобразований является параллельная комбинация s,t-путей - очень простой параллельно-последовательный граф. Верхняя граница при группировании ребер для двухтерминальной надежности аналогична использованию I-преобразования, которое идентифицирует два узла [H.M.F. AboElFotoh and C.J.Colbourn, “Series-parallel bounds for the two-terminal reliability problem”, ORSA J. Computing 1 (1989), 205-222]. Использование преобразований для получения двухтерминальных границ при группировании ребер позволяет “рано” остановить процесс преобразования. Раз сеть преобразована в последовательно-параллельную сеть, надежность может быть вычислена точно за полиномиальное время и в дальнейших преобразованиях нет необходимости.

Одним частным приложением преобразований является анализ блокирующих свойств “канальных графов”. Преобразования для канальных графов используются и в отношении s,t-связности.

Два преобразования, треугольник-звезда (delta-wye) и звезда-треугольник достойны отдельного упоминания. Дельта (или D) в сетях является набором из трех ребер {{x,y},{x,z},{y,z}}, образующих треугольник, а wye (или у) является набором из трех ребер {{x,w},{y,w},{z,w}}, для которого вершина w является входящей для перечисленных выше вершин. Преобразования треугольник-звезда и звезда-треугольник являются лишь заменой одной конфигурации на другую. В 1962 году Леманом были предложены два метода определения вероятностей для ребер звезды (треугольника) при заданных вероятностях ребер треугольника (звезды, соответственно). Его два метода не являются, вообще говоря, точными, он скорее показал, что одно из преобразований является I-преобразованием, а другое D-преобразованием в предположении, что центральный узел не является терминальным. Удивительно, но то, какое из этих преобразований является I-преобразованием, зависит от численного значения вероятностей. Таким образом, преобразования треугольник-звезда и звезда-треугольник представляются отличными от ранее упомянутых преобразований, так как здесь нет простой комбинаторной настройки преобразования.

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

4.2.4. Различные ограничения

Существует много других методик ограничений, которые были исследованы и которые не могут быть легко классифицированы как “группировка ребер” или как ограничения, базирующиеся на преобразованиях. Используя модель случайного графа, введенную Эрдёсом и Ренаем, Ломоносов [M.V.Lomonosov, “Bernoulli scheme with closure”, Problems of Information Transmission, 10 (1974), 73-81] рассмотрел процесс эволюции графа. Предположим, что в момент времени 0 каждое из ребер отсутствует, но имеет экспоненциально распределенную вероятность того, что оно появится в графе. Когда впервые граф станет связанным? Ломоносов установил эквивалентность между процессом эволюции графа и статической эволюцией всетерминальной надежности, путем рассмотрения ожидаемого времени, когда произойдет переход из состояния сети с l компонентами в состояние с l-1> компонентом (для l=n,…,2), он установил нижнюю границу всетерминальной надежности.

4.2.5. Постоптимизация ограничений

До сих пор мы обсуждали базовые стратегии получения ограничений. Даже конспективное описание каждого показывает, что существует огромное разнообразие доступных методов получения ограничений. Естественно попытаться объединить их для уточнения границ или получения более общих ограничений. Предпочтительным путем является нахождение общей теории, в которой число границ унифицировано. Потерпев неудачу в этом, можно пожелать получить какую-либо информацию о надежности, и это возможно с помощью разных рассмотренных методов. Например, если известна вероятность достижения u из s, и независимо известна также вероятность достижения t из u, что можно сказать о вероятности достижения t из s? Используя известную теорему Алсведе и Дайкина, Брехт и Кольбурн разработали методы для улучшения нижних границ. Они заметили, что если сеть G соединена с терминальным набором К₁, с вероятностью р₁, соединена с терминальным набором К₂ и с вероятностью р₂ и К₁ÇК₂¹0, то G соединена с терминальным набором К₁cК₂ с вероятностью, по крайней мере, р₁р₂. Это дает мультипликативный треугольник неравенств для границ двухтерминальной надежности, который Брехт и Кольбурн нашли эффективным для улучшения границ двухтерминальной надежности, которые были вычислены другими методами (в частности методом группирования ребер). Ключом здесь является постоптимизация, методика улучшения ограничений для произвольных границ.

В чем-то похожий метод для верхних границ, называемый ренормализацией, был изучен недавно. Для двухтерминальной надежности вероятность х_е того, что один терминал s не может связаться с другим терминалом t через специфицированное ребро е, ограничена сверху вероятностью того, что само ребро е не обеспечивает связь плюс вероятность того, что е работает с вероятностью, кратной вероятности х_f для каждого ребра f, соединенного с е. Двухтерминальные верхние границы могут быть использованы для определения исходных оценок вероятности х_е для каждого ребра е. Тогда каждое неравенство может привести к некоторому сокращению значения х_е. Ренормализация дает верхнюю границу при недооценке влияния пересечения s,t-маршрутов и при рассмотрении s,t-маршрутов, а не только s,t-проходов. Для s,t-связности ориентированных графов без циклов отсутствие ориентированных циклов гарантирует, что все s,t-маршруты являются s,t-проходами; в этом случае ренормализация является методом с полиномиальным временем, который гарантирует улучшение для верхнего ограничения. Ренормализация является существенно постоптимизационной стратегией, но может использоваться сама по себе, начиная с начальной переоценки вероятности отказа х_е для ребра е.

Одна стратегия окончательной постоптимизации была сформирована для применения, когда вероятности работоспособности всех ребер равны между собой. Кольбурн и Хармс заметили, что если произвести оценку полинома при фиксированном значении р, будет получена линейная комбинация F₀,…,F_d. Следовательно, если известна верхняя или нижняя граница значения надежности и она полиномиальна при специфицированном значении р, то мы получаем линейное ограничение. Таким образом, любой метод, применяемый к сети с ребрами, вероятности работоспособности которых равны между собой, выдает линейное ограничение этого вида. Все линейные неравенства, полученные так, удовлетворяются одновременно, и, следовательно, можно комбинировать ограничения разных видов, используя методы линейного программирования. Если все базовые используемые ограничения эффективно вычислимы, можно использовать алгоритмы с полиномиальным временем для линейного программирования, чтобы сохранить полное время вычислений в полиномиальных пределах.

5. Методы Монте-Карло

В связи с крайней сложностью точных вычислений различных характеристик надежности и невозможностью для полиномиальных алгоритмов выдать жесткие ограничения этих характеристик, необходимо обратиться к методикам моделирования с целью получения точных оценок. Это, конечно, имеет свою цену - полученные оценки имеют некоторый уровень неопределенности. Несмотря на это, данный недостаток обычно вполне оправдан благодаря тому, что моделирование позволяет получить лучшие результаты по сравнению с детерминистскими методами. Из-за относительно простой структуры этих проблем вполне естественно использовать для моделирования стохастического поведения системы мощные и хорошо исследованные методы Монте-Карло.

5.1. Наивная схема генерации событий

Мы сначала введем нотацию, которая будет использоваться в этом разделе. Пусть (Ф,p) конкретный пример проблемы надежности с вектором компонентов оперативных вероятностей р=(p₁, …, p_m). Пусть q =(q₁,…, q_m) = (1-p₁,…,1-p_m) является вектором 0 вероятностей, обозначим вероятность того, что реализуется конкретный вектор х, как Р(х)

Мы заинтересованы в получении оценки Ř для истинной надежности системы R=Pr[Ф=1].

Простой метод генерации событий достаточно прямолинеен. Набор из К векторов, , k=1,…,k формируется из распределения Р, путем получения mK независимых псевдослучайных событий Ǘ_kj, k=1,…, K, j=1,…,m от однородного генератора случайных чисел и последующей установки

k=1,…,K, j=1,…,m.

Пусть ‚ число векторов x^k, для которых Ф(x^k)=1. Тогда несмещенной оценкой для R является Ř=‚/K, а его вариация ограничена сверху R(1-R)/K. Уменьшение этой вариации может быть получено разнообразными методами генерации событий Монте-Карло, такими как антитетический способ, с управляемыми случайными величинами, а также с помощью условной, приоритетной и послойной выборки.

5.2. Генерация событий по методу даггера.

Метод генерации событий даггера был разработан Кумамото [K.Kumamoto et al “Dagger sampling Monte-Carlo for system unavailability evaluation”, IEEE Transaction Reliability, R-29 (1980)122-125] и может рассматриваться как “m-мерное” расширение антитетического способа. Идея, которая является общей для нескольких методик Монте-Карло, заключается в том, чтобы разбросать отдельные неудачи на краях так, что повторные испытания минимизируются. Процедура описана ниже.

Генерация событий по методу даггера (кинжала)

1. Пусть (N_e: eÎE) является вектором целых чисел, выбранных пропорционально (действительным) q_e.
2. Генерируем вектор события размером К*, так что для каждого ребра е последовательность К* репликаций может быть разделена на N_e субблоков размера К*/N_e.
3. Для каждого ребра е выбираем случайным образом репликацию в каждом из субблоков N_e, для того края, для которого испытание оказалось неудачным. В результате получается совокупность неудач для репликаций К*, для которых частота неудач на каждом из краев пропорциональна среднему значению частоты неудач данного края.
4. Делаем окончательный проход по репликациям К*, вычисляя усредненную долю репликаций, соответствующих работе системы. Это число является несмещенной оценкой R.

5.3. Последовательное построение/разрушение

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

Пространство событий для последовательного метода построения состоит из пары (x,p), где х - вектор состояния системы, а p = (p(1),…,p(m)) является перестановкой индексов ребер Е, такой, что для некоторого индекса k мы имеем:

x_p(1)=…=x _p(k) =1, x_p(k+1)=,…,x _p(m) =0.

Если вектор состояния х выбран согласно предписанным вероятностям состояния, а перестановки p выбраны независимо и однородно по отношению ко всем подходящим перестановкам, тогда вероятность реализации конкретной пары (x,p) равна

,

где k равно числу рабочих элементов в х. Метод последовательного конструирования испытывает перестановку и рассматривает одновременно набор P всех возможных пар состояний (x,p) p= и х, согласующимся с в рамках выше приведенных критериев. Значение надежности набора испытаний (sample) является условной вероятностью работы системы с учетом P, то есть, отношение суммы вероятностей пар (x,p) Î P_, для которого Ф(х)=1, к вероятности P. Подробности представлены ниже.

Метод последовательного конструирования

1. Выбираем образец перестановки =((1),…,(m)) из набора перестановок {1,…,m}. Определяем векторы x^(k), k=1,…,m как

2. Определяем первый индекс r=0,…,m, для которого Ф(x^(r))=1.

3. Вклад в оценочный параметр R тогда

4. Складываем набор значений и делим на число выбранных перестановок набора. Это является несмещенной оценкой R.

Оценка, полученная для каждой выбранной перестановки из набора, имеет меньшую вариацию, чем полученная для одного образца при наивном алгоритме. Наибольшие вычислительные усилия тратятся на этапе 2 и это сильно зависит оттого, как быстро можно обновить значение Ф(x^(k)), т.е. насколько легко можно определить функциональность системы по ребрам, восстановленным одно за другим. Заметим, однако, что восстановление ребер должно производиться только до тех пор, пока система не станет полностью функциональной (в предположении связности системы), так как дальнейшее восстановление ребер графа не изменит рабочего состояния системы. Таким образом, объем выполненной работы может быть много меньше чем порядок m. В случае надежности коннективности было показано, что определение индекса r может быть выполнено почти также легко, как определение Ф(х) для одного значения х, так что последовательные выборки будут получаться по той же цене, что одна выборка в наивном методе. Наконец, при равных вероятностях отказов для ребер мы получаем дополнительное преимущество того, что знаменатель в выражении для этапа 4 (см. выше) всегда равен 1, что сокращает объем вычислений.

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

5.4. Испытания с использованием ограничений

Это является мощным гибридом классических приоритетных испытаний и схем Монте-Карло с управляемыми случайными величинами. Метод может быть в принципе применен к любой задаче надежности, где системная функция Ф ассоциирована с нижней ограничивающей функцией связи Ф^L и верхней ограничивающей функцией Ф^U, имеющими следующие свойства

• Ф^L(х) £ Ф(х) £ Ф^U(х) для каждого вектора состояния х.
• Для k = 0,…,m и любых значений для первых k компонент х, значения

и

могут быть вычислены в рамках полиномиальной оценки.

Значения и являются безусловными вероятностями работоспособности для ограничивающих функций Ф^L и Ф^U и обычно могут быть вычислены с привлечением простых алгоритмов. Для метрик неориентированного графа, однако, значения и могут быть получены путем вычисления значений и для графа, где удалены все ребра e_k, для которых , и стягивания всех ребра e_k, для которых . Таким образом, вычисление этих величин является не более сложным, чем расчет безусловных вероятностей.

Значения и 1- представляют собой легко вычисляемые величины для случаев, когда структурная функция Ф имеет известные значения. Метод испытаний, базирующийся на ограничениях, выбирает события из остального пространства.

в пропорции к их вероятности для исходного пространства. Известная вероятность для пространства, где испытания не проводятся, т.е., где Ф^L(x)=1 или Ф^L(x)=0, учитывается при оценке надежности R для пространства испытаний Х. Полученный выигрыш находится в прямой пропорции к доле исходной вероятности, которая оставлена для испытаний в Х. Соответствующая схема Монте-Карло представлена ниже.

Метод испытаний, базирующийся на ограничениях

1. Берутся события из пространства испытаний Х путем последовательного розыгрыша для k=1,…,m компонент состояния с операционной вероятностью



2. Вычисляем пропорцию тех испытаний, для которых Ф(х)=1. Число теперь является несмещенной оценкой R.

Простой пример этой схемы использует тот факт, что для любого вектора состояния х, по крайней мере, r элементов должно работать, чтобы работала система и, по крайней мере, g элементов должно отказать, для того чтобы системы вышла из строя, где r равно минимальному числу путей для системы, а g минимальному числу разрезов (обрывов) для системы. Теперь мы определяем Ф^U(x) равным 1, когда, по крайней мере, r элементов из х работают, и 0 в противном случае, мы также определяем Ф^L(x) равным 0, когда, по крайней мере, g элементов х отказало, и 1 в противном случае. Вычисления R^L и R^U являются задачами определения надежности k-из-m, которые, как известно, имеют эффективные алгоритмы расчета вероятности, а пространство испытаний Х является пространством векторов состояния х, имеющих, по крайней мере r, но не больше чем m-g работающих элементов. Ограничения по числу проходов/разрезов, рассмотренные в 4.2.1, могут использоваться для получения эффективной схемы Монте-Карло, базирующейся на ограничениях. Здесь, если С₁,…,С_r являются отдельными разрезами, а Р₁,…,Р_s - отдельными проходами, тогда

Значения и могут быть вычислены, как в разделе 4.2.1 и это распространяется также на расчет и .

5.5. Метод покрытия

Точность схем Монте-Карло, представленных выше обычно оценивается по вариации оценки . Оценка вариации в каждом случае оказывается грубо равной a/K, где К - число проб, а a - некоторая константа, которая зависит от R и типа производимых испытаний. Таким образом, грубое аналитическое сравнение этих оценок может быть сделано на основе относительных значений a. Действительная величина вариации зависит от многих других факторов, и при линейном уменьшение К время испытаний может стать критическим. Таким образом, сравнения в действительности следует делать на эмпирической основе.

Метод покрытия разработан Карпом и Луби [R.M.Karp, M.Luby “Monte Carlo algorithms for the planar multiterminal network reliability problems”, J. Complexity 1 (1985), 45-64] и базируется на более жестком критерии, требующем большей эффективности от схемы Монте-Карло. В частности, пусть e и d являются положительными скалярами. Предположим, что мы хотим вычислить некоторую относительную меру значения R, и пусть является результатом оценки R некоторой схемы Монте-Карло. Тогда оценка является e-d аппроксимацией для R, если

Схема Монте-Карло называется полной полиномиальной рэндомизованной аппроксимацией FPRAS, если, кроме того, время получения оценки имеет порядок e^-1, log(d^-1). Грубо говоря, FPRAS является алгоритмом, который эффективно осуществляет оценку R, чья относительная ошибка с высокой вероятностью может быть гарантировано малой.

Схема Монте-Карло Карпа-Луби является в действительности гибридом методов приоритетных и послойных выборок, и использует миниразрезы системы для улучшения наивной схемы выборок. Чтобы сохранить совместимость со статьей Карпа-Луби, мы рассматриваем вычисление R=Pr[Ф=0], т.е., вероятность отказа системы, если даже можно разработать аналогичную схему с точки зрения работы системы. Идея встроить набор F событий отказов в универсальное взвешенное пространство (U,w) - где w является неотрицательной весовой функцией для элементов U, которые удовлетворяют следующим критериям:

• w(F)=Pr(F) = R
• w(U) эффективно вычисляемо (т.е. за полиномиальное время), выборка событий может быть эффективно осуществлена из U с вероятностью, пропорциональной их весу.
• Можно эффективно распознать, когда элемент из U принадлежит также и F.
• w(U)/w(F) ограничено сверху некоторой величиной М для всех случаев класса задач

Тогда ясно, что если осуществлена выборка из U и определена оценка путем умножения доли этой выборки, которая содержится в F, на w(U), тогда является несмещенной оценкой R. Установлено, что для любых положительных скаляров e e и d, если размер выборки равен, по крайней мере, M´ln(2/d)4.5/e², тогда результирующая оценка является e-d аппроксимацией для R. Другими словами, эта схема выборки является FPRAS.

Теперь рассмотрим метод покрытия с точки зрения его использования для проблемы надежности (s,t)-связности, хотя та же методика может быть применена для широкого круга ситуаций. Пусть (G,s,t,p) является примером проблемы надежности (s,t)-связности и пусть С является минимальным набором (s,t)-разрезов для G. Определяем универсальное взвешенное пространство U, которое состоит из пар (х,С), где х - вектор состояния, СÎ С, и х_е=0 для всех e ÎC. Вес, приписываемый каждой паре (х,С) просто равен Р(х). Теперь каждое состояние отказа х системы отражается в элементах U столько раз, сколько требуется мини разрезов для отказа х. Для того чтобы F входило в U, необходимо приписать каждому х уникальное СÎС. В проблеме (s,t)-связности это сделано с помощью нахождения набора элементов, которые могут быть достижимы от s через рабочие ребра (с учетом х) и установки СºС(х), соответствующих ребрам их Х в V\X. Элементы F теперь появляются в U, >как (х,С), такие что С=С(х), а элементы U могут быть определены на долгое время соответствующими элементу F путем проверки условия С=С(х). Метод покрытия для задачи (s,t)-связности рассмотрен ниже.

Метод покрытия

1. Определяем множество С набора (s,t)-разрезов G. Для каждого СÎ С вычисляем w(C)=П_{eÎ С}q_e = полному весу всех элементов U со второй компонентой, равной С, и затем вычисляем w(U) =3_{СÎ С}w(C).
2. Осуществляем выборку элементов (x,C) из U в пропорции их весов при первом розыгрыше С из С с вероятностью w(C)/w(U) и затем производим розыгрыш х путем установки х_е=0, eÎС, и приписав другим компонентам х значения согласно их вероятностям.
3. Вычисляем долю , когда событие (х,С) имеет С=С(х). Тогда (U) является несмещенной оценкой R.

Рассмотренная выше схема не является FPRAS по двум причинам. Во-первых, необходимо нумеровать все разрезы в наборе С и мощность набора растет экспоненциально с ростом объема задачи. Во-вторых, условие ограничения для w(U)/w(F) не удовлетворяется для общих случаев задачи. Карп и Луби однако, модифицировали процедуру, описанную выше, для случая задач надежности (s,t)-связности, где граф G является плоским и однонаправленным и ограничения сопряжены с множественностью и суммарной вероятностью, а также выполняется условие ограничения сверху П_{eÎ С}(1+q_e) некоторым фиксированным М.

Мы здесь не вдаемся в детали, главная идея заключается в расширении С, чтобы включить разрезы, которые являются “почти минимальными”, таким образом, чтобы ассоциированное пространство U, определенное выше, удовлетворяло требуемым свойствам с учетом F. Плоскость G используется, чтобы разрешить эффективную выборку элементов расширенного пространства U с правильными вероятностями, так чтобы модифицированная схема для задач надежности (s,t)-связности стала FPRAS.

5.6. Оценка коэффициентов полиномов надежности

Одной из проблем, связанных с методами, которые рассматривались до сих пор, является то, что они только оценивают надежность для одиночного вектора вероятностей p. Больший интерес часто представляет оценка функциональной формы полинома вероятности. Это становится особенно важно, когда вероятности отказа связей (ребер) все равны р, так что надежность системы может быть записана как это представлено в разделе 2 - в одной из двух полиномиальных форм:

В этом случае более полезной схемой Монте-Карло была бы та, которая оценивает каждый коэффициент F_i или H_i, тогда эти оценки можно было бы использовать для получения значения надежности для любой заданной величины p.

Нел и Кольбурн исследовали проблему надежности всех терминалов и предлагают схему для оценки коэффициентов H_i для данной задачи. Так как сумма коэффициентов H_i равна числу деревьев в графе G, в противоположность числу подключенных наборов G, которое равно сумме коэффициентов F_i, тогда число состояний, дающих вклад в оценки коэффициентов H_i, много меньше того, которое нужно разыграть для оценки коэффициентов F_i. Сошлемся на раздел 4.1.5 и предположим, что U={[L_i,U_i]| i=1,….b} является какой-то оболочкой F-комплекса G. Из определения H_i, как мощности i L_j, следует, что для любой однородной выборки интервалов [L_j,U_j] в U, пропорция L_j мощности i является несмещенной оценкой H_i. Нел и Кольбурн развили этот подход, чтобы получить методику для однородной выборки из множества интервалов канонической оболочки F-комплекса G, базирующейся на однородной выборке деревьев связи в G.

Описание функции надежности, когда имеются отказы в соединениях, является проблематичным, так как сама полиномиальная форма имеет экспоненциально большое число членов. Предположим, что нам нужно знать надежность R, как функцию вероятностей работоспособности p₁,…,p_k выбранного набора из k ребер графа e₁,…,e_k, при заданных конкретных вероятностях работоспособности для остальных ребер e_k+1,…,e_m. Теперь мы вычисляем “коэффициенты” частичного описания надежности, реализуя вариант послойных испытаний (или условных испытаний, в зависимости от точки зрения). Процедура выглядит следующим образом: для каждого вектора состояния для ребер e₁,…,e_k, производим выборку слоя состояний, где ребра i=1,…,k и остальные ребра работают согласно их заданным вероятностям. Мы после этого вычисляем оценку для ассоциированной надежности. Когда связи функционируют независимо, послойная выборка достаточно проста, но могут достаточно часто использоваться другие способы улучшения, описанные ранее в данном разделе. Оценка для требуемой функциональной формы для R может быть теперь записана в виде

Поскольку это описательная величина, данная функциональная форма полезна при измерении “критичности” связей, для которых определена функция, при проверке производного влияния на функцию изменений определенных компонент надежности. Хотя мерам критичности уделяется большое внимание в теории надежности, эта сторона выходит за пределы рассмотрения этой главы. Из нашего обсуждения следует, что методы Монте-Карло разрабатывались и использовались независимо от разработки ограничений, однако мы подчеркнем, что ограничения и подходы Монте-Карло более эффективны, когда используются совместно.

6. Анализ работоспособности, стохастические потоки и длины путей

Предыдущие четыре главы касались мер связности. В контексте коммуникационных сетей базовым предположением для этих мер является то, что до тех пор, пока между двумя узлами имеется соединение, они беспрепятственно могут обмениваться данными. Во многих практических постановках задач это совсем не так. В частности, такие параметры как задержка, длина пути, полоса пропускания и прочее может иметь жизненную важность: сеть не просто должна быть связанной, она должна обеспечивать определенный уровень функциональности. Эта точка зрения ведет к разработке мер работоспособности. Чтобы изучать такие меры, нужна дополнительная информация, такая как длины, пропускные способности каналов, сопряженные с компонентами сети. Кроме того, возможно, что должна быть представлена информация, характеризующая загрузку сети, например, набор требований к трафику между определенными узлами сети. Вообще, объявление ценности такой информации изменяет природу проблемы надежности от вероятностной характеристики состояний типа “исправен/сломан” к оценке, включающей в себя множественные состояния системы и ее компонент. Во многих случаях это просто приводит к более комплексному варианту проблемы двух состояний, но это также включает задачи определения усредненного поведения и/или к введению “непрерывных” состояний и системных переменных, которые требуют существенно других методик решения. Мы обращаемся с этим более общим типом проблемы надежности, как с проблемой многих состояний и намерены ввести меры работоспособности, а также некоторые другие меры (метрики).

Общий формат для проблем сетей со многими состояниями рассматривается в данной статье следующим образом:

У нас есть сеть G=(V,E) с набором случайных переменных {X_e: eÎE}, сопряженных со связями (ребрами) этой сети. Значение, присваиваемое случайной переменной ребра, представляет собой параметр, такой как длина пути, пропускная способность или задержка. В большей части данного раздела мы будем предполагать, что каждая случайная переменная связи может принимать q дискретных значений. Во многих ситуациях случай, когда q=2 (система с двумя состояниями) представляет вполне реалистическую модель. Здесь является обычным называть состояния “плохим” и “хорошим”. В случае “хорошего” состояния связь работает со специфицированной пропускной способностью, длиной и т.д., а в случае “плохого” состояния - канал не работает, имеет нулевую пропускную способность, бесконечную длину и пр. (Случайные величины могут также быть приписаны вершинам графа сети, чтобы охарактеризовать требования в пропускной способности или задержке в узле сети. Мы не касаемся здесь этих моделей, за исключением упоминания того, что они часто моделируются как проблемы со стохастическими параметрами связей). Соответствие вектора случайным переменным связи самой системы задается значением , которое представляет собой некоторую метрику работоспособности системы. Таким образом, значение состояния системы характеризуется случайной переменной, чье распределение является комплексной функцией распределения значений индивидуальных параметров. Целью проблемы оценки систем со многими состояниями является вычисление или оценка некоторых характеристик случайной переменной, описывающей состояние системы. Это может подразумевать полное описание распределения состояния системы, вероятность того, что достигнут определенный порог работоспособности системы, а также среднее, вариацию или выбранные моменты распределения состояния системы.

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

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

6.1. Метод наиболее вероятных состояний

Метод наиболее вероятных состояний является ограничивающей процедурой, которая может быть применена к достаточно общему классу многопараметрических проблем. Единственным требованием является эффективное вычисление Ф. Мы описываем его применение к метрике работоспособности Pr[Ф£a]. Приложение к E[Ф] осуществляется аналогично. Предположим, что состояния сети упорядочены , где s = qⁿ, такое что Метод наиболее вероятных состояний базируется на нумерации состояний в этом порядке. Важность использования этого порядка заключается в том, что процесс может быть завершен раньше с хорошим ограничением. Определим lp_Ф(k) и up_Ф(k) как нижнее и верхнее ограничение, для . Верхнее и нижнее ограничения обычно используются здесь, как легко вычислимые, и, фактически, в большинстве случаев являются тривиальными границами, которые не зависят от k. Для систем с двумя состояниями, если p_e равно вероятности “хорошего” состояния для ребра е, а q_e - вероятности “плохого” состояния для ребра е, типичным предположением служит то, что p_e ≥ q_e и как следствие , так что мы можем установить и для всех k. Ограничения для наиболее вероятных состояний определяются как

Здесь может определяться динамически на основе некоторого критерия остановки. Наиболее типичным критерием является требование того, чтобы разность между верхним и нижним ограничениями лежала в допустимых пределах. Нижнее и верхнее ограничение для ожидаемого значения метрики могут быть определены аналогичным образом.

Сансо и Саумис предположили, что вместо нумерации по наиболее вероятным состояниям, много лучше осуществлять нумерацию по “наиболее важным” состояниям. Аргументация заключается в том, что в некоторых ситуациях определенные мало вероятные состояния, которые могут быть не пронумерованы, оказывают большое влияние на метрику работоспособности системы. Такие состояния могут соответствовать ситуациям, в которых система демонстрирует крайне плохую работоспособность. В частности, может быть относительно мала, но может быть очень велико или очень мало. Это особенно важно при вычислении ограничений Е[Ф].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Работоспособность сети PERT: Если обрыв связи соответствует T_e=0, а рабочее состояние связи соответствует T_e=1 и каждый путь в G имеет идентичную длину n, тогда Rel₂(G,s,t,p)=Pr[Ф_PERT=n].

Отсюда следует, что эти проблемы являются #P-полными для любого класса графа, для которого ассоциированная проблема надежности (s,t)-связности является #P-полной. (сюда входят и проблемы, которые удовлетворяют дополнительным требованиям соответствия PERT). Аналогичные рассуждения показывают, что вычисление E[Ф] является также #P-полным для этих классов графов.

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

• свертка двух независимых случайных переменных Х₁ и Х₂, т.е. распределение их суммы Х₁ + Х_2;
• (min) двух независимых случайных переменных Х₁ и Х₂, т.е. распределение max(Х₁,Х₂) или min(Х₁,Х₂).

Класс распределений связей для проблем сетей с большим числом состояний должен критически удовлетворять одному или более из следующих трех критериев, в зависимости от типа выполняемого анализа:

1. Вычисление данного значения интегральной функции распределения cdf (cumulative distribution function) элемента в фиксированном классе должно допускать расчет за полиномиальное время с нужным числом значащих цифр при заданной точности входного описания распределения.
2. Заданный набор распределений в классе и последовательность k операций min/max/свертки, выполняемых на основе этих распределений, распределение, полученное в результате последовательности операций должно принадлежать этому же классу, и далее, должно быть можно за полиномиальное время найти описание результирующих распределений при фиксированных исходных распределениях.

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

Обычно предполагается, что случайные величины имеют дискретное распределение, то есть, могут иметь конечное число значений. Хотя вычисление одной свертки или распределения min/max является элементарным, вычисление распределения для серии k таких операций считается #P-полным, даже если каждая исходная переменная имеет только два значения. Что необходимо, чтобы гарантировать эффективное вычисление свертки и min/max распределения, так это то, чтобы случайные переменные принимали последовательные значения {1, 2,…, x_q} (или в более общем случае последовательные значения, кратные некоторому общему знаменателю) для всех ребер графа, для некоторого фиксированного q.

Существует два класса распределений с бесконечным числом состояний, которые относятся к наиболее известным и удовлетворяют сформулированным выше требованиям (1-3). Первое является дискретным и может быть описано как смесь геометрических распределений, имеющих форму pdf(probability distribution function)

x=0,1,…

для 0 < p < 1 и при соответствующем выборе значений a_ij. Существует также класс непрерывных распределений, которые имеют нужные свойства. Эти распределения могут быть описаны как “смесь Эрланговых” распределений (известных также как Coxian-распределения). Они являются аналогом “смеси геометрических” распределений, описанных выше. Они имеют форму cdf (cumulative distribution function):

0 £ t < ¥

при соответствующем выборе a_ij.

Дадим краткое описание методик основных оценок и ограничений для сетей с большим числом состояний. В большинстве случаев оказывается, что одна и та же техника используется для двух или более упомянутых выше проблем. Большинство методик имеют варианты для двоичных версий, которые представлены в разделах 3 и 4. Таким образом, мы организовали обсуждения методики, а не предмета, и следуем, когда возможно, формату для двоичной версии проблемы. Для большей части обсуждения мы концентрируемся на расчете Pr[Ф³a] для конкретного системного значения функции Ф и специфической величины a.

6.3. Преобразования и сокращения

Одним из “сокращений” популярных в задачах с большим числом состояний, которые не имеют аналогов в бинарных проблемах, является преобразование задачи с большим числом состояний в проблему, в которой каждое ребро с состоянием “отказ” удаляется из сети, а “работающая” связь имеет длину, пропускную способность и время завершения. Хотя это вообще не дает улучшения в сложности ассоциированного алгоритма вычисления надежности, эта техника позволяет концептуально облегчить использование факторизации и других методов нумерации. В частности, если случайная переменная связи X_e берется из ряда x₁ £ x₂<…< x_q с Pr[X_e=x_i]= p_i, i=1,…,q, тогда связь е может быть замещена посредством

Кратчайшего пути: q параллельных путей, i-ая связь имеет длину x_i и вероятность работоспособности p_i(1-

Максимального потока: q последовательных связей, i-ая связь имеет пропускную способность x_i и вероятность работоспособности p_i(1-

Сети с работоспособностью PERT: q параллельных путей, i-ая связь имеет время завершения операции x_i и вероятность работоспособности p_i(1-

Удаление неподходящих связей, рассмотренное в 3.1, применимо также и к трем проблемам, упомянутым выше, так как состояние связи, которое не лежит на минимальном (s,t)-пути не влияет ни на длину пути, ни на поток, ни на время выполнение операции. Обязательные ребра графа могут быть аналогично связаны с проблемой максимального потока. В частности, если обязательное ребро е подключено к мгновенному графу G, когда вычисляется Pr[Ф_FLOW≥ a], тогда мультипликативный фактор, применяемый к проблеме для подключенного графа G·e, равен Pr[С_е≥ a]. В случае проблем наикратчайшего пути или PERT обязательные связи не могут быть немедленно присоединены, так как параметры этих ребер графа повлияют на длину кратчайшего и самого длинного пути исходного графа. Они, в действительности, вводят три односвязные субсети и, следовательно, могут обрабатываться, как это описано в разделе 6.3.

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

Кратчайший путь: Для последовательного сокращения L_g является сверткой L_e и L_f. Для параллельного сокращения L_g является минимумом L_e и L_f

Максимальный поток: Для последовательного сокращения С_g является минимумом С_e и С_f. Для параллельного сокращения С_g является сверткой С_e и С_f.

Работоспособность сети PERT: Для последовательного сокращения Т_g является сверткой Т_e и Т_f. Для параллельного сокращения Т_g является максимумом Т_e и Т_f.

Во-первых, предположим, что Н является односвязной субсетью графа G c r подключенными точками, и пусть Ф^Н и являются системными оценочными функциями для соответствующей проблемы, где субсети Н и G\Н содержат терминалы s,v и v и t, соответственно. Тогда системная оценочная функция Ф^G удовлетворяет следующим условиям

Кратчайший путь и работоспособность сети PERT: Ф^G является сверткой Ф^Н и .

Максимальный поток: Ф^G является минимумом Ф^Н и .

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

6.4. Эффективные алгоритмы для ограниченных классов

Вычисление Ф для последовательно-параллельных графов может быть выполнено тем же способом, каким это делается для задачи (s,t)-связности с последовательным и параллельным сокращениями, выполненными как это описано выше. Сложность равна O(Rn), где R является сложностью наихудшего варианта выполнения операции свертки или определения min/max в любой момент реализации алгоритма. Таким образом, сложность этих алгоритмов критически зависит от времени выполнения последовательных и параллельных операций. Для трех типов распределений, представленных в начале данного раздела, R является линейным в nq (в конечном случае) или nqr (в двух бесконечных случаях). Обычно считается, что существуют полиномиальные алгоритмы и для графов с ограниченной шириной дерева (смотри раздел 3.2) хотя это специально и не рассматривалось.

6.5. Методы, базирующиеся на состояниях

Нумерационные методы для вычисления надежности систем с большим числом состояний обязательно ограничены кругом проблем с конечным числом состояний для каждой из связей. В частности, пусть каждое ребро e_j имеет ассоциированный параметр X_j из ряда значений 1, 2,…,q, с вероятностями p_ij=Pr[X_j = x_j], x_j =1,…,q, и пусть функция оценки системы Ф принимает значения из ряда 1,…,К. Тогда две классические, стохастические величины, а именно, cdf для Ф, вычисленная при заданном уровне a Î{1,…,К} и среднее значение Ф могут быть записаны как

Ф(x₁,…,x_n) £α

число членов в приведенных двух выражениях может иметь порядок q^|E|, и, следовательно, эти проблемы становятся трудноразрешимыми в существенно меньшем масштабе, чем даже в случае расчета надежности для систем с двумя состояниями.

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

(2)

Методика базируется на простом наблюдении, что в любом нециклическом графе без параллельных ребер всегда может быть осуществлена редукция, по крайней мере, одного узла, скажем путем подключения ребра е, один из концов которого v имеет только е в качестве входного (выходного) ребра. Пусть е₁,…, е_k являются другими концами по отношению к вершине v. Тогда система G_e,x, заданная выше, является просто G×e с переменными, ассоциированными с е₁,…, е_k, модифицированными следующим образом

Кратчайший путь: L_ei является смещенным на х, т.е.

Максимальный поток: С_ei ограничивается сверху величиной х, т.е. , i=1,…, k.

Работоспособность сети PERT: T_ei также смещается на величину х, i=1,…,k.

Распределения этих модифицированных случайных переменных легко вычисляются для распределений конечных состояний, например, путем обработки их как сверток или максимумов, имеющих одну случайную переменную с одним значением. Таким образом, уравнение (2) сводит конкретную проблему сети G к k субпроблем, где k равно числу значений, характеризующих дугу е, для одной и той же сети G×e, но с разными распределениями для ребер е₁,…, е_k. Сложность вычисления значения или среднего cdf в этом случае критически зависит от числа таких редукций узлов, которые должны быть произведены, в комбинации с выполнением возможных последовательных и параллельных сокращений, для того чтобы уменьшить сеть до одного ребра. Бейн и др. выдали алгоритм О(n³) для определения минимального числа редукций узлов, которые должны быть выполнены, для того чтобы сократить граф выше описанным образом. Это число, следовательно, в некотором смысле также представляет “сложность” сети с точки зрения проблем пути и потока.

Методики нумерации, предложенные выше, мало используются в решении проблем, сопряженных с бесконечным числом или непрерывным рядом случайных переменных ребер. Когда случайные переменные ребер имеют экспоненциальное распределение, Кулькарни и др. предложили интересные процедуры для решения проблем наикратчайшего пути, максимального потока для плоских сетей и проблем PERT. Мы показываем, что для проблем наикратчайшего пути, максимального потока и PERT имеются аналогичные, хотя более сложные методики решения. Мы рассматриваем команду “бегунов”, которые стартуют в узле отправления s и далее двигаются по ребрам, исходящим из s. Спустя некоторое время при известном (гамма) распределении, один из бегунов достигает конца своего ребра. В этой точке бегун останавливается, и новые бегуны устремляются вдоль ребер, исходящих из данной вершины. (Бегуны не посылаются бежать по ребрам, откуда прибыл бегун предыдущего этапа). Благодаря экспоненциальному распределению (отсутствие памяти) для времен пробега, следует, что в точке, откуда стартуют бегуны, они начинают новый этап одновременно. Короче говоря, процесс путешествия бегунов по сети является цепью Маркова с непрерывным временем. Состояние этой цепи Маркова соответствует возможному набору вершин, которые бегуны посетили и набору ребер, по которым они движутся в данный момент, а состояния поглощения соответствуют тем, что помечены t в качестве вершины адресата. Среднее время для вероятности поглощения этой цепи Маркова в точности равно длине наикратчайшего пути. Вероятность состояния поглощения может быть вычислена легко путем соответствующего упорядочения состояний цепи Маркова. Хотя время вычисления является линейным по отношению к числу состояний цепи Маркова, это число растет экспоненциально с ростом размера сети. Для сетей порядка 15-20 дуг, этот метод вполне эффективен при нахождении соответствующих решений.

6.6. Методики ограничений

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

Исторически первой использовалась методика для аппроксимации надежности в стохастических сетях и среди них одна, которой уделялось наибольшее внимание, возникает из интуитивно привлекательной идеи, что ожидаемое значение E[Ф] длины кратчайшего пути/максимального потока/времени завершения может быть получено путем замены случайной длины/максимального потока/времени завершения для каждого ребра на детерминистский параметр, чье значение равно ожидаемой величине, и последующего решения детерминистского варианта проблемы. Это было фактически методикой решения, предложенной в оригинальном рассмотрении PERT в работе Малькольма и др. [D.G.Malcolm et al, “Application of a technique for research and development program evaluation”, Oper. Res. 7 (1959), 646-669]. Кажется фольклором то, что значение, полученное с помощью этой методики является верхней границей истинного значения ЕФ в проблеме PERT и нижней границей в проблемах наикратчайшего пути и максимального потока.

Наиболее успешные исследования концентрируются вокруг аппроксимации значения cdf F(a) =Pr[Ф£a] для Ф. Методика вначале была применена к проблеме PERT с непрерывными значениями параметров ребер, но может быть модифицирована для применения к проблемам кратчайшего пути, наибольшего потока и для случайных переменных ребра с дискретным распределением. В частности, предположим, что нужно вычислить число a, для которого F_PERT(a)=b для некоторой специфицированной вероятности b. Заменяем каждую случайную переменную ребра Т_е на t_e, для которого Pr[T_e£ t_e]= b, и решаем для детерминистского значения наикратчайшего времени завершения. Полученная величина снова является верхней границей действительного времени завершения проекта, выдавая cdf значения b.

Улучшения выше описанной схемы для проблемы PERT заключается в вычислении для каждой вершины v в графе распределения для промежуточных случайных переменных

Ф_v= наидлиннейший маршрут до вершины v.

Во всех случаях вычисления производятся в топологическом порядке v₁= s,v₂,…,v_n, т.е. все ребра, указывающие на v_i исходят из вершин v_j с j<i. Данная схема служит для вычисления нижней границы для E[Ф_vi], используя достаточно простую рекурсивную формулу

j = 2,…,n

суммирование производится по всем векторам b= ( b_ji: j<I) значений параметра, которые могут быть приняты для ребер, указывающих на вершину v_i (члены, где (v_j,v_i) не существуют, игнорируются). Улучшения этой методики первоначально включали в себя оценки cdf значений F_i(a) для Ф_vi, в частности, вычисление верхней и нижней границы и , соответственно. Заметим, что эти величины могут использоваться по очереди, чтобы вычислить нижнюю и верхнюю границы, соответственно для значений E(Ф_vi), используя элементарную формулу

Все они используют одну и ту же формулу с для всех неотрицательных a (и нуль в противном случае).

Соответствующие ограничения для Е[Ф_vi] могут быть также упорядочены и их нижние ограничения лучше, чем полученные Фулкерсоном, нижние ограничения Фулкерсона и Кляйндорфера не могут быть единообразно сравнены. Ограничения Фулкерсона, Кляйндорфера и Шогана могут быть также модифицированы при использовании для проблемы кратчайшего пути (если исходный граф не содержит циклов) и для случая непрерывных параметров ребра. Ограничения Кляйндорфера априори вычисляемы за полиномиальное время.

Здесь мы предполагаем, что случайное значение пропускной способности С_е является двоичным с ”рабочим” состоянием, представляющим нормальную пропускную способность с_е с вероятностью р_е, и состоянием отказа, представляющим пропускную способность нуль с вероятностью 1-р_е. Пусть Г₁,…,Г_r является набором всех цепочек (s,t) в G и пусть h₁,…,h_r равны потоку для каждого r цепочки (s,t). Этот значение потока верно, если для каждого ребра е в G, сумма потоков цепочки последовательных ребер, проходящих через е, меньше чем или равна пропускной способности е, а величина потока равна . Рассмотрим любую фиксированную цепочку потоков h₁,…,h_r, которая корректна для нормального набора пропускных способностей (с_е: eÎE). В стохастической модели конкретная цепочка Г_k может, следовательно, дать запрошенную долю потока h_k, если и только если все ее ребра находятся в рабочем состоянии, в противном случае выдается нуль. Крайняя вероятность реализации этого равна, следовательно, . Во-первых, заметим, что значение Е[Ф_FLOW] очевидно, по крайней мере, также велико, как ожидаемое значение случайного потока, полученного путем допущения потока вдоль каждой цепочки Г_k, равного h_k, несмотря на рабочие условия других цепочек, использующих те же ребра, что и Г_k. Это ожидание в свою очередь равно сумме ожидаемых значений потоков для каждой из цепочек Г₁,…,Г_r, рассматриваемых как независимые случайные переменные.

Метод группировки ребер и непересекающихся разрезов, обсужденные в разделах 4.2.1 и 4.2.2, предоставляют также эффективный способ расчета ограничений для проблем сетей с большим числом состояний. В частности, пусть Р₁,…,Р_q и Г₁,…,Г_r являются наборами разъединенных (s,t)-маршрутов и (s,t)-разрезов, соответственно. Эти два набора дают естественные верхние и нижние границы функций Ф^L и Ф^U для действительной функции Ф, зависящей от проблемы:

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

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

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

Эти функциональные ограничения в свою очередь дают естественные границы как для cdf, так и для действительной функции Ф, в частности,

и

Далее, каждая функция, описанная выше, состоит из одного min/max и одной свертки, поэтому cdf и ожидания для всех этих функций могут быть вычислены за полиномиальное время.

Две разные методики ограничений, представленные в разделе 4.2.4, были изучены в контексте проблем для систем со многими состояниями.

6.7. Методы Монте-Карло

Проблемы с большим числом состояний и, в частности, проблемы PERT, всегда были первейшими кандидатами для методов Монте-Карло. Как в случае детерминистских схем многие схемы Монте-Карло, представленные в разделе 5, могут быть адаптированы для задач с большим числом состояний. Ради краткости мы коснемся только главных схем моделирования по методу Монте-Карло.

Схемы Монте-Карло для проблем с большим числом состояний имеют дело почти исключительно с проблемой PERT. В частности, предположим, что нужна оценка для, скажем, среднего значения выборки Е[Ф]. Пусть F_e(a)=Pr[X_e£a] для каждого ребра е является cdf для переменной Х_е. Значение выборки для этой случайной переменной получено с помощью выборки от однородного генератора случайных чисел и установки (или х_е = min{x|F_e(x)³U_e} для дискретных распределений). После того как сформирован весь вектор состояния , с помощью определенного детерминистского алгоритма вычисляется . Среднее по всем системным значениям выборки равно несмещенной оценке Е[Ф].

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

К сожалению, в разумно сложных графах все или почти все дуги будут являться общими и таким образом, это не приведет к существенному улучшению при моделировании. Некоторые авторы предлагают использовать при условных выборках однородно ориентированные (s,t)-разрезы. Однородно ориентированные (s,t)-разрезы являются набором ребер, для которых каждый (s,t)-путь в G пересекается с С только на одном ребре. Важность кондиционирования ребер однородно ориентированных (s,t)-разрезов заключается в том, что это допускает возможность независимого анализа активности (s,t)-маршрутов для каждой из сторон разрезов. Кроме того, каждый граф всегда содержит, по крайней мере, один однородно ориентированный (s,t)-разрез.

Большинство методик Монте-Карло, представленных выше, используется также для проблем наикратчайшего пути и, в общем, не требуют того, чтобы базовый граф не имел циклических структур, как это имеет место во многих методиках ограничения для проблем PERT. Как было показано выше, пусть для еÎЕ параметр ребра X_e имеет cdf F_e(x). Предположим, что вы имеете функциональные ограничения Ф^L и Ф^U для мультивариантной меры Ф, удовлетворяющей условиям

• Ф^L(x) £ Ф(х) £ Ф^U(x) для каждого вектора состояния х

• Для любого присвоения величинам первой компоненты х при k=0,…,m, условная cdf имеет вид

и

может быть вычислено за полиномиальное время. Пространство Х важности в мультивариантной версии проблемы равно теперь

X={xÎ{0,1}^E:Ф^L(x)£ a, Ф>^U(x)>a}

а модификация метода розыгрыша, базирующегося на ограничениях, представленная в разделе 5.1 приобретает вид

1. Разыгрывается событие из пространства Х путем последовательного розыгрыша для k=1,…,m компонент состояния из cdf

2. Вычисляется доля тех выборок, для которых Ф(х) £ a. Число равно теперь несмещенной оценке R.

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

7. Использование вычислительных методик на практике

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

7.1. На что нужна надежность?

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

• Минимизируем стоимость объекта с учетом:

• ограничений пропускной способности
• ограничений эксплуатационных характеристик
• ограничений надежности.

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

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

1. Компоненты сети сами по себе являются высоко надежными.
2. Случайные отказы сети не являются разрушительными.
3. Сети были спроектированы на основе других (не надежностных) критериев, которые достаточно часты и обеспечивают высокую надежность (это может случиться, если полоса канала мала по сравнению с требующейся пропускной способностью).

Аналогичный набор заявлений может быть сделан в отношении критериев работоспособности и пропускной способности. С другой стороны, если полоса сетевых каналов достаточно высока, при проектировании возникает тенденция к созданию распределенных схем, так что явные ограничения на надежность становятся необходимы.

7.2. Выбор метрики

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

1. Важность и природа критерия работоспособности.
2. Сообщество обслуживаемых пользователей.
3. Философия обслуживания: хорошее качество в среднем или хорошее качество в экстремальных режимах.

Фундаментальным решением является, следует ли использовать меру связности или меру работоспособности. Меры связности включают все версии k-терминальных метрик, а также определенные относительные метрики, такие как сетевая адаптивность, ожидаемая доля пар узлов, участвующих в обмене одновременно. Меры работоспособности явно отражают модель вариации рабочих характеристик при сетевых отказах. Мера связности может быть полезной, когда функционирование сети считается удовлетворительным, если обеспечивается ее связность. Это так для многих оптоволоконных сетей. Мера связности полезна также при измерении вероятности того, что сеть способна обеспечить некоторый минимальный уровень обслуживания, т.е. вероятность того, что сеть может обработать важные вызовы или аварийные сигналы. Исследования мер работоспособности мотивировалось тем, что существуют сети, где при отказе какого-то компонента уровень функционирования сети падает ниже приемлемого уровня, хотя сеть и остается связной. В таких случаях использование меры работоспособности является обязательным.

Выбор одного из двух терминалов, k-терминалов или всех терминалов зависит от сообщества заинтересованных пользователей. Двухтерминальная метрика определяет способность сети обеспечить коммуникацию для двух специфицированных терминалов пользователей. Таким образом, метрика может рассматриваться как метрика, специфическая для пользователя. С другой стороны всетерминальная метрика характеризует возможности сервис провайдера. Она описывает работоспособность системы по отношению к возможности предоставить услуги всем возможным терминальным парам. Следует заметить, что в определенном смысле всетерминальная мера надежности весьма “консервативна”. В частности, всетерминальная метрика меньше чем самая малая мера для двух терминалов и вообще должна быть много меньше.

Другой всесистемной мерой надежности является минимум метрик надежности для всех терминальных пар. Это может интерпретироваться как уровень надежности, гарантируемый всем пользователям. Другой относительной величиной является средняя метрика надежности для всей совокупности пар терминалов, которая характеризует степень устойчивости. Выбор между минимумом и средним относится к общей философии сервис провайдера, в частности, объективным показателем того, что услуга будет удовлетворительной “в среднем” или гарантировано.

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

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

7.3. Выбор правильного алгоритма

В дополнение к предоставлению читателю разнообразных мер надежности эта глава дает широкий выбор для вычисления каждой из упомянутых мер, включая точные алгоритмы, аналитические границы и моделирование по методу Монте-Карло. Таким образом, здесь может также возникнуть чувство неуверенности. Выбор из числа алгоритмов сильно зависит от размера вовлеченной сетевой структуры. В идеале предпочтителен алгоритм, который выдает точное значение надежности. Однако эффективные (полиномиально ограниченные) алгоритмы доступны только для определенных структурных классов графов, описанных в разделе 3. Для произвольных графов перечисленные алгоритмы могут решить задачи только ограниченного объема. Для других ситуаций должны использоваться аппроксимационные алгоритмы. Выбор между аналитическими ограничениями и методом Монте-Карло является более тонким. Аналитические ограничения зависят от специфики проблемы. Следовательно, как это описано в разделе 4, такие ограничения существуют только для определенных классов задач. Далее, их качество и сопряженное с ним время работы алгоритма может отличаться в зависимости от класса решаемой задачи. Для определенных классов доступные ограничения весьма хороши и могут быть вычислены достаточно быстро. Однако для других классов это не так. Преимущества Монте-Карло заключаются в том, что некоторые подходы Монте-Карло могут быть реализованы потенциально для всех метрик, представляющих интерес, а сам алгоритм Монте-Карло может работать долгий или короткий период времени с соразмерным увеличением или уменьшением уровня точности. Нам следует заметить, что некоторые более продвинутые методы Монте-Карло используют проблемные структуры и, следовательно, не имеют первого преимущества.

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

Следует рассмотреть еще один момент, относящийся к данной проблеме, какую модель использовать, с ориентированным или неориентированным графом. Как было отмечено в разделе 2, модель ориентированного графа является более общей и пригодна для широкого класса мер, она пригодна для моделирования как ориентированных, так и неориентированных проблем, с отказами узлов и без отказов.

7.4. Критерии проектирования

Критерий проектирования, который наиболее часто используется, заключается в том, что суррогатом для ограничения всетерминальной надежности служит ограничение связности, т.е. ограничение, требующее, чтобы связность была, по крайней мере, с. Обобщение этого критерия на SCBS (и на другие классы систем, включая k-терминальные проблемы и определенные меры работоспособности) является ограничением, которое определяет то, что SCBS не содержит набора разрезов с размером с-1 или меньше. Вероятно, наиболее типичным сценарием является случай, где с=2. С с=2 конструктивный критерий утверждает, что система не должна содержать ни одной точки отказа.

Рассмотрим уровень надежности, гарантированный критерием проектирования. Если нет набора разрезов размером с-1 или меньше, тогда нижняя граница надежности системы будет получена в предположении, что каждый набор элементов размером с является набором разрезов. Для m-элемента SCBS надежность этой системы будет равна надежности системы К из N при K=m-c и N=m. Предполагая равные вероятности отказов, надежность системы может быть:

Эта величина равна наилучшей возможной нижней границе уровня надежности системы, гарантированной при ограничении с-связности в предположении, что никакой дополнительной информации о структуре системы не известно. Мы заметим, что при с=2, это ограничение получается для случая всетерминальной надежности с помощью простого цикла.

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