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

• Автор: Назарова, Ирина Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 131 с. : ил.

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

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

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

потоковых методов

3. Исследование задачи анализа уязвимости МПсети с помощью

теоретикографовых методов.

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

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

2 Способы построения простых разрезов
3. Алгоритм построения простых разрезов
Глава 3. Исследование уязвимости многопродуктовой сети с помощью формализма несократимых разрезов
1. Свойства несократимых разрезов сети.
2. Схема метода ветвей и границ для задачи анализа уязвимосш
многопродуктовой ев1 и
3. Алгоритм комбинирования простых разрезов
Глава 4. Результаты модельного вычислительного эксперимента
1 Построение и исследование на уязвимость модели
междугородной телефонной сети на территории РФ . . . 2 Исследование уязвимости моделей со случайными
физическими и логическими графами сети
Заключение
Список литературы


Для оценки ущерба в условиях неполной информированности будем следовать методологии исследования операций и опираться на принцип гарантированного результата (3, ]. Критерием уязвимости МП-сети далее будем считать гарантированную (наихудшую) оценку ущерба пользователей поврежденной сети. Для решения задачи анализа уязвимости МП-сети предлагается использовать теоретико-игровую модель "оборона против нападенияп[4], и повреждение ребер рассматривать как результат целенаправленной аіаки противника ограниченной мощности В рамках предлагаемой модели предположим, что нападающий может преследовать две цели либо исходя из имеющихся ресурсов нанести максимальный ущерб, либо, минимизируя свои затраты, разделить хотя бы одну тягоіеіощую пару. При этом будем считать, что обороняющийся занимает пассивную позицию, т. Опираясь на разработанную модель, для исследования уязвимости многопродуктовой сети будем в равной степени использовать методы теории графов [2, , , , ), дискретного программирования [, , , ), комбинаторной [, ] и многокритериальной [, , 5, ] оптимизации. Задача анализа уязвимости МП-сети имеет свои особенности, однако, некоторые се частные случаи могут быть исследованы с помощью известных теоретико-графовых и потоковых методов. Этому посвящена глава 1 настоящей работы. В §1 делаются основные предположения, формально онисываеюя используемая модель и обосновываются различные постановки рассматриваемой задачи в виде двухкритериальных лексикографических задач оптимизации. Нападающий стремится минимизировать свои затраты, разделив хотя бы одну тяготеющую пару. Там же указываются соответствующие алгоритмы. В §4 обсуждаются вопросы, связанные со сложностью поставленной задачи в общем случае и построением для нее приближенного решения. Две следующие главы посвящены решению общего случая задачи анализа уязвимости МП-сети с помощью аппарата несократимых разрезов, формализованного в данной работе. В второй главе задача рассматривается в предположении, что ресурсов нападающего достаточно только для разделения графа сети на две части. В §3 приводится формализованный алгоритм построения простых разрезов (АППР) сети и доказательство его допустимости. В третьей главе задача анализа уязвимости МП-сети рассматривавюя в предположении, что ресурсы нападающего хотя и ограничены, но позволяют разделить граф сети более чем на две части. В §1 исследованы некоторые свойства несократимых разрезов. В §2 обсуждается схема метода ветвей и границ для решения задачи анализа уязвимости МП-сети и дается теоретическое обоснование соответствующего алгоритма. В четвертой главе приводятся результаты модельного вычислительного эксперимента. РФ, §2 — на сетях, физические и логические графы коюрых являются случайными и разреженными. В заключении приводится перечень основных научных результатов Основные результаты диссертации опубликованы в работах [5, 6, 7, 8, 9, 0, 1]. Глава 1. В качестве математической модели многопользовательской сетевой системы рассмотрим многоиродуктовую сеть О = {(7, М), которая задается физическим графом сети (3 = (Лг, А) (пусть, неориентированным, без петель), где N = {У1,У2, . А = {Г[,Г2,га} с N х N — множество ребер, соединяющих вершины; и набором М = {р1,Р2) — )Рт} тяготеющих пар (видов продуктов) — вершин {у3,,%) графа С, называемых источником и стоком для тяготеющей пары ри г = 1,т Остальные вершины N х АГМ являются транзитными. Каждому ребру гг ? А физического графа сети формально сопоставим пару противоположно направленных дуг ег и е1+а для потоков прямого и обратного направления, соответственно При этом для любой вершины V еУ определим множества Т(у) и 5(г;) индексов входящих и выходящих дуг. Обозначим через / = {/г;} матрицу распределения потоков но дугам МП-сети, здесь /у > 0 — поток г-го вида продукта (тяготеющей пары рг) по дуге ег Считается, что в транзитных для рг узлах сети не происходит потери потока [), те. На ребрах графа С заданы веса, определяющие целочисленные значения ук ? Z+ пропускной способности ребер г*, А; = 1,а, и соответствующие физическому числу каналов связи, имеющихся в сети.