Материал: Теория сетевых войн. Живучесть атакуемых сетей. учеб. пособие. Остапенко А.Г., Калашников А.О

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

Пусть в графе G найдены L{V’, V”} -длины кратчайших путей между всеми парами вершин V’, V” ϵV. Тогда величину Lназывают диаметром графа.

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

Обобщенное понятие диаметра

где х,у —произвольные точки на ребрах графа информационной СИС, а р(х,у)- длина пути в графе между этими точками [20].

Условная связность.

Вершины графа СИС считаются связными, если длина соединяющего их пути не превосходит заданной величины. Например, граф G считается условно связным, если удаление некоторого минимального числа ребер (вершин) оставляет в образовавшихся компонентах присущие исходному графу свойства: планарность, двудольность, заданную степень вершин, и т.д. если критерием связности положить минимальное число ребер, удаление которых в каждой компоненте оставляет некоторое N0 число вершин [20].

обеспечивающих эту живучесть, т.е. проблема стойкости. Стойкость численно равна наименьшей средней стоимости создания новой компоненты связности. Если стойкость графа C(g) ≥C0, то граф содержит не менее C0 ребернонепересекающихся остовных деревьев [20].

Вычисление плотности графа.

Пусть граф G'=(V',R') - подграф графа G. Плотностью p(G') подграфа G'называется отношение мощности множества его ребер к мощности множества его вершин:

Плотные графы являются менее уязвимыми [20].

Сечение и разрез.

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

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

67

задается наихудшим состоянием разрушения графа. При удалении ребер одна из вершин графа оказывается в изоляции, однако, если ее заранее объединить с какой-либо устойчивой вершиной, связность графа удастся сохранить. Продолжая далее этот часто употребляемый прием удаления и контракции ребер, сводят исходный граф G к петле. Если всем удалениям ребер обозначить одинаковую вероятность удаления р, то контракция их будет иметь вероятность q=l-p. В результате совокупности всех таких действий создается многочлен из произведений р и q различной степени. Численное значение такого многочлена при заданном значении р принимают за критерий живучести R(G)графа G [20[.

Верхний предел живучести СИС.

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

По определению Кmизоморфен Un-1, 1.

Формула соответствует рекурсивному применению формулы удаления/контракции ко всем ребрам, примыкающим к vи объединяющим все изоморфные миноры. Например, применим формулу удаления/контракции к n-1 ребрам, которые инцидентны вершине Кn. Как и в предыдущей процедурной модели, если мы объединим изоморфные миноры с одинаковым расположением ребер, то получим 2(n-1)-n+1 неизоморфных миноров. Однако эта формула предполагает дальнейшее объединение изоморфных миноров с различным расположением ребер. В этом случае мы получаем, что есть только n-1 неизоморфных миноров.

68

получаем из расчета всех T(Uj,k; х,у), таких, что j + k<n-

1[20].

4.3.Потоковая модель исследования живучести

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

[20].

При решении задач анализа стохастического графа определяют:

1.Вероятность распадения исходного графа на р компонентов; как правило, отыскивается вероятность того, что стохастический граф связан Р(р= 1))

2.Вероятность р существования ребра или вершин;

3.Вероятность принадлежности двух вершин одной

компоненте;

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

Структура случайного графа описывается множеством вершин {V0,Vn} и множеством элементарных ситуаций {ɛij};i,j= 1...n,где ɛijопределяет событие, состоящее в наличии или отсутствии связи между вершинами Viи Vjчерез ребро {Vi, Vj}.

Определяется вероятность (или распределение вероятностей, если случайные события не являются независимыми) p(ɛij). Если события независимы и

69

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

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

Пусть Qi- событие, состоящее в том, что не существует поврежденных ребер, инцидентных Vi. Объединение событий {Qi},i= 1..n есть событие, что одна вершина графа не имеет поврежденных ребер. Дополнительным событием поэтому служит следующее: каждая вершина имеет, по крайней мере, одно существующее инцидентное ребро [20].

Рис. 4.2. Общая живучесть для d=2, d=3, d=8

Для решетчатых структур общая живучесть определяется

(рис.4.3):

70