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

Федеральное государственное бюджетное учреждении науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

На правах рукописи

005052454

Подкорытов Дмитрий Игоревич

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Я4 0КТ 2012

Новосибирск - 2012

005052454

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

Научный руководитель: Родионов Алексей Сергеевич, д.т.н., с.н.с. Официальные оппоненты: Окольнишников Виктор Васильевич,

Защита состоится 02 октября 2012г. в 16 часов 30 минут на заседании диссертационного совета Д 003.ОСІ.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук но адресу: 030090, г. Новосибирск, пр. ак. Лаврентьева, С

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Автореферат разослан 1 сентября 2012г.

д.т.н., с.н.с., ведущий научный сотрудник КТИ ВТ СО РАН

Куликов Игорь Михайлович, к.ф.-м.н., научный сотрудник ИВМиМГ СО РАН

Ведущая организация: Федеральное государственное бюджетное образо-

вательное учреждение высшего профессионального образования "Новосибирский государственный технический университет''

диссертационного совета, д.ф.-м.н., проф.

Общая характеристика работы

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

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

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

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

2. Разработана архитектура MAC имитационного моделирования AGNES (AGent NEtwork Simulator).

3. Разработаны и реализованы:

• среда исполнения AGNES.

• библиотека агентов для построения моделей локально-вычислитель-

ных сстсй, и модель исследования методов проведения и средств защиты от DDoS атак.

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

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

Научная новизна заключается в:

• разработке новой архитектуры системы мульти-агентного имитационного моделирования систем с дискретными событиями;

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

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

Практическая значимость работы продемонстрирована на примере разработки имитационных моделей "супер" вычислений, которые использованы при выполнении Государственного контракта № 07.514.11.401G "Исследования и разработка методов имитационного моделирования функционирования гибридных экзафлопеных вычислительных систем" в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития научно-техни-чсского комплекса России на 2007-2013 годы".

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

лично. Разработка архитектуры системы AGNES выполнена совместно с Родионовым A.C., интерпретация результатов моделирования в работах [1, 2] выполнена совместно с соавторами этих работ.

Основные защищаемые положения. Основными защищаемыми положениями диссертационной работы являются:

1. Мульти-агентная система имитационного моделирования AGNES (AGent NEtwork Simulator).

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

3. Имитационная модель распределённой атаки "отказ в обслуживании" (DDoS) типа SYN flood и средств защиты от неё внутри локальных вычислительный сетей (ЛВС). Найдены пути по повышению эффективности атаки, а также потенциальные возможности для повышения эффективности защиты.

4. Имитационная модель сенсорной беспроводной сети, предназначенная для сравнительного анализа алгоритмов широковещательной доставки сообщений.

5. Имитационные модели вычислений сеточных методов и методов статистического моделирования Монте-Карло. Результаты имитационного моделирования вычисления методов Монте-Карло, позволившие улучшить структуру алгоритма для исполнения на высокопроизводительных (более 100,000 ядер) вычислительных системах.

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях:

• Всероссийская конференция "Актуальные проблемы вычислительной математики и математического моделирования", Новосибирск, 2012

• 6th International Conference on Ubiquitous Information Management and Communication, Kuala Lumpur, Malaysia, 2012

• Международная сунсркомньютерная конференция "Научный сервис в сети Интсрнст:экзафлоиснос будущее", Абрау-Дюрсо, 2011

• Конференция молодых ученых ИВМиМГ СО РАН, Новосибирск, 2011

• 8-я Российская конференция с международным участием "Новые информационные технологии в исследовании сложных структур", Томск, 2010

• Пятая международная научная конференция по проблемам безопасности и противодействия терроризму, Москва, 2009

• XLVII Международная научная студенческая конференция (МНСК), Новосибирск, 2009

Публикации. Основное содержание диссертации достаточно полно отражено в семи печатных работах соискатсля[1-7], включая две работы в журнале из списка ВАК и одну регистрацию программы в Фонде Алгоритмов и Программ СО РАН.

Структура и объём диссертации. Диссертация состоит из введения, трех глав, заключения, библиографии и приложений с кодом агента и поведения. Общий объём диссертации 114 страниц, из них 93 страница текста, включая 27 рисунков и 4 таблицы. Библиография включает 85 наименований на 10 страницах.

Первая глава диссертации посвящена исследованию современных подходов имитационного моделирования. В этой главе приводится описание и

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

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

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

Содержание работы

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

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

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

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

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

Для системы моделирования важны следующие характеристики:

• Кросс-платформенность.

• Возможность распределенного запуска.

• Возможность иолу натурного моделирования.

• Отказоустойчивость.

• "Простота" усвоения системы моделирования.

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

Платформа JADE (Java Agent DEvelopment Framework) - это бесплатное программное обеспечение, распространяемое в исходных кодах и написанное на JAVA. Она состоит из двух взаимосвязанных компонентов. С одной стороны JADE — это среда разработки java-aretrroB, а с другой — это платформа, в рамках которой могут функционировать эти агенты. JADE ориентировано на использование спецификации FIPA (the Foundation for Intelligent Physical Agents).

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

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

• Инициализация и запуск модели.

• Сбор и хранение информации о ходе моделирования.

• Синхронизация модельного времени.

• Перераспределение нагрузки между вычислителями, участвующими в моделировании.

• Взаимодействие с пользователем (вывод отчетов и предоставление возможности влиять на ход моделирования).

• Обеспечение отказоустойчивости, восстановление модели.

• Балансировка нагрузки.

Внутри AGNES циркулируют два типа сообщений: управляющие команды и информационные сообщения внутри модели.

Дли обеспечения отказоустойчивости AGNES реализует несколько механизмов:

• Отсутствие централизованного хранения данных для восстановления. Храпение необходимой информации ведется подобно peer-to-peer сетям, т.е. информация располагается частями на разных агентах среды моделирования, и эта информация хранится с избытком, для гарантии сё восстановления.

• Динамическое изменение хранилищ информации во время работы среды моделирования. То есть в ходе моделирования хранилище данных о конкретном агенте изменяется, эта обязанность переходит от одного агента к другому.

Таким образом, основные принципы улучшенной отказоустойчивости среды моделирование - это децентрализация хранилищ и избыточность информации. Эффективность средств обеспечения отказоустойчивости проверена на экспериментах с физическими нарушениями аппаратной среды (локальной сети персональных ЭВМ) исполнения модели сенсорной сети.

Основными особенностями архитектуры AGNES являются:

• разделение агентов среды моделирования на управляющих и функциональных;

• включение в стандартные интерфейсы агентов средств взаимодействия в интересах обеспечения отказоустойчивости;

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

Результаты второй главы опубликованы в работах [G, 7].

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

Модель исследования DDoS атак типа SYN flood и средств защиты от них создавалась в рамках выполнения Проекта 1.1.7. (2.2.С) СО РАН "Исследование и разработка математического аппарата и программной среды для решения задач анализа и синтеза систем информатики". Для модели были созданы следующие функциональные агенты:

• Web сервер (имитация HTTP и FTP серверов);

• Web клиент (имитация действия обычного пользователя Интернет);

• клпент-"зомбн" (пользователь зараженный вредоносным ПО, проводящим атаку);

• консоль-атаки (инициатор и координатор проведения атаки SYN flood).

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

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

Рис. 1. Модель сенсорной сети в среде моделирования AGNES.

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

Модели вычислений созданы в рамках выполнения Государственного контракта № 07.514.11.4016 "Исследования и разработка методов имитационного моделирования функционирования гибридных экзафлонсных вычислительных систем" в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2007-2013 годы".

В качестве алгоритмов для исследования были выбраны методы статистического моделирования (методы Монте-Карло) и сеточные методы. Ато-

• ■ ■ Реальные данные модельные данные

35000 30000 25000 §! 20000

о /

| 15000 о

т юооо

5000

1.2 2.5 4 6 12 18 24 30 50 100 200 300 Тысяч ядер

Рис. 2. Рост времени счета с ростом количества ресурсов.

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

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

1оё(М)

Рис-. 3. Сравнение ускорения распределенного статистического моделирования для разных вариантов организации обмена данными для числа ядер М до 500 ООО (горизонтальная ось в логарифмическом масштабе;).

возможности алгоритма распараллеливаться до 1,5 миллионов вычислительных ядер без заметных потерь в производительности. Модельные результаты подтвердили себя в реальных экспериментах. Во время исследований методов Монте-Карло на модели был замечен эффект линейного роста производительности до определенного момента, а затем наступает состояние (после 100,000 агентов), когда узел-"сборщик" не справляется с потоком приходящих на него данных. Реальные эксперименты подтвердили подобный артефакт. Было предложено изменение схемы вычислений с введением иерархической системы узлов-"сборщиков". Результаты моделирования показаны на рисунке 3. Моделирование вычислений методов Монте-Карло позволило оптимизировать алгоритм реальных больших вычислений, а затем этот подход был

применен на практике.

Результаты третьей главы опубликованы в работах [1-3, 5].

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

1. Мульти-агентная система имитационного моделирования AGNES (AGcnt NEtwork Simulator).

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

3. Имитационная модель DDoS атаки и средств защиты от неё. Найдены пути по повышению эффективности атаки типа SYN flood, а также потенциальные возможности для повышения эффективности защиты.

4. Имитационная модель сенсорной беспроводной сети, предназначенная для сравнительного анализа алгоритмов широковещательной доставки сообщений.

5. Имитационные модели вычислений сеточных методов и методов статистического моделирования Монте-Карло. Результаты имитационного моделирования вычисления методов Монте-Карло, позволившие улучшить структуру алгоритма для исполнения на высокопроизводительных (более 100,000 ядер) вычислительных системах.

Список публикаций

1. Podkorytov D., Rodionov A. S., Sokolova О., Yurgcnson A. Using Agent-Oriented Simulation System AGNES for Evaluation of Sensor Networks // MA-

COM / Ed. by A. V. Vinel, В. Bellaita, С. Sacchi et al. Vol. 6235 of Lecture Notes in Computer Science. Springer, 2010. P. 247-250.

2. Глинский Б.M., Родионов A.C., Марченко М.А., Подкорытов Д.И., Вине Д.В. Агентно-ориентированный подход к имитационному моделированию суперЭВМ экзафлопеной производительности в приложении к распределенному статистическому моделированию // Вестник ЮУрГУ, 2012. № 18 (277), Вып. 12., С. 93-106.

3. Подкорытов Д.И. Мультиагентное моделирование DDoS атак // ИВМиМГ СО РАН. Труды Конференции молодых учёных ИВМиМГ СО РАН, Новосибирск. 2008.

4. Родионов A.C., Подкорытов Д.И. Агенто-ориентированная среда моделирования сетевых систем AGNES // Новые информационные технологии в исследовании сложных структур: тезисы докладов Восьмой Российской конференции с международным участием. Томск: Изд-во: НТЛ, 2010, 05 - 08 октября 2010 года. С.24.

5. Родионов A.C., Подкорытов Д.И. Моделирование DDoS атак в отказоустойчивой мультиагентной среде имитационного моделирования AGNES // Материалы пятой международной научной конференции по проблемам безопасности и противодействия терроризму, Москва, 2009. С. 293-296.

6. Podkorytov D., Rodionov A. S., Choo H. Agent-based simulation system AGNES"1 for networks modeling: review and researching // ICUIMC / Ed. by S.-H. Lee, L. Hanzo, R. Ismail et al. ACM, 2012. P. 115.

7. Подкорытов Д.И. Агентно-ориентированная среда моделирования сетевых систем AGNES // Ползуновский вестник, 2012. № 2/1, С. 94-99.

Подписано к печати 31.07.2012 г. Формат 60х84'/|6. Бумага офсетная. Уч.-изд. л. 0,95. Тираж 100 экз. Заказ № 24438.

Отпечатано в типографии ООО «ИНТ», г. Кемерово, ир-т Химиков, 43а, тел.: (3842) 73-75-13, факс: (3842) 73-87-97, e-mail: typoint@mail.ru

Введение

Глава 1. Обзор современных подходов и средств моделирования

1.1. Мульти-агентные системы имитационного моделирования

1.2. Программная среда разработки мульти-агентных систем JADE

1.3. Выбор базовых языка и платформы.

1.4. Выводы к первой главе.

Глава 2. Среда имитационного моделирования AGNES

2.1. Архитектура мульти-агентной среды имитационного моделирования AGNES

2.2. Обеспечение отказоустойчивости.

2.3. Основные управляющие агенты AGNES.

2.4. Пример создания модели в AGNES.

2.5. Выводы ко второй главе

Глава 3. Использование AGNES для решения задач.

3.1. Моделирование распределенных атак "отказ в обслуживании" (DDoS) типа SYN Flood и средств защиты от них.

3.2. Моделирование алгоритмов маршрутизации сообщений в беспроводных сенсорных сетях.

3.3. Моделирование распределенных реализаций вычислительных алгоритмов исполняемых на суперкомпьютерном центре

3.4. Выводы к третьей главе.

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

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

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

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

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

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

2. Разработана архитектура MAC имитационного моделирования AGNES

AGent NEtwork Simulator).

3. Разработаны и реализованы:

• среда исполнения AGNES.

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

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

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

Основные защищаемые положения. Основными защищаемыми положениями диссертационной работы являются:

1. Мульти-агентная система имитационного моделирования AGNES (AGent NEtwork Simulator).

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

3. Имитационная модель распределённой атаки "отказ в обслуживании" (DDoS) типа SYN flood и средств защиты от неё внутри локальных вычислительный сетей (ЛВС). Найдены пути по повышению эффективности атаки, а также потенциальные возможности для повышения эффективности защиты.

4. Имитационная модель сенсорной беспроводной сети, предназначенная для сравнительного анализа алгоритмов широковещательной доставки сообщений.

5. Имитационные модели вычислений сеточных методов и методов статистического моделирования Монте-Карло. Результаты имитационного моделирования вычисления методов Монте-Карло, позволившие улучшить структуру алгоритма для исполнения на высокопроизводительных (более 100,000 ядер) вычислительных системах.

Научная новизна заключается в:

• разработке новой архитектуры системы мульти-агентного имитационного моделирования систем с дискретными событиями;

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

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

Практическая значимость работы продемонстрирована на примере разработки имитационных моделей "супер" вычислений, которые использованы при выполнении Государственного контракта № 07.514.11.4016 "Исследования и разработка методов имитационного моделирования функционирования гибридных экзафлопсных вычислительных систем" в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2007-2013 годы".

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях:

• Всероссийская конференция "Актуальные проблемы вычислительной математики и математического моделирования", Новосибирск, 2012

• 6th International Conference on Ubiquitous Information Management and Communication, Kuala Lumpur, Malaysia, 2012

• Международная суперкомпьютерная конференция "Научный сервис в сети Интернет:экзафлопсное будущее", Абрау-Дюрсо, 2011

• Конференция молодых ученых ИВМиМГ СО РАН, Новосибирск, 2011

• 8-я Российская конференция с международным участием "Новые информационные технологии в исследовании сложных структур", Томск, 2010

• Пятая международная научная конференция по проблемам безопасности и противодействия терроризму, Москва, 2009

• XLVII Международная научная студенческая конференция (МНСК), Новосибирск, 2009

Публикации. Основное содержание диссертации достаточно полно отражено в семи печатных работах соискателя[1-7], включая две работы в журнале из списка ВАК и одну регистрацию программы в Фонде Алгоритмов и Программ СО РАН.

Личный вклад автора. В перечисленных работах все результаты, связанные с разработкой принципов и средств обеспечения отказоустойчивости исполнения, программной реализацией системы AGNES, разработкой и реализацией имитационных моделей описанных в работе, получены автором лично. Разработка архитектуры системы AGNES выполнена совместно с Родионовым А.С., интерпретация результатов моделирования в работах [4, 5] выполнена совместно с соавторами этих работ.

Структура и объём диссертации. Диссертация состоит из введения, трех глав, заключения, библиографии и приложений с кодом агента и поведения. Общий объём диссертации 114 страниц, из них 93 страница текста, включая 27 рисунков и 4 таблицы. Библиография включает 85 наименований на 10 страницах.

3.4. Выводы к третьей главе

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

Результаты моделирования вошли в отчёты по темам Государственного контракта № 07.514.11.4016 "Исследования и разработка методов имитационного моделирования функционирования гибридных экзафлопсных вычислительных систем" в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2007-2013 годы".

Заключение

В результате диссертационного исследования создана мульти-агентная среда распределённого имитационного моделирования систем с дискретными событиями AGNES. В ходе её создания были решены следующие задачи:

1. Исследованы существующие современные системы имитационного моделирования. На основе исследования сделан выбор в пользу JADE.

2. Разработана архитектура MAC имитационного моделирования AGNES.

3. Разработаны и реализованы:

• среда исполнения AGNES.

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

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

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

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

В диссертации дано описание платформы JADE, описана архитектура и основные преимущества AGNES, приведены примеры использования AGNES для решения практических задач, показана ценности полученных при помощи AGNES модельных данных.

Основными защищаемыми положениями диссертационной работы являются:

1. Мульти-агентная система имитационного моделирования AGNES (AGent NEtwork Simulator).

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

3. Имитационная модель распределённой атаки "отказ в обслуживании" (DDoS) типа SYN flood и средств защиты от неё внутри локальных вычислительный сетей (ЛВС). Найдены пути по повышению эффективности атаки, а также потенциальные возможности для повышения эффективности защиты.

4. Имитационная модель сенсорной беспроводной сети, предназначенная для сравнительного анализа алгоритмов широковещательной доставки сообщений.

5. Имитационные модели вычислений сеточных методов и методов статистического моделирования Монте-Карло. Результаты имитационного моделирования вычисления методов Монте-Карло, позволившие улучшить структуру алгоритма для исполнения на высокопроизводительных (более 100,000 ядер) вычислительных системах.

1. Подкорытов Д.И. Мультиагентное моделирование DDoS атак // ИВМиМГ СО РАН. Труды Конференции молодых учёных ИВМиМГ СО РАН, Новосибирск. 2008.

2. Podkorytov D., Rodionov A. S., Choo H. Agent-based simulation system

3. AGNES* for networks modeling: review and researching // ICUIMC / Ed. by S.-H. Lee, L. Hanzo, R. Ismail et al. ACM, 2012. P. 115.

4. Подкорытов Д.И. Агентно-ориентированная среда моделирования сетевых систем AGNES // Ползуновский вестник, 2012. № 2/1, С. 94-99.

5. Нечепуренко М.И. Моделирование вычислительных систем: сборник научных трудов. Системное моделирование. Сибирское отд-ние Ан СССР, Вычислительный центр, 1975.

6. Шеннон Р. Имитационное моделирование систем искусство и наука. -М.: Мир, 1978.

7. Киндлер Е. Языки моделирования. М.:Энергоатомиздать, 1985.

8. Рыжиков Ю.И. Имитационное моделирование: Теория и технологии. -СПб.: Альтекс, 2004.

9. Окольнишников . Разработка системы распределённого имитационного моделирования // Информационные технологии. 2006. Т. 12. С. 28-31.

10. Строгалев В.П., Толкачева И.О. Имитационное моделирование. М.: МГ-ТУ им. Н. Э. Баумана, 2008.

11. Fujimoto R. М. Parallel simulation: distributed simulation systems // Winter Simulation Conference / Ed. by S. E. Chick, P. J. Sanchez, D. M. Ferrin, D. J. Morrice. ACM, 2003. P. 124-134.

12. Tanenbaum A. S., van Steen M. Distributed systems: principles and paradigms. Pearson Prentice Hall, 2007. ISBN: 9780132392273.

13. Андрианов A.H., Бычков С.П., Хорошилов А.И. Программирование на языке Симула-67. М.: Наука, 1985.

14. Tognetti К. P., Brett С. SIMSCRIPT II and SIMULA '67 A Comparison // Australian Computer Journal. 1972. Vol. 4, no. 2. P. 50-57.

15. Dimsdale В., Markowitz H. M. A Description of the SIMSCRIPT Language // IBM Systems Journal. 1999. Vol. 38, no. 2/3. P. 151-161.

16. ШрайберТ.Дж. Моделирование на GPSS. M.: Машиностроение, 1980.

17. Herscovitch H., Schneider T. GPSS III An Expanded General Purpose Simulator // IBM Systems Journal. 1965. Vol. 4, no. 3. P. 174-183.

18. Gould R. L. GPSS/360 An Improved General Purpose Simulator // IBM Systems Journal. 1969. Vol. 8, no. 1. P. 16-27.

19. Schruben L. Simulation modelling with event graphs // Communication of the ACM. 1983. Vol. 26, no. 11. P. 957-963.

20. Fujimoto R. M. Time Management in The High Level Architecture // Simulation. 1998. Vol. 71, no. 6. P. 388-400.

21. Pegden C. D. Future directions in future directions in simulation modeling // Winter Simulation Conference. 2005. P. 1-35.

22. Ferber J. Multi-agent systems an introduction to distributed artificial intelligence. Addison-Wesley-Longman, 1999. P. I-XVIII, 1-509.

23. Multi-Agent Programming: Languages, Platforms and Applications / Ed. by R. H. Bordini, M. Dastani, J. Dix, A. E. Fallah-Seghrouchni. Springer, 2005. Vol. 15 of Multiagent Systems, Artificial Societies, and Simulated Organizations. ISBN: 0-387-24568-5.

24. Stallmann F. A model-driven approach to multi-agent system design: Ph. D. thesis. 2008. P. 1-344.

25. Hadzic M., Wongthongtham P., Dillon T. S., Chang E. Ontology-Based Multi-Agent Systems. Springer, 2009. Vol. 219 of Studies in Computational Intelligence. P. 1-273. ISBN: 978-3-642-01903-6.

26. Gulyds L., Kozsik T., Corliss J. B. The Multi-Agent Modelling Language and the Model Design Interface //J. Artificial Societies and Social Simulation. 1999. Vol. 2, no. 4.

27. Rouchier J. Multi-Agent System: An Introduction to Distributed Artificial Intelligence by Jacques Ferber //J. Artificial Societies and Social Simulation. 2001. Vol. 4, no. 2.

28. Gorodetski V. I., Kotenko I. V., Karsaev O. Multi-agent technologies for computer network security: attack simulation, intrusion detection and intrusion detection learning // Comput. Syst. Sci. Eng. 2003. Vol. 18, no. 4. P. 191-200.

29. Shibuya K. A Framework of Multi-Agent-Based Modeling, Simulation, and Computational Assistance in an Ubiquitous Environment // Simulation. 2004. Vol. 80, no. 7-8. P. 367-380.

30. Lopez-Sanchez M., Noria X., Rodriguez J. A., Gilbert N. Multi-Agent Based Simulation of News Digital Markets // IJCSA. 2005. Vol. 2, no. 1. P. 7-14.

31. Obst 0., Rollmann M. Spark A generic simulator for physical multi-agent simulations // Comput. Syst. Sci. Eng. 2005. Vol. 20, no. 5.

32. Guyot P., Honiden S. Agent-Based Participatory Simulations: Merging Multi- Agent Systems and Role-Playing Games //J. Artificial Societies and Social Simulation. 2006. Vol. 9, no. 4.

33. Helleboogh A., Vizzari G., Uhrmacher A., Michel F. Modeling dynamic environments in multi-agent simulation / / Autonomous Agents and Multi-Agent Systems. 2007. Vol. 14, no. 1. P. 87-116.

34. Hu J., Feijs L. M. G. A Distributed Multi-agent Architecture in Simulation Based Medical Training // T. Edutainment. 2009. Vol. 3. P. 105-115.

35. Kubera Y., Mathieu P., Picault S. IODA: an interaction-oriented approach for multi-agent based simulations // Autonomous Agents and Multi-Agent Systems. 2011. Vol. 23, no. 3. P. 303-343.

36. Gans G. An agent-based modeling and simulation methodology for strategic inter-organizational networks: Ph. D. thesis. 2008. P. 1-174.

37. Cavrak I., Stranjak A., Zagar M. SDLMAS: A Scenario Modeling Framework for Multi-Agent Systems // J. UCS. 2009. Vol. 15, no. 4. P. 898-925.

38. Minson R., Theodoropoulos G. K. Distributing RePast agent-based simulations with HLA // Concurrency and Computation: Practice and Experience. 2008. Vol. 20, no. 10. P. 1225-1256.

39. Cicirelli F., Furfaro A., Giordano A., Nigro L. HLAACTORREPAST: An approach to distributing RePast models for high-performance simulations // Simulation Modelling Practice and Theory. 2011. Vol. 19, no. 1. P. 283-300.

40. Economic Simulations in Swarm: Agent-Based Modelling and Object Oriented Programming Edited by Francesco Luna and Benedikt Stefansson. Kluwer-AP, 2000.

41. Cui X., Potok T. E. A Particle Swarm Social Model for Multi-Agent Based Insurgency Warfare Simulation // SERA. IEEE Computer Society, 2007. P. 177-183.

42. Cajias R., González-Pardo A., Camacho D. A Swarm Simulation Platform for Agent-Based Social Simulations // IDC / Ed. by F. M. T. Brazier, K. Nieuwen-huis, G. Pavlin et al. Vol. 382 of Studies in Computational Intelligence. Springer, 2011. P. 265-270.

43. Sklar E. NetLogo, a Multi-agent Simulation Environment // Artificial Life. 2007. Vol. 13, no. 3. P. 303-311.

44. Damaceanu R.-C. An agent-based computational study of wealth distribution in function of resource growth interval using NetLogo // Applied Mathematics and Computation. 2008. Vol. 201, no. 1-2. P. 371-377.

45. Borshchev A., Karpov Y., Kharitonov V. Distributed simulation of hybrid systems with AnyLogic and HLA // Future Generation Comp. Syst. 2002. Vol. 18, no. 6. P. 829-839.

46. Borshchev A. XJ technologies: AnyLogic 6 // Winter Simulation Conference. ACM, 2005. P. 82.

47. Kondratyev M., Garifullin M. Parallel Discrete Event Simulation with AnyLogic // PaCT / Ed. by V. Malyshkin. Vol. 5698 of Lecture Notes in Computer Science. Springer, 2009. P. 226-236.

48. Bellifemine F. L., Caire G., Greenwood D. Developing Multi-Agent Systems with JADE. Wiley, 2007.

49. Gawinecki M., Frackowiak G. Multi-Agent Systems with JADE: A Guide with Extensive Study // IEEE Distributed Systems Online. 2008. Vol. 9, no. 3.

50. Bellifemine F., Caire G., Poggi A., Rimassa G. JADE: A software framework for developing multi-agent applications. Lessons learned // Information Sz Software Technology. 2008. Vol. 50, no. 1-2. P. 10-21.

51. Charlton P., Cattoni R. Evaluating the Deployment of FIPA Standards when Developing Application Services // IJPRAI. 2001. Vol. 15, no. 3. P. 551-577.

52. FIPA ACL Message Structure Specification: FIPA agent communication language specifications.

53. León-Soto E. Agent Communication Using Web Services, a New FIPA Message Transport Service for Jade // MATES / Ed. by P. Petta, J. P. Müller, M. Klusch, M. P. Georgeff. Vol. 4687 of Lecture Notes in Computer Science. Springer, 2007. P. 73-84.

54. Niemeyer P., Knudsen J. Learning Java a bestselling hands-on Java tutorial: covers J2SE 5.0 (3. ed.). O'Reilly, 2005. P. I-XX, 1-954. ISBN: 978-0-596-00873-4.

55. Jefferson D. Virtual Time II: Storage Management in Conservative and Optimistic Systems // PODC. 1990. P. 75-89.

56. Dickens P. M., Reynolds P. F., Jr. SRADS With Local Rollback // in proceedings of the SCS multiconference on distributed simulation. 1990. P. 161-164.

57. Mattern F. Efficient algorithms for distributed snapshots and global virtual time approximation // Journal of Parallel and Distributed Computing. 1993. Vol. 18. P. 423-434.

58. Zhang J. L., Tropper C. The Dependence List in Time Warp // Workshop on Parallel and Distributed Simulation.

59. Окольнишников В.В. Представление времени в имитационном моделировании // Вычислительные технологии. 2005. Vol. 10. Р. 57-80.

60. МайерсГ. Надежность программного обеспечения. М.: Мир, 1980.

61. ЛиповМ., Нельсон Э., ТейерТ. Надежность программного обеспечения. М.: Мир, 1981.

62. ДодоновА.Г., Кузнецова М.Г., ГорбачикЕ.С. Введение в теорию живучести вычислительных систем. Киев : Наукова думка, 1990.

63. Тормасов А.Г., Хасин М.А., ПахомовЮ.И. Обеспечение отказоустойчивости в распределенных средах // Программирование, 2001. № 5. С.26-34.

64. Хорошевский В.Г., Майданов Ю.С., Мамойленко С.Н., ПавскийК.В., Моренкова О.И. Живучая кластерная вычислительная система // Труды школы-семинара "Распределенные кластерные вычисления", Красноярск, 2001.

65. Черкесов Г.Н. Надежность аппаратно-программных комплексов. СПБ.: Питер, 2005.

66. Siris V. A., Papagalou F. Application of anomaly detection algorithms for detecting SYN flooding attacks // Computer Communications. 2006. Vol. 29, no. 9. P. 1433-1442.

67. Chen W., Yeung D.-Y. Throttling spoofed SYN flooding traffic at the source // Telecommunication Systems. 2006. Vol. 33, no. 1-3. P. 47-65.

68. Yuan D., Zhong J. A lab implementation of SYN flood attack and defense // SIGITE Conference. 2008. P. 57-58.

69. Шахов В.В., Родионов А.С. Анализ средств противодействия одному виду атак типа "отказ в обслуживании" // Вестник НГУ, 2008. Серия: Информационные технологии, том 6, вып. 2. С. 80-88.

70. Kotenko I. V., Alexeev A., Man'kov E. Formal Framework for Modeling and Simulation of DDoS Attacks Based on Teamwork of Hackers-Agents // I AT. IEEE Computer Society, 2003. P. 507-510.

71. Lee H.-W., Kwon T., Kim H.-J. NS-2 Based IP Traceback Simulation Against Reflector Based DDoS Attack // AIS / Ed. by T. G. Kim. Vol. 3397 of Lecture Notes in Computer Science. Springer, 2004. P. 90-99.

72. Kotenko I. V., Ulanov A. The Software Environment for Multi-agent Simulation of Defense Mechanisms against DDoS Attacks // CIMCA/IAWTIC. IEEE Computer Society, 2005. P. 283-289.

73. Gallardo M. M., Merino P., Panizo L., Linares A. A practical use of model checking for synthesis: generating a dam controller for flood management // Softw., Pract. Exper. 2011. Vol. 41, no. 11. P. 1329-1347.

74. Karl H., Willig A. Protocols and architectures for wireless sensor networks. Wiley, 2005. P. I-XXV, 1-497. ISBN: 978-0-470-09510-2.

75. Liu D., Ning P. Security for Wireless Sensor Networks. Springer, 2007. Vol. 28 of Advances in Information Security. P. 1-209. ISBN: 978-0-387-32723-5.

76. Busse M. Algorithms for energy efficiency in wireless sensor networks: Ph. D. thesis. 2008. P. 1-227.