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

□ ОЗОБ2 Ю8

КОМБИНАТОРНЫЕ МЕТОДЫ АНАЛИЗА УЯЗВИМОСТИ МНОГОПРОДУКТОВЫХ СЕТЕЙ

05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 20(17

003052108

Работа выполнена в отделе Исследования операций Вычислительною центра им. А. А. Дородницына РАН

Научный руководитель:

доктор физико-математических наук, профессор Новикова Наталья Михайловна

Официальные оппоненты-

доктор технических наук, профессор Сигал Израиль Хаимович

кандидат физико-математических наук, доцент Романов Дмитрий Сергеевич

Ведущая организация-

Институт вычислительной математики и математической геофизики СО РАН (г Новосибирск)

Защита диссертации состоится ^Р^ОУРг 2007 г в ч. на заседании диссертационного совета Д002.017.04 при Вычислительном центре им. А. А. Дородницына РАН по адресу: 119333, Москва, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан 2007

г

Ученый секретарь диссертационного совета д ф -м н , профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на: 2-й (1998) и 3-й (2001) Московских международных конференциях по исследованию операций; IX международной конференции "Проблемы функционирования информационных сетей"в г. Новосибирск (2006). Ряд результатов диссертации использовался в работе по проектам РФФИ № 98-01-00233, 01-0100502, 04-01-00203.

Публикации. По материалам диссертации опубликовано 7 печатных работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 141 наименования. Общий объем работы — 131 страница, включая 14 рисунков и 7 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена исследованию частных случаев задачи анализа уязвимости МП-сети с помощью известных теоретико-графовых и потоковых методов.

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

В качестве математической модели многопользовательской сетевой системы рассмотрим МП-сеть И — (С,М), которая задается физическим графом сети О = (ЛТ,А) (неориентированным, связным, без петель), где N = {^1,г>2>...,ьп} — множество вершин (узлов), А — {г!,Г2, --^Га} С. N х N — множество ребер, соединяющих вершины; и набором М — {рг,р2, ■■■тРт,} тяготеющих пар (видов продуктов) — вершин графа называемых источником и стоком для пары рг, г = 1 , т. Вершины N х являются транзитными.

Каждому ребру гг € А формально сопоставим пару противоположно направленных дуг ег, ег+а для потоков прямого и обратного направления, соответственно. При этом для любой вершины V £ V определим множества Т(у) и 5(и) индексов входящих и выходящих дуг. Обозначим через / = {¡г]} матрицу распределения потоков по дугам МП-сети, здесь > 0 — поток г-го вида продукта по дуге ег Считается, что в транзитных для узлах сети выполнены условия сохранения потока г-го вида продукта:

^ = /и ^ Ф ^ /„ = 1ч,г = Ьгп.

(1)

На ребрах графа заданы веса, определяющие целочисленные значения у к € Z+ пропускной способности ребер к = 1, а, и соответствующие физическому числу каналов связи, имеющихся в сети. Набор у = {уь\к = 1 , а} задает ограничения на распределение потоков по ребрам МП-сети:

т

£(/.* + /,(*+«)) < Ук Vrfc 6 А. (2)

г=1

Ограничения (1), (2) определяют множество Z(y) достижимых векторов г(/) = где

1г] — У, Л? количество потока г-го вида

¿еяк)_ з&гы,)

продукта, г — 1 ,т, пропускаемое по сети в соответствии с распределением потоков /.

Для МП-сети I? вводится граф тяготений или логический граф Ор = (АГР, М) (неориентированный, возможно, состоящий из < ш компонент связности), где = {и 6 3 рг £ М : V = или V = у^} — подмножество вершин графа являющихся источником или стоком для тяготеющей пары рг, г — 1, т; М = (р1,р2) •■чРт} — множество логических ребер, соединяющих источник и сток г>г, г-й пары. Всем ребрам рг £ М логического графа приписаны числа (1г > 0, измеряемые в условных единицах потока, указывающие какой поток следует пропустить по г-му логическому ребру и имеющие смысл требований или заявок на величину потока для г-й тяготеющей пары. Если <I € 2(у), (I = то сеть называется допустимой.

Предположим, что МП-сеть подвергается разрушающему воздействию, которое приводит к полному уничтожению одного или нескольких (заранее неизвестно каких) физических ребер сети D, а множество узлов и тяготеющих пар остается прежним. Обозначим через Я(ги) множество ребер, уничтоженных в результате удара го, тогда у3 = 0 для ребер т^ € Я(ю), и у1(ш) = уу для г3 £ Пусть распределение потоков в сети

после разрушения производится исходя из лексикографически максиминного правила.

Введем понятие мощности (силы) удара как суммарной пропускной способности выбитых ребер г, е Д(ги), обозначим ее и(гл) = ^Г^ у^ и предположим, что известно ограничение на г, 6й(ш)

мощность удара и{ш) < \¥о. Мощность удара можно также ин-

терпретировать в терминах числа ребер (что формально соответствует у к = 1 ,к = 1,а), тогда ограничение обозначим через /о- Далее рассмотрим два вида пропускной способности — исходную у к и единичную.

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

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

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

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

кографической задачи оптимизации.

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

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

Постановка 1. При мощности удара, не превосходящей \¥о, необходимо найти множество ребер Щт*), при удалении которых из сети разъединяется хотя бы одна тяготеющая пара, и сумма требований для разъединенных пар — максимальна.

Постановка 1'. Необходимо найти множество В,(и)*) из не более ¿о ребер, при удалении которых из сети разъединяется максимальное число тяготеющих пар.

Если положить ук = 1, с?г = 1 для всех Л;, г, то постановка 1 смыкается с постановкой 1'. Однако мы выносим отдельно рассмотрение постановки 1', так как она содержательно соответствует отсутствию у атакующего информации о пропускной способности ребер и требованиях в сети

Для постановок 1,1' будем различать две задачи:

1) найти удар и>*, наносящий максимальный ущерб пользователям (найти одно, любое решение) — задача А-,

2) найти все множество решений — ударов с максимальным ущербом, кроме неэффективно использующих мощность удара — задача В.

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

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

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

Постановка 2. Найти удар -ш* минимальной мощности и (го*), разъединяющий хотя бы одну тяготеющую пару.

Постановка 2'. Найти удар из*, выбивающий минимальное число I* ребер, при удалении которых из сети была бы разъединена хотя бы одна тяготеющая пара.

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

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

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

вой для задачи А, или все такие разрезы для задачи В. При этом решение задач А и В эквивалентно, сложность — не более 0(тпа2), для планарных графов — О(тп log п).

Утверждение 1. Задача анализа уязвимости МП-сети в постановке 2,2' (задачи А,В) допускает эффективное решение, при условии, что мощности удара Wo достаточно для разрушения минимального сетевого разреза. Решение задачи — это соответствующий минимальный сетевой разрез (разрезы).

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

Если мощности удара Wo достаточно для разрушения минимального МП-разреза, решение задачи анализа уязвимости МП-сети совпадает с решением классической задачи о минимальном МП-разрезе. Однако последняя в общем случае является ./VP-трудной для любого m > 2, и NP-трудной для нахождения приближенного решения. В настоящее время известно три класса графов, для которых эта задача является полиномиально разрешимой — кольцевые графы (сложность 0(min[an2,n3])), ориентированные и корневые деревья (сложность соответственно 0(max[m2logn,n2logn]) и 0(min[an,n2])). Кроме того, для т = 2 задача о минимальном МП-разрезе эффективно решается, например, двухкратным применением потокового алгоритма построения минимального разреза для пары вершин.

Утверждение 2. Задача анализа уязвимости МП-сети в постановке 1,1' (задачи А,В) допускает эффективное решение для двухпродуктовой сети, и для сетей, граф которых являются кольцевым графом, ориентированным или корневым деревом, при условии, что мощности удара Wq достаточно для

разрушения минимального МП-разреза. Решение задачи — это соответствующий минимальный МП-разрез (МП-разрезы).

В §3 рассматриваются случаи, в которых для решения поставленной задачи могут применяться традиционные теоретико-графовые методы. Нарушение связности графа дает решение задачи в постановках 2,2' для МП-сети в случае, когда множество вершин графа тяготений С?р совпадает со всем N (в графе нет транзитных вершин), и граф (?р содержит остовное дерево физического графа С?. Такой граф тяготений обозначим С?о, он состоит из одной связной компоненты, и разбиение С на две части автоматически влечет за собой разделение хотя бы одной тяготеющей пары, поэтому минимальный реберный разрез здесь оказывается минимальным сетевым. Решение задачи в постановках 2,2' для С? — минимальный реберный разрез с пропускной способностью не более \¥о, если для (7 такой существует. Решение для постановки 2' может быть найдено известным алгоритмом А.В.Карзанова (сложность 0(Лп2), где Л — число ребер в минимальном разрезе графа б), строящего все минимальные разрезы для графа с единичными весами ребер (вес ребра отождествим с его пропускной способностью). Для задачи в постановке 2 рассмотрим граф с кратными ребрами.

Утверждение 3. Для случая графа тяготений задачи А, В в постановках 2, 2' допускают эффективное решение. Решение задачи — соответствующие минимальные разрезы сети.

Заметим, что специфика графа тяготений позволяет снизить сложность поиска решения для задачи в постановках 2, 2' с 0(тпа2) до 0(Лп2). К сожалению, для постановок 1,1' даже в случае изложенный выше полиномиальный алгоритм применить не удается, для них таким образом можно только убедиться в отсутствии решения.

В §4 обсуждаются вопросы, связанные со сложностью задачи в постановках 1,1' и построением для нее приближенного

решения. В связи с изучением близких по смыслу Л^Р-полных задач для однопродуктовой сети, в литературе высказываются предположения об Л^Р-трудиости рассматриваемой задачи при т > 2, однако результаты изучения ее сложности автору не известны. Основным фактором, влияющим на трудоемкость решения, является невозможность до построения произвольного разреза Я сети И определить точно, какие тяготеющие пары он разделит, и какой ущерб будет нанесен вследствие его разрушения. Очевидно, что и то, и другое зависит от имеющихся у нападающего ресурсов, расположения тяготеющих пар, структуры сети и пропускной способности ребер. Однако если разрез — решение разделяет более двух тяготеющих пар, то его вряд ли удастся найти полиномиальным алгоритмом.

В силу специфики задачи анализа уязвимости МП-сети в постановках 1,1', построением ^-оптимального решения перечисленные проблемы снять не удается, что ставит под сомнение целесообразность его поиска.

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

Определение 3. Простым разрезом графа С? назовем такой разрез Я, у которого любое собственное подмножество элементов разрезом не является, т.е. Я — простой, если любое подмножество В! Я, Я! ф 0, не является разрезом.

Обозначим через 1(Я) множество номеров тяготеющих пар, разделенных разрезом Я: 1(Я) = {г| Я разделяет рг}. Если Я — минимальный МП-разрез, то \1{Я)\ = т.

Определение 4. Простым разрезом для множества тяготеющих пар с индексами I будем называть такой простой разрез Я графа С, для которого 1(Я) = I. Далее нас будут интересовать простые разрезы сети, для которых 1{Я) ф 0.

Определение 5. Для произвольного разреза Я введем вели-

чину ущерба как сумму требований на поток разделенных пользователей сети после удаления Я : в (Я) = ^^ <1г.

Ш(Н)

Задача анализа уязвимости МП-сети в постановках 1,1' состоит в поиске

тах5(Д),

ЯСА

при условии

]С У* <

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

Определение 5. Несократимым разрезом назовем такой разрез Я графа С, что удаление любого ребра г из Я приводит к уменьшению ущерба пользователей, т.е. Я несократим, если V г 6 Л, 1(Я\{г}) с 1{Я). Примерами могут служить минимальные сетевой и многопродуктовый разрезы.

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

Во второй главе задача рассматривается в предположении, что ресурсов нападающего достаточно для разделения графа сети ровно на две части. В §1 указана связь между несократимыми и простыми разрезами сети, исследованы некоторые свойства простых разрезов, обосновано использование последних для решения поставленной задачи. В частности, свойства 1,3 определяют структуру связного графа, разделенного простым разрезом, свойство 2 — реберный состав последнего, свойства 4,5 для любого разреза Я, не являющегося простым и разделяющего непустое множество тяготеющих пар, гарантируют существование простого разреза Я', для которого 1(Я) = 1(Я'),

и У (Л) > У (В,'). Далее доказывается

Утверждение 4. Пусть разрез Л разделяет граф (7 на две связные компоненты, 1(Я) ф 0. Этот разрез несократим тогда и только тогда, когда он простой.

Из последнего утверждения и свойств 4,5 следует: если ресурсы нападающего ограничены и не позволяют ударом разделить сеть более чем на две части, разрушив пути соединения для непустого множества тяготеющих пар, то решение задачи анализа уязвимости МП-сети в постановках 1, V следует искать среди множества Я простых разрезов сети, для которых 1{Я) ф 0, и У (Я) < \Уо- Однако для решения задачи придется построить более широкое множество 72. всех простых разрезов сети, так как в общем случае до построения разреза трудно определить, разделит ли он какие-нибудь тяготеющие пары. Заметим следующее: вместе с решениями задачи в постановках 1,1', множество Я содержит и решения для постановок 2,2' (если они существуют), поскольку минимальный сетевой разрез является простым и разделяет непустое множество тяготеющих пар.

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

Утверждение 5. Пусть граф & = (./V,А) связен, не содержит кратных ребер, и в нем для любой пары вершин существует по крайней мере два вершинно непересекающихся пути, их соединяющих. Пусть разрез Я' является простым и делит граф (? на две связные компоненты С и 0\С, в которых множества содержат 2<т<пип — т вершин. Тогда найдутся: I) последовательность простых разрезов Л1, .••> Л® € А;

И) последовательность вершин и1, ...,ит,г>г 6 ТУ7; и III) последовательность связных подграфов С1, й2,..., С"1-1, (Зт, такие, что каждый из подграфов С1 = и1, СУ?1 - связен, Л1 отделяет б?1 от СУ?1,

<32,СУ32- связен, С2 = (^2,А2),ЛГ2 = {у\у2},А2=Яи

Я1 = {г = отделяет С2 от

(7\ С\С71-связен, = (ЛГ\ А1), И1 = 1>г, Аг = А1'1 №-1,

Я1 отделяет йг от ...,

(?т~1,а\Ст-1- связен, вт~1 = (ЛГт-2,ЛГ-2),

Нт-2 = д^т-Зу^т-^ ¿т-2 = дт-ЗуДт_2)

Л"1"1 отделяет от С7\Ст~\

ст = Ст-1 у Лт_г у „т = ^ _ ^^

Л' отделяет О' от где Яг — непустое множество ребер, соединяющих подграф б*г с вершиной и,+1. Кроме того, в любом С найдется вершина и, смежная по крайней мере с одной из вершин подграфа

Суть алгоритма, называемого далее алгоритмом построения простых разрезов сети (АППР), состоит в следующем. Для каждой вершины V графа (7 рассматриваются все последовательности связных подграфов 67^ = V, С?2,..., (7^, порожденных 1,..., к смежными вершинами, к < Ц. Причем С} С С?2 С ... С (7?

У У

для любой из ] последовательностей. Для каждого г,],г = 1,Лг, подграф проверяется на связность. Если С7\(7] — связен,

то разрез Л®, отделяющий (7* от С\(7*, — простой, и он находится исходя из свойства 2 простого разреза. Далее исследуется на связность подграф (7\С7*+1, порожденный г + 1 вершиной. Если не является связным, то процесс исследования текущей ,7-ой последовательности подграфов прерывается. Алгоритм переходит к следующей вершине, если для всех последовательностей, построенных для вершины V, процесс исследования на связность соответствующего подграфа оказался прерван или если все такие последовательности рассмотрены до конца, т.е. до к = Щ]. Так как алгоритм рассматривает все последовательности вложенных подграфов для всех имеющихся вершин, то согласно утверждению 5, будет построено все множество 71.

В §3 приводится формализованный алгоритм построения про-

стых разрезов (АППР) сети и доказывается следующая

Теорема 1. Пусть граф сети Б является связным, не содержит кратных ребер, и множество N состоит по крайней мере из п > 2 вершин. Кроме того, пусть в б для любой пары вершин существует по крайней мере два вершинно непересекающихся пути, их соединяющих, тогда алгоритм АППР закончит свою работу построением всех простых разрезов этой сети.

Для случая, когда ресурсы нападающего позволяют разделить физический граф сети ровно на две части, решение задачи анализа уязвимости МП-сети в постановках 1,1' выберем из построенного опираясь на второй критерий, а также исходя из ограничения на удар. Решение задачи А — простой разрез из И, удовлетворяющий ограничению на удар, удаление которого из сети нанесет максимальный ущерб пользователям, или все такие разрезы для задачи В. Вместе с решениями задачи в постановках 1,1', построены решения для постановок 2,2'. Это — простые разрезы из % с наименьшей пропускной способностью среди разрезов, разделяющих хотя бы одну тяготеющую пару.

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

В §1 исследованы некоторые свойства несократимых разрезов. В частности утверждение 7 для любого несократимого разреза Я, делящего физический граф сети на п частей, для которого 1{Я) Ф 0, гарантирует существование представления в виде объединения простых разрезов этого графа Я\, Я2,—, Яп-г, таких, что 1(Яг) ф 0,Яг Ф Я$ для любых г ф ¿г = 1,п — 1, 3 = И при этом 1(Я) = 1(Яг) и /(Д2) II... ЩСйп-О-

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

емой сети с помощью алгоритма АППР строятся все простые разрезы, пропускная способность которых не превосходит Для них вычисляются значения величины ущерба Б (И), которые упорядочиваются по невозрастанию в (Я) и нумеруются: Я.1, Я.2,..., Яц. Решение задачи уязвимости многопродуктовой сети в постановках 1,1' будем искать в виде комбинации разрезов из множества Я, Я — {Дг| У(Лг) < г = 1,и}. Для удобства воспользуемся деревом перебора. Далее под разрезом Я будем подразумевать комбинацию Я = (Яа и... и Л/ и 7?п), Яг ЕЯ.

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

ЗД = 5(Д«) + ... + 5(Дг) + 3{Яп)._ Для произвольного простого разреза Яг положим 3(Яг) = ¿'(Лг).

Поиск на дереве перебора будем вести в глубину, о перспективности разрушения простого разреза Як или комбинации разрезов Я будем судить по оценке величины ущерба, причиненного разделенным пользователям поврежденной сети (после удаления Як или Я ). Простые разрезы Яп (или Я), имеющие ббльшие значения оценки 8{Яп) (5(Я)), будем последовательно объединять с простыми разрезами с меньшими значениями ¿"(Яг), Ь = п + 1,п + 2,..., так, чтобы не выйти за границу силы удара И^о- Будем следить, чтобы каждый разрез, присоединяемый к уже построенной комбинации, разделял хотя бы одну тяготеющую пару, не разделенную этой комбинацией ранее, и отсекать бесперспективные ветви, если сила удара, необходимая для уничтожения комбинации простых разрезов, больше 1¥о. Такое построение дерева перебора отвечает предположению об эффективном использовании ресурсов нападающим.

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

силу удара. Дополнительным — оценку величины ущерба, нанесенного пользователям удалением из сети разреза Я. Тогда перебор можно сократить, не рассматривая такие комбинации простых разрезов, оценка ущерба от удаления которых из сети Я {Я) меньше ущерба от удаления построенного решения Я*, т.е. отсечь на дереве такие ветви, отвечающие Я, для которых 5(Д) < 5 (Я*), при условии, что У (Я) < \Уо- Доказанные в работе утверждения 8-10 показывают, что использование предложенной оценки позволяет результативно отсекать бесперспективные ветви и строить все множество оптимальных решений.

Алгоритм, изложенный в общих чертах выше, в §3 формализован и назван алгоритмом комбинирования простых разрезов (АКПР). Там же исследуются свойства предложенного алгоритма. В частности, доказана следующая

Теорема 2. Пусть граф С сети И является связным, не содержит кратных ребер, и множество N состоит из п > 2 вершин. Кроме того, пусть в С? для любой пары вершин существует по крайней мере два вершинно непересекающихся пути, их соединяющих. Пусть, множество М содержит хотя бы одну тяготеющую пару, и силы удара достаточно для разделения по крайней мере одной тяготеющей пары. Тогда алгоритм АКПР закончит свою работу построением всех оптимальных решений задачи в постановках 1,1'.

Для случая, когда ресурсы нападающего позволяют разделить физический граф сети на три и более частей, решение задачи анализа уязвимости МП-сети в постановках 1,1' построим комбинированием разрезов из Я. Решение задачи А — это комбинация простых разрезов из Я, удовлетворяющая ограничению на удар, удаление которой из сети нанесет максимальный ущерб пользователям, или все такие разрезы для задачи В.

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

нения скорости построения оптимального решения дополнительно к АППР были написаны алгоритмы, использующие для построения простых разрезов полный перебор ребер и перебор всех возможных комбинаций отделяемых вершин (ППВ). Временные затраты, необходимые для построения И перебором ребер оказались несоизмеримо больше, чем для АППР и ППВ, поэтому далее этот алгоритм не рассматривался. Дополнительно к АКПР были запрограммированы алгоритмы, использующие соответственно полный перебор всех возможных разрезов (ППР) и перебор с помощью дерева. Последний представлен в двух вариантах, первый — ПДУ — ветвит и отсекает вершины, используя точное значение ущерба S(R), второй — ПДР — имеет свое правило ветвления: разрез Rn добавляется к комбинации разрезов, если он содержит хотя бы одно ребро, не входящее в R.

§1 служит иллюстрацией работы алгоритмов на предложенной в работе модели междугородной телефонной сети на территории РФ, §2 — на сетях, физические и логические графы которых являются случайными и разреженными (с единичными пропускными способностями ребер и требованиями на поток). В первом случае рассматривалась потеря 5% и 10%, во втором — 5%, 10% и 15% пропускной способности ребер.

По результатам эксперимента сделаны следующие выводы:

1. По работе алгоритмов:

а). Все алгоритмы являются допустимыми, так как строят одно и то же множество оптимальных решений;

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

мами. В частности, использование алгоритма АППР позволило уменьшить время построения множества всех простых разрезов (для разреженных сетей на 25 вершинах в среднем в 4 раза); алгоритмы АКПР, ПДУ, ПДР рассмотрели примерно равное количество комбинаций разрезов, в несколько сот раз меньшее, чем ППР, однако, дерево перебора, построенное вместе с оптимальными решениями алгоритмом АКПР, оказалось меньше, чем для ПДУ, ПДР, примерно в 20-40 раз.

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

а). Удаление из сети 5%, 10% и 15% ребер ведет к более серьезным последствиям, чем удаление соответствующей пропускной способности;

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

Результаты, выносимые на защиту.

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

2. Результаты исследования частных случаев задачи анализа уязвимости МП-сети с помощью известных полиномиальных алгоритмов.

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

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

случае, когда удар делит сеть на три или более частей.

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

Основные результаты диссертации опубликованы в работах:

1. Nazarova I.A. The Problem of Vulnerability for Telecommunication Networks. Тезисы докладов 2-й Московской международной конференции по исследованию операций. Москва, 1998. С. 26.

2. Nazarova I.A. Branch-and-bound Method for the Network Vulnerability Problem. Тезисы докладов 3-й Московской международной конференции по исследованию операций. Москва, 2001. С. 83-84.

3. Назарова И.А. Лексикографическая задача анализа уязвимости многопродуктовой сети // Изв. РАН. ТиСУ. 2003. N 5. С. 123-134.

4. Назарова И.А. Модели и методы анализа многопродуктовых сетей. М.: ВЦ РАН, 2004.

5. Назарова И.А. Методы решения дискретной задачи анализа уязвимости многопродуктовой сети. Материалы IX международной конференции "Проблемы функционирования информационных сетей". Новосибирск, 2006. С. 125-130.

6. Назарова И.А. Модели и методы решения задачи анализа уязвимости сетей // Изв. РАН. ТиСУ. 2006. N 4. С. 61-72.

7. Назарова И.А. Анализ переборных алгоритмов для задачи оценки уязвимости многопродуктовых сетей. М.: ВЦ РАН, 2006.

Назарова Ирина Александровна

Комбинаторные методы анализа уязвимости многопродуктовых сетей

Подписано в печать 30.01.2007

Формат бумаги 60x84 1/16 Уч.-изд.л. 0.8. Усл.-печ. л. 1.25 Тираж 100 экз. Заказ 6

Отпечатано на ротапринтах в Вычислительном центре им. А А. Дородницына Российской академии наук 119991, Москва, ул. Вавилова, 40

Введение

Глава 1. Исследование уязвимости многопродуктовой сети с помощью теоретико-графовых и потоковых методов

§1. Основные предположения и формулировки.

§2. Исследование задачи анализа уязвимости МП-соти с помощью потоковых методов.

§3. Исследование задачи анализа уязвимости МП-сети с помощью теоретико-графовых методов.

§4 О сложности решения общего случая задачи анализа уязвимости МП-сети и о построении приближенного решения

Глава 2. Исследование уязвимости многопродуктовой сети с помощью формализма простых разрезов

§1. Свойства просгых разрезов графа

§2 Способы построения простых разрезов.

§3. Алгоритм построения простых разрезов.

Глава 3. Исследование уязвимости многопродуктовой сети с помощью формализма несократимых разрезов

§1. Свойства несократимых разрезов сети

§2. Схема метода вегвей и границ для задачи анализа уязвимосхи многопродуктовой cein.

§3. Алгоритм комбинирования просгых разрезов.

Глава 4. Результаты модельного вычислительного эксперимента

§1 Построение и исследование на уязвимость модели междугородной телефонной сети на территории РФ

§2 Исследование уязвимости моделей со случайными физическими и логическими графами сети.

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

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

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

Под анализом уязвимости обычно понимают исследование изменения функциональных характеристик сетевой системы в зависимости от ухудшения показателей работоспособности ее элементов или при полном разрушении последних [45, 67, 51, 88, 101, 26, 9, 54, 58, 73].

Математической моделью различных многопользовательских сетевых систем традиционно служит многонродуктовая потоковая сеть (МП-сеть) [24, 27, 76, 90]. В этой модели терри юриально-распределенная структура описывается с помощью взвешенного графа с заданными значениями пропускной способности ребер. В графе имеется выделенное подмножество упорядоченных пар вершин (тяготеющих пар), соответствующих источнику и стоку для потока некоторого вида "продукта" Считается, что все потоки проходят по МП-сети одновременно, являются невзаимозаменяемыми, для каждого из них заданы требования, имеющие смысл заявки на величину потока данного вида, и в неповрежденной сети все требования на передачу ноiока полностью удовлетворяются. Примером сетевой системы, функционирование которой может быть описано МП-сегыо, является телефонная сеть, поскольку последняя характеризуется невзаимозаменяемостью разговоров ее абонентов. В этом случае поюки-разговоры между разными парами абонентов соответствуют как бы различным видам "про-дукюв" , которые в сети не могут смешиваться или перераспределяться между другими абонентами

Для априорной оценки уязвимости реальной сехевой сис1емы моделируется повреждение соответствующей МП-сети, при этом характер повреждения определяется изучаемой сетевой системой. Чаще всего исследуются ситуации, когда в результате внешнего воздействия либо частично понижается (уничтожается полностью) пропускная способность отдельных ребер [56, 99, 52, 95, 87, 129], либо из МП-сети удаляются некоторые вершины [50, 59, 128]. Первый вид разрушения может рассматриваться, например, для оценки уязвимости обычной (проводной) телефонной сети, второй — для мобильной (беспроводной) сеги. Анализ уязвимости конкретной МП-сети сводится к изучению того, как определенный вид разрушений влияет на связность, обеспеченность потоковых требований, ущерб пользователей, затраты на восстановление, и другие функциональные характеристики, интересующие исследователя. В данной работе рассмотрим задачу при условии выхода из строя ребер МП-сети. Существует несколько подходов к решению этой проблемы.

1. Теоретико-графовые методы. При анализе сетевых систем с помощью теории графов основное внимание направлено на изучение структурных особенностей сети [50, 51, 104, 114]. Продолжается активное исследование ставших уже традиционными теоретико-графовых показателей уязвимости таких, как связность [35, 65, 56, 99, 78, 105, 94, 109, 110], диаметр [131, 53, 64, 66, 122, 77], гамильтонова связность [62, 126, 63], разреженность [133, 132], стойкость [73, 85, 86] Вводятся новые характористики такие, как слабая полнота [97, 98], индекс уязвимости [114], эффективность [88, 72, 100, 101]. Однако использование этих величин в качестве меры уязвимости требует серьезного методоло1 ического обоснования, прослеживающего взаимосвязь функциональных и 'юпологических свойств сеги. Теоретико-графовый подход к анализу уязвимости обычно не предполагает специального выделения множества тяготеющих пар, т.е считается, что любые две выбранные вершины могут быть парой источник — сток, таким образом, структура требований пользователей в этом случае не учитывается

2. Потоковые методы. Большая часть теории о потоках в сетях построена вокруг основополагающей теоремы Форда-Фалкерсона [42] о максимальном потоке и минимальном разрезе однопродуктовой сети. Применение моделей и методов потокового программирования [1, 9, 12, 19, 20, 41] позволило подробно изучить одно- и двухпродуктовые сети. Попытки прямого распространения полученных результатов на многопродуктовые сети к успеху не привели [83, 71, 111, 92, 102, 112]. Это объясняется, во-первых, невыполнением в общем случае свойства потоково-разрезной двойственности и, как следствие, невозможностью применения тех потоковых алгоритмов, которые используются для исследования однопродуктовых сетей; во-вторых, спецификой сети как многопользовательской системы, для которой оказались узки рамки традиционных оптимизационных постановок.

В терминах потокового программирования формулируются близкие по смыслу к задаче анализа уязвимости МП-сети задачи о нахождении наиболее разреженного многопродуктового разреза [121, 55, 79, 46, 81], и о построении минимального многопродуктового разреза [82, 74, 130, 80, 47, 83, 70, 103, 71, 111]. Однако применение потоковых алгоритмов для их решения носит скорее вспомогательный характер.

3. Вероятностные методы. В настоящее время для исследования сетевых систем, функционирующих и развивающихся в условиях неполной информации или возможных внешних воздействий, достаточно часю предлагается использовать модели и постановки [9, 69, 118, 84, 106, 89, 127, 93,

61, 11], опирающиеся на формализм теории вероятностей . В этом случае следует четко определить границы, в которых применение аппарата теории вероятностей для описания неопределенности является правомерным [28]. Например, целенаправленные разрушающие воздействия или умышленные разрушения сети вряд ли можно рассматривать как случайное многократно повторяющееся событие, поэтому трудно говорить о вероятности таких событий в общепринятом математическом смысле. Таким образом, при анализе уязвимости многопродуктовых сетей вероятностными методами повторяемость случайных событий должна быть теоретически обоснована. Если для описания неопределенности используются функции распределения случайных величин, то они должны указываться в явном виде.

4. Многокритериальные модели и методы, на наш взгляд, позволяют наиболее точно описывать многопользовательские сетевые системы и максимально глубоко изучать их свойства [7, 25, 26, 27, 24, 28, 21]. В [28] исследуются многокритериальный и параметрический подходы к анализу уязвимости МП-сеги с неизвестным вектором требований, указываются условия, при которых эти подходы оказываются эквивалентны, предлагаются мех оды, использующие обратную линейную свертку Кроме того, в [26, 23, 24, 28] поставлена задача нормативного анализа уязвимости МП-сети как системы, ориентированной на обеспечение требований пользователей, и разработана методология ее решения при неточно известных параметрах внешних разрушающих воздействий, снижающих пропускную способность ребер сети. Предложенная формализация позволяет получить наглядное описание уязвимости конкретной МП-сети с произвольным числом продуктов в виде трехмерной ступенчатой диаграммы.

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

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

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

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

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

Опираясь на разработанную модель, для исследования уязвимости многопродуктовой сети будем в равной степени использовать методы теории графов [2, 17, 22, 36, 30], дискретного программирования [38, 37, 43, 29], комбинаторной [18, 33] и многокритериальной [34, 44, 5, 39] оптимизации.

Задача анализа уязвимости МП-сети имеет свои особенности, однако, некоторые ее частные случаи могут быть исследованы с помощью известных теоретико-графовых и потоковых методов. Этому посвящена глава 1 настоящей работы. В §1 делаются основные предположения, формально 0писывае1ся используемая модель и обосновываются различные постановки рассматриваемой задачи в виде двухкритериальных лексикографических задач оптимизации. В §2 с помощью традиционных потоковых, в §3 — теоретико-графовых методов изучаются некоторые частные случаи рассматриваемой задачи, а именно а). Ресурсы атакующего позволяют разрушить любой разрез МП-сети; б) Любая вершина МП-сети является источником или стоком некоторого вида продукта; в). Нападающий стремится минимизировать свои затраты, разделив хотя бы одну тяготеющую пару.

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

Две следующие главы носвящены решению общего случая задачи анализа уязвимости МП-сети с помощью аппарата несократимых разрезов, формализованного в данной работе. В второй главе задача рассматривается в предположении, что ресурсов нападающего достаточно только для разделения графа сети на две части. В §1 указана связь между несократимыми и простыми разрезами сети, обосновано использование последних для решения поставленной задачи, исследованы некоторые свойства простых разрезов §2 носит технический характер, в нем дается теоретическое обоснование алгоритма, строящего все простые разрезы сети. В §3 приводится формализованный алгоритм построения простых разрезов (АППР) сети и доказательство его допусгимости.

В третьей главе задача анализа уязвимости МП-сети рассматривав 1ся в предположении, что ресурсы нападающего хотя и ограничены, но позволяют разделить граф сети более чем на две части. В §1 исследованы некоторые свойства несократимых разрезов. В §2 обсуждается схема метода ветвей и границ для решения задачи анализа уязвимости МП-сети и дается теоретическое обоснование соответствующего алгоритма. В §3 приводится формализованный алгоритм комбинирования простых разрезов (АКПР) и доказательство его допустимости

В четвертой главе приводятся результаты модельного вычислительного эксперимента. §1 служит иллюстрацией работы алгоритмов построения и комбинирования простых разрезов на предложенной в работе модели междугородной телефонной сети на терри юрии РФ, §2 — на сетях, физические и логические графы коюрых являются случайными и разреженными. В заключении приводится перечень основных научных результатов Основные результаты диссертации опубликованы в работах [135, 136, 137, 138, 139, 140, 141].

Основные результаты, полученные в рабою.

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

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

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

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

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

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

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

Указанные результаты опубликованы в работах [135, 136, 137, 138, 139, 140, 141].

Заключение

1. Андельсон-Вельский ГМ , Диниц Е.А., Карзанов А.В. Потоковые алгоритмы М. Наука, 1975

2. Берж К. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962.

3. Вентцель Е.С. Исследование операций М Советское Радио, 1972

4. Гермейер Ю.Б Введение в теорию исследования операций. М • Наука, 1971.

5. Гольдппейн A.J1. Исследование операций: многокритериальные задачи Конспект лекций. Пермь, 1995.

6. Гэри М , Джонсон Д Вычислительные машины и труднорешаемые задачи М.: Мир, 1982.

7. Давидсон М.Р., Малашенко Ю Е., Новикова Н.М. и др. Математические постановки задач восстановления и обеспечения живучести для многопродуктовых сетей. М.: ВЦ РАН, 1993.

8. Диниц Е.А., Карзанов А.В., Ломоносов М.В. О структуре системы минимальных реберных разрезов графа // Исследования по дискретной оптимизации. М : Наука, 1976 С 290-306

9. Дудник Б.Я , Овчаренко В Ф , Орлов В К. и др. Надежность и живучесть систем связи М Радио и связь, 1984.

10. Евстигнеев В.А., Касьянов В.Н. Толковый словарь по теории графов в информатике и программировании. Новосибирск: Наука, Сибирское предприятие РАН, 1999.

11. Заманский Л.Я., Гиллер Д.М. Анализ живучести стохастических графов // Исследование операций и АСУ. Киев. 1982 N. 19. С. 27-30.

12. Йенсен П , Барнес Д. Поюковое программирование. М.: Радио и связь, 1984

13. Карзанов А.В. Комбинаторные способы решения разрезных задач о мультипоюках // Комбинаторные методы в потоковых задачах. Выи 3 М. ВНИИСИ, 1979. С. 6-69

14. Карзанов А.В., Тимофеев Е.А. Эффективный алгоритм нахождения всех минимальных реберных разрезов неориентированного графа // Кибернетика. 1986. N 2. С. 8-12.

15. Кауль С.Б., Попков В К О сложности вычисления характеристик связности// Эффективность и структурная надежность информационных систем. Системное моделирование Новосибирск, 1982. С. 99103

16. Корбут А.А , Сигал И X , Финкелышейн Ю.Ю. Метод ветвей и границ. Обзор теории алгоритмов, программ и приложений// Math Opetat Statist. Ser Optimizat 1977. В. 8. N 2. С. 253-280

17. Кристофидес Н Теория графов. Алгоритмический подход М.: Мир, 1978.

18. Леонтьев В.К. Комбинаторика: Ретроспектива и перспектива// 2000 Компьютер и задачи выбора М.: Наука, 1987.

19. Ловецкий С.Е., Меламед И И Статические потоки в сетях // Автоматика и телемеханика. 1987. N 10. С. 3-29.

20. Ловецкий С.Е., Меламед И.И. Динамические потоки в сетях // Автоматика и телемеханика 1987. N 11. С. 7-29

21. Лочмелис Я.Я. Многокритериальные задачи оптимизации сетей связи // Радиоэлектроника и электросвязь / Исслед. по электродинамике и теории цепей. Рига, 1981. С. 105-11122 2324