Разработка отказоустойчивых мульти-агентных средств имитационного моделирования систем с дискретными событиями тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Подкорытов, Дмитрий Игоревич

• Подкорытов, Дмитрий Игоревич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Подкорытов, Дмитрий Игоревич

Введение

Глава 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 ядер) вычислительных системах.

Список литературы диссертационного исследования кандидат технических наук Подкорытов, Дмитрий Игоревич, 2012 год

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.