Содержание к диссертации
Введение
1 Анализ решения задачи распределения потоков в сетевых информационных системах 13
1.1 Оценка информационной эффективности сетевых информационных систем 14
1.1.1 Подходы к оценке информационной эффективности на основе вероятностных показателей 15
1.1.2 Оценка информационной эффективности на основе обобщенного параметра кибернетическая мощность сетевой информационной системы 18
1.2 Анализ задач распределения информационных потоков в сетевой информационной системе 19
1.2.1 Анализ задач распределения информационных потоков на основе алгоритмов на графах 22
1.2.2 Анализ задач распределения информационных потоков на основе потоковой модели
1.2.3 Распределение информационных потоков на основе использования потоковой ситуации и топологии сети 33
1.2.4 Тензорный подход и использование кибернетической мощности информационной сети для решения задачи распределения информационных потоков 36
1.3 Сравнительный анализ алгоритмов распределения
информационных потоков данных 40
1.4 Определение вероятности связи между узлами для задания k связности сетевой информационной системы при случайных топологиях 41
1.5 Выводы по первой главе 43
2 Процедуры распределения информационных потоков на основе кибернетической мощности информационной сети 45
2.1 Оценка информационной эффективности модели идеальной сетевой информационной системы 46
2.2 Задача распределения информационных потоков с использованием метрики на основе применения кибернетической мощности информационной сети 50
2.3 Процедуры распределения информационных потоков на
основе параметра кибернетической мощности информационной сети 54
2.3.1 Процедура распределения информационных потоков на основе кибернетической мощности путевой цепи 56
2.3.2 Процедура распределения информационных потоков на основе кибернетической мощности зон нагрузки 2.4 Процедура отклонения входных информационных потоков 65
2.5 Выводы по второй главе 67
3 Процедурная модель и анализ информационной эффективности сетевой информационной системы 68
3.1 Процедурная модель сетевой информационной системы 68
3.2 Особенности реализации процедурной модели сетевой информационной системы 70
3.2.1 Формирование топологии сетевой информационной системы 70
3.2.2 Формирование входных информационных потоков 75
3.2.3 Обслуживание пакетов в узлах коммутации 76
3.2.4 Передача информационных пакетов в сетевой информационной системе 77
3.2.5 Характеристика параметров оценки информационной эффективности сетевой информационной системы 79
3.2.6 Определение кратчайших путей в сетевой информационной системе 82
3.3 Анализ результатов моделирования 85
3.4 Рекомендации по применению процедур распределения информационных потоков на основе применения кибернетической мощности информационной сети 100
3.5 Выводы по третьей главе 103
Заключение 104
Список литературы 106
- Подходы к оценке информационной эффективности на основе вероятностных показателей
- Анализ задач распределения информационных потоков на основе потоковой модели
- Задача распределения информационных потоков с использованием метрики на основе применения кибернетической мощности информационной сети
- Передача информационных пакетов в сетевой информационной системе
Введение к работе
Актуальность темы исследования. В условиях высоких темпов информатизации общества и роста рынка инфокоммуникационных услуг особое место среди задач оптимизации работы сетевых информационных систем (СИС) занимают те, которые направлены на повышение эффективности работы СИС. Они предусматривают разработку и применение как программного обеспечения, реализующего средства и способы сбора, передачи, хранения, обработки и представления информации, так и новых протоколов прикладной направленности, что позволяет повысить качество работы СИС. Принципы организации функционирования СИС на основе распределения информационных потоков являются важным инструментом, с помощью которого достигается желаемый результат для СИС в указанном смысле.
Информационная эффективность СИС оценивается вероятностно-временными характеристиками, в том числе: производительностью СИС, средней или в виде ограничения временной задержкой передаваемых пакетов (фиксированный набор данных в виде передаваемого объекта в СИС), информационными потерями. Наряду с указанными показателями, в ряде опубликованных работ используется обобщенный параметр «Кибернетическая мощность информационной сети», который позволяет одновременно учитывать передающие и накопительные возможности СИС при наличии ограничения на время доведения пакета данных. В результате применения модели идеальной СИС также введен показатель информационной эффективности – «КПД информационной сети в смысле передачи информации». В связи с особенностью использования этих величин, в условиях повышенной нагрузки СИС, в силу одновременного учета хранимого и передаваемого количества информации, их использование при распределении информационных потоков является актуальной задачей.
Степень разработанности темы. Решение и практическая реализация задач распределения потоков в информационных сетях является важной составной частью их организационного построения. Особую значимость в развитии теории и практики этого направления внесли: Л. Клейнрок, Д. Бертсекас, Р. Галлагер, М. Шварц, Б. Я. Советов, С. А. Яковлев, Б. С. Цыбаков, В. Г. Лазарев, Г. П. Захаров, А. П. Кулешов, И. А. Мизин, В. А. Богатырев, А. Н. Шаров. Развитие теории анализа сложных систем на основе тензорной методологии Г. Крона получило в трудах А. Е. Петрова (он также показал методом моделирования инвариантность мощности системы), а ее применение для информационных систем, находящихся в стационарном состоянии, – в работах М. Н. Петрова, Ю. Ю. Громова, И. И. Пасечникова, А. М. Межуева и др. Особенностью тензорной методологии Г. Крона является возможность совмещения непрерывных процессов, протекающих в структуре, с дискретной структурой системы на основе ее формулы поведения. В качестве инварианта преобразования служит полная мощность. Введенный применительно к информационной системе параметр «Мощность» (И. И. Пасечников, Т. Я. Гораздовский), названный кибернетическим параметром – «Кибернетическая мощность информационной сети», имеет обобщенное свойство учета ко- и контравариантного характеров
количественной меры информации и определяет в информационном пространстве изменения состояний информационной сети. Рассматриваемый кибернетический параметр позволяет не только создавать новые подходы к анализу СИС, но и с использованием показателя «Коэффициент полезного действия в смысле передачи информации» оценивать информационную эффективность СИС, показывающую степень близости к идеальности в смысле передачи информации с учетом ее хранения в элементах системы.
В связи с указанным, практической задачей исследования является расчет оценки информационной эффективности СИС на основе применения кибернетической мощности СИС при вычислении КПД СИС в смысле передачи информации и использования в процедурах распределения информационных потоков. Научная задача работы состоит в разработке моделей описания и оценки информационных ресурсов СИС, процедур распределения информационных потоков СИС, находящейся в стационарном состоянии, с использованием параметра «Кибернетическая мощность информационной сети» в условиях высокой нагрузки на СИС.
Объект исследования: сетевые информационные системы (СИС).
Предмет исследования: модель зоны нагрузки СИС, процедуры распределения информационных потоков СИС.
Цель работы: повышение информационной эффективности СИС в условиях высокой информационной нагрузки с помощью разработанной модели зоны нагрузки и усовершенствованных процедур распределения информационных потоков.
Для достижения цели требуется решение следующих задач:
– провести анализ задачи распределения информационных потоков в СИС в целях определения особенностей ее решения, условий применения и оптимизации;
– разработать процедуру распределения информационных потоков в СИС на основе применения кибернетической мощности путевой цепи;
– разработать модель зоны нагрузки и процедуру распределения информационных потоков в СИС на основе применения кибернетической мощности зон нагрузки;
– разработать процедуру отклонения и перераспределения входных информационных потоков, использующую в расчетах ограничение на временную задержку пакетов;
– разработать процедурную модель СИС и на ее основе провести анализ информационной эффективности СИС при применении исследуемых процедур распределения информационных потоков, выработать рекомендации по их использованию.
Методы исследования. При решении задач исследования использовались методы статической теории систем, теории систем массового обслуживания, информации, графов и аналогий. Применен метод исследования информационных систем на основе имитационного моделирования с использованием языка программирования С++. Общей методологической основой исследования является системный подход.
Научная новизна:
-
Построена модель зоны нагрузки участка СИС, отличающаяся применением суммарной кибернетической мощности для оценки путевой цепи и определяемая топологической структурой СИС.
-
Разработана процедура распределения информационных потоков в сетевой информационной системе, отличающаяся применением метрики, основанной на использовании кибернетической мощности элементарных составляющих СИС.
-
Разработана процедура распределения информационных потоков в сетевой информационной системе, отличающаяся применением метрики на основе кибернетической мощности зон нагрузки.
-
Разработана процедура отклонения и перераспределения входных информационных потоков СИС, отличающаяся использованием процедур распределения потоков на основе применения значений кибернетической мощности участков СИС.
Теоретическая и практическая значимость работы.
-
Применена метрика на основе параметра «Кибернетическая мощность информационной сети» при решении задач распределения информационных потоков в СИС.
-
Разработаны процедуры распределения информационных потоков на основе кибернетического параметра.
-
На основе моделирования получены количественные значения оценки качества функционирования СИС, подтверждающие повышение ее КПД в смысле передачи информации на 8% при применении процедур распределения информационных потоков на основе кибернетического параметра в условиях повышенной информационной нагрузки.
-
Практическая значимость заключается в использовании полученных программных реализаций, разработанных моделей и процедур для исследования информационной эффективности СИС.
Положения, выносимые на защиту.
-
Модель зоны нагрузки, определяемая для элементарного участка путевой цепи СИС.
-
Процедура распределения информационных потоков СИС на основе кибернетической мощности путевой цепи.
-
Процедура распределения информационных потоков СИС на основе кибернетической мощности зон нагрузки.
Внедрение результатов исследования. Результаты диссертационной работы внедрены в учебный процесс кафедры общей физики ФГБОУ ВПО «ТГУ им. Г. Р. Державина».
Степень достоверности и апробация результатов. Достоверность результатов основана на корректном применении методов математического моделирования дискретных систем и математической статистики путем использования статистического усреднения полученных результатов и многократного машинного моделирования с последующим усреднением, а также на результа-
тах имитационных исследований, подтверждающих повышение информационной эффективности СИС вследствие применения разработанных моделей и процедур, совпадения характера изменений результатов при различных входных информационных нагрузках с результатами других авторов.
Материалы диссертации докладывались на XXI Международной научно-практической конференции «Радиолакация, навигация, связь» RLNC 2015 14 – 16 апреля 2015 г. (г. Воронеж), на конференции «Современное состояние и перспективы развития технических наук», секция Радиотехника и связь 2015 г. (г. Уфа).
Соответствие паспорту специальности. Диссертационная работа соответствует п. 1 «Методы и модели описания, оценки, оптимизации информационных процессов и информационных ресурсов, а также средства анализа и выявления закономерностей в информационных потоках. Когнитивные модели информационных систем, ориентированных на человекомашинное взаимодействие» паспорта специальности 05.25.05 «Информационные системы и процессы».
Публикации. Результаты диссертационной работы отражены в 9 публикациях, в том числе в 6 статьях в научных журналах, рекомендованных ВАК при Минобрнауки РФ.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Работа изложена на 119 страницах машинописного текста, включает 35 рисунков, 3 таблицы, список литературы из 111 наименований, 1 приложение.
Подходы к оценке информационной эффективности на основе вероятностных показателей
В общем случае эффективность функционирования СИС определяется совокупностью показателей, отражающих существенные свойства информационных процессов, протекающих в ней, а также характеристики элементов СИС, реализующих эти процессы. Составными компонентами вектора эффективности СИС 3n(t) являются векторы показателей качества функционирования 3K(t) , системных показателей 3c(t) и эксплуатационных показателей 33(t) [107]. Последние в свою очередь функционально зависят от множеств параметров среды Zc(t)и потоковой обстановки в сети An(t), а также множества используемых алгоритмов распределения информационных потоков (маршрутизации) A(t) , вида сигналов Sc(t)и структуры кадра (пакета) CK(t) . Поэтому вектор показателей эффективности СИС имеет вид: 3„(t) = 3K(t),3c(t),33(t)T = Z(Zc(t),A„(t),A(t),CK(t)). (1.1) 3K(t) определят качество функционирования СИС с множественным доступом к общему каналу и характеризуется: - своевременностью доведения пакетов от источника до получателя сообщений; - достоверностью восстановления пакетов получателем сообщений; - безопасностью информационного обмена в сети. Своевременность доставки пакетов получателям описывается функцией распределения времени доставки Гд пакета: FTд(t) = р(Тд t). (1.2) Функция распределения FT (t), по сути, определяет гарантированное время доставки пакета Гд в СИС с множественным доступом, соответствующее заданной вероятности р. В работе данный параметр будет выступать в качестве ограничения времени доведения пакетов до адресата, при определении интегрального показателя оценки информационной эффективности. Показатель Гд в СИС может служить временным ограничением на время существования пакета в системе. Решение задачи множественного доступа более подробно рассматриваются в работах [4-6,13].
Математической формой обобщенного показателя качества информационного обмена в СИС с коммутацией пакетов являются вероятностно-временные характеристики пребывания информационных пакетов в системе, определяемые посредством одномерных интегральных функций распределения времени доставки пакетов их пользователям, при удовлетворении требований по достоверности и безопасности [107]: FTJt) = р(Гд tPomn рош п доп; Вп 5ПД0П), (1.3) где Рош п доп — 1 — Рпр п дош #п доп– допустимые величины пот ерь достоверности и безопасности при передаче пакетов соответственно. Для исследования СИС применяется такой показатель, как вероятность своевременного пребывания сообщений с учетом закона старения информации [31,32]: FTap(t)= [ Z(s)dFTap(t), (1.4) о где Z(s) - закон сохранения ценности информации; 5 = 1/Гд - допустимое среднее время пребывания сообщения в сети. Составляющими вектора системных показателей 3c(t) СИС могут служить [107]: функция распределения времени готовности Тг к обмену информационными пакетами FTr(t) = р(Гг t); (1.5) - вероятность функционирования СИС pH(t) без эксплуатационных отказов оборудования; - вероятность ошибки p0III(t) при поэлементном приеме сигналов, несущих информацию о передаваемом пакете; - вероятность связи между пользователями информационной сети с потерями достоверности при поэлементном приеме сигналов не более допустимой Рош доп Составляющие вектора эксплуатационных показателей 33(t) характеризуют затраты ресурса сетевой системы, необходимые для их нормального функционирования. К основным эксплуатационным показателям СИС, функционирующим на основе беспроводных технологий в определенной полосе радиочастот, относятся: - ширина полосы частот AFC, занимаемой сигналами, используемыми для передачи пакетов, которая характеризует затраты частотного ресурса устройств СИС; - отношение сигнал/помеха h в общем канале связи, при котором выполняются требования по достоверности обмена информацией (рош п Рош п доп — 1 — Рпр п допХ определяющее затраты энергетического ресурса СИС; - стоимость оборудования пользователей С0 , обусловливающая затраты аппаратурного ресурса пакетной радиосети (ПРС).
Изложенный векторный подход к оценке информационной эффективности позволяет оценивать эффективность ее работы и существенно упростить задачу векторной (многокритериальной) оценки ее эффективности на этапе проектирования. Рассмотренный подход получил широкое практическое применение в мобильных сетевых системах. Вместе с тем, известные количественные показатели оценки эффективности информационного обмена в сетях не позволяют оценить степень близости СИС к ее предельным возможностям. В связи с чем, необходимо учитывать не только скоростные возможности системы, но и ее свойство хранить информацию, при ограничении на гарантированное время доставки пакета в СИС. Данную оценку можно осуществить при использовании обобщенного параметра сети. 1.1.2 Оценка информационной эффективности на основе обобщенного параметра кибернетическая мощность сетевой информационной системы
По аналогии с физическими процессами введено понятие кибернетическая мощность информационной сети (СИС) [77]: PHC = NG\Tд, (1.6) где N - максимальное количество пакетов, находящихся в системе, G -производительность системы, Гд - ограничение на время доведения пакета, соответствующее гарантированному времени доставки пакета.
Выражение (1.6) показывает, что мощность СИС есть характеристика, учитывающая ее производительность и число пакетов, находящихся в ней, в том числе в режиме хранения. Параметр Гд- время нахождения пакетов в системе, в данном случае является ограничением, характеризующим систему. Это означает, что задав гарантируемое сетью значение Гд, при имеющейся производительности, можно найти кибернетическую мощность сети, которая определяет максимально допустимое число пакетов в системе ЛЛ
Проводя аналогию с тензорным анализом электрических сетей [48,77] в качестве модели эталонной сети, целесообразно рассматривать примитивные контурные или разомкнутые СИС, которые представляют собой набор замкнутых или, соответственно, разомкнутых одноканальных систем [39, 45]. Если кибернетическую мощность одной, i-ой ОС определить как: Pi=NiGi\Tд, (1.7) то кибернетическая мощность примитивной сети из M ОС, при одинаковом ограничении на Гд, будет равна:
Анализ задач распределения информационных потоков на основе потоковой модели
Классические подходы к распределению информационных потоков оптимизируют один параметр сети или их совокупность [13], при этом, потоковая ситуация в СИС рассматривается как совокупность потоков отдельных пар отправитель-адресат (ОА-пар). В условиях высокой информационной нагрузки СИС путевые информационные потоки на каждом узле коммутации, из-за ограничений пропускных способностей УН выходных КС, претерпевают изменения характера передаваемой информации (ко– и контрвариантный характер) [77], а именно: часть количества информации в виде пакетов находится в состоянии передачи, а часть – в состоянии ожидания в буферных или накопительных устройствах. В связи с этим в работе с целью обеспечения повышения информационной эффективности СИС основным параметром оценки используется кибернетическая мощность СИС и ее структурных составляющих. В качестве составляющих элементов СИС, в силу ее нагруженности, в модельном отображении применяются одноканальные системы, то есть системы с памятью. При этом путь для каждой ОА-пары представляет собой цепь последовательно соединенных ОС, выбранных на основе решения задачи маршрутизации в СИС.
Так как информационная эффективность СИС с точки зрения передачи информации в значительной степени определяется способом распределения потоков информации, то в работе предложено использование: 1) решения задач маршрутизации в СИС на основе определения кратчайших путей на графе в силу их эффективности в СИС с меняющейся в течение времени случайной топологией; 2) значений кибернетической мощности СИС и ее элементов в качестве основы построения метрики при решении задач распределения потоков информации и оценки информационной эффективности СИС; 3) показателя информационной эффективности СИС – КПД СИС в смысле передачи информации, наряду с общепринятыми характеристиками сетевых информационных систем.
Для модельного описания сетевых устройств СИС в работе используются элементы теории систем массового обслуживания (СМО) [39]. Обработка требований в СМО производится обслуживающими приборами, а в силу случайного характера поступающего на вход системы потока и фиксированных возможностей обслуживающего устройства, перед последним имеет место устройство накопления (УН). В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на: - системы с потерями, в которых требования, не нашедшие в момент поступления ни одного свободного прибора, теряются; - системы с ожиданием, в которых имеется УН бесконечной ёмкости для буферизации поступивших требований, при этом ожидающие требования, образуют очередь; - системы с УН конечной ёмкости (ожиданием и ограничениями), в которых длина очереди не может превышать ёмкости накопителя; при этом требование, поступающее в переполненную СМО (отсутствуют свободные места для ожидания), теряется.
При разработке модели СИС рассматривается второй вариант СМО. Выбор требования из очереди на обслуживание производится с помощью протокола обслуживания. Их примерами являются FCFS/FIFO (пришедший первым – обслуживается первым), LCFS/LIFO (пришедший последним – обслуживается первым). В разрабатываемой модели СИС применяется первый вариант протокола.
Так как целью работы является повышение информационной эффективности СИС в условиях высокой нагрузки с использованием новых метрических особенностей при решении задач распределения потоков, то в качестве основного элемента модели СИС применяется система массового обслуживания М/М/1. Система М/М/1 характеризуется одной очередью и одним обслуживающим прибором (в контексте СИС — с одной линией связи между узлами). Моменты поступления пакетов на вход системы образуют пуассоновский поток с интенсивностью А, а распределение времени обслуживания является і экспоненциальным со средним значением, равным - секунды.
Любой узел коммутации совместно с выходящим в направлении адресата КС можно представить в виде последовательно соединенных ОС (рисунок 2.1) [93]. Первая ОС характеризуется УН для входящих пакетов, а в качестве обслуживающего устройства рассматривается процессор УК. Вторая ОС соответствует одиночному цифровому КС, то есть КС с памятью. Так как в цифровом КС устройство памяти используется, по сути, для согласования скорости передачи информации, то есть в виде буфера, то его в дальнейшем будем называть буферное запоминающее устройство (БЗУ) канала связи. В виду того, что быстродействие цифрового процессора значительно выше быстродействия КС, то есть его пропускной способности, а пакет, изымаемый из УН УК в БЗУ канала связи, является одним и тем же, то общее количество информации в УК можно характеризовать в виде значения N (рисунок 2.1). Очереди пакетов в УК формируются относительно соответствующих выходных каналов связи. В связи с этим, сегмент СИС, например из трех УК, можно представить в виде соединенных ОС в соответствии с его топологией и путевыми потоками (рисунок 2.2). Буферное запоминающее устройство КС
Центральный процессор Устройство накопления канала связи совокупное количество информационных пакетов в системе,G - производительность системы, Гд - максимально допустимое время для обработки информационных пакетов в СИС. Коэффициент полезного действия СИС в смысле передачи информации [77] при заданном Гд, и высокой загрузке имеет вид: где Рж - кибернетическая мощность реальной сетевой системы с заданной топологией, Рид - кибернетическая мощность модели идеальной СИС.
КПД СИС в смысле передачи данных является показателем оценки информационной эффективности, показывающим насколько текущее состояние СИС отличается от предельно возможного для данной структуры СИС. Для расчета кибернетической мощности реальной (соединенной) СИС находится общее количество информационных пакетов в УН УК СИС, которое умножается на совокупную производительность узлов адресатов. Последние характеризуют суммарную интенсивность выходного потока СИС.
Задача распределения информационных потоков с использованием метрики на основе применения кибернетической мощности информационной сети
Процедурная модель СИС реализует основные процессы передачи информации в сети, в которой осуществляется решение задачи распределения потоков информации и оценки информационной эффективности СИС, как с использованием ее основных характеристик, так и с использованием обобщенного показателя – кибернетическая мощность информационной сети. В процедурной модели СИС применяются предложенные процедуры распределения потоков информации, использующие новую метрику на основе кибернетической мощности информационной сети и предварительное решение построения потоковой ситуации на основе алгоритмов определения кратчайших путей на графе. Процедурная модель СИС имеет следующие основные особенности:
1. Время при моделировании СИС дискретно и представлено единичным интервалом времени – тиком (продолжительность 1 мс), за который моделируется элементарный процесс. Работа модели состоит в последовательном выполнении элементарных процессов.
2. Накопительные устройства в узлах коммутации имеют очереди бесконечной длины. Такое допущение сделано для того, чтобы была возможность исследовать поведение сетевой информационной системы в высоконагруженном состоянии.
3. Топология СИС представлена случайным графом G(V,E), где V – множество вершин графа, а E – множество ребер, соединяющих вершины. При этом, граф топологии генерируется с заданной вероятностью существования связи p и k-связностью. Для реализации информационного обмена в модели используется дискретное системное время, при этом имитация процессов реализуется через равные его промежутки.
4. Считается, что для каждой линии связи существует отдельный канал передачи служебной информации. При этом служебная информация имеет малый размер, а каналы её передачи способны обрабатывать всю служебную информацию без существенной задержки, поэтому в модели не учитывается время обработки служебной информации. В связи с этим, при построении потоковой ситуации предполагается, что процедура распределения информационных потоков всегда имеет актуальную информацию о состоянии системы.
5. Для решения задачи множественного доступа в условиях конфликтной ситуации при приеме реализован протокол единичного захвата. При этом узел-отправитель уведомляется о захвате с помощью идеальной обратной связи.
6. Входной поток пакетов задается в виде Пуассоновского потока, который генерируется для каждого узла. Протокол обслуживания в УК основывается на принципе «первый пришел – первый вышел». На каждом шаге моделирования происходит расчет необходимых параметров оценки качества функционирования СИС.
7. Все пакеты, обрабатываемые СИС, имеют схожие характеристики: размер информационного пакета, временное ограничение на обработку пакета, размер заголовка.
Модель СИС, позволяющая определить качество распределения информационных потоков на основе нахождения основных характеристик СИС, включает выполнение следующей последовательности шагов: Шаг 1. Ввод исходных данных. Генерация графа (топологии) СИС, задание параметров узлов и каналов связи, сохранение значений параметров в файл. Шаг 2. Инициализация СИС. Загрузка топологии из файла. Инициализация констант и всех необходимых параметров СИС, узлов и линий связи. Шаг 3. Построение потоковой ситуации. Шаг 4. Имитация процессов передачи информации в СИС. Шаг 5. Сбор статистики, показателей качества работы СИС, расчет кибернетической мощности, КПД в смысле передачи данных. На рисунке 3.1 представлена структура основных элементов процедурной модели СИС, в которой взаимосвязаны предлагаемые в работе процедуры распределения информационных потоков с используемыми алгоритмами определения кратчайших путей и методика оценки информационной эффективности СИС.
использованием параметра p – вероятности существования связи между узлами СИС. Дополнительным ограничением при окончательном выборе графа для моделирования служит параметр k–связность. Это ограничение важно для случая слабой связности СИС. Генерации топологии состоит в выполнении следующей последовательности операций: Шаг 1. Инициализация системы. Шаг 2. Генерация n узлов. Шаг 3. Генерация случайного количества связей между узлами СИС на основе вероятности p. Шаг 4. Проверка связности топологии [13]. Данная проверка осуществляется с помощью алгоритма поиска максимального потока на графе (алгоритм Диница [91]). Шаг 5. Если сеть k-связана, то сгенерированный граф сохраняется в файл, иначе переход к шагу 3. Формируемая топология удовлетворяет одновременно заданным параметрам p и k. Процедура генерации графа топологии сети представлена на рисунке 3.2. Для того чтобы сгенерированный граф топологии СИС удовлетворял требованиям k-связности необходимо, чтобы каждая пара узлов (i;j) в графе имела k независимых путей [13]. Это эквивалентно требованию о существовании не менее k путей, соединяющих i и j и имеющих только 2 общих узла: отправитель сообщения и его адресат. Для поиска значения величины k используется следующая последовательность шагов: Шаг 1. Заполнить таблицу связанности графа не «весами» переходов, а единицами. Шаг 2. Для каждой пары узлов (i;j) найти максимальный поток в графе по алгоритму Диница [91]. При единичной цене перехода максимальный поток показывает количество непересекающихся путей, что по определению эквивалентно k-связности [13].Топология СИС описывается графом G(V,E), который формируется случайным образом, путем
Передача информационных пакетов в сетевой информационной системе
В основе процедур распределения потоков, с использованием параметра кибернетическая мощность сети, применяется алгоритм определения кратчайших путей на графе. Для проведения сравнительного анализа информационной эффективности разработанных процедур используются алгоритмы нахождения кратчайших путей. В процессе решения задачи построения потоковой ситуации применяются таблицы маршрутизации (ТМ). При этом, каждый узел СИС имеет свою собственную ТМ, которая, в зависимости от процедуры распределения информационных потоков, может быть статической или динамической. Модель предусматривает применение различных процедур распределения информационных потоков. В связи с этим они могут взаимодействовать с моделью КС только посредством ТМ, тем самым, изменяя движение пакетов в СИС. ТМ для каждого СИС имеет двумерный вид. В ячейках таблицы хранится следующий узел, которому должен быть перенаправлен информационный пакет после текущего.
Процедура распределения информационных потоков, основанная на кратчайших путях В работе данная процедура имеет следующие особенности: - движение пакетов для ОА-пары осуществляется только по одному фиксированному маршруту; - маршрутные таблицы, после их формирования не меняются (статичность таблиц маршрутизации).
Работа процедуры осуществляется в несколько шагов. Процедуре выбора маршрутов пакетов предшествует процедура построения ТМ для каждого узла. Так как все ТМ статичны, то их расчет реализуется до начала работы модели. Процесс формирования ТМ состоит из следующих шагов: Шаг 1. Выбор метрики. В зависимости от параметров моделирования могут используются несколько вариантов метрик: векторный показатель, скорость передачи данных в каналах связи, количество транзитных участков. В ходе данного исследования используется метрика число транзитных участков. Шаг 2. Поиск кратчайших путей на графе между всеми вершинами на основе одной из метрик с помощью алгоритма Флойда-Уоршелла [91]. Шаг 3. Проход по ребрам всех полученных путей и заполнение соответствующих таблиц маршрутизации.
На каждом шаге алгоритм генерирует матрицу M. Матрица Mсодержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица Mзаполняется длинами рёбер графа. В системах для определения кратчайших путей используется асинхронный алгоритм Беллмана-Форда. Но в силу того, что алгоритм Беллмана-Форда и алгоритм Флойда-Уоршелла генерируют одинаковые кратчайшие пути и алгоритм Флойда-Уоршелла имеет более высокую скорость расчетов при моделировании [91], он был выбран как основной алгоритм для поиска кратчайших путей.
После выполнения данного псевдокода матрица М содержит кратчайшие пути между всеми парами вершин. В результате ее анализа строится ТМ для СИС. Выбор следующего узла при наличии построенной ТМ сводится к получению из неё соответствующего значения и отправки пакета адресату.
Процедура распределения информационных потоков, основанная на кратчайших путях с учетом накоплений (аналог протокола RIP) Используемая процедура распределения потоков информации в СИС имеет следующие особенности: - движение пакетов между ОА-парой осуществляется по одному маршруту; - каждые 30 секунд маршруты в СИС перестраиваются в зависимости от текущей сетевой обстановки. Построение кратчайших путей осуществляется на основе пропускных способностей каналов. В случае, если существуют несколько кратчайших путей – выбирается тот, который имеет наименьшее суммарное накопление на всех транзитных участках. Для автоматизации и ускорения алгоритма поиска модернизируется таблица смежности графа сети. Вместо пропускных способностей она содержит пары чисел: пропускная способность – накопление (ПСН – пара). Причем, накопление считается как сумма накоплений УК соединенных соответствующим КС. Для данной пары должны быть введены операции сравнения. ПСН – пара больше другой пары в том случае, если пропускная способность первой пары больше пропускной способности второй. Если пропускные способности ПСН – пар равны, первая пара больше второй в том случае, когда накопление первой пары больше накопления второй. Если накопления и пропускные способности ПСН – пар равны, то пары считаются равными. После определения операций над ПСН – парами к ним применяется алгоритм Флойда-Уоршелла для поиска кратчайших путей. Работа алгоритма построения ТМ описывается следующей последовательностью шагов:
Осуществляется поиск кратчайших путей в графе между всеми вершинами на основе пропускных способностей канала и накоплений с помощью алгоритма Флойда-Уоршелла [91]. В отличии от простого алгоритма поиска по кратчайшим путям алгоритм поиска по кратчайшим путям с учетом накоплений в качестве основной матрицы смежности использует матрицу пар значений пропускная способность – накопление. Для данной пары определены операции сравнения и сложения, что позволяет использовать стандартный алгоритм Флойда-Уоршелла.