Комбинаторные методы анализа уязвимости многопродуктовых сетей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Назарова, Ирина Александровна

• Назарова, Ирина Александровна
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Назарова, Ирина Александровна

Введение

Глава 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].

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Назарова, Ирина Александровна, 2007 год

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