Содержание к диссертации
Введение
Глава 1. Моделирование и задачи анализа живучести информационных сетей 10
1.1. О моделировании систем сетевой структуры гиперсетями 10
1.1.1 . О многослойных моделях информационных сетей 10
1.12. Математические модели многослойных сетей 12
1.1.3. Модель гиперсети 16
1.2. Известные методы исследования живучести сетей связи 17
1.2.1. Понятия "устойчивости" и "живучести" 18
1.2.2. Методы анализа живучести 21
1.2.3. Классификация основных структурных показателей живучести многослойных сетей 24
Глава 2. Задачи поиска максимальных (s — t) потоков в гиперсетях 27
2.1. Максимальный поток и минимальный разрез в гиперсетях 27
2.1.1. Основные определения 27
2.1.2. Соотношение максимального потока и минимального разреза в гиперсетях 29
2.1.3. О сложности задачи поиска целочисленного максимального (s — t) потока в гиперсети 34
2.1.4. Выводы 37
2.2. Алгоритмы поиска максимального (s — t) потока в гиперсети 37
2.2.1. Алгоритм Форда - Фалкерсона (Ф-Ф) 37
2.2.2. Построение v-цепей 45
2.2.3. Построение простых цепей 48
2.2.4. Численные результаты 49
2.2.5. Выводы 54
2.3- Поиск простой (s ~ t) цепи с максимальной пропускной способностью в нестационарной гиперсети 55
2.3.1. Постановка задачи 55
2.3.2. Классический метод ветвей и границ 56
2.3.3. Метод ветвей и границ с частичным ветвлением 58
2.3.4. Результаты численных экспериментов 59
2.3.5. Выводы 60
Глава 3. Применение задачи поиска максимального (s — і) потока в нестационарной гиперсети для моделирования РИВ 61
3.1. О моделировании систем сетевой структуры нестационарными гиперсетями 61
3.1.1. Методы сведения нестационарных сетей к стационарным моделям 62
3.2. Моделирование РИВ на сеть на модели нестационарной гипер сети 65
3.2.1. Моделирование РИВ распространяющихся во времени 65
3.2.2. Поиск оптимальной стратегии атаки 67
3.2.3. Атака "с возвращением ресурса" 69
3.2.4. Атака "без возвращения ресурса" 74
3.2.5. Поиск минимального разреза для оптимальной атаки "без возвращения ресурса" 77
3.2.6. Выводы 79
3.3. Максимальный поток в нестационарной гиперсети с мобиль ными абонентами 79
3.3.1. Моделирование процесса атак на мобильные терминалы 82
3.3.2. Результаты численных экспериментов 84
3.3.3 Выводы 86
Заключение 89
Литература
- . О многослойных моделях информационных сетей
- Соотношение максимального потока и минимального разреза в гиперсетях
- Поиск простой (s ~ t) цепи с максимальной пропускной способностью в нестационарной гиперсети
- Моделирование РИВ на сеть на модели нестационарной гипер сети
Введение к работе
В настоящее время информационные сети и информационно-вычислительные ресурсы используются практически во всех областях деятельности современного общества. Возрастает зависимость от информационно-коммуникационных услуг, что обуславливает важность задачи обеспечения безопасности и определенного уровня надежности, живучести и качества обслуживания телекоммуникационных сетей.
Сложные механизмы взаимодействия между разными уровнями информационной сети и нетривиальность возникающих задач требует многослойной математической модели, способной описать протоколы и процессы, происходящие в реальных сетях. Действительно, сложность и высокая стоимость современных телекоммуникационных систем не позволяют основывать проектирование и формирование их архитектуры, выбор основных конструктивных параметров и оценку характеристик лишь на инженерной интуиции [60].
В процессе проектирования сетей также необходимо учитывать ряд параметров живучести и надежности. Это позволит выявить узкие места сети, прогнозировать возможный ущерб до разрушений и в дальнейшем укрепить или модернизировать сети, сводя к минимуму возможные потери, выбрать оптимальные параметры и строить рациональные стратегии управления
Стоит отметить, что современные информационные сети связи предполагают включение в свою структуру эффективных систем мониторинга, отслеживающих параметры состояния сети для обеспечения контроля и безопасности. Также мониторинг предполагает выявление различных неполадок или угроз вирусных атак. Существенная доля атак нацелена на максимальное потребление предоставляемых ресурсов с целью значительного ухудшения или прекращения предоставления услуг пользователям. Например, DDoS-атаки (Distributed Denial Of Service Attack) направлены на значительное увеличение трафика к атакуемому объекту (обычно атакуемыми ресурсами являются: ширина канала, процессорное время серверов и роутеров, конкретные реализации протоколов) [15].
Математическое моделирование позволяет получить возможные варианты поведения характеристик сети при различных разрушающих информационных воздействиях на сеть. Таким образом, моделирование позволяет создать базу для систем мониторинга.
Одним из универсальных параметров, чувствительным к изменению состояния сети, является отслеживание изменений величины информационного потока в сети (трафика). В связи с этим задача моделирования разрушающих информационных воздействий (РИВ) на сеть и выявление характерных, соответствующих данному воздействию, изменений потока в сети является одной из актуальных проблем информационной безопасности.
При описании модели информационных сетей приходится иметь дело со сложным комплексом взаимосвязанных и согласованно функционирующих программных и аппаратных компонентов. Моделирование должно учитывать большинство принципов и механизмов работы сети. Гиперсеть [61], как модель сети, позволяет учитывать иерархичность современных сетей. В частности, она позволяет учитывать как физическую сеть, так и реализацию логических каналов в первичной сети.
Цель работы заключается в моделировании работы сети с помощью нестационарной гиперсети при разрушающих информационных воздействиях, распространяющихся во времени. Величина максимального потока рассматривается как характеристика живучести сети. В качестве РИВ рассматривается последовательное уменьшение пропускной способности каналов первичной сети. Для этого в диссертационной работе решаются следующие задачи:
• создание теоретической базы для работы с понятием максимального потока и минимального разреза в гиперсетях;
• создание методов и алгоритмов поиска величины максимального потока в стационарных и нестационарных гиперсетях; • моделирование процесса распространения РИВ в нестационарной гиперсети;
• проведение численных экспериментов.
Структура работы
Материал диссертации состоит из трех глав и организован следующим образом:
В Главе 1 описываются многослойные модели информационных сетей. В частности, описана модель гиперсети, позволяющая учитывать вторичную сеть, построенную на базе каналов первичной сети. Гиперсеть [62] более адекватно чем граф описывает сложность и иерархичность современных сетей.
Далее рассматриваются методы исследования живучести сети. Перечисляются основные показатели живучести многослойных и однослойных сетей
Глава 2 посвящена теоретическим результатам для задачи поиска величины максимального потока между двумя выделенными вершинами в гиперсети. Введено понятие минимального разреза. Показано, что теорема Форда-Фалкерсона о равенстве величин максимального потока и минимального разреза в графах не верна в гиперсетях. Для некоторых видов гиперсетей получены соотношения между величинами максимального потока и минимального разреза в гиперсетях. Также дано доказательство NP-полноты задачи поиска максимального потока в гиперсети.
Далее описаны приближенные алгоритмы для решения задачи поиска максимального потока в гиперсети. Было предложено несколько подходов:
• модификация алгоритма Форда-Фалкерсона,
• построение v-цепей,
• построение простых цепей.
• комбинация трех первых методов. Для модифицированного алгоритма Форда-Фалкерсона доказаны 2 теоремы, дающие нижние оценки величины потока в гиперсетях специального вида. Также показано, что стратегия "посылать как можно больший поток по найденному дополняющему пути" не всегда приводит к максимальному потоку.
Далее в работе описана программная реализация алгоритмов и приведены результаты численных экспериментов для сравнения результатов работы алгоритмов. Отмечено, что комбинированный алгоритм в среднем позволяет найти лучший поток, чем остальные приближенные алгоритмы.
В конце главы рассмотрена задача поиска простых цепей в нестационарных гиперсетях. Для ее решения использован метод ветвей и границ. Приведены результаты численных экспериментов для сравнения разных алгоритмов ветвления.
Глава 3 посвящена моделированию разрушающих информационных воздействий (РИВ), распространяющихся во времени, на модели нестационарной гиперсети. Сделан обзор нескольких методов сведения нестационарной гиперсети к стационарной. Для оценки живучести и поиска нижних границ параметров живучести рассмотрена задача построения "оптимальных" атак, минимизирующих максимальный поток за некоторый период времени. Алгоритм построения оптимальных атак был описан для двух крайних случаев: для атаки "с возвращением ресурса" и "без возвращения ресурса" Приведены результаты численных экспериментов для сравнения разрушающих воздействий атак построенных оптимально и случайно.
В конце главы рассмотрена задача моделирования РИВ на мобильные сети на модели нестационарной гиперсети. Приведены численные результаты для гиперсетей с различной топологией первичной сети.
Основные положения, выносимые на защиту
• Теоретические результаты (доказательство теорем) для величин максимального потока и минимального разреза в гиперсетях.
• Приближенные алгоритмы поиска максимального (s — t) потока в гиперсетях.
• Метод поиска простых цепей в нестационарной гиперсети.
• Методика моделирования РИВ, распространяющихся во времени, на модели гиперсети. Алгоритмы поиска оптимального маршрута распространения атак "с возвращением ресурса" и "без возвращения ресурса" в гиперсети.
• Методика моделирования РИВ, распространяющихся во времени, для мобильных сетей.
Научная новизна работы состоит в следующем:
• Изложенные теоретические результаты показывают, что при работе с гиперсетями нужна особая методика и особые алгоритмы, отличные от общеизвестных, опирающихся на теорию Форда-Фалкерсона.
• Предложены оригинальные алгоритмы, позволяющие осуществлять поиск приближенного максимального потока в гиперсети.
• Разработаны оригинальная методика моделирования РИВ на нестационарных гиперсетях и алгоритмы поиска оптимальных маршрутов распространения атак в гиперсетях.
Апробация работы
Результаты работы докладывались на следующих конференциях:
• Конференции молодых ученых ИВМиМГ (2004-2006 гг.)
• Международная научно-практическая конференция "Связь - 2004", (Бишкек, Киргизия, август 2004г.)
• Конференция "Математика и безопасность информационных технологий" (Москва, МГУ, 28-29 октября 2004 года)
• Международная конференция "Проблемы функционирования информационных сетей" (Новосибирск, 31 июля - 3 августа 2006 г.)
• • Международная конференция "Вычислительные технологии в науке,
технике и образовании" (Павлодар, Казахстан, сентябрь 2006г.)
Основные результаты были опубликованы в журналах [43, 75], материалах конференций [42, 65, 64, 66, 68, 79] и трудах ИВМиМГ СО РАН [36, 42, 67).
Структура и объем диссертации
Диссертационная работа состоит из введения, трех глав, заключения. Она содержит 97 страниц машинописного текста, 2 таблицы. В библиогра фию включено 80 наименований.
Автор выражает глубокую признательность Попкову В.К. и Соколовой О.Д. за постановку задач, осуществление научного руководства, Родионову А.С. и Залюбовскому В.В. за ценные замечания, и Ломакину СВ. за данные о структуре и работе информационной сети ИВМиМГ.
. О многослойных моделях информационных сетей
Информационная сеть - это сложный комплекс взаимосвязанных и согласованно функционирующих программных и аппаратных компонентов. Моделирование должно учитывать принципы и механизмы работы таких сетей. Весь комплекс программно-аппаратных средств сети может быть описан многослойной моделью [58].
1. Аппаратный слой стандартизированных компьютерных платформ.
2. Коммуникационное оборудование. Хотя компьютеры и являются центральными элементами обработки данных в сетях, в последнее время не менее важную роль стали играть коммуникационные устройства. Кабельные системы, повторители, мосты, коммутаторы, маршрутизаторы и модульные концентраторы из вспомогательных компонентов сети превратились в основные наряду с компьютерами и системным программным обеспечением, как по влиянию на характеристики сети, так и по стоимости.
3. Операционные системы. От того, какие концепции управления локальными и распределенными ресурсами положены в основу сетевой ОС, зависит эффективность работы всей сети. При проектировании сети важно учитывать, насколько легко данная операционная система может взаимодействовать с другими ОС сети, какой она обеспечи вает уровень безопасности и защищенности данных, до какой степени позволяет наращивать число пользователей, можно ли перенести ее на компьютер другого типа и многие другие соображения.
4 Самый верхний слой сетевых средств образуют различные сетевые приложения, такие как сетевые базы данных, почтовые системы, средства архивирования данных, системы автоматизации коллективной работы и т.д.
Более полной многослойной моделью информационных сетей служит модель OSI (Open System Interconnection), определяющая различные уровни взаимодействия систем [58]: физический уровень, канальный уровень, сетевой уровень, транспортный уровень, сеансовый уровень, представительный уровень, прикладной уровень.
Сети ряда Интернет-провайдеров построены сегодня на основе многоуровневой модели, подразумевающей, что логическая маршрутизируемая IP-сеть функционирует поверх коммутируемой топологии второго уровня (ATM либо Frame Relay) и независимо от нее. Коммутаторы второго уровня обеспечивают высокоскоростные соединения, в то время как IP- маршрутизаторы на периферии сети, связанные друг с другом сетью виртуальных каналов второго уровня, осуществляют интеллектуальную пересылку IP-иакетов. Проблемы, возникающие при таком подходе, связаны со сложностью взаимного отображения двух различных сетевых архитектур друг на друга, которое требует построения и поддержания двух раздельных топологий, адресных пространств, протоколов маршрутизации и сигнализации, алгоритмов резервирования ресурсов. Появление методов многоуровневой коммутации - это один из шагов на пути эволюционного развития сети Интернет в сторону упрощения ее инфраструктуры путем интеграции функций второго (коммутация) и третьего (маршрутизация) уровней [59].
Методы многоуровневой коммутации базируются на двух основных принципах: разделение функций пересылки пакетов и управления этим процессом; пересылка пакетов с использованием последовательных меток.
Механизм виртуальных каналов (virtual circuit или virtual channel) создает в сети устойчивые пути следования трафика через сеть с коммутацией пакетов. Этот механизм учитывает существование в сети потоков данных.
Сеть только обеспечивает возможность передачи трафика вдоль виртуального канала, а какие именно потоки будут передаваться по этим каналам, решают сами конечные узлы. Узел может использовать один и тот же виртуальный канал для передачи всех потоков, которые имеют общие с данным виртуальным каналом конечные точки, или же только части из них. [58]
Технология многоуровневой коммутации позволяет определить модель дифференцированных услуг, т.е. определить ряд механизмов для разделения всего трафика на небольшое число классов обслуживания, например, электронная почта, передача голоса и видео. Таким образом, появляется потребность в многопродуктовой многослойной модели информационной сети.
Соотношение максимального потока и минимального разреза в гиперсетях
Утверждение 2.1. Теорема равенстве величин максимального (s — t) потока и минимального (s — t) разреза в графе, доказанная в [77] не верна для гиперсетей.
Доказательство. В качестве контрпримера на рис. 2.1 приведен пример гиперсети (для простоты показаны только вершины и ребра), в которой величина максимального (s — і) потока не равен величине минимального (s t) разреза. Пусть пропускная способность каждого ребра и ветви равна 2. В качестве вершины s возьмем вершину 6, в качестве вершины t -вершину 3. Величина максимального (s — t) потока равна 3 (по единице в каждой из цепей {(6, 5,4,3)}, {(6,1,2), (2,5,4,3)}, {(6, 5, 2,3)}). В то же время величина минимального (s — t) разреза первичной сети PS равна 4, а величина минимального (s — t) разреза вторичной сети WS равна 6.
Утверждение 2.2. Пусть HS - гиперсетъ, s и t - выделенные вершины. Если \MinCut(HS)\ - минимальный (s — t) разрез гиперсети, а р -максимальный (s — t) поток в гиперсети, то /? \MinCut(HS)\
Доказательство. Из определения минимального разреза гиперсети следует, что: либо \MinCut{HS)\ = \MinCut{PS)\, либо \MinCut(HS)\ = \MinCut(WS)\. Рассмотрим первый случай. Пусть MinCut(PS) минимальный разрез. Из (2.2) следует, что ]Г /(1) J2 = \MmCut(PS)\ rkeF-l{MinCut{PS)) VjEMinCutiPS)
Так как MinCut(PS) - минимальный разрез, то после удаления его ветвей в графе PS не остается ни одного маршрута из вершины s в t. Таким образом, по удаленным ветвям проходил некоторый поток. Итак, р \MinCut{PS)\ = \MinCut(HS)\.
В случае \MinCut{HS)\ = \MinCut(WS)\ можно проделать аналогичные рассуждения, опираясь на ограничения (2.1). Теорема 2.1. Пусть HS = {X, V, R\ Р, F, W) - гиперсеть, s и і - выделенные вершины, р - максимальный (s — t) поток.
Пусть HS = {X,V ,R ;P ,F,W ) гиперсеть: WS С WS, в которой каждое ребро используется для передачи максимального потока; m PS С PS, v3 PS & 3rk Є WSf: v} F{rk).
Если в гиперсети HS Vuj Є І "(ГЙ) 4 = cvj, ft = 1,..., Я, тогда Существует MinCut(PS ) минимальный разрез первичной сети PS , все ветви которого насыщены (то есть неравенство (2.2) превращается в равенство для ветвей минимального разреза), при этом \MinCut{HS )\ = \MinCut(PS )\.
Доказательство. Пусть множество Н = {,г = 1,...,/} такое, что)г = (/з, и г - наибольший поток, который можно пропустить по некоторому маршруту рг из s в t. Построим MinCut(PS ). В начальный момент MinCut(PS ) = 0. Для каждого элемента Н совершим следующие действия:
а) Если , меньше минимальной пропускной способности ребер марш рута рг, существует хотя бы одна насыщенная ветвь, через которую проходит маршрут рг (то есть через эту ветвь может проходить марш рут pt несколько раз, или один или более других маршрутов с потока ми). Действительно, если бы такой ветви не существовало, то через маршрут рг можно было бы пропустить поток больше, чем ,, что противоречит определению множества Б. Найденную насыщенную ветвь включаем в MinCut(PS ). Исключаем из множества 2 все потоки, проходившие через найденную ветвь. Если насыщенных ветвей несколько, то выбираем ту, включение которой приводит в конечном итоге к наименьшему значению MinCut(PS ).
b) Если , равна минимальной пропускной способности ребер маршрута рг и нет насыщенных ветвей, пропускная способность которых больше &, в множество MinCut(PS ) включаем любую ветвь ребра, на котором достигается минимум (по условию теоремы пропускная способность ветви равна пропускной способности ребра, поэтому все ветви ребра насыщены), через которое проходит рг. Исключаем , из множества Хг.
с) Если j равна минимальной пропускной способности ребер маршрута ри но есть насыщенные ветви, пропускная способность которых больше &, в множество MinCut(PS ) включаем насыщенную ветвь, добавление которой приводит к наименьшему значению MinCut(PS ). Итак, MmCut(PS) действительно является минимальным (s — t) разрезом по построению и состоит из насыщенных ветвей. Нетрудно заметить, что \MinCut{HS )\ = \MinCut(PS )\, то есть \MmCut{WS )\ \MinCut{PS% Действительно, в случае b), когда , = $k — ji для соответствующей ветви v3 6 MinCut(PS ) вклад в \MmCut(PS )\ равен вкладу в \MmCut(WS )\ для соответствующего ребра Гк Є рг
В случаях а),с) пусть v3 - ветвь, по которой проходит некоторый поток &. По условию теоремы для каждого ребра г к пропускные способности всех ветвей v}) по которым оно проходит, удовлетворяют условию $к = (Xj 1, причем хотя бы одно ребро впервые участвует в разрезе (по построению). Таким образом, вклад в \MinCut{PS )\ ветви Vj не превосходит вклада описываемых ребер в \MinCut{WS )\.
Итак, \MinCut{WS )\ \MinCut(PS )\, то есть \MtnCut(HS )\ = \MinCut{PS )\. Теорема 2.2. Пусть HS - гиперсетъ, s ut - выделенные вершины, HS - сужение гиперсети HS, определенное в 2.1. Пропускные способности всех ребер и ветвей в HS равны С. Тогда для величины (р максимального (s — t) потока в гиперсети HS верно следующее: V (2.4)
Доказательство. По теореме 2.1 существует минимальный разрез первичной сети PS, все ветви которого насыщены. Пусть MinCut(PS) является таковым. Поток может быть меньше величины минимального разреза, если какой-либо маршрут, по которому посылается поток (или часть потока), несколько раз проходит по ветвям MinCut(PS). Рассмотрим два случая;
Поиск простой (s ~ t) цепи с максимальной пропускной способностью в нестационарной гиперсети
Большинство потоковых задач на нестационарной сети относятся к классу NP - трудных. В работах [S, 13] предлагается ряд подходов и алгоритмов для получения точного и приближенного решений этих задач. К сожалению, эти подходы не всегда остаются действенными при усложнении модели.
В данном разделе для решения задачи поиска простой (з — і) цепи с максимальной пропускной способностью за интервал времени [О, Т] предлагается применить метод ветвей и границ с частичным ветвлением.
Пусть HS[T) = (X, V, R\ Р, Fj W) - гиперсеть, где каждому ребру г Є Я сопоставлены аг(т) 0 - пропускная способность ребра в момент времени т, и тг О - задержка передачи потока по ребру. (В перечисленных параметрах гиперсети можно учитывать аналогичные параметры для ветвей.)
Постановка задачи: Найти в гиперсети HS(r) простую (s - t) цепь р, такую что min(ar( У ту)) - max (2.10) Vr p\r $ r T (2.11) Wr&p
Под обозначением p\r будем понимать часть цепи р до ребра г. Поставленная задача является NP-полной [62].
Как упоминалось выше, алгоритм, предложенный в [8], не подходит для решения поставленной задачи, т.к. предполагает построение расширенной сети (каждому моменту времени соответствует своя копия сети). Применение этого алгоритма к гиперсети приводит к построению гиперсети большой размерности. Поэтому было предложено применить метод ветвей и границ [35].
В качестве допустимых решений будем рассматривать последовательности ВерШИН {s,X2, ,{}. Каждому допустимому решению поставим в соответствие: множество простых цепей Simple {р\р — (s, п, ж2, , П-ь ()} qp - пропускные способности указанных цепей, time(p) - задержки передачи потока по цепям р. Очевидно, что одной последовательности вершин может соответствовать несколько простых цепей. Базовый алгоритм Шаг 1. В начальный момент времени {s} - единственное допустимое решение. Рекорд равен 0. Шаг 2. Пусть {s,Х2,...,хп} - допустимое решение, полученное на некотором этапе {к которому еще не была применена операция ветвления), Simple = {р\р — (e,ri, 2,---, 71-1,)} множество его простых цепей. Ветвление: Пусть хг Є X \ {s,X2,...,хп} и существует хотя бы одно ребро г = (хп,хг) R. Последовательность вершин {s,#2,-. -,xmxt} включается в множество допустимых решений, если существует хотя бы одна простая цепь р := (s, г\, #2,.. -, Ї П-І хПі т, xt), такая что: q p := mm(qp,ar[time{p))) q, time{p ) := time{p) + т(г) Т. Если нет ни одного допустимого решения, к которому можно применить операцию ветвления, то алгоритм заканчивает работу.
Шаг 3. Если хг = t, то в качестве рекорда берем максимум из предыдущего рекорда и q p. Запоминаем допустимое решение и простую цепь на которой был достигнут рекорд. На Шаг 2. Конец.
На рис. 2.13 а) графически показана схема ветвления базового алгоритма для гиперсети с первичной сетью, изображенной на рис. 2.13 Ь) (вторичная сеть соответствует рис. 2.13 а)).
Метод ветвей и границ позволяет найти точное решение, но является переборным алгоритмом и может иметь экспоненциальную сложность. В следующем разделе будет приведено несколько приближенных алгоритмов, основанных на данном методе.
Для сокращения перебора множества допустимых решений и соответствующих им множеств простых цепей, введем выборку по некоторому критерию. В первом алгоритме вводится ограничение на число простых цепей для одного допустимого решения. Во втором алгоритме выборка осуществляется по ребрам,
Пусть к некоторое заданное число (например, некоторая характеристика гиперсети). Изменения вносимые в Базовый алгориетшкасаются только Шага 2 операции ветвления. Алгоритм 1 Ветвление: 1а) Каждому допустимому множеству будем сопоставлять не более к простых цепей, лучших по пропускной способности, где к - заданное число. (Далее в работе алгоритма будут участвовать только они.) lb) Среди простых цепей допустимого множества случайным образом выбирается к цепей, при этом вероятность выбора цепи прямо пропорциональна ее пропускной способности. Алгоритм 2 Ветвление: 2а) В множестве В! = {т = (хп, хг) Є Я ж, Є X \ {s, а?2,..., хп}} выбираются к лучших по пропускной способности ребер, где к - заданное число 2Ь) случайным образом выбирается к ребер (вероятность выбора прямо пропорциональна его пропускной способности)
В данном разделе приведено сравнение результатов работы вышеописанных алгоритмов. Алгоритмы тестировались на случайных гиперсетях с параметрами: Л" — 20, V = 100, jjRj = 500. Задержка передачи потока по ребру - случайное целое число из интервала [1,10]. Вершины 5, t выбирались случайно. Т = 20, к = 5.
Обозначения в таблице 2.2: maxq - максимальная пропускная способность простой цепи, найденная алгоритмом, \Q\ - количество допустимых решений, построенных в процессе работы алгоритма (если количество допустимых решений превышало 1400, то алгоритм прекращал работу).
Приведены численные эксперименты для сравнения разных схем ветвления: базовый алгоритм (обычный метод ветвей и границ), Sort - базовый алгоритм ветвей и границ с сортировкой ребер по убыванию на этапе ветвления, Алгоритмы 1 и 2, для которых в операции ветвления участвует а) только к лучших цепей и ребер, Ь) к случайных цепей и ребер, где к -заданное число.
Моделирование РИВ на сеть на модели нестационарной гипер сети
Пусть HS(T) = (Л", У, R; Р, F, W) нестационарная гиперсеть, где т Є [О, Т] Пусть Т 2. В каждый отрезок времени [р,р+ 1], р = 0,...,Г будем считать гиперсеть стационарной с параметрами: rp+ї рр+1 V«; Є V otj — I aj(T)dT; Vr R 5k := / А(Т)С?Т Итак, в каждый момент времени г — 1,...,71 поток есть сумма трех потоков: 1. Поток (s — t), который считается по описанному в первом разделе модифицированному алгоритму Ф-Ф; 2 Поток из всех вершин (кроме s) в t (открытие буферов); 3. Поток из s во все вершины (кроме t) (заполнение буферов).
Моделирование атак на сеть осуществляется путем изменения пропускной способности первичной сети нестационарной гиперсети.
Постановка задачи: Моделирование изменений поведения величины максимального потока из вершины s в t во вторичной сети WS при условии, что пропускная способность ветвей первичной сети PS изменяется в результате атак на нее.
Рассмотрим два типа атак на первичную сеть: атака типа "червь" и атака типа "взрыв". Моделирование атаки типа "червь": Шаг 1. Пусть атака начата в вершине ж, т := 1; 4 Шаг 2, Из вершины х случайным образом выбирается вершина ш, смеж ная с х (ветвь v3 = (х, w) в первичной сети PS), в которую переходит атака. Пропускная способность а3 (г) атакуемой ветви v3 первичной сети уменьшается на некоторую величину. Шаг 3. х := w, г : г + 1, на шаг 2. Моделирование атаки типа "взрыв": Шаг 1, Пусть атака начата в вершине х, К = [х] - множество атакован-ных вершин, г := 1; Шаг 2. Для каждой вершины к Є К во все, смежные с к, вершины переходит атака. Пропускная способность а3(т) каждой атакуемой ветви v} (инцидентных к) первичной сети уменьшается на некоторую величину. К :=. Шаг 3. В множество К записываем вершины, в которые перешла атака. т := т + І.На шаг 2. Численные результаты моделирования РИВ на нестационарную гиперсеть На рис. 3.2 представлены результаты моделирования поведения максималь ного потока при атаках трех типов: червь, забирающий у ребра ресурс в 3 единицы; две атаки типа взрыв, забирающие у ребра ресурс в 1 едини цу и 0.1 единицы, соответственно. Для сравнения приведен график макси мального потока во времени, при нормальном функционировании сети (без %- атаки).
Моделирование производилось на случайных гиперсетях со следующими параметрами: \Х\ = 20, \V\ = 62, Д = 500, Т = 60, s = 1 и і = 20. Первичная сеть первой гиперсети - случайный граф, первичная сеть второй гиперсети - регулярный граф. В первый момент времени атакована вершина 10. Атака продолжает свое распространение в каждый момент времени. На графике отражено значение максимального потока за интер вал времени [г,т+ 10] Vr Є [0,50]. Ось абсцисс- моменты времени, ось ординат - величина найденного алгоритмами потока.
В предыдущем разделе рассматривалась задача моделирование атаки на гиперсеть, но хотя алгоритм атаки и задавался определенным образом, но все равно присутствовал эффект случайности (в выборе следующей вершины-жертвы). Таким образом, чтобы оценить живучесть гиперсети необходимы множественные численные испытания эксперименты на модели, но даже в этом случае нельзя гарантировать, что нижняя оценка живучесть будет найдена.
В работе [50] рассматривалась задача о "наихудших" стратегиях противника, то есть о наиболее опасных стратегиях РИВ в многопродуктовых сетях. В рамках теории исследования операций вводится векторный критерий оценки качества функционирования (набор значений лексикографически максиминных уровней). Автор рассматривает зависимость гарантированных оценок качества функционирования сети от относительных потерь суммарной пропускной способности ребер многопродуктовой сети,
Интерес представляет не только зависимость оценок качества от потерь пропускной способности ребер, но и случай, когда потери происходят постепенно (во времени) и потеря на следующем шаге зависит от потерь на предыдущем шаге. V, В данном разделе рассмотрим следующую задачу: как должна распространяться атака, чтобы максимальный поток в гиперсети достиг минимума7 Пусть HS{r) = (X, V, R; Р, F, W) - нестационарная гиперсеть, где г = О Т U, . . . , J. .
Пусть s и і выделенные вершины гиперсети, (р{т) - максимальный (s—t) поток, проходящий в момент времени т. Под атакой будем понимать следующее: пусть вначале "заражена" некоторая вершина х; в каждый момент времени атака переходит в любую смежную с х вершину по соединяющей их ветви первичной сети PS; у этой ветви атака забирает часть пропускной способности (возможно всю).
