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

4. ОЦЕНКА ЖИВУЧЕСТИ ИНФОРМАЦИОННОТЕЛЕКОММУНИКАЦИОННЫХ СЕТЕЙ 4.1. Информационная система и оценки живучести

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

[20].

Задачи анализа сетевых структур большой размерности являются NP-сложными и для их решения часто приходится строить отдельную модель, что сказывается на временных и ресурсных затратах. Исследования в данной области ведутся с середины XX века, и выработано множество подходов для моделирования задач живучести. Основные модели:

-Вероятностные полиномиальные процедурные модели расчета;

-Процедурные модели, построенные с искусственной нейронной сети— ИНС;

-Потоковые модели, основанные на критерии допустимости сетевой информационно-телекоммуникационной системы (ИТКС).

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

Так как количество параметров модели велико и, к тому же, может варьироваться в зависимости от используемой

61

модели возникает потребность хранения большого количества данных, т.е. потребность в БД параметрах модели. Кроме того, часто приходится анализировать не только модель самой сетевой структуры, но также и модели чрезвычайных ситуаций (ЧС), при воздействии которых система должна функционировать. ЧС разделяют на внешние и внутренние. Моделирование внутренних рассматривает отказы программных средств, а внешних действия всех ЧС, лежащих вне системы. После параметризации полученные данные по ЧС также нужно хранить в специализированной БД. Ситуация развития сетевой структуры с течением времени приводит к необходимости создания БД готовых решений (или моделей), к которым можно будет вернуться в дальнейшем, не производя параметризацию СИС снова. Информационная СИС (СИС) представляет собой распределенную структуру, размещенную на большой территории. Схема функционирования ее задается с помощью графа, который определяет физическую структуру СИС, его ребра ri соответствуют физическим компонентам информационной СИС (таким, как каналы связи), проложенным от одной вершины графа (узла) Viк другому [20].

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

Если для любых двух вершин графа существует путь (Vi,Vj), то граф называется связным (рисунок 4.1а), в противном случае граф не связан (рисунок 4.1б). Каждое ребро, входящее в вершину или исходящее из нее, называется инцидентным этой вершине. Общее количество ребер d(i),инцидентных вершине, называется степенью вершины. Если граф ориентирован, то различают полустепень исхода d+(i)и захода d-(i).

Сечением по ребрам (рисунок 4.1 в) называют наименьшее количество ребер, удаление которых из графа

62

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

Разбиение множества всех вершин графа на два подмножества называется разрезом по вершинам.

V1 V2=V, (4.1)

Это разбиение определяет разрез по ребрам

где E1 — множество всех ребер, выходящих из вершин V1и входящих в вершины V2.Если элементу графа (ребру, вершине) приписана какая либо физическая величина (например, длина ребра, пропускная способность, задержка обработки информации), эта величина отмечается числом, называемым весом элемента (ребра, вершины) [20].

Рис. 4.1. Примерысвязного(а),несвязного(б)графаи сеченияграфапоребрам(в).

Длина пути между вершинами определяется матрицей расстояний ||Vi,Vj||, выбирается j-й столбец, и суммируются по i все длины ребер, расположенных в столбце. Вершина, расположенная на наименьшем расстоянии от всех остальных вершин, называется медианой графа, медианное расстояние R— радиусом графа. Удаление даже одного ребра увеличивает радиус графа, т.к. в таком случае необходимо отыскать обходной и потому более длинный путь. Таким образом,

63

удаление одного или даже нескольких ребер не всегда уничтожает связность графа. Такое свойство графа носит название живучести.

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

Для обеспечения наибольшей живучести граф должен строиться с наибольшей степенью d(i)всех его вершин, т.е. полный граф, в котором каждая вершина связана ребром с каждой другой вершиной [20].

Число ребер m вычисляется по формуле:

где n- число вершин.

Каждая вершина имеет максимальную степень d = n-1, но на практике не все вершины нуждаются в подобной «защите», подобный усиленный граф нерентабелен. Необходимо создать такой граф из n вершин, чтобы каждая из них имела заданную ей степень Kαi, i =[1,n].

Решение задачи возможно при использовании «сжимающегося множества» чисел. Некоторое множество чисел {K1, …, Kn} при n>1 реализуется в качестве множества степеней вершин ненаправленного графа G c n вершинами и d = k тогда и только тогда, когда {K1, …, Kn} последовательно сжимаема.

Задается n вершин, строится последовательность чисел n- 1 ,n-2,...,1, из которой и выбираются необходимые значения степени d. Построение графа осуществляется

64

последовательным соединением смежных вершин, не превышая при этом их степени.

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

4.2. Процедурные модели вычисления основных графовых характеристик

K-связность как мера живучести СИС.

Неориентированный граф G=(V,R)называется k-связным относительно пары вершин V',V"ϵV, если после удаления любых k-1 ребер обязательно останется путь, соединяющий вершины v',v". Граф Gназывается k-связным, если он является k-связным относительно каждой пары своих вершин. В k-связном графе для любой пары вершин существует не менее К ребернонепересекающихся путей их соединения. Основываясь на этих определениях, можно поставить задачу синтеза графа гарантированной высокой живучести: задан граф G=(V,R),для каждой пары вершин задано целое неотрицательное число K(v',v").Требуется в графе Gнайти подграф, в котором для любой пары узлов v',v”ϵV существует не менее K(v',v")ребернонепересекающихся путей соединения [20].

Живучесть и диаметр графа СИС.

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

65