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

Тезисы докладов

Назарова И.А.

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

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

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

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

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

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

Вопрос о сложности задачи анализа уязвимости МП-сети в постановке 1 в общем случае остается открытым, хотя в работе [1] высказывается предположение об ее N

-трудности для любого числа тяготеющих пар, большего двух. Близкие по смыслу задача сетевого торможения [2], задача торможения сети с единственным сервером [1] для однопродуктовой сети и задача о разделении для однопродуктовой сети с единственным источником и несколькими стоками [3] являются соответственно N

-полными и N

-трудной.

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

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

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

Было показано, что любой несократимый разрез сети представим в виде объединения простых разрезов графа [5]. Для решения задачи в постановке 2 предлагается алгоритм комбинирования простых разрезов (КПР), основанный на схеме перебора по методу ветвей и границ. Отсечение бесперспективных ветвей производится согласно оценкам возможного ущерба от удаления соответствующей комбинаци разрезов.

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

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

[1]. Aura T., Bishop M., Sniegpwski D. Analyzing single-server network inhibition // Proc. of the IEEE 13th Computer Security Foundations Workshop. Los Alamos: IEEE Computer Society Press, 2000. P. 108-117.

[2]. Phillips Cynthia A. The network inhibition problem // Proc. 25th Ann. ACM Symp. on the Theory of Comp. ACM Press. 1993. P. 776-785.

[3]. Martel C., Nuckolls G., Sniegpwski D. Computing the Disconnectivity of a Grahp. Technical Report CSE-2002-38. Davis: University of California, 2001.

[4]. Ausiello G., Crescenzi P., Gambosi G. et al. Complexity and Approximation. Complexity and Approximation. Combinatorial optimization problems and their approximability properties. Springer-Verlag, 1999.

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2006, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2006, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:52)