Разработка моделей загруженности топологически сложных информационно-вычислительных сетей и алгоритмов маршрутизации трафика на основе методов стохастической динамики и теории перколяции тема диссертации и автореферата по ВАК РФ 05.13.15, доктор наук Лесько Сергей Александрович

• Лесько Сергей Александрович
• доктор наук
• 2022

Оглавление диссертации доктор наук Лесько Сергей Александрович

ВВЕДЕНИЕ

Глава 1. ОПИСАНИЕ ОБЪЕКТА ИССЛЕДОВАНИЙ, СОВРЕМЕННОГО УРОВНЯ ЕГО ИЗУЧЕНИЯ И ОБОСНОВАНИЕ ВЫБОРА МЕТОДОВ И ПОДХОДОВ ДЛЯ ИЗУЧЕНИЯ ТОПОЛОГИЧЕСКИ СЛОЖНЫХ ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ И МОДЕЛИРОВАНИЯ В НИХ ПРОЦЕССОВ ПЕРЕДАЧИ ДАННЫХ

1.1. Прогнозирование роста числа пользователей, устройств и эпидемий компьютерных вирусов в сети интернет на основе анализа статистических данных

1.2. Предметно-ориентированное описание информационно-вычислительных сетей

1.3. Моделирование работы информационно-вычислительных сетей

1.3.1. Математический аппарат систем массового обслуживания

1.3.2. Математический аппарат теории графов и сетевого анализа

1.3.3. Математический аппарат теории нечетких множеств и нечеткой логики

1.3.4. Имитационное моделирование вычислительных сетей

1.3.5. Стохастическое моделирование с дискретным временем (TSS)

1.3.6. Моделирование трафика и передачи данных в информационно-вычислительных сетях

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

1.4.1. Централизованные и/или распределенные алгоритмы маршрутизации

1.4.2. Проактивные и/или реактивные алгоритмы маршрутизации

1.4.3. Маршрутизация по географическим признакам

1.4.4. Многопутевая маршрутизация

1.4.5. Иерархическая маршрутизация

1.4.6. Б^^^ориентированные (или потокоориентированные) алгоритмы маршрутизации

1.4.7. Алгоритмы маршрутизации с геокастингом

1.4.8. Многоадресные алгоритмы маршрутизации

1.4.9. Алгоритмы маршрутизации, учитывающие энергопотребление

1.4.10. Гибридные алгоритмы маршрутизации

1.5. Генерация, обнаружение и анализ трафика вредоносного типа при вирусных и DDoS атаках в информационно-вычислительных сетях

1.6. Выводы

ГЛАВА 2. ИССЛЕДОВАНИЕ ПЕРКОЛЯЦИОННЫХ СВОЙСТВ ТОПОЛОГИЧЕСКИ

СЛОЖНЫХ СЕТЕВЫХ СТРУКТУР

2.1. Описание основных положений и методов теории перколяции

2.2. Методика изучения кластеризации узлов в топологически сложных сетевых структурах и достижения порогов перколяции

2.3. Кластеризация узлов в топологически сложных сетевых структурах

2.4. Определение порогов перколяции в топологически сложных сетевых структурах

2.5. Выводы

ГЛАВА 3. МОДЕЛИРОВАНИЕ СТОХАСТИЧЕСКОЙ ДИНАМИКИ БЛОКИРОВКИ

УЗЛОВ И СВЯЗЕЙ В ТОПОЛОГИЧЕСКИ СЛОЖНЫХ СЕТЕВЫХ

СТРУКТУРАХ

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

3.2. Формулировка и решение краевой задачи для блокировки сетей без ускорения изменения состояний. Анализ модели

3.3. Формулировка и решение краевой задачи для блокировки сетей при ускорении изменения состояний. Анализ модели

3.4. Выводы

ГЛАВА 4. РАЗРАБОТКА И ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ РАБОТЫ

АЛГОРИТМОВ БАЛАНСИРОВКИ ПОТОКОВ И МАРШРУТИЗАЦИИ В

ТОПОЛОГИЧЕСКИ СЛОЖНЫХ СЕТЕВЫХ СТРУКТУРАХ С УЧЕТОМ ИХ

ПЛОТНОСТИ И СТОХАСТИЧЕСКОЙ ДИНАМИКИ БЛОКИРОВКИ УЗЛОВ

ИЛИ СВЯЗЕЙ

4.1. Описание алгоритмов балансировки потоков в информационно-вычислительных сетях на основе теории перколяции и стохастической динамики блокировки отдельных узлов и связей

4.2. Описание алгоритмов балансировки потоков в информационно-вычислительных сетях на основе теории перколяции и стохастической динамики блокировки всей сети в целом

4.3. Описание используемых данных для процессов моделирования трафика в информационно-вычислительных сетях

4.4. Моделирование передачи трафика в информационно- вычислительных сетях152

4.5. Результаты численного моделирования передачи трафика в информационно-вычислительных сетях, имеющих случайную структуру. Анализ

эффективности разработанных алгоритмов

4.6.1. Методика проведения численного моделирования

4.6.2. Результаты численного моделирования работы алгоритмов балансировки потоков в информационно-вычислительных сетях на основе теории перколяции и стохастической динамики блокировки отдельных узлов и связей

4.6.3. Результаты численного моделирования работы алгоритмов балансировки потоков в информационно-вычислительных сетях на основе теории перколяции и стохастической динамики блокировки сети в целом

4.6. Использование метрик стоимости маршрута в алгоритмах и протоколах маршрутизации на основе разработанных моделей

4.7. Выводы

ГЛАВА 5. ОПИСАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ

МОДЕЛИРОВАНИЯ РАБОТЫ АЛГОРИТМОВ МАРШРУТИЗАЦИИ В ТОПОЛОГИЧЕСКИ СЛОЖНЫХ СЕТЕВЫХ СТРУКТУРАХ РАЗНОЙ ПРИРОДЫ И ПРОВЕРКИ ИХ ЭФФЕКТИВНОСТИ

5.1. Используемые технологии для создания программного обеспечения моделирования работы алгоритмов маршрутизации трафика и проверки их эффективности

5.2. Структура программного обеспечения для моделирования работы алгоритмов маршрутизации трафика и проверки их эффективности

5.3. ЦМЬ-диаграмма процесса моделирования работы алгоритмов маршрутизации трафика и проверки их эффективности

5.3. БЯ-диаграмма базы данных при моделировании работы алгоритмов маршрутизации трафика и проверки их эффективности

5.4. Инструментальные средства разработки программного обеспечения для моделирования работы алгоритмов маршрутизации трафика и проверки их эффективности

5.5. Алгоритмическая реализация решения задачи моделирования передачи трафика в сетях

5.6. Требования к сценариям моделирования и аппаратной платформе их выполнения

5.7. Тестирование разработанного программного обеспечения для моделирования передачи трафика в сетях

5.8. Выводы

ГЛАВА 6. ОПИСАНИЕ РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ НА ОСНОВЕ

ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯ ВТОРОГО ПОРЯДКА С ПОМОЩЬЮ МЕТОДА ПРЕОБРАЗОВАНИЙ ЛАПЛАСА

6.1. Решение краевой задачи для блокировки сетей при ускорении изменения

состояний

6.2. Решение краевой задачи для блокировки сетей без ускорения изменения состояний

ЗАКЛЮЧЕНИЕ И ВЫВОДЫ

БЛАГОДАРНОСТИ

ПРИНЯТЫЕ ТЕРМИНЫ И СОКРАЩЕНИЯ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

ПРИЛОЖЕНИЕ А

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

порогов перколяции

А.1. Алгоритм построения топологически сложных сетевых структур с

разной плотностью связей

А.2. Алгоритм расчета числа и размеров кластеров блокированных узлов в

топологически сложных сетевых структур с разной плотностью связей для

задачи узлов

А.3. Алгоритм расчета числа и размеров кластеров блокированных узлов в

топологически сложных сетевых структурах с разной плотностью связей для

задачи связей

A.4. Алгоритм расчета порогов перколяции в топологически сложных

сетевых структур с разной плотностью связей

ПРИЛОЖЕНИЕ Б

Пример моделирования стохастической динамики переходов между состояниями в

сетевых структурах с помощью прикладного пакета Mathcad

ПРИЛОЖЕНИЕ В

B.1. Исходный код модуля для математических расчетов

В.2. Исходный код скрипта анализа метрик моделирования

ПРИЛОЖЕНИЕ Г

Свидетельства РОСПАТЕНТ (ФИПС) на специализированное программное обеспечение для моделирования перколяционных процессов в топологически

сложных сетевых структурах различной природы

ПРИЛОЖЕНИЕ Д

Акты о внедрении результатов исследований

Введение диссертации (часть автореферата) на тему «Разработка моделей загруженности топологически сложных информационно-вычислительных сетей и алгоритмов маршрутизации трафика на основе методов стохастической динамики и теории перколяции»

ВВЕДЕНИЕ

Актуальность исследования. В настоящее время происходит значительное увеличение объема данных, генерируемых и передаваемых в информационно -вычислительных сетях (далее - ИВС). Создание интернета вещей (IoT) и снижение стоимости доступа в интернет многократно увеличивают сетевой трафик, поскольку миллиарды устройств напрямую начинают общаться друг с другом. По оценкам экспертов, в 2020 году общемировой объем различных электронных данных составил более 35 ООО Экзобайт (приставка экзо = 1018), что в более чем 4О раз превышает показатели 2О1О года.

^обходимо отметить, что современная экономика во многом существует и функционирует благодаря существенному развитию сетевых технологий, базирующихся на серьезном теоретическом фундаменте и его практическом применении. И существенный вклад в исследования этой области науки и технологий внесли как российские ученые - Смелянский Р.Л., Гурин H.H., Кулагин В.П., Леохин Ю.Л., Hазаров A.H., Парамонов НБ., Потехин Д.С., Топорков В.В., Корячко В.П., Перепелкин ДА., Коган ЯА., Будко ПА., Федоренко В.В., Турко СА., Фомин ЛА., Зданевич С.Н, Гахова H.H., Куракин Д.В., Пасечников И.И., Aвен О.И., Лазарев В.Г., Лазарев Ю.В., Заборовский В.С., Швиков Ю.В., Кондратенко С.В., Ябных r.A., Столяров БА., Якубайтис ЭА., Малинковский Ю.В., Aбышкин ВА., Самуйлов К.Е., Ивницкий ВА., Герасимов

A.H, Рыбко A.H., Мизин ИА., Богатырев ВА., Кулешов A.H, Цвиркун A.Д., Aкинфиев В.К., Филидиов B.A., Aдаменко Г.М., Батурина Л.Н, Лепешинский H.A., Бакланов A^., Смирнов М.И., Яковлев СА., Богуславский Л.Б., Бондарев

B.Н, Орлов ВА., Власов A.C, Hечепуренко М.И., Родионов A.O. и многие другие, так и иностранные специалисты - Клейнок Л., Столлингс В., Филлипс Д., Гарсиа-Диас A., Simon В., Foley R.D., Pittel B., Walrand J., Varaiya P., Chao X., Miyazawa M., Serfozo R., Takada H., Mandelbaum A., Pats G., Kelly F.P., Williams R.J., Towsley D.F., Morales F., Ruiz M., Gifre L., Contreras L.M., López V., Velasco L., Moharana L., Biswal B.K., Raj R., Naik S., Li X., Tang F., Chen L., Li J.,

Abdelgadiï M., Saeed R.A., Babiker A., Bhola J., Soni S., Cheema G.K., Navaгidas J., Pascual J.A., Erickson, A., Stewart I.A., Luján M., Wang J., Miao Y., Zhou P., Hossain M.S., Rahman S.M., Cegrell T.A., Chou W., Frank H., Vanslyker R., Stassinopoulos G. и многие другие.

К применению теории перколяции в исследовании сетей различных топологий прибегали такие авторы, как Тарасевич Ю.Ю., Жуков Д.О., Ландэ Д.В., Снарский А.А., Безсуднов И.В., Голубев А.С., Звягин М.Ю. и многие другие.

Одной из проблем развития сетей в настоящее время является существенное увеличение объемов и трафика передачи данных, что приводит к необходимости повышения затрат на установку и обслуживание, а также использования все большего числа различных устройств и сетевого оборудования. Однако следует учитывать, что, по оценкам экспертов, предел увеличения числа пользователей и устройств в сети интернет в рамках реализуемой системы технологий составляет порядка 5-6 млрд единиц. По сути, в самое ближайшее время может быть достигнут технологический физический предел развития сетей передачи данных. Это в значительной степени определяется функциональными возможностями существующих систем передачи и обработки данных, моделями и алгоритмами маршрутизации потоков и балансировки нагрузки на оборудование (отказы в обслуживании из-за переполнения очередей, блокирования каналов связи и т.д.).

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

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

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

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

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

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

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

(кластеров) при произвольном законе распределения времен поступления заявок на узлы сети, и/или их блокирования в результате вирусной атаки.

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

На рисунке 1 представлена условная схема, которой можно описать большинство современных крупномасштабных ИВС, к которым, например, можно отнести традиционный интернет, промышленные сети, 1оТ и т.д.

Рисунок 1 - Условная графическая схема крупномасштабных ИВС

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

сказывается на их способности быть блокированными при перегрузках и вирусных или DDoS атаках, а следовательно, может быть связана с вероятностными характеристиками процесса их блокировки.

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

В представленной диссертации для достижения поставленной цели были решены следующие задачи:

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

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

2) Разработаны и проанализированы модели стохастической динамики загруженности узлов ИВС при произвольном распределении значений времени поступления заявок на узлы в результате генерации полезного трафика или их блокирования в результате вирусной или DDoS атаки. Это позволяет определить зависимость от времени вероятности блокирования их единичных узлов или достижения порогов перколяции, и таким образом связать между собой динамические свойства сетей по передаче данных и их структурные характеристики.

Следует отметить, что динамика блокирования узлов или связей, связанная с их перегрузкой в результате ограничений на производительность элементов сети, отличается от блокировки, связанной с распространением вирусов. При распространении вирусов следует учитывать процессы самоорганизации трафика, связанные с заложенными в действия вирусов алгоритмами (как минимум, вирусы способны саморазмножаться) и возможное наличие памяти о рассылке, реализуемое при их распространении. К примеру, такое поведение характерно для трафика, генерируемого рассылкой вирусов Sapphire/Slammer и Conficker.

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

4) Разработанные динамические и перколяционные модели также могут быть использованы для совершенствования уже существующих алгоритмов балансировки нагрузки и маршрутизации в ИВС. На основании зависимости от

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

5) Для проверки полученных в диссертационной работе результатов было проведено имитационное моделирование работы топологически сложных сетевых структур с учетом их плотности и стохастической динамики блокировки узлов или связей на основе разработанных алгоритмов балансировки потоков и маршрутизации. Результаты проверки показали:

а) разработанные модели являются непротиворечивыми и адекватными;

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

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

Предмет исследования - разработка моделей блокировки узлов и каналов связи топологически сложных ИВС, а также моделей их загруженности и алгоритмов маршрутизации трафика на основе использования методов стохастической динамики и теории перколяции. Предмет исследования соответствует паспорту специальности 05.13.15 «Вычислительные машины, комплексы и компьютерные сети», область исследования № 1 «Разработка научных основ создания вычислительных машин, комплексов и компьютерных сетей, исследования общих свойств и принципов функционирования вычислительных машин, комплексов и компьютерных сетей». В части разработки научных основ создания и исследования общих свойств и принципов функционирования компьютерных сетей; № 5 «Разработка научных методов и

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

Методы и средства исследования. Научные результаты диссертации были получены с использованием теории вероятностей, теории дифференциальных уравнений и решения краевых задач, операционного исчисления, метода преобразований Лапласа, теории систем и системного анализа, теории моделирования систем, методов математического анализа, теории алгоритмов, методов теории перколяции, теории принятия решений, численного моделирования. Для разработки и создания специализированного программного обеспечения, необходимого при моделировании и проведении численных расчетов, были использованы методы объектно-ориентированного программирования и разработки баз данных.

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

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

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

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

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

При решении задач маршрутизации и балансировки нагрузки узлов сетей также можно использовать в качестве порогового значения обеспечения работоспособности понятие доступности, например, задать, что вероятность перегруженности (блокировки) узла (или связи) не должна превышать некоторую установленную величину (например, 0,01) или величину, при которой достигается

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

Для построения динамических моделей работы сети в представленной диссертации проводится декомпозиция поставленной задачи, ее решение разделяется на два уровня:

1) Уровень описания динамики блокирования отдельных элементов сети (узлов или связей).

2) Уровень описания, учитывающий топологию сети и динамику блокирования ее отдельных элементов.

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

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

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

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

исходного кода, а кроме того этот член уравнения учитывает то, что сами вирусы становятся источниками новых вирусов (процесс размножения, при котором копии новых вирусов способны создавать дополнительную нагрузку на сеть -блокировку узлов и увеличение трафика при их рассылке). Такое поведение было продемонстрировано вирусами Sapphire/Slammer и Conficker. Без учета второй производной по времени модель применима для описания процессов передачи в сетях полезного трафика, генерируемого обычным способом.

В созданных динамических моделях передача и обработка данных в сети может быть описана произвольным законом распределения времени между заявками во входном и выходном потоках на узлах, что необходимо учитывать при управлении ее работой (при перерасчете таблиц маршрутизации).

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

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

Предлагаемые модели могут быть использованы для модификации уже имеющихся алгоритмов. Для локальных сетей может быть использован, например, иерархический динамический многомаршрутный алгоритм, учитывающий состояние каналов либо векторы расстояний и ориентирующийся не просто на «первоочередность наикратчайшего маршрута», а на состояние критичности для каждого узла (или группы узлов). Таким образом, кратчайшее расстояние выбирается с учетом того, что некоторые узлы могут оказаться в ближайшее время в состоянии перегруженности, и такие узлы должны быть исключены из выбора узлов кратчайшего маршрута при отправке пакета. Для осуществления подобных алгоритмов могут быть использованы протоколы внутренней динамической маршрутизации, например протокол RIP (Routing Information Protocol). Однако в этом случае необходимо, чтобы в таблице маршрутов присутствовала информация о том, насколько близко каждый из узлов сети находится к состоянию блокировки, а также предсказанная информация о времени, в течение которого узел достигнет критического порога. Узлы, находящиеся в перегруженном состоянии, могут быть исключены из маршрутов

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

Выбор оптимального пути может осуществляться путем анализа ориентированного графа сети по алгоритму Дейкстры1. При анализе графа сети от узла отправки до узла назначения рассчитываются суммарные значения метрик, и пути с наименьшим значением метрики считаются наилучшими.

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

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

Для региональных и глобальной сети можно использовать протоколы внешних маршрутизаторов, таких как EGP и BGP. При этом в протоколе BGP веса маршрутов нужно определять с учетом состояний узлов (или групп узлов) таким образом, что близость узла (группы) к критическому состоянию будет увеличивать вес данного маршрута и таким образом влиять на выбор приоритетов. В случае использования протокола EGP формат пакета должен содержать сведения о возможных изменениях состояния узла сети или для протокола BGP - дополнительные сообщения об изменении маршрутов, связанные с возможными перегрузками узлов.

Список литературы диссертационного исследования доктор наук Лесько Сергей Александрович, 2022 год

/ // //

у/ //■' 2

2

у/ / / //

A J

W м « «к IMQ UM 1400 яо «П 4ВО ВС ММ ОМ И00

niiM тц>и.м> Йичмии» мчи тЛ.иш

Рисунок 58 - Результаты моделирования зависимости от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - cluster» - кривая 3, «Композит I - percolation» - кривая 2 и «Дейкстра I» - кривая 1

/

¿Г

1/ г

/ /

уУ

п «о «И Md IM Ml им м <И «ОС flM) им им МИ

AllMMMIIk (VMM (oAi/MM mmwHHIfl» ПШи гиЛ^ии

Рисунок 59 - Результаты моделирования зависимости от интенсивности потока сообщений среднего времени их доставки для алгоритмов

«Композит I - cluster» - кривая 3, «Композит I - percolation» - кривая 2

и «Дейкстра I» - кривая 1

Анализ данных на рисунках 57-59 показывает, что динамика поведения зависимостей доли блокированных узлов, процента потерянных сообщений и среднего времени доставки сообщений от интенсивности их потоков имеют принципиально такой же характер, как и описанный ранее для сети с плотностью 3,54 связей в расчете на один узел (см. рисунки 49-51), однако числовые характеристики указанных процессов различаются. Эти различия будут описаны подробно далее.

Рассмотрим результаты численного моделирования работы алгоритма «Композит II». Для сравнения будем использовать эксперименты, в которых было принято Li = 50£- и Li = 100£. Справа на рисунках 60-62 представлены данные для Li = 100£-, а с левой стороны - для Li = 50£-.

Кривые 1 на рисунках 60-62 соответствуют поведению алгоритма «Дейкстра II», кривые 2 - алгоритму «Композит II - percolation», а кривые 3 описывают поведение алгоритма «Композит II - cluster».

Рисунок 60 - Результаты моделирования зависимости средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - cluster» - кривая 3, «Композит II - percolation» - кривая 2 и «Дейкстра II» - кривая 1. Левый - для Li = 50<^, правый - для Li = 100<^

На рисунке 60 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II -cluster», «Композит II - percolation» и «Дейкстра II», на рисунке 61 - процент потерянных сообщений, а на рисунке 62 - среднего времени их доставки.

Рисунок 61 - Результаты моделирования зависимости процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - cluster» - кривая 3, «Композит II - percolation» - кривая 2

и «Дейкстра II» - кривая 1

Анализ данных на рисунках 60-62 показывает, что динамика поведения зависимостей доли блокированных узлов, процента потерянных сообщений и

среднего времени доставки сообщений от интенсивности их потоков имеют принципиально такой же характер, как и описанный ранее для сети с плотностью 3,54 связей в расчете на один узел (см. рисунки 52-54), однако числовые характеристики указанных процессов различаются. Эти различия будут описаны подробно далее.

Рисунок 62 - Результаты моделирования зависимости среднего времени доставки сообщений от интенсивности потока сообщений для алгоритмов «Композит II -cluster» - кривая 3, «Композит II - percolation» - кривая 2 и «Дейкстра II» - кривая 1

Рассмотрим результаты численного моделирования работы алгоритма «Композит III». На рисунке 63 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит III - cluster», «Композит III - percolation» и «Дейкстра III», а на рисунке 64 - среднего времени их доставки. Процент потерянных сообщений для данного алгоритма не рассматривается, так как по своему описанию в нем все сообщения рано или поздно доставляются без потерь.

Рисунок 63 - Результаты моделирования зависимости средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит III - cluster» - кривая 3, «Композит III - percolation» - кривая 2

и «Дейкстра III» - кривая 1

Рисунок 64 - Результаты моделирования зависимости среднего времени доставки сообщений от интенсивности потока сообщений для алгоритмов «Композит III -cluster» - кривая 3, «Композит III - percolation» - кривая 2 и «Дейкстра III» - кривая 1

Анализ данных на рисунках 63 и 64 показывает, что динамика поведения зависимостей доли блокированных узлов и среднего времени доставки сообщений от интенсивности их потоков имеют принципиально такой же характер, как и описанный ранее для сети с плотностью 3,54 связей в расчете на один узел.

Рассмотрим случайную сеть с плотностью связей 2,57

Рассмотрим результаты численного моделирования работы алгоритма «Композит I». Для сравнения будем использовать эксперименты, в которых было принято Ь = 50£- и Ь = 100£. Справа на рисунках 65-67 представлены данные для = 100£-, а с левой стороны - для = 50£-.

Рисунок 65 - Результаты моделирования зависимости от интенсивности потока сообщений средней доли блокированных узлов сети для алгоритмов «Композит I - cluster» - кривая 3, «Композит I - percolation» - кривая 2 и «Дейкстра I» - кривая 1

Рисунок 66 - Результаты моделирования зависимости от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - cluster» - кривая 3, «Композит I - percolation» - кривая 2

и «Дейкстра I» - кривая 1

Кривые 1 на рисунках 65-67 соответствуют поведению алгоритма «Дейкстра I», кривые 2 - алгоритму «Композит I - percolation», а кривые 3 описывают поведение алгоритма «Композит I - cluster».

Для снижения информационной нагрузки при анализе данных для сети с такой плотностью графические зависимости от шага моделирования величины доли блокированных узлов; величины средней загрузки; среднего числа сообщений в очереди узла на обработку и числа потерянных сообщений мы рассматривать не будем. Они имеют характер поведения, схожий с динамикой, описанной для сетей с плотностью 3,54 и 3,08, поэтому сразу перейдем к описанию и анализу обобщенных характеристик.

ям «м «и ас roe© иго и» jn ом мм во то то мое

»»if—« 11* т» fvtxmm :irtMiii«

Рисунок 67 - Результаты моделирования зависимости от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит I - cluster» -кривая 3, «Композит I - percolation» - кривая 2 и «Дейкстра I» - кривая 1

На рисунке 65 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит I -cluster», «Композит I - percolation» и «Дейкстра I», на рисунке 66 - процента потерянных сообщений, а на рисунке 67 - среднего времени их доставки.

Рассмотрим результаты численного моделирования работы алгоритма «Композит II». Для сравнения будем использовать эксперименты, в которых было принято Li = 50£i и Li = 100£. Справа на рисунках 68-70 представлены данные для Li = 100£-, а с левой стороны - для Li = 50£-.

Кривые 1 на рисунках 68-70 соответствуют поведению алгоритма «Дейкстра II», кривые 2 - алгоритму «Композит II - percolation», а кривые 3 описывают поведение алгоритма «Композит II - cluster».

Рисунок 68 - Результаты моделирования зависимости средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - cluster» - кривая 3, «Композит II - percolation» - кривая 2 и «Дейкстра II» - кривая 1. Левый для Li = 50^, правый для Li = 100^

На рисунке 68 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II -cluster», «Композит II - percolation» и «Дейкстра II», на рисунке 69 - процента потерянных сообщений, а на рисунке 70 - среднего времени их доставки.

1 X

у /

У /2,3

Рисунок 69 - Результаты моделирования зависимости процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - cluster» -кривая 3, «Композит II - percolation» - кривая 2 и «Дейкстра - II» - кривая 1

/ч

/ \ / >

/

/ У— 2

/ / 1 з ----]

/ / *

у

2 3

/ /

/ / 1 * * -—-

А/

/У

Рисунок 70 - Результаты моделирования зависимости среднего времени доставки сообщений от интенсивности потока сообщений для алгоритмов «Композит II -cluster» - кривая 3, «Композит II - percolation» - кривая 2 и «Дейкстра II» - кривая 1

Рассмотрим результаты численного моделирования работы алгоритма «Композит III». На рисунке 71 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит III - cluster», «Композит III - percolation» и «Дейкстра III», а на рисунке 72 - среднего времени их доставки. Процент потерянных сообщений для этого алгоритма не рассматривается, так как по своему описанию в нем все сообщения рано или поздно доставляются без потерь.

ме «о m m vm им мм м m ■»«м ммом мм

#N»<i*iewn>wTeM«e4wi*w« мы'иошсп ш»т<м смвмтн

Рисунок 71 - Результаты моделирования зависимости средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит III - cluster» - кривая 3, «Композит III - percolation» - кривая 2 и «Дейкстра III» - кривая 1. Левый для Li = 50^, правый для Li = 100^

Рисунок 72 - Результаты моделирования зависимости среднего времени доставки сообщений от интенсивности потока сообщений для алгоритмов «Композит III -cluster» - кривая 3, «Композит III - percolation» - кривая 2 и «Дейкстра III» - кривая 1. Левый для Li = 50^i, правый для Li = 100^i

Анализ данных на рисунках 65-72 показывает, что динамика поведения зависимостей доли блокированных узлов, процента потерянных сообщений и среднего времени доставки сообщений от интенсивности их потоков имеют принципиально такой же характер, как и описанный ранее для сетей с плотностью 3,54 и 3,08 связей в расчете на один узел (см. рисунки 49-51 и соответствующие рисунки для сети с плотностью 3,08), однако числовые характеристики указанных процессов различаются. Эти различия будут описаны подробно далее.

Проведем общий анализ полученных результатов численного моделирования. Данные, представленные на рисунках 49, 50, 52, 53, 57, 58, 60, 61, 65, 66, 68 и 69, показывают качественное превосходство разработанных в диссертации алгоритмов классов «Композит I» и «Композит II» над алгоритмами класса «Дейкстра I и II» по таким показателям, как доля блокированных узлов и процент потерянных сообщений.

Для количественного и обобщенного сравнения характеристик работы алгоритмов классов «Композит» и «Дейкстра» при разной плотности сети (см. таблицу ) можно ввести интегральные показатели, определяющие, насколько различаются площади под кривыми, описывающими зависимость от интенсивности потока сообщений доли блокированных узлов, процента потерянных сообщений и среднего времени доставки для рассматриваемых алгоритмов (в диапазоне интенсивности потоков от 100 до 1500 сообщений на одном шаге).

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

рассматриваемых алгоритмов

№ Алгоритм Величина Плотность сети

L, 3,54 3,08 2,57

Площадь по доле блокированн ых узлов Площадь по проценту потерянны х сообщений Площадь по времени доставки Площадь по доле блокированн ых узлов Площадь по проценту потерянных сообщений Площадь по времени доставки Площадь по доле блокированн ых узлов Площадь по проценту потерянны х сообщений Площадь по времени доставки

1. «Композит I L, = 50% 0.05644 40.7232 61.0209 0.0580 46.4420 65.2074 0.0526 55.1207 63.7677

2. percolation» L, = 100% 0.02095 20.2909 116.4728 0.0274 28.5238 122.3299 0.0253 37.3211 137.7533

3. «Композит I L, = 50^, 0.05779 40.7985 58.4329 0.0594 46.8561 62.1623 0.0522 54.9664 63.5808

4. - cluster» l, = 100^i 0.02215 21.1514 110.4456 0.0275 28.4236 120.8164 0.0255 37.3984 135.7625

5. «Дейкстра l, = 50^i 0.07535 42.2589 48.3568 0.0795 48.6854 52.2933 0.0664 56.2581 54.4321

6. I» l, = 100% 0.03468 25.2259 89.8013 0.0410 31.7152 102.4790 0.0384 41.1085 113.6281

7. «Композит l, = 50% 0.05383 34.3891 96.0128 0.0582 39.9039 107.8622 0.0388 45.9064 121.4028

8. II - percolation» L, = 100%, 0.01612 13.5084 160.6191 0.0234 18.7479 201.1559 0.0147 24.8792 256.4190

9. «Композит L, = 50% 0.05137 33.5594 93.89798 0.0552 39.3950 105.4314 0.0382 45.6251 120.8269

10. II - cluster» L, = 100% 0.01446 13.3141 157.3982 0.0205 18.2022 200.7045 0.0139 24.8150 252.1785

11. «Дейкстра L, = 50% 0.07905 34.9507 65.0910 0.0896 41.3553 71.9295 0.0743 49.2270 78.7665

12. II» L, = 100% 0.03152 16.5368 116.2529 0.0444 22.1425 141.6501 0.0418 30.2584 171.2704

13. «Композит L, = 50% 0.24482 0 359.2434 0.2700 0 535.2638 0.2809 0 600.5275

14. III - percolation» L, = 100% 0.13904 0 297.3257 0.1647 0 398.0023 0.1901 0 529.5863

15. «Композит L, = 50% 0.24913 0 329.2191 0.2626 0 453.8406 0.2805 0 548.8747

16. III - cluster» L, = 100% 0.14908 0 321.1118 0.1765 0 454.7648 0.1933 0 546.6449

17. «Дейкстра L, = 50% 0.14662 0 184.6042 0.1534 0 252.4414 0.2077 0 361.1832

18. III» L, = 100% 0.07901 0 184.6042 0.0913 0 252.4414 0.1390 0 361.1832

Данные, представленные в таблице , количественно показывают, что во всем исследованном диапазоне плотностей сетей (от 3,54 до 2,57 связей в расчете на один узел) алгоритмы классов «Композит I» и «Композит II» дают лучшие результаты в абсолютных величинах по долям блокированных узлов и проценту потерянных сообщений, чем алгоритмы класса «Дейкстра I и II».

Рисунок 73 - Зависимость интегрального показателя «Площадь по доле блокированных узлов» от плотности сети для алгоритмов «Композит I - cluster» -кривая 3, «Композит I - percolation» - кривая 2 и «Дейкстра I» - кривая 1 (справа представлены данные для Li = 100<^, слева - для Li = 50^i)

Рисунок 74 - Зависимость интегрального показателя «Площадь по доле блокированных узлов» от плотности сети для алгоритмов «Композит II - cluster» - кривая 3, «Композит II - percolation» - кривая 2 и «Дейкстра II» - кривая 1 (справа представлены данные для Li = 100^i, слева - для Li = 50^i)

На рисунках 73 и 74 представлены зависимости (в абсолютных величинах, см. таблицу 1) интегрального показателя «Площадь по доле блокированных узлов» от плотности сети для алгоритмов «Композит I - cluster» и «Композит I -percolation» (справа представлены данные для Li = 100£, слева - для Li = 50£).

¿0,00

i

1

3 50.00

Я

I

X 40 U0

& щоо

с

* ¡ом

А ,аоо

Рисунок 75 - Зависимость интегрального показателя «Площадь по проценту потерянных сообщений» от плотности сети для алгоритмов «Композит I - cluster» - кривая 3, «Композит I - percolation» - кривая 2 и «Дейкстра I» - кривая 1 (справа представлены данные для Li = 100<^, слева - для Li = 50<^)

^ 4Q0Q

S

ж

Г ЗО Ю

I

I 101»

Рисунок 76 - Зависимость интегрального показателя «Площадь по проценту потерянных сообщений» от плотности сети для алгоритмов «Композит II -cluster» - кривая 3, «Композит II - percolation» - кривая 2 и «Дейкстра II» - кривая 1 (справа представлены данные для Li = 100^, слева - для Li = 50^)

Представленные на рисунках 73 и 74 данные показывают, что зависимость интегрального показателя «Площадь по доле блокированных узлов» от плотности сети для всех алгоритмов носит сложный нелинейный характер и имеет

максимум, примерно находящейся при величине плотности сети, равной 3,08. Однако следует отметить, что во всех случаях все разработанные алгоритмы превосходят алгоритмы класса «Дейкстра» по меньшей доли блокированных узлов (для них доля блокированных узлов меньше при любой плотности сети, как для Li = 100£- , так и для Li = 50£).

На рисунках 75 и 76 представлена (в абсолютных величинах) зависимость интегрального показателя «Площадь по проценту потерянных сообщений» от плотности сети для алгоритмов «Композит I - cluster» и «Композит I -percolation» (справа представлены данные для Li = 100<£, слева - для Li = 50£).

Представленные на рисунках 75 и 76 данные показывают, что величина интегрального показателя «Площадь по проценту потерянных сообщений» в абсолютных единицах снижается при увеличении плотности сети (чем больше плотность, тем меньше процент потерянных сообщений). Однако следует отметить, что во всех случаях все разработанные в диссертации алгоритмы все равно превосходят алгоритмы класса «Дейкстра» по снижению процента потерянных сообщений (для них процент потерянных сообщений меньше при любой плотности сети, как для Li = 100£- , так и для Li = 50£).

Для детального анализа данных, представленных в таблице и на рисунках 73-78, можно вычислить относительный процент изменения интегральных показателей «Площадь по доле блокированных узлов», «Площадь по проценту потерянных сообщений» и «Площадь по среднему времени доставки». Для этого можно соответствующее значение интегрального показателя для любого из алгоритмов «Композит I - cluster», «Композит I - percolation», «Композит II -cluster», «Композит II - percolation», «Композит III - cluster», «Композит III -percolation» разделить на величину соответствующего показателя алгоритма класса «Дейкстра I, II и III».

Для сети с плотностью 3,54 уменьшение относительного процента (относительно алгоритма класса «Дейкстра») доли блокированных узлов при критической длине очереди Li = 100£- составляет примерно 36-40% для алгоритмов «Композит I - cluster» и «Композит I - percolation», и примерно

50-54% для алгоритмов «Композит II - cluster», «Композит II - percolation». При критической длине очереди Li = 50£- уменьшение относительного процента составляет примерно 23-25% для алгоритмов «Композит I - cluster» и «Композит I - percolation», и примерно 32-35% для алгоритмов «Композит II - cluster» и «Композит II - percolation». Таким образом, алгоритмы «Композит II - cluster» и «Композит II - percolation» показывают более высокие результаты по снижению доли блокированных узлов, чем алгоритмы «Композит I - cluster» и «Композит I -percolation». А среди алгоритмов «Композит II - cluster» и «Композит II -percolation» предпочтение можно отдать алгоритму «Композит II - cluster» (напомним, что в нем дополнительное взвешивание узлов в маршруте основано на использовании вероятности образования кластера размером в два блокированных узла).

Для сети с плотностью 3,08 уменьшение относительного процента (относительно алгоритма класса «Дейкстра») доли блокированных узлов при критической длине очереди Li = 100£- составляет примерно 33% для алгоритмов «Композит I - cluster» и «Композит I - percolation», и примерно 47-54% для алгоритмов «Композит II - cluster» и «Композит II - percolation». При критической длине очереди Li = 50£- уменьшение относительного процента составляет примерно 26% для алгоритмов «Композит I - cluster» и «Композит I -percolation», и примерно 35-38% для алгоритмов «Композит II - cluster», «Композит II - percolation». При плотности сети 3,08 алгоритмы «Композит II -cluster» и «Композит II - percolation» также показывают более высокие результаты по снижению доли блокированных узлов, чем алгоритмы «Композит I - cluster» и «Композит I - percolation». А среди алгоритмов «Композит II - cluster» и «Композит II - percolation» предпочтение можно также отдать алгоритму «Композит II - cluster».

Для сети с плотностью 2,57 уменьшение относительного процента (относительно алгоритма класса «Дейкстра») доли блокированных узлов при критической длине очереди Li = 100£- составляет примерно 34% для алгоритмов «Композит I - cluster» и «Композит I - percolation», и примерно 66% для

алгоритмов «Композит II - cluster» и «Композит II - percolation». При критической длине очереди Li = 50£i уменьшение относительного процента составляет примерно 21% для алгоритмов «Композит I - cluster» и «Композит I -percolation» (см. рисунок 73), и примерно 48% для алгоритмов «Композит II -cluster», «Композит II - percolation». При плотности сети 2,57 алгоритмы «Композит II - cluster» и «Композит II - percolation» также показывают более высокие результаты по снижению доли блокированных узлов, чем алгоритмы «Композит I - cluster» и «Композит I - percolation». А среди алгоритмов «Композит II - cluster» и «Композит II - percolation» небольшое предпочтение можно также отдать алгоритму «Композит II - cluster».

Для сети с плотностью 3,54 при критической длине очереди Li = 100£t уменьшение относительного процента (относительно алгоритма «Дейкстра») доли потерянных сообщений примерно одинаково и составляет около 20% для всех алгоритмов «Композит I - cluster», «Композит I - percolation», «Композит II -cluster» и «Композит II - percolation». При критической длине очереди Li = 50£i уменьшение относительного процента для всех алгоритмов составляет около 4%.

Для сети с плотностью 3,08 при критической длине очереди Li = 100£i уменьшение относительного процента (относительно алгоритма класса «Дейкстра») доли потерянных сообщений для алгоритмов «Композит I - cluster» и «Композит I - percolation» одинаково и составляет около 10%, а для алгоритмов «Композит II - cluster» и «Композит II - percolation» - 15-18%. При критической длине очереди Li = 50£i уменьшение относительного процента для всех этих алгоритмов составляет около 4%.

Для сети с плотностью 2,57 при критической длине очереди Li = 100£t уменьшение относительного процента (относительно алгоритма класса «Дейкстра») доли потерянных сообщений для алгоритмов «Композит I - cluster» и «Композит I - percolation» одинаково и составляет около 9%, а для алгоритмов «Композит II - cluster» и «Композит II - percolation» - около 18%. При критической длине очереди Li = 50£t уменьшение относительного процента для алгоритмов «Композит I - cluster» и «Композит I - percolation» одинаково и

составляет около 2%, а для алгоритмов «Композит II - cluster» и «Композит II -percolation» - около 6%.

Из анализа данных для сетей с разной плотностью можно сделать вывод, что по показателю уменьшения относительного процента (относительно алгоритма класса «Дейкстра») доли потерянных сообщений алгоритмы «Композит II - cluster» и «Композит II - percolation» также показывают более высокие результаты, чем алгоритмы «Композит I - cluster» и «Композит I -percolation». А среди алгоритмов «Композит II - cluster» и «Композит II -percolation» небольшое предпочтение также можно отдать алгоритму «Композит II - cluster».

Анализ изменения относительных процентов интегрального показателя «Площадь по доле блокированных узлов» показывает, что при увеличении плотности сети алгоритмы «Композит I - cluster» и «Композит I - percolation» для Li = 100£- наблюдается небольшой рост относительного процента по снижению доли блокированных узлов (чем выше плотность, тем выше процент снижения доли блокированных узлов), а алгоритмы «Композит II - cluster» и «Композит II -percolation», наоборот, показывают некоторое снижение при увеличении плотности. При Li = 50£ с ростом плотности сети алгоритмы «Композит I -cluster» и «Композит I - percolation» показывают небольшое увеличение относительного процента по снижению доли блокированных узлов, а алгоритмы «Композит II - cluster» и «Композит II - percolation» также показывают снижение относительного процента уменьшения доли блокированных узлов (чем ниже плотность, тем выше процент снижения).

Анализ изменения относительных процентов интегрального показателя «Площадь по проценту потерянных сообщений» показывает, что при увеличении плотности сети алгоритмы «Композит I - cluster» и «Композит I - percolation» для Li = 100£- наблюдается рост относительного процента по снижению доли блокированных узлов (чем выше плотность, тем выше процент снижения потерянных сообщений), а алгоритмы «Композит II - cluster» и «Композит II -percolation» почти не показывают изменений. При Li = 50£- с ростом плотности

сети алгоритмы «Композит I - cluster» и «Композит I - percolation» также показывают небольшое увеличение относительного процента по снижению процента потерянных сообщений, а алгоритмы «Композит II - cluster» и «Композит II - percolation», наоборот, показывают снижение относительного процента уменьшения доли блокированных узлов (чем ниже плотность, тем выше процент снижения).

Все это (и динамика изменений по доле блокированных узлов, и по проценту потерянных сообщений) позволяет говорить о том, что для работы и высокопроизводительного оборудования (для которого длина критической очереди обрабатываемых сообщений может быть большой) и малопроизводительного, использование алгоритмов «Композит II - cluster» и «Композит II - percolation» дает некоторое преимущество по сравнению с алгоритмами «Композит I - cluster» и «Композит I - percolation», особенно для сетей с низкой плотностью. А среди алгоритмов «Композит II - cluster» и «Композит II - percolation» небольшое предпочтение можно отдать алгоритму «Композит II - cluster».

Следует отметить, что в любом случае все разработанные алгоритмы дают при использовании больше преимуществ, чем алгоритмы класса «Дейкстра».

По среднему времени доставки сообщений разработанные алгоритмы уступают алгоритму класса «Дейкстра» от 20% до 40%, но следует учитывать, что этот параметр является менее значимым, чем процент потерянных сообщений или доля блокированных узлов.

Следует заметить, что в абсолютных величинах по среднему времени доставки сообщений алгоритмы «Композит I - cluster» и «Композит I -percolation» показывают более высокие результаты (время меньше), чем алгоритмы «Композит II - cluster» и «Композит II - percolation» (см. таблица 1), но проигрывают им во многом другом.

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

на то, что разработанные алгоритмы превосходят по своей надежности алгоритмы класса «Дейкстра».

При малых потоках (до 500 сообщений за шаг) алгоритмы классов «Композит I» и «Композит II» совпадают по результатам работы с алгоритмами класса «Дейкстра I и II», но затем, при повышении нагрузки, начинают его существенно превосходить (и тем сильнее, чем выше интенсивность потока). При увеличении интенсивности потока сообщений на каждом шаге моделирования (см. рисунки 49, 50, 52, 53 и соответствующие рисунки для сетей с плотностью 3,08 и 2,57) алгоритмы класса «Композит I» и «Композит II» при любой плотности сети показывают все больший рост доступности сети по сравнению с алгоритмами класса «Дейкстра» по таким параметрам, как доля блокированных узлов и процент потерянных сообщений. При сравнении между собой алгоритмы класса «Композит II» превосходят алгоритмы класса «Композит I», а внутри класса «Композит II» предпочтение можно отдать алгоритму «Композит II -cluster». Напомним, что в качестве допустимой вероятности Q(L, t) при расчете времени блокировки узла или связи (оценка доступности отдельных элементов сети) в этом алгоритме используется величина, при которой достигается максимум на кривой, описывающей зависимость доли блокированных узлов в кластерах размера S = 2 от обратной величины плотности сети (начинает происходить образование кластеров блокированных узлов малого размера), рассчитанная по формуле ln(JPmax(Qi)} = 3,57 x - 2,33, где x - обратная величина плотности сети. Этот результат можно использовать для балансировки работы высоконагруженных сетей.

4.6.3. Результаты численного моделирования работы алгоритмов балансировки потоков в информационно-вычислительных сетях на основе теории перколяции и стохастической динамики блокировки

сети в целом

При моделировании работы алгоритмов балансировки потоков в ИВС на основе теории перколяции и стохастической динамики блокировки всей сети в целом и их сравнения по эффективности с алгоритмом Дейкстры были разработаны алгоритмы, которые получили названия «Spread I» (порог перколяции достигается в результате перегрузки сети за счет вредоносных потоков, при описании которых не рассматривается ускорение, для расчета плотности вероятности используются функции (3.3a) и (3.3b)) и «Spread II» (порог перколяции также достигается в результате перегрузки сети за счет вредоносных потоков, но рассматривается ускорение и для расчета плотности вероятности используются уравнения (8a) и (8b)). В этих алгоритмах проводится дополнительное «взвешивание» узлов по прогнозируемым значениям времени достижения состояния блокировки, но уже не отдельных узлов, а всей сети в целом (за счет заражения) для ее зависящего от плотности сети порога перколяции. Узлы, у которых время обработки сообщений больше или равно времени достижения порога перколяции, из маршрута исключаются.

1. Для каждого узла (связи) сети задаем некоторое пороговое значение Li - допустимого возможного числа находящихся на нем заявок (или пропускной способности для связи), а также значения числа обрабатываемых на одном шаге (т = 1) заявок Величины ^ и Li выбираются из некоторого случайного диапазона.

2. Для каждого узла (или связи) сети определяем на каждом шаге моделирования т значение параметров: si - входящего числа заявок, xi - длину очереди, а также долю блокированных узлов x0.

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

193

работоспособности за счет заражения узлов вирусами), используя уравнение Л = 4,39г — 2,41, где z - величина, обратная плотности сети.

х Л

4. Вычисляем интеграл Р(Л, 0 =[ 0 р2(х, ¿)(1х + ( р^_(х, ¿)(1х, который

и х0

задает вероятность того, что состояние системы (всей сети в целом) к моменту времени ? будет находиться на отрезке от 0 до Л, т.е. порог перколяции (по заражению узлов вирусами, но не блокировки за счет обработки полезного трафика) не будет достигнут; где X - величина порога перколяции, х0 - доля зараженных вирусами узлов сети на данном шаге моделирования т. Параметры х0, е и £ для вычисления Р(Л, €) при заражении вирусами при проведении численного моделирования можно задать следующим образом. Для примера выберем в = 0,010 (1% от величины числа незараженных узлов сети на данном шаге, за время одного шага т = 1) и £ = 0,005 (0,5% от величины числа зараженных узлов, за время одного шага т = 1). На первом шаге принимаем х0 = 0,01, а на каждом следующем рассчитываем исходя из предыдущего значения х0 и его изменения за счет е и £ на предыдущем шаге. Выбираем в сети случайным образом те узлы, которые являются зараженными, и помечаем их как блокированные. Блокированные таким образом зараженные узлы исключаем из рассмотрения маршрутов до тех пор, пока они не становятся излеченными. При излечивании зараженных узлов их выбор для разблокирования также проводится случайным образом. После излечивания, состояние узлов по числу сообщений на них для продолжения работы считаем таким же, как было в момент заражения.

5. При расчете Р(Л,1) принимаем Ь=1. Допустимый порог работоспособности Р(Л, €) можно выразить через доступность, например, считать, что в сети допустимо не более 5% (или 0,05 доли от единицы, т.е. Р(Л, €) = 0,95) блокированных узлов (или любой заданной величины). Плотности вероятности рг (х, €) и р2 (х, €) в случае перегрузки узлов в результате повышения нагрузки за счет атак, не имеющих характера самоорганизации, можно рассчитывать по формулам (3.3а) и (3.3Ь), а в случае атак, которые учитывают динамику самоорганизации, по формулам (8а) и (8Ь).

При х > х0

cos(п п)

^•Ш-2^)- (8а)

При х < х0

2 { , , , 5 т(пп1 ,х°)зт(ппт)

р2(х,1) = -2-е-^ек(х-х°) '£п-1—(-V л ( ь)

' ' Ь ^-чг-1 ^(пп)

, . г 2а-т-п2п2 I . ил

--ЬП ) ' ( )

где к =

(£-0 2(£2+%2У

£2 + $2 2т

а =

6. Далее, используя формулу Р(Л,1) = р2(х^)йх + ( р1(х^)йх,

0 х°

можно определить время снижения порога доступности, если принять Р(Л,1) = 0,95 начиная с данного момента времени (шага моделирования) для всей сети в целом.

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

как зависимость от величины интенсивности потока среднего времени доставки, числа блокированных узлов, потерянных сообщений и т.д. и сравнить работу разработанных алгоритмов и алгоритма Дейкстры. При их сравнении можно рассмотреть следующие сценарии обработки заявок на узлах:

1. «Композит I». Отправка сообщений после его обработки проводится всегда, но если узел-получатель не активен (блокирован заявками), то сообщение ставится на нем в очередь. Узел после блокировки считается снова свободным, когда очередь уменьшается до величины 0,5Li, где Li - принятый максимальный размер очереди для данного i-го узла сети (величина Li задается в единицах числа, обрабатываемых за один шаг т = 1 данным узлом, сообщений £).

2. «Композит II». Его отличие от «Композит I» заключается только в том, что узел после блокировки снова считается свободным, когда очередь просто становится меньше величины Li.

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

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

Справа на рисунках 77-102 представлены данные для Li = 100<£, а с левой стороны - для Li = 50<£..

Вертикальные линии на рисунках 77-84 соответствуют шагу 150, после которого прекращается генерация сообщений в сети.

Рассмотрим случайную сеть с плотностью связей 3,54

Кривые 1 на рисунках 77-84 соответствуют поведению алгоритма Дейкстры, кривые 2 - алгоритму «Композит I - spread I», кривые 3 на рисунках описывают поведение алгоритма «Композит I - spread II».

« "

I

Рисунок 77 - Результаты моделирования величины среднего числа сообщений в очереди узла на обработку в зависимости от шага моделирования (при интенсивности потока 1500 сообщений)

! »

в * ив ж ж пс ь £ ¡5 5 Хс л7 5 м

иш т «1Мги

Рисунок 78 - Результаты моделирования величины среднего числа сообщений в очереди узла на обработку в зависимости от шага моделирования (при интенсивности потока 500 сообщений)

На рисунке 75 представлены результаты моделирования величины среднего числа сообщений в очереди на обработку в зависимости от шага моделирования при интенсивности потока 1500 сообщений (на каждом шаге), а на рисунке 78 -при интенсивности потока 500 сообщений.

На рисунке 79 представлены результаты моделирования величины средней загрузки узлов в зависимости от шага моделирования при интенсивности потока 1500 сообщений (на каждом шаге), а на рисунке 80- при интенсивности потока 500 сообщений.

Рисунок 79 - Результаты моделирования величины средней загрузки узлов в зависимости от шага моделирования (при интенсивности потока 1500 сообщений)

Рисунок 80 - Результаты моделирования величины средней загрузки узлов в зависимости от шага моделирования (при интенсивности потока 500 сообщений)

На рисунке 81 представлены результаты моделирования величины потерянных сообщений в зависимости от шага моделирования при интенсивности потока 1500 сообщений (на каждом шаге), а на рисунке 82 - при интенсивности потока 500 сообщений.

Рисунок 81 - Результаты моделирования величины числа потерянных сообщений

в зависимости от шага моделирования (при интенсивности потока 1500 сообщений)

Рисунок 82 - Результаты моделирования величины числа потерянных сообщений

в зависимости от шага моделирования (при интенсивности потока 500 сообщений)

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

скачкообразная потеря сообщений. Повторяемость этого процесса отражена в осцилляциях на графиках на рисунках 80-82.

На рисунке 83 представлены результаты моделирования величины доли блокированных узлов в зависимости от шага моделирования при интенсивности потока 1500 сообщений (на каждом шаге), а на рисунке 84 - при интенсивности потока 500. Горизонтальные линии на рисунках 83 и 84 показывают величину порога перколяции. Отметим, что при этом проводимость сети в целом прекращается, но это не означает, что не может продолжаться работа и блокирование ее отдельных узлов. В данном случае речь идет о блокировках, вызванных перегрузкой, а не заражением узлов (рисунки 85 и 86).

Рисунок 83 - Результаты моделирования величины доли блокированных (в результате превышения очередей) узлов в зависимости от шага моделирования (при интенсивности потока 1500 сообщений)

Рисунок 84 - Результаты моделирования величины доли блокированных (в результате превышения очередей) узлов в зависимости от шага моделирования (при интенсивности потока 500 сообщений)

I

"п

1 011 * В 1С

м

ьос ,-- ---

• ятяояомпм * * *■* 01

ш, ко

Рисунок 85 - Результаты моделирования величины доли инфицированных узлов в зависимости от шага моделирования (при интенсивности потока

1500 сообщений)

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

Рисунок 86 - Результаты моделирования величины доли инфицированных узлов в зависимости от шага моделирования (при интенсивности потока

500 сообщений)

Поведение кривых 1-3 на рисунках 77-86 показывает сложный характер динамики работы моделируемых алгоритмов. Более наглядное и информативное представление результатов численного моделирования и их описание можно получить, если построить и проанализировать:

1) зависимости от интенсивности потока сообщений средней доли блокированных узлов сети (рассчитывается для всей сети, по всему времени моделирования);

2) зависимости от интенсивности потока процента или доли потерянных сообщений. Напомним, что потерянным сообщением считается сообщение, которое не может быть доставлено, т.к. для него нет неблокированного пути. Такое сообщение помечается как недоставленное и исключается из дальнейшего рассмотрения;

3) зависимости от интенсивности потока среднего времени доставки сообщений (рассчитывается для всей сети, по всему времени моделирования).

На рисунке 87 представлена зависимость от интенсивности потока сообщений средней доли блокированных (в результате перегрузки) узлов сети для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 87 - Результаты моделирования зависимости от интенсивности потока сообщений средней доли блокированных (в результате перегрузок) узлов сети для алгоритмов «Композит I - spread II» - кривая 3, «Композит I - spread I» - кривая 2

и «Дейкстра I» - кривая 1

Рисунок 87 показывает, что, если при балансировке потоков сообщений в условиях распространения вирусов и блокировки узлов как в результате достижения критических величин очередей на узлах, так и их блокировки вирусами, процент потерянных сообщений зависит от того, по какой модели будет описываться процесс заражения узлов - «Spred I» или «Spred II».

При использовании модели «Spred I» (кривая 2) при всех интенсивностях потоков сообщений наблюдается большее уменьшение средней доли блокированных узлов, чем при использовании модели «Spred II» (кривая 3), которая показывает результаты, близкие к алгоритму «Дейкстра I». Таким образом, по этому показателю алгоритм «Spred I» выигрывает у алгоритмов «Spred II» и «Дейкстра I», показывающих близкие друг другу результаты.

На рисунке 88 представлена зависимость от интенсивности потока средней доли инфицированных узлов для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I». Как видно из рисунка, и по этому показателю при использовании алгоритма «Композит I - spread I» (кривая 2) наблюдается существенное преимущество, т.е. происходит заражение меньшей доли узлов.

Рисунок 88 - Результаты моделирования зависимости от интенсивности потока сообщений средней доли инфицированных узлов сети для алгоритмов «Композит I - spread II» - кривая 3, «Композит I - spread I» - кривая 2 и «Дейкстра I» -

кривая 1

На рисунке 89 представлена зависимость от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - spread I», «Композит I -spread II» и «Дейкстра I».

Рисунок 89 - Результаты моделирования зависимости от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - spread II» -кривая 3, «Композит I - spread I» - кривая 2 и «Дейкстра I» - кривая 1

Рисунок 89 показывает, что, если при балансировке потоков сообщений в условиях распространения вирусов и блокировки узлов как в результате достижения критических величин очередей на узлах, так и их блокировки вирусами, процент потерянных сообщений существенно зависит от того, по какой модели будет описываться процесс заражения узлов - «Spred I» или «Spred II». При использовании модели «Spred I» (кривая 2) наблюдается больший процент потерь, чем при использовании модели «Spred II» (кривая 3), которая показывает результаты, близкие к алгоритму «Дейкстра I». Таким образом, по показателю «процент потерянных сообщений» алгоритм «Spred I» проигрывает алгоритмам «Spred II» и «Дейкстра I», показывающих близкие друг другу результаты.

На рисунке 90 представлена зависимость от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 90 - Результаты моделирования зависимости от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит I - spread II» - кривая 3, «Композит I - spread I» - кривая 2 и «Дейкстра I» - кривая 1

Рисунок 90 показывает, что при использовании модели «Spred I» (кривая 2) наблюдается более существенный выигрыш по показателю «среднее время доставки сообщений», чем при использовании модели «Spred II» (кривая 3), которая показывает результаты, близкие к алгоритму «Дейкстра I». Таким образом, по показателю «среднее время доставки сообщений» алгоритм «Spred I» выигрывает у алгоритмов «Spred II» и «Дейкстра I», показывающих близкие друг другу результаты.

Можно сделать общий вывод (см. рисунки 85-90), что при использовании для балансировки потоков алгоритма «Композит I - spred I» (кривые 2) наблюдается более существенный выигрыш по показателю «среднее время доставки сообщений», выигрыш по показателю «средняя доля блокированных узлов» и «средняя доля инфицированных узлов», чем при использовании алгоритмов «Композит I - spred II» (кривые 3) и «Дейкстра I» (кривые 1). Однако он проигрывает им по показателю «процент потерянных сообщений». Это объясняется тем, что при сокращении числа обрабатываемых сообщений освобождаются ресурсы для обработки оставшихся. Например, при введении приоритезации скорость доставки высокоприоритетных сообщений, как и работоспособность всей сети, будет возрастать за счет потери менее критичных сообщений.

На рисунке 91 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II -spread I», «Композит II - spread II» и «Дейкстра II».

Рисунок 91 показывает, что по этому показателю алгоритм «Композит II -spread I» показывает лучшие результаты, чем при использовании для управления потоками алгоритмов «Композит II - spread II» и «Дейкстра II».

т мв во юоо им мм яо ш т ш мм ом мм

И*-«»«—mi iv чипа« .orfur««* M4WI ими «пи Ш^ум*

Рисунок 91 - Результаты моделирования зависимости средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2

и «Дейкстра II» - кривая 1

На рисунке 92 представлена зависимость средней доли инфицированных узлов для алгоритмов «Композит II - spread I», «Композит II - spread II» и «Дейкстра II». Как видно из рисунка, использование алгоритма «Композит II -spread I» (кривая 2) также приводит к лучшим результатам, чем алгоритмов «Композит II - spread II» и «Дейкстра II».

Рисунок 92 - Результаты моделирования зависимости средней доли инфицированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2

и «Дейкстра II» - кривая 1

На рисунке 93 представлена зависимость процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - spread I», «Композит II -spread II» и «Дейкстра II».

2 /

/ 3

UM ДОС

1

// /У

П «О СП М Ш1 ИМ 14М

Рисунок 93 - Результаты моделирования зависимости процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - spread II» -кривая 3, «Композит II - spread I» - кривая 2 и «Дейкстра II» - кривая 1

На рисунке 94 представлена зависимость от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит II - spread I», «Композит II - spread II» и «Дейкстра II».

Рисунок 94 - Результаты моделирования зависимости среднего времени доставки сообщений от интенсивности потока сообщений для алгоритмов «Композит II -spread II» - кривая 3, «Композит II - spread I» - кривая 2 и «Дейкстра II» - кривая 1

Проанализировав рисунки 91-94, можно сделать общий вывод, что при использовании для балансировки потоков алгоритма «Композит II - spred I» (кривые 2) наблюдается более существенный выигрыш по показателю «среднее время доставки сообщений», по показателю «средняя доля блокированных узлов» и «средняя доля инфицированных узлов», чем при использовании алгоритмов «Композит II - spred II» (кривые 3) и «Дейкстра II» (кривые 1). Однако он проигрывает им по показателю «процент потерянных сообщений».

Анализ всех полученных результатов для сети с плотностью связей 3,54 (см. рисунки 87-94) говорит о том, что среди алгоритмов классов «Spred» и большими преимуществами для балансировки потоков по таким показателям, как «среднее время доставки сообщений», «средняя доля блокированных узлов» и «средняя доля инфицированных узлов» обладают алгоритмы класса «Spred I» («Композит I - spred I» и «Композит II - spred I»). Если в качестве показателя выбрать минимизацию «процента потерянных сообщений», то необходимо использовать алгоритмы класса «Spred II» («Композит I - spred II» и «Композит II - spred II»).

Рассмотрим случайную сеть с плотностью связей 3,08

Для снижения информационной нагрузки при анализе данных для сети с такой плотностью графические зависимости от шага моделирования величины доли блокированных узлов; величины средней загрузки; среднего числа сообщений в очереди узла на обработку и числа потерянных сообщений мы рассматривать не будем. Они имеют характер поведения, схожий с динамикой, описанной для сети с плотностью 3,54, поэтому сразу перейдем к описанию и анализу обобщенных характеристик.

На рисунке 95 представлена зависимость от интенсивности потока сообщений средней доли блокированных узлов сети для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 95 - Результаты моделирования зависимости от интенсивности потока сообщений средней доли блокированных узлов сети для алгоритмов «Композит I - spread II» - кривая 3, «Композит I - spread I» - кривая 2

и «Дейкстра I» - кривая 1

На рисунке 96 представлена зависимость от интенсивности потока сообщений средней доли инфицированных узлов для алгоритмов «Композит I -spread I», «Композит I - spread II» и «Дейкстра I».

SO «Я М М пи ЮТ VOT JM се ОТ ВО MB UN шл

ЧЧМК» 1ЙШ<ЩЧ>-адтт»»

Рисунок 96 - Результаты моделирования зависимости от интенсивности потока сообщений средней доли инфицированных узлов сети для алгоритмов «Композит I - spread II» - кривая 3, «Композит I - spread I» - кривая 2

и «Дейкстра I» - кривая 1

На рисунке 97 представлена зависимость от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - spread I», «Композит I -spread II» и «Дейкстра I».

/ 3

// у

А

Рисунок 97 - Результаты моделирования зависимости от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - spread II» -кривая 3, «Композит I - spread I» - кривая 2 и «Дейкстра I» - кривая 1

На рисунке 98 представлена зависимость от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 98 - Результаты моделирования зависимости от интенсивности потока

сообщений среднего времени их доставки для алгоритмов «Композит I -spread II» - кривая 3, «Композит I - spread I» - кривая 2 и «Дейкстра I» - кривая 1

На рисунке 99 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II -spread I», «Композит II - spread II» и «Дейкстра II».

ЯО «м

Рисунок 99 - Результаты моделирования зависимости средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2

и «Дейкстра II» - кривая 1

На рисунке 100 представлена зависимость средней доли инфицированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II -spread I», «Композит II - spread II» и «Дейкстра II».

яш жп тх ко

Рисунок 100 - Результаты моделирования зависимости средней доли инфицированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2

и «Дейкстра II» - кривая 1

На рисунке 101 представлена зависимость процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - spread I», «Композит II -spread II» и «Дейкстра II».

Рисунок 101 - Результаты моделирования зависимости процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - spread II» -кривая 3, «Композит II - spread I» - кривая 2 и «Дейкстра II» - кривая 1

На рисунке 102 представлена зависимость от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит II - spread I», «Композит II - spread II» и «Дейкстра II».

Рисунок 102 - Результаты моделирования зависимости среднего времени доставки сообщений от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2

и «Дейкстра II» - кривая 1

Рисунки 95-102 показывают, что для сети с плотностью связей 3,08 в целом наблюдаются результаты, схожие с полученными при моделировании процессов в сети с плотностью связей 3,54. И их анализ позволяет сделать выводы, аналогичные полученным при анализе данных для сети с плотностью связей 3,54. Рассмотрим случайную сеть с плотностью связей 2,57 Для снижения информационной нагрузки при анализе данных для сети с такой плотностью графические зависимости от шага моделирования величины доли блокированных узлов; величины средней загрузки; среднего числа сообщений в очереди узла на обработку и числа потерянных сообщений мы рассматривать не будем. Они имеют характер поведения, схожий с динамикой, описанной для сети с плотностью 3,54 и 3,08, поэтому сразу перейдем к описанию и анализу обобщенных характеристик.

На рисунке 103 представлена зависимость от интенсивности потока сообщений средней доли блокированных узлов сети для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 103 - Результаты моделирования зависимости от интенсивности потока сообщений средней доли блокированных узлов сети для алгоритмов «Композит I - spread II» - кривая 3, «Композит I - spread I» - кривая 2

и «Дейкстра I» - кривая 1

На рисунке 104 представлена зависимость от интенсивности потока сообщений средней доли инфицированных узлов сети для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 104 - Результаты моделирования зависимости от интенсивности потока сообщений средней доли инфицированных узлов сети для алгоритмов «Композит I - spread II» - кривая 3, «Композит I - spread I» - кривая 2

и «Дейкстра I» - кривая 1

На рисунке 105 представлена зависимость от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 105 - Результаты моделирования зависимости от интенсивности потока процента потерянных сообщений для алгоритмов «Композит I - spread II» -кривая 3, «Композит I - spread I» - кривая 2 и «Дейкстра I» - кривая 1

На рисунке 106 представлена зависимость от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит I - spread I», «Композит I - spread II» и «Дейкстра I».

Рисунок 106 - Результаты моделирования зависимости от интенсивности потока

сообщений среднего времени их доставки для алгоритмов «Композит I -spread II» - кривая 3, «Композит I - spread I» - кривая 2 и «Дейкстра I» - кривая 1

На рисунке 107 представлена зависимость средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II -spread I», «Композит II - spread II» и «Дейкстра II».

JVM им

Рисунок 107 - Результаты моделирования зависимости средней доли блокированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2

и «Дейкстра II» - кривая 1

На рисунке 108 представлена зависимость средней доли инфицированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II -spread I», «Композит II - spread II» и «Дейкстра II».

Рисунок 108 - Результаты моделирования зависимости средней доли инфицированных узлов сети от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2 и

«Дейкстра II» - кривая 1

На рисунке 109 представлена зависимость процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - spread I», «Композит II -spread II» и «Дейкстра II».

Рисунок 109 - Результаты моделирования зависимости процента потерянных сообщений от интенсивности потока для алгоритмов «Композит II - spread II» -кривая 3, «Композит II - spread I» - кривая 2 и «Дейкстра II» - кривая 1

На рисунке 110 представлена зависимость от интенсивности потока сообщений среднего времени их доставки для алгоритмов «Композит II - spread I», «Композит II - spread II» и «Дейкстра II».

Рисунок 110 - Результаты моделирования зависимости среднего времени доставки сообщений от интенсивности потока сообщений для алгоритмов «Композит II - spread II» - кривая 3, «Композит II - spread I» - кривая 2

и «Дейкстра II» - кривая 1

Рисунки 103-110 показывают, что для сети с плотностью связей 2,57 в целом наблюдаются результаты, схожие с полученными при моделировании процессов в сетях с плотностью связей 3,54 и 3,08. Их анализ позволяет сделать

выводы, аналогичные полученным при анализе данных для сети с плотностью связей 3,54 и 3,08.

Для количественного и обобщенного сравнения характеристик работы алгоритмов классов «Композит» и «Дейкстра» при разной плотности сети (см. таблицу 2) можно ввести интегральные показатели, определяющие, насколько различаются площади под кривыми, описывающими зависимость от интенсивности потока сообщений доли блокированных узлов, процента потерянных сообщений и среднего времени доставки для рассматриваемых алгоритмов (в диапазоне интенсивности потоков от 100 до 1500 сообщений на одном шаге).

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

рассматриваемых алгоритмов

№ Алгоритм Величина Li Плотность сети

3,54 3.08 2.57

Площадь по доле блокирован ных узлов Площадь по доле инфициро ванных узлов Площадь по проценту потерянн ых сообщени й Площадь по времени доставки Площадь по доле блокирова нных узлов Площадь по доле инфицирова нных узлов Площадь по проценту потерянн ых сообщени й Площадь по времени доставки Площад ь по доле блокиро ванных узлов Площадь по доле инфициро ванных узлов Площадь по проценту потерянн ых сообщени й Площадь по времени доставки

1. «Композит I - spread I» L, = 502, 0,0177 0,2706 85,8259 14,1744 0,0262 0,2664 83,1396 17,8453 0,0278 0,2797 87,2569 20,3434

2. L, = 1002, 0,0044 0,2709 85,8517 15,6106 0,0078 0,2668 83,0834 20,6091 0,0107 0,2801 87,3165 27,3725

3. «Композит I - spread II» L, = 502 0,0409 0,2769 72,9909 29,3545 0,0401 0,2767 78,8820 27,5574 0,0318 0,2769 88,0219 21,1177

4. L, = 1002, 0,0202 0,2841 69,1350 50,7888 0,0221 0,2850 74,9051 48,6929 0,0183 0,2834 86,6821 35,4665

5. «Дейкстра I» L, = 502 0,0414 0,2741 73,9530 28,9843 0,0427 0,2760 79,1763 27,7665 0,0297 0,2779 87,5254 21,8082

6. L, = 1002, 0,0207 0,2854 70,2932 53,0393 0,0214 0,2849 77,2452 48,2597 0,0146 0,2810 88,6823 33,2535

7. «Композит II - spread I» L, = 502 0,0144 0,2708 85,6522 14,3400 0,0187 0,2663 83,5017 18,1802 0,0205 0,2768 87,9454 21,7554

8. L, = 1002, 0,0021 0,2709 85,6730 15,1570 0,0051 0,2681 83,6958 20,4500 0,0065 0,2845 88,0336 29,7721

9. «Композит II - spread II» L, = 502, 0,0373 0,2780 71,4067 35,4134 0,0346 0,2811 77,1789 33,6509 0,0231 0,2781 87,3249 23,3137

10. L, = 1002, 0,0123 0,2852 67,7675 59,4260 0,0143 0,2878 75,6359 55,5273 0,0108 0,2880 87,1251 40,4983

11. «Дейкстра II» L, = 502, 0,0358 0,2777 72,2018 35,3705 0,0328 0,2816 79,1756 32,8194 0,0232 0,2806 88,5366 24,1986

12. L, = 1002, 0,0131 0,2865 67,4655 61,4077 0,0132 0,2886 75,9853 54,9012 0,0105 0,2875 87,4503 39,2244

На рисунке 111 представлена зависимость интегрального показателя «площадь по доле блокированных узлов» от плотности сети для алгоритмов «Дейкстра I» - кривая 1, «Композит I - spread I» - кривая 2 и «Композит I - spread II» - кривая 3, а на рисунке 112 - для алгоритмов «Дейкстра II» - кривая 1, «Композит II - spread I» - кривая 2 и «Композит II - spread II» - кривая 3.

Рисунок 111 - Зависимость интегрального показателя «площадь по доле блокированных узлов» от плотности сети для алгоритмов «Дейкстра I» - кривая 1, «Композит I - spread I» - кривая 2 и «Композит I - spread II» - кривая 3 (справа представлены данные для Li = 100£i, слева - для Li = 50£i)

Рисунок 112 - Зависимость интегрального показателя «площадь по доле блокированных узлов» от плотности сети для «Дейкстра II» - кривая 1, «Композит II - spread I» - кривая 2 и «Композит II - spread II» - кривая 3 (справа представлены данные для Li = 100£i, слева - для Li = 50£i)

Как показывают рисунки 111 и 112, алгоритмы «Композит I - spread I» и «Композит II - spread I» существенно выигрывает по этому показателю у

алгоритмов «Композит I - spread II», «Дейкстра I» и «Композит II - spread II», «Дейкстра II». Следует обратить внимание, что зависимость этого показателя снижается при увеличении плотности сети, в то время как у алгоритмов «Композит I - spread II», «Дейкстра I» и «Композит II - spread II», «Дейкстра II» она может увеличиваться.

На рисунке 113 представлена зависимость интегрального показателя «площадь по доле инфицированных узлов» от плотности сети для алгоритмов «Дейкстра I» (кривая 1), «Композит I - spread I» (кривая 2) и «Композит I - spread II» (кривая 3), а на рисунке 114 - для алгоритмов «Дейкстра II» (кривая 1), «Композит II - spread I» (кривая 2) и «Композит II - spread II» (кривая 3).

Рисунок 113 - Зависимость интегрального показателя «площадь по доле инфицированных узлов» от плотности сети для алгоритмов «Дейкстра I» - кривая 1, «Композит I - spread I» - кривая 2 и «Композит I - spread II» - кривая 3 (справа представлены данные для Li = 100£i, слева - для Li = 50£i)

Рисунок 114 - Зависимость интегрального показателя «площадь по доле инфицированных узлов» от плотности сети для «Дейкстра II» - кривая 1,

«Композит II - spread I» - кривая 2 и «Композит II - spread II» - кривая 3 (справа представлены данные для Li = 100£i, слева - для Li = 50£i)

Как показывают рисунки 113 и 114, алгоритмы «Композит I - spread I» и «Композит II - spread I» выигрывают по этому показателю у алгоритмов «Композит I - spread II», «Дейкстра I» и «Композит II - spread II», «Дейкстра II». Следует обратить внимание, что зависимость этого показателя от величины плотности сети для алгоритмов «Композит I - spread I» и «Композит II - spread I» проходит через минимум для плотности 3,08.

На рисунке 115 представлена зависимость интегрального показателя «площадь по проценту потерянных сообщений» от плотности сети для алгоритмов «Дейкстра I» (кривая 1), «Композит I - spread I» (кривая 2) и «Композит I - spread II» (кривая 3), а на рисунке 116 - для алгоритмов «Дейкстра II» (кривая 1 ), «Композит II - spread I» (кривая 2) и «Композит II - spread II» (кривая 3).

£ W®

Рисунок 115 - Зависимость интегрального показателя «площадь по проценту потерянных сообщений» от плотности сети для алгоритмов «Дейкстра I» - кривая 1, «Композит I - spread I» - кривая 2 и «Композит I - spread II» - кривая 3 (справа представлены данные для Li = 100£i, слева - для Li = 50£i)

0,00

Рисунок 116 - Зависимость интегрального показателя «площадь по проценту потерянных сообщений» от плотности сети для алгоритмов «Дейкстра II» -кривая 1, «Композит II - spread I» - кривая 2 и «Композит II - spread II» - кривая 3 (справа представлены данные для Li = 100£i, слева - для Li = 50£i)

Как показывают рисунки 115 и 116, алгоритмы «Композит I - spread I» и «Композит II - spread I» проигрывают по этому показателю алгоритмам «Композит I - spread II», «Дейкстра I» и «Композит II - spread II», «Дейкстра II». Следует обратить внимание, что зависимость этого показателя от величины плотности сети для алгоритмов «Композит I - spread I» и «Композит II - spread I» является почти постоянной, а для остальных алгоритмов почти линейно снижается с увеличением плотности сети. Также следует заметить, что этот показатель практически не зависит от того, каким образом задана критическая длина очереди (справа на рисунках 115 и 116 представлены данные для Li = 100^, а с левой стороны - для Li = 50£).

Анализ всех полученных результатов для сетей с разной плотностью связей (см. рисунки 111-116) говорит о том, что предпочтение выбора алгоритма маршрутизации зависит от выбора показателя. Если в качестве показателя выбрать минимизацию «процента потерянных сообщений», то необходимо использовать алгоритм «Композит I - spred II» или алгоритм «Композит II - spred II»; если выбрать минимизацию «среднего времени доставки сообщений», «средней доли блокированных узлов» или «средней доли зараженных узлов», то

необходимо отдать предпочтение алгоритму «Композит I - spred I» или «Композит II - spread I».

4.6. Использование метрик стоимости маршрута в алгоритмах и протоколах маршрутизации на основе разработанных моделей

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

Для локальных сетей может быть использован, например, иерархический динамический многомаршрутный алгоритм, учитывающий состояние каналов либо вектора расстояний и ориентирующийся не просто на «первоочередность наикратчайшего маршрута», а на состояние критичности для каждого узла (или группы узлов). Таким образом, кратчайшее расстояние выбирается с учетом того, что некоторые узлы могут оказаться в ближайшее время в состоянии перегруженности и потому должны быть исключены из выбора узлов кратчайшего маршрута для отправки пакета. Для осуществления подобных алгоритмов могут быть использованы протоколы внутренней динамической маршрутизации, например протокол RIP (Routing Information Protocol). Однако в таком случае необходимо, чтобы в таблице маршрутов присутствовала информация о том, насколько каждый из узлов сети находится близко к состоянию блокировки, и предсказанная информация о времени, в течение которого узел достигнет критического порога. Узлы, находящиеся в перегруженном состоянии, могут быть исключены из маршрутов (с помощью метрик) для всех пакетов данных, если пунктом назначения пакетов данных не являются исключенные узлы.

Выбор оптимального пути может осуществляться путем анализа ориентированного графа сети по алгоритму Дейкстры. При анализе графа сети от

узла отправки до узла назначения рассчитываются суммарные значения метрик, и пути с наименьшим значением метрики считаются наилучшими.

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

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

Для региональных и глобальной сети можно использовать протоколы внешних маршрутизаторов, таких как EGP, BGP, EIGRP. При этом в протоколе BGP веса маршрутов нужно определять с учетом состояний узлов (или групп узлов) таким образом, что близость узла (группы) к критическому состоянию будет увеличивать вес данного маршрута и таким образом влиять на выбор приоритетов. В случае использования протокола EGP формат пакета должен содержать сведения о возможных изменениях состояния узла сети или (для протокола BGP) дополнительные сообщения об изменении маршрутов, связанные с возможными перегрузками узлов. А в случае использования EIGRP параметр Reliability (Надежность) может задаваться на основе расчитанной вереятности блокировния узла в пути маршрута, согласно моделям стахостической динамики и топологии сети.

Разработанные модели также могут быть использованы и в многопутевой QoS-маршрутизации. При которой обеспечивается приоритетное управление сетевым трафиком.

Выделяют следующие 4 типа задач QoS-маршрутизации [307] :

1. MCP QoS-маршрутизация.

2. MCOP QoS-маршрутизация.

3. CSP QoS-маршрутизация.

4. LARAC QoS-маршрутизация.

В основе большиства алгоритмов для решения задачи многопутевой QoS-маршрутизации лежат хорошо известные алгоритма поиска кратчайшего пути, такие как алгоритм Дейкстры или алгоритм Беллмана - Форда.

Во всех них предполагается использовать параметр стоимости (cost) -некоторую внешнюю функцию расчёта по интересующей метрике. Так если в качестве функции стоимости задать время достижения его блокировки по формуле (3.4). Тем самым проактивно перестроить таблицу маршрутизации, перераспределяя нагрузку с узлов, находящиеся в предкритическом состоянии.

4.7. Выводы

В диссертационной работе на основе методов теории перколяции и моделей стохастической динамики блокировки как отдельных узлов (связей), так и всей сетевой структуры в целом были разработаны новые алгоритмы маршрутизации и балансировки потоков в ИВС, имеющих случайную структуру. Эти алгоритмы получили названия «Композит I - percolation», «Композит II - percolation», «Композит III - percolation», «Композит I - cluster», «Композит II - cluster» и «Композит III - cluster», «Композит I - spred I», «Композит I - spred II», «Композит II - spred I» и «Композит II - spred II».

Исходя из сценариев блокировки узлов и обработки на них сообщений, разработанные алгоритмы относятся к следующим классам:

Класс «Композит I». Отправка сообщений после обработки проводится всегда, но если узел получатель не активен (блокирован), то сообщение ставится на нем в очередь. Узел после блокировки считается снова свободным, когда очередь уменьшается до величины 0,5Li, где Li — принятый максимальный размер очереди для данного i-го узла сети (величина Li задается в единицах числа, обрабатываемых за один шаг т = 1, данным узлом сообщений £i).

Класс «Композит II». Его отличие от «Композит I» в том, что узел после блокировки считается свободным, когда очередь обрабатываемых сообщений для этого узла становится меньше величины Li.

Класс «Композит III». Алгоритм, в котором при превышении порога L узлы не считаются блокированными. Они продолжают работать со своей производительностью, на них отправляются сообщения. В практическом смысле предполагается для очереди сообщений на узле наличие бесконечного буфера. Например, в случае, когда узел может быть низкопроизводительным, но при этом хранение очереди сообщений «дешевое», мы можем позволить себе накапливать сообщения без ограничений.

При сравнении работы алгоритмов классов «Композит I», «Композит II» и «Композит III» с работой алгоритма Дейкстры также учитывались описанные выше сценарии обработки заявок на узлах, поэтому при описании полученных результатов были использованы наименования «Дейкстра I», «Дейкстра II» и «Дейкстра III».

Работа алгоритмов, в название которых входит слово «percolation», основана на том, что в качестве допустимой вероятности Q(L, t) при расчете времени блокировки узла или связи (доступность отдельных элементов сети) при использовании выведенных в работе стохастических уравнений применяется величина порога перколяции, рассчитанная по уравнению y = 4,39 z - 2,41, где y = ln(Q(L, t)), а z - величина, обратная плотности сети.

Работа алгоритмов, в название которых входит слово «cluster», основана на том, что в качестве допустимой вероятности Q(L, t) при расчете времени блокировки узла или связи (доступность отдельных элементов) при использовании выведенных в работе стохастических уравнений используется величина, при которой достигается максимум на кривой, описывающей зависимость доли блокированных узлов в кластерах размера S = 2 от обратной величины плотности сетей (начинает происходить образование кластеров блокированных узлов малого размера), рассчитанная по формуле ln(Pmax(Qz)} = 3,57 x - 2,33, где x - обратная величина плотности сети.

На основании величины времени достижения блокировки узла или связи, для них может быть рассчитан коэффициент (который пропорционален обратному времени блокировки: чем больше время достижения блокировки, тем

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

В алгоритмах классов «Spread I» и «Spread II» (порог перколяции достигается в результате перегрузки сети за счет вредоносных потоков) на каждом шаге при выборе маршрутов сравниваются значения времени достижения порога перколяции сети (за счет заражения узлов) и время обработки заявок на узлах.

Динамика вредоносных потоков может существенно отличаться от динамики невредоносных и должна быть описана на основе иных стохастических уравнений. Подробно этому описанию посвящена глава 3 диссертации, однако это должно учитываться в работе алгоритмов.

В этих алгоритмах проводится дополнительное «взвешивание» узлов по прогнозируемым значеням времени достижения состояния блокировки, но уже не отдельных узлов, а всей сети целиком (для зависящего от плотности сети порога перколяции). Узлы, у которых время обработки сообщений больше или равно времени достижения порога перколяции, сетью из маршрута исключаются.

На основе анализа результатов численного моделирования работы алгоритмов балансировки потоков в ИВС, имеющих случайную структуру и плотность от 2,57 до 3,54 связи в расчете на один узел, можно сделать ряд важных выводов.

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

При малых интенсивностях потоков (до 500 сообщений за шаг) алгоритмы классов «Композит I - cluster и percolation» и «Композит II - cluster и percolation» совпадают по результатам работы с алгоритмами, в которых балансировка нагрузки на узлах не осуществляется, но при увеличении нагрузки разработанные алгоритмы начинают существенно превосходить (и тем сильнее, чем больше интенсивность потока) традиционные решения на базе алгоритмов Дейкстры.

В частности, в зависимости от возможной производительности узлов по обработке сообщений, алгоритмы классов «Композит I - cluster», «Композит I -percolation», «Композит II - cluster» и «Композит II - percolation» могут показывать повышение работоспособности и увеличение доступности по следующим показателям:

1) «доля блокированных узлов» - примерно на 30-65% по сравнению с алгоритмами, в которых балансировка нагрузки на узлах не осуществляется (в зависимости от плотности сети и того, какой именно алгоритм из двух предложенных классов используется - «Композит I» или «Композит II») для высокопроизводительной обработки заявок на узлах (Li = 100£г), и примерно на 30-55% для низкопроизводительной обработки заявок на узлах (Li = 50£г). Среди алгоритмов «Композит I - cluster», «Композит I - percolation», «Композит II -cluster» и «Композит II - percolation» лучшие результаты показывают «Композит II - cluster» и «Композит II - percolation», а среди алгоритмов класса «Композит II» лучшим является «Композит II - cluster»;