Содержание к диссертации
Введение
Глава 1. Проблема живучести сетевых информационных систем и ее
изложение в научной литературе
Глава 2. Аналитическое обеспечение информационной системы оценки живучести сетевых информационных систем
2.1. Общее описание информационной системы оценки живучести сетевых структур
2.2. Критерий живучести графа. Максимизация живучести. Условие существования физического графа сетевой информационной системы
2.3. Вычисление общей живучести сетевой информационной системы в полиномиальной форме
2.4. Оценка живучести сетевых информационных систем с использованием модели искусственной нейронной сети
2.5. Потоковая модель живучести сетевой информационной системы
2.5.1. Исследование живучести стохастической сетевой информационной системы
2.5.2. Описание потоковой модели сетевой информационной системы
2.5.3. Организация нормативного потока
Выводы по главе 2
Глава 3. Процедурное обеспечение информационной системы оценки живучести сетевых информационных систем
3.1. Описание блока анализа сетевой структуры
3.2. Процедурные модели оценки живучести сетевых информационных систем
3.3. Анализ сетевой информационной системы на основе модели мп-сети 119
3.3.1. Задача выбора пропускных способностей 123
Процедурная модель выбора пропускных способностей для
3.3.2. дискретных пропускных способностей 124
3.3.3. Комбинаторная задача выбора пропускных способностей и распределения потоков. Постановка задачи 126
3.3.4. Обобщенная задача вычисления пропускных способностей и распределения потоков 127
3.3.5. Процедурная модель нахождения кратчайших путей и расчёта объемов суммарной передачи информации (трафиков) 128
3.4. Построение графика уязвимости 133
3.5. Процедурная модель анализа уязвимости сетевой информационной системы 137
3.6. Поиск гарантированного уровня допустимости сетевой
информационной системы 146
3 7 Синтез сетевой информационной системы с гарантией живучести. Построение по критерию допустимости 149
Выводы по главе 3 155
Глава 4. Построение информационной системы оценки живучести сетевых информационных систем 158
4.1. Общее описание информационной системы оценки живучести сетевых информационных систем 159
4.2. Описание информационного обеспечения . 161
4.3. Описание программного обеспечения. 169
4.3.1. Общее программное обеспечение 169
4.3.2. Специальное программное обеспечение 172
4.3.3. Описание лингвистического обеспечения 174
Выводы по главе
Заключение
Библиография
- Критерий живучести графа. Максимизация живучести. Условие существования физического графа сетевой информационной системы
- Исследование живучести стохастической сетевой информационной системы
- Процедурные модели оценки живучести сетевых информационных систем
- Описание информационного обеспечения
Введение к работе
Глава 1. Проблема живучести сетевых информационных систем и ее
изложение в научной литературе Глава 2. Аналитическое обеспечение информационной системы
оценки живучести сетевых информационных систем
2.1.
Общее описание информационной системы оценки
живучести сетевых структур
2.2.
Критерий живучести графа. Максимизация живучести.
Условие существования физического графа сетевой
информационной системы
2.3.
Вычисление общей живучести сетевой информационной системы в полиномиальной форме
2.4.
Оценка живучести сетевых информационных систем с использованием модели искусственной нейронной сети 2.5. Потоковая модель живучести сетевой информационной системы
Исследование живучести стохастической сетевой информационной системы
Описание потоковой модели сетевой информационной системы
2.5.3. Организация нормативного потока
Выводы по главе 2
Критерий живучести графа. Максимизация живучести. Условие существования физического графа сетевой информационной системы
При разработке ИСЖС одной из главных ставилась задача возможности легкой адаптации ИС под различные программные платформы. Для решения данной задачи необходимо выбрать среду разработки основных модулей ИСЖС.
В качестве такой среды был выбран программный комплекс Lazarus, основанный на среде разработки (IDE) Free Pascal Project (FPP). Основными достоинствами данного решения являются наличие средств сборки ПО как под программную платформу Microsoft Windows, так и под программные платформы семейства nix (семейство ОС Unix - BSDUnix, FreeBSD, Solaris, IBM AX, HP UX, MacOS X, SGI Irix и ряда других свободно распространяемых и коммерческих ОС, а также многочисленное семейство ОС Linux) и наличие большого количества компонент для создания графических пользовательских интерфейсов для рассматриваемых программных платформ.
Использование собственного компилятора IDE FPP при сборке модулей позволяет также решить вопрос выбора аппаратной платформы для функционирования пользовательской и администраторской частей ИСЖС, так как при сборке модулей, отвечающих за выбор моделей оценки живучести СИС и собственно проводящих оценку живучести, автоматически будет включено использование только тех функций аппаратной платформы, под которую и производится сборка ПО. В остальном же выбор и ограничения, налагаемые на ТО, зависят только от тех требований, которые предъявляются к техническому обеспечению со стороны программной платформы.
В качестве информационного обеспечения выбрана СУБД Oracle 10, на основании которой произведено построение СЗ. Основные соображения для выбора данной СУБД являются такими же, как и для выбора программной платформы для функционирования ИСЖС, т.е. кроссплатформенность СУБД. Кроме того, данная СУБД используется ведущими компаниями в различных отраслях промышленности, для создания ERP, CRM и так называемых биллинговых систем (автоматизированных расчетных систем, АСР) такими лидерами мирового рынка как IBM, Hewlett-Packard, Schlumberger Sema, Amdox и Telesens KSCL, что облегчает интеграцию ИСЖС и указанных выше систем.
Основываясь на выборе ПО и ИО, в качестве лингвистического обеспечения выбран язык обработки данных SQL.
Взаимодействие пользователя с подсистемами осуществляется посредством специализированного языка взаимодействия ИС и пользователя, который организован в виде диалога с пользователем, включая в себя следующие виды диалога: «Окно», «Меню» и «Заполнение бланков». МеО для ИСЖС состоит из руководств системных администраторов, разработчиков ПО и пользователей того технического, программного и информационного обеспечения, которое используется для функционирования ИСЖС в каждом конкретном случае.
Использование при проектировании СИС ИСЖС позволяет: 1. найти оптимальные параметры исследуемой (или проектируемой) СИС; 2. проводить анализ информации на любой из стадий проектирования; 3. проводить имитационное моделирование изменения структуры СИС, находящихся под воздействием внешних НФ на ЭВМ с последующей визуализацией результатов моделирования; хранить большое количество вариантов параметров (таких как распределение потоков по ребрам графа СИС, пропускная способность ребер и пр.) в памяти ЭВМ и быстро выбирать из них нужные на всех стадиях проектирования: расчете оптимальных параметров, создание документации и т.д.
Разработанная ИСЖС является инструментом для проектирования и исследования сетевых информационных систем (в том числе опорных, транспортных сетей) в первую очередь в сфере предоставления услуг связи, а также для энергетической, транспортной и других отраслей промышленности
В заключении сформулированы основные результаты работы. Публикации. По теме диссертации опубликовано 18 работ, из них 8 в изданиях, рекомендованных ВАК РФ.
Объем и структура работы. Диссертация, общий объем которой составляет 215 страниц (основной текст - 180 страниц) состоит из введения, четырех глав, заключения, списка использованной научной литературы, содержащего 272 наименования научных трудов на русском и иностранном языках. Диссертация содержит 52 иллюстраций и 3 таблицы.
Исследование живучести стохастической сетевой информационной системы
Киоко Секине (Kyoko Sekine) и Хироши Имаи (Hiroshi Imai) Департамента Информационных наук Токийского университета предложили процедурную модель расчета живучести многополюсной СИС через полином Татта (Tutte polynomial) для любого графа с максимум 14 вершинами и v2; = 91 ребрами (полный граф), а также для планарного графа, например, решетчатого графа 12 х 12, содержащего 144 вершины и 264 ребра.
Сама по себе живучесть ИС исследовалась на протяжении долгого времени (например, см. [24, 225]), и рассматривалось много видов живучести, а также процедурные модели для их расчета. Учитывая, что расчет живучести СИС — NP-сложная задача [26], поэтому интенсивно исследовалась приблизительная процедурная модель расчета верхнего и нижнего предела живучести СИС [25].
Пусть G=(V,E) - простой, связный, неориентированный граф с количеством вершин V и количеством ребер Е. Рассмотрим СИС (граф) G={V,E). Каноническая живучесть многополюсной СИС R(G;p) определяется как вероятность того, что G останется связным после того, как каждое ребро будет удалено с одинаковой вероятностью р. R (G; p) можно рассчитать с помощью перечисления остовов G. На практике это тесно связано с полиномом Татта, который является инвариантом в теории графов. Полином Татта графа G — это полином с двумя переменными T(G;x,y), рассчитываемый по формуле (2.4): T(G;x,y) = 5 - \у -Р \у - 1)И-/ . (2 6) АсЕ где р: 2 —» Z — это ранговая функция графа G. Это значит, что р(А) это ранг подграфа G = (V(A),A): количество вершин, V(A), минус количество связных компонентов G .
Исходя из определения полинома Татта, его значения в определенных точках будут следующими: T(G; 1,1) рассчитывает количество остовных деревьев G, которое вычисляется полиномиально. T(G; 2,1) рассчитывает количество лесов G, которое NP-сложно для вычисления. T(G; 1,2) рассчитывает количество остовов G, которое также NP-сложно для вычисления.
Чтобы получить информацию о других смыслах и множестве вариантов применения полинома Татта см. [23, 24].
Связь между канонической живучестью СИС и полиномом Татта рассчитывается по формуле:
Здесь, для ребра еаЕ, мы обозначаем с помощью G\e граф, получаемый удалением е из G, а с помощью Gle - граф, получаемый контрактацией е из G. Петля - это ребро, соединяющее одну и ту же вершину, а копетля — это ребро, удаление которого уменьшает ранг графа на 1. По определению, полином Татта для петли - это у, а для копетли - х. Полином Татта для пустого графа равен 1.
Общая живучесть информационной сие в полиномиальной форме
Пусть р{е) - заданная вероятность удаления ребра є є Е. Тогда общая живучесть СИС определяется как вероятность того, что граф останется связным после того, как каждое ребро е будет удалено с вероятностью р{е). Эта живучесть будет просто определяться как R(G).
В этом общем случае мы не находим никакой связи с полиномом Татта. Тем не менее, его все-таки можно рассчитать перечислением остовов. Тогда, в виде полинома Татта будет использоваться следующая формула удаления/контракции ребра.
Процесс расчета с использованием формулы (2.9) может быть представлен в виде двоичного дерева, в котором корень соответствует начальному графу G, и у каждого предка есть максимум два потомка. Узлы в этом двоичном дереве соответствуют минорам G. Здесь граф, получаемый из G путем удаления и контракции ребер, называется минором G. Для каждого маршрута от корня к конечной вершине, ряд контрактированных ребер однозначно соответствует остовному дереву G. Тогда количество листьев равно количеству остовных деревьев.
Более того, для каждого маршрута ребра, состоящие из удаленных петель, соответствуют внешне активным ребрам соответствующего остовного дерева. Здесь мы говорим, что ер с концевыми вершинами а и Ъ, является внешне активным для остовного дерева Т, если для каждого ек, которое является ребром в простом маршруте в Т, соединяющим а и Ь, выполняется условие, что k j [26]. Например, для графа на рис. 1.5 ребра е4, е5 и е-] являются внешне активными для остовного дерева {е\, е2, ез, е6}. Мы можем перечислить остовы путем прибавления внешне активных ребер для каждого остовного дерева. Так как р(еу)+(1-р(е,))=1, то, согласно вышеуказанной рекурсивной формуле, оба случая (удаление е,- и не удаление ej) суммируются для каждого внешне активного ребра е,-.
Процедурные модели оценки живучести сетевых информационных систем
В СЗ данные о СИС хранятся в виде реальных значений (пропускная способность каналов, размерность и топология графа, информация о возможном воздействии НФ на систему и т.д.), работа с которыми (например выбор топологии, от которого зависит выбор процедурной модели расчета) аналитическими методам сложна. Решение класса подобных задач было предложено в работе [260] с помощью лингвистических переменных и нечетких множеств и в дальнейшем продолжено в работах [261, 262]. Для создания логико-лингвистической модели необходимо задать набор некоторых правил, содержащих в своем составе логические термы. Так как логико-лингвистические модели работают с набором нечетких множеств, реальные переменные из БД№1-№№ СЗ (четкие значения) нужно привести к нечеткому виду. Данная процедура называется процедурой фаззификации (fuzzification,OT англ. fuzzy — нечеткий) и описана в работах авторов [262]. После этого из набора нечетких значений необходимо составить некоторые правила, исходя из которых и будет определяться выбор процедурной модели расчета СИС. Для этого рассмотрим процедурную модель составления правил, содержащую следующие компоненты:
1. Компонент фаззификации. Данный компонент процедурной модели работает с четкими значениями из БД СЗ. В теории нечетких множеств нечеткое подмножество предметной области U описывается функцией принадлежности вида V(F):U- [0,1], представляющее из себя
степень принадлежности /ue\J принадлежащего множеству V. Нечеткая лингвистическая переменная V является атрибутом, домен которого содержит лингвистические значения для нечетких подмножеств [263]. Реальные значения переводятся в лингвистические переменные, например, размерность графа СИС в лингвистических переменных может быть записана как: Размерность. Количество_вершин. Малое (S), Размерность. Количество_вершин. Среднее (М) и Размерность. Количество_вершин. Большое (L). Функция принадлежности для данных нечетких множеств представлена на рисунке 3.1. Пределы каждого терма определены с использованием гладкой гистограммы четких значений по работе авторов [264].
Компонент анализа. Данный компонент используется для анализа уровня доверительной вероятности (Рс) конъюнкции различных значений в БД. Значения в заданной БД делятся на N атрибутов предсказания и один целевой атрибут (класс). Каждый атрибут описан переменной Al(i = \,2,...,N) и различными вероятностными значениями ПІІ для атрибута А -Vjj(j = 1,2,..,,тг), каждый целевой атрибут делится на К классов и описан переменной classk{k = 1,2,...,К). Глубина уровня поиска возможных значений описана переменной /eve/, (і 1 N -1). Таким образом компонента анализа выделяет конъюнкции значения(значений) удовлетворяющих условию Рс = 1. Поиск начинается с пустого набора данных test_set и множества S. Каждый раз конкретное значение Vy добавляется в множество S и отвечает условной вероятности, вычисляется P[S\classk). Таким образом условная вероятность Рс для множества S и classk представлено термом P[S\classk). Если P[S\classk) = 1, тогда создаем правило включающее значение множества S, принадлежащее также classk и не создающее конъюнкции с остальными оставшимися элементами множества S. Таким образом мы сокращаем время поиска в процедурной модели.
Если P\S\classk )= 1, тогда модифицируем S, добавляя другое значение из оставшихся атрибутов и проверяем условную вероятность Рс. Добавление новых значений в S ограничено количеством условий в правиле, АГ-1.
3. Компонент очистки. Данный компонент «очищает» выделенные правила в течение трех уровней. 3.1. На первом уровне происходит удаление избыточных (повторяющихся) правил. 3.2. На втором уровне происходит суммирование правил, состоящих из одинаковых атрибутов но содержащих различные значения. Например: (IF А1 is vll THEN Classl) AND (IF Al is vl3 THEN Classl), Суммирующее правило будет иметь следующий вид: IF Al is vl 1 vvl3 THEN Classl 3.3. На третьем уровне отбрасываются правила, уровень точности которых ниже специфичного граничного уровня точности. Это необходимо по следующим причинам: 3.3.1. поиск на всем множестве конъюнкций реальных значений в БД СЗ может потребовать значительных ресурсов и времени; 3.3.2. Если процедурная модель выполняет поиск по нижней границе уровня доверительной вероятности Рс, количество индуцированных правил может быть огромным, и соответственно комбинаторно сложным для дальнейших вычислений. 3.3.3. Если поиск процедурной моделью ведется на высоком уровне точности и отбрасывает значения правил с низким уровнем точности, то полученный набор правил может быть бесполезен для предсказания класса скрытых наборов и создавать обобщения.
Схема процедурной модели индукции правил для блока анализа исходных данных представлена на рисунке 3.2.
С помощью данной процедурной модели был создан набор следующих правил: Топологии (графа СИС): 1. Радиальная 2. Радиально-кольцевая 3. Сетчатая 4. 2полюсная полная 5. Древовидная 6. Гибридная
Описание информационного обеспечения
Условные стоимости передачи одного пакета (кадра) информации С і-. 2. Матрица требований в передаче информации \Щ ПРОЦЕДУРНАЯ МОДЕЛЬ РЕШЕНИЯ ВПС РП. Предложенная процедурная модель использует многократное решение комбинации задач ВПС РП. Он состоит из начального этапа и конечного числа однотипных итераций Начальный этап.
1. В качестве метрики L = [/ j используем длины всех каналов связи.
2. Определяем кратчайшие пути в СИС с выбранной метрикой nfn и находим начальный поток Л = [ЛгJ по кратчайшим путям.
3. Решаем задачу ВПС по критерию min Су, при ограничении Рсд([аге}) рД и находим начальные пропускные способности всех каналов связи {/4}. Переходим к 1-ой итерации. Пусть уже проведено к итераций и найден некоторый поток в СИС А(к) = [Лп(к)] и соответствующие ему пропускные способности всех каналов jUrs(k),(r,s)eE. (к+1)-я итерация.
1. Решаем задачу РП при заданных пропускных способностях {jurs(k)}n находим такое распределение потоков A(A: + l) = [;i5(& + l)J, которое обеспечивает max Рсд {лГ5 (к + і)).
2. При новом распределении потоков Л0(& +1) решаем задачу ВПС по критерию min Cs({//„( +1)}) при ограничении Рсд {{urs (к + l)}/L„ (к +1)) Рз и находим новые оптимальные значения пропускных способностей всех каналов связи \jurs(k +1)}.
3. Вычисляем новое значение критерия Cs( + l) = C„(//„(Ar+l),/„). Сравниваем Cs (к +1) и С (к). Если CZ (к) - С2 ( +1) , то переходим к шагу 1 (к+1)-ой итерации, иначе конец работы процедурной модели. Распределение потоков А(к + \) = [Я„(& + 1)] и пропускные способности /лк(к +1), (г,s) є JE найдены.
В процессе работы процедурных моделей ВПС РП и нахождения максимального потока в СИС при отказах многократно используется процедурная модель нахождения кратчайших путей и расчёта информационных потоков (трафиков) в многосвязной СИС.
Пусть имеем многосвязную СИС, которая задана в виде графа G(X, Е), где Х = {Х7} - множество вершин графа, Е = {(/,/)} - множество его ребер.
Будем считать, что при нескольких маршрутах передачи информации от х{ к Xj она всегда передаётся по пути минимальной стоимости.
Необходимо рассчитать параметры СИС G (X, Е): такие маршруты передачи информации и информационные потоки в каждом канале frs, (r,s) є Е,при которых общая стоимость информации будет минимальной, при этом задана матрица требований Н = h Исходные данные: Матрица смежности В = \\bijj ,где: 1, если х. смежна с х Ь,= 4 0, в другом случае Матрица удельных стоимостей передачи информации С = В процессе работы процедурной модели используются такие рабочие матрицы: а; А = — матрица удельных стоимостей передачи информации из xt в ТП; Xj по пути минимальной стоимости я-" (если Ъу=\,то ajj=Cy), М = матрица минимальных маршрутов nfn по СИС, где ту=г — вершина, смежная с Xj на пути 7Г т, F = /у - искомая матрица информационных потоков (или трафиков) в СИС, где fy - суммарный трафик, который передаётся по каналу связи (ij).
Процедурная модель состоит из конечного числа однотипных итераций, в ходе которых строят и уточняют матрицы А(к), M(k). 1-я итерация. и7 и оо, в другом случае. с , если Ъ = 1, 1. Определяем матрицу А{\) = ау :ац(\) = 2. Заполняем матрицу маршрутов М(1), в соответствии с соотношением т (1) = /, если btj = 1, О, в другом случае. Таким образом в результате 1-ой итерации рассчитаны характеристики СИС для маршрутов длины 1. 2-я итерация.
Определяем минимальные маршруты длиной / =2 и рассчитываем А (2), М(2). 1. Просматриваем і-тую строку матрицы А(1),і=1,2... и определяем я„(2) = тш{а,,(1) + ау(1)} ац(1) (3.30) 2. Если Яу(1) = 2у(2),то Шу(2) =7щ(1) и приравнивая у =j+1,переходим к рассмотрению следующего элемента і-той строки.
