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

• Северов, Дмитрий Станиславович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Северов, Дмитрий Станиславович

Содержание

ВВЕДЕНИЕ

Актуальность работы

Цели и задачи работы

Научная новизна

Научная и практическая ценность

Соответствие специальности 05.13.18

Глава 1. Методология имитационного моделирования

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

1.1.1. Цели имитационного моделирования компьютерных сетей

1.1.2: Возможности имитационной модели компьютерной сети

1.1.3. Что именно моделируется в компьютерной сети?

1.2. Средства имитационного моделирования компьютерных сетей

1.2.1. Архитектура систем имитационного моделирования

1.2.2. Объекты и состояния имитационной модели-------------------------------------------------------------------------17

1.2.3. Примеры средств имитационного моделирования

1.3.Имитационное моделирование проводных сетей

1.3.1. Альтернативы моделирования

1.3.2. Пакетные модели

1.3.3. Потоковые имитационные модели

Глава 2. Инструменты имитационного моделирования

2.1. Специализированные системы моделирования компьютерных сетей

2.1.1. Системы динамического моделирования пакетных сетей

2.1.2 Особенности динамических систем имитационного моделирования

2.1.3. Комплексы имитационного моделирования пакетных сетей

2.1.4. Интегрированные инструменты имитационных комплексов

2.2. Имитаторы структурно-вариабельных сетей

2.3. Имитационное моделирование беспроводных сетей

2.3.1. Широковещательная передача

2.3.2. Вычисление потерь сигнала

2.3.3. Мобильность моделируемой системы

2.3.4. Спонтанная маршрутизация

Глава 3. Имитационная модель на основе уравнений в частных производных

3.1. Математическая модель ориентированного графа сети

3.1.1. Структура потоковой математической модели

2

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

3.1.3. Сессия потокового имитатора

3.1.4. Ребро имитатора: очередь и канал связи

3.1.5. Узел - маршрутизатор потокового имитатора

3.1.6. Входы и выходы графа - источники и получатели

3.1.7. Программы и алгоритмы численного решения задачи

3.2. Сравнительные результаты потокового моделирования

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

3.2.2. Результаты моделирования сложных конфигураций

Заключение

Список литературы

Приложение 1. Сокращения

Приложение 2. Определения

Приложение 3. Основные обозначения

Введение диссертации (часть автореферата) на тему «Компьютерное моделирование потоков данных в пакетных сетях на основе уравнений в частных производных»

ВВЕДЕНИЕ

Актуальность работы

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

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

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

На актуальность потокового подхода к моделированию сетей пакетной

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

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

дискретным, имеющим молекулярную структуру, достаточно адекватно и

эффективно представляется математическими моделями непрерывного типа.

Учитывая отсутствие чётких границ применимости дискретного и потокового

4

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

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

Цели и задачи работы

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

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

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

2. Построение новой потоковой модели объектов сети, сопоставимой по качеству моделирования с дискретно-событийными моделями.

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

4. Проведение ряда сравнительных вычислительных экспериментов с использованием потоковой и дискретно-событийной имитационных моделей

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

Научная новизна

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

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

Научная и практическая ценность

В соответствии с указанными целями исследования моделирующая сеть представлялась ориентированным графом. В качестве примера для моделирования выбраны наиболее распространённые протоколы и алгоритмы глобальной сети Интернет: базовый протокол сетевого уровня IP - Internet Protocol, протокол управления передачей TCP - Transmission Control Protocol в версии Reno-1990; алгоритм активного управления очередями маршрутизаторов RED-Random Early Detection.

Выявлено, что вычислительная эффективность потокового метода

моделирования в значительной мере зависит не только от свойств самого метода,

но и от свойств комплекса программ, который реализуется метод: объёма

используемых ресурсов; возможностей распараллеливания процессов; полноты

набора моделируемых протоколов; совместимости с существующими средствами

6

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

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

Соответствие специальности 05.13.18

Работа содержит все необходимые компоненты специальности 05.13.18:

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

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

3. Комплексы программ. Для проведения имитационного моделирования пакетных сетей на основе полученной потоковой модели был разработан программный комплекс для численного моделирования компьютерных сетей с использованием высокопроизводительных вычислительных алгоритмов (свидетельство о государственной регистрации № 2011617671 от 03.10.2011).

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Северов, Дмитрий Станиславович

Основные результаты диссертации:

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

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

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

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

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Северов, Дмитрий Станиславович, 2013 год

Список литературы

1. Д.С.Северов, Н.В. Ковшов, М.И. Миненко, Математическое моделирование работы вычислительных сетей, использующих протоколы UDP и ТСРЯР. Материалы 48-й научной конференции МФТИ, с. 30-31, 2005.

2. Kholodov Y.A, Kholodov A.S., Kovshov N.V., Simakov S.S., Severov D.S., Bordonos A.K., Bapaev A.Z., Computational models on graphs for nonlinear hyperbolic and parabolic systems of equations. Proceedings of the III European Conference on Computational Mechanics, Springer, eds. C. A. Mota Soares et, al., 2006. p. 43.

3. Д.С. Северов, О моделировании TCP/IP сетей на основе сетевых потоков данных. // Труды 50-й научная конференции МФТИ, Современные проблемы фундаментальных и прикладных наук, Часть VII, Том 2, стр.140-142. Москва-Долгопрудный, 2007.

4. Д.С. Северов, Н.В. Ковшов, М.И. Миненко, Я.А. Холодов. Численное моделирование IP-сетей передачи информации на основе пакетных потоков данных // Сборник научных трудов МФТИ, Моделирование и обработка информации. М. 2008. с. 19-31.

5. Д.С. Северов, С.В. Трифонов, М.И. Миненко, Я.А. Холодов. Численное моделирование IP-сетей передачи данных в рамках уравнений сплошной среды. Научно-технический вестник СПбГУ ИТМО, Санкт-Петербург. 2008. №46. с. 218-227.

6. Д.С. Северов. Потоковая модель сплошной среды для анализа IP-сетей // Современные технологии. Системный анализ. Моделирование. ИрГУПС. 2009. №1. с. 146-149.

7. S. Severov, A.S. Kholodov, Y.A. Kholodov. Comparison of Packet Level and Fluid Models of IP Networks // Mathematical Models and Computer Simulations. - 2012. - V. 4, N 4, P. 385-393..

8. Шеннон P.H. Имитационное моделирование систем - искусство и наука. Пер. с английского. 1978 - 425 с.

9. Andradottir S. and T. Ott, "Time-segmentation parallel simulation of networks of queues with loss or communication blocking," ACMTrans. Model Comput. SimuL, Vol. 5, No. 4, pp. 269-305, 1995.

10.Ayani R. "A parallel simulation scheme based on the distance between objects," in Proc. of the SCS Multiconference on Distributed Simulation, Society for Computer Simulation, pp. 113-118, 1989.

11.Baccelli F. and M. Canales, "Parallel simulation of stochastic petri nets using recurrence equations," in ACMTrans. Model. Comput. Simul., Vol. 3, No. 1, pp. 20-41,1993.

12.Y. J. Lee, and G. F. Riley, "Efficient simulation of wireless networks using lazy MAC state update," in 19th Workshop on Principles of Advanced and Distributed Simulations (PADS'05), Monterey, CA, USA, 2005, pp. 131-140.

13.Bryant R.E., "Simulation of packet communications architecture computer systems," MIT-LCS-TR-188, 1977.

14.Cai W. and S.J. Turner, "An algorithm for distributed discrete-event simulation— the "carrier null message" approach," in Proc. of the SCS Multiconference on Distributed Simulation, SCS Simulation Series, pp. 3-8, 1990.

15.Carothers C.D., K. Perumalla, and R.M. Fujimoto, "Efficient optimistic parallel simulation using reverse computation," ACM Trans. Model. Comput.Simul., Vol. 9, No 3, pp. 224-253, 1999.

16.Chandy K.M. and J. Misra, "Distributed simulation: a case study in design and verification of distributed programs," IEEE Trans. Softw. Eng., Vol. SE-5, No. 5, pp. 440-452,1978.

17.Chen G. and B.K. Szymanski, "Four types of lookback," in Proc. 17thWorkshop on Parallel and Distributed Simulation, pp. 3-10,2003.

18.Cowie J.H., D.M. Nicol, and A.T. Ogielski, "Modeling the global internet," Comput. Sci. Eng., Vol. 1, No. 1, pp. 42-50, 1999.

19.Das S.R. and R.M. Fujimoto, "Adaptive memory management and optimism control in time warp "ACMTrans. Model. Comput. Simul., Vol. 7, No. 2, pp. 239-271,1997.

20.Deelman E. et al., "Improving lookahead in parallel discrete event simulations of large-scale applications using compiler analysis," in Proc. 15th Workshop on Parallel and Distributed Simulation, pp. 5-13,2001.

21.Dickens P.M. and P.F.J. Reynolds, "SRADS with local rollback," in Proc. of the SCS Multiconference on Distributed Simulation, pp. 161-164, 1990.

22.Ferscha A. "Probabilistic adaptive direct optimism control in time warp," in Proc. 9th Workshop on Parallel and Distributed Simulation, pp. 120-129K) 1995.

23.Richard M. Fujimoto, Kalyan S. Perumalla and George F. Riley, Network Simulation, Morgan & Claypool, 72 p. 2007. DOI 10.2200/S00046ED 1V01Y200609CNT001

24.Fujimoto R.M. George F. Riley - Georgia Institute of Technology, Kalyan S. Perumalla - Oak Ridge National Laboratory, Network Simulation Synthesis lectures on communication networks, 72 p. 2006.

25.Fujimoto R.M. "Exploiting temporal uncertainty in parallel and distributed simulations," in Proc. 13th Workshop on Parallel and Distributed Simulation, pp. 46-53,1999.

26.Fujimoto R.M. t al. "Large-scale network simulation: how big? how fast?" in Proc. 11th Int. Symp. on Modeling, Analysis and Simulation of Computer andTelecommunication Systems (MASCOTS'03), 2003.

27.Greenberg A. et al., "Efficient massively parallel simulation of dynamic channel assignment schemes for wireless cellular communications," in Proc. 8thWorkshop on Parallel and Distributed Simulation, pp. 187-194, 1994.

28.IEEE Std 1278.1-1995, IEEE Standard for Distributed Interactive Simulation Application Protocols. New York, NY: Institute of Electrical and Electronics Engineers, Inc., 1995.

29.IEEE Std 1278.2-1995, IEEE Standard for Distributed Interactive SimulationCommunication Services and Profiles.NewYork^Y: Institute of Electrical and Electronics Engineers, Inc., 1995.

30.IEEE Std 1516.3-2000, IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA)—Interface Specification. New York, NY: Institute of Electrical and Electronics Engineers, Inc., 2000.

31.S.Y. Wang, "NCTUns 1.0", in the column "Software Tools for Networking", IEEE Networks, Vol. 17, No. 4, July 2003

32.Varga, A., "Using the OMNeT++ discrete event simulation system in education", IEEE Transactions on Education, 42,4: 11 pp..

33.http://web.scalable-networks.com/content/qualnet.

34.Xiang Zeng, Rajive Bagrodia, Mario Gerla, "GloMoSim: a Library for Parallel Simulation of Large-scale Wireless Networks"; Proceedings of the 12th Workshop on Parallel and Distributed Simulations — PADS '98, May 26-29, 1998 in Banff, Alberta, Canada

35.http://www.riverbed.com/products-solutions/products/network-planning-simulation/Network-Simulation.html

36.1516-2010 - IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA)-- Framework and Rules

37.Lin, Y.B. and E.D. Lazowska, "A time-division algorithm for parallel simulation," ACM Trans. Model. Comput. Simul.,Vol. 1, No. 1, pp. 73-83, 1991.

38.Liu J. and D.M. Nicol, DaSSF 3.0 User's Manual, 2001 (h3: http://www.cs.dartmouth.edu/research/DaSSF/Papers/dassf-manual.ps).

39.Lubachevsky B.D. "Efficient distributed event-driven simulations of multiple-loop networks," Commun. ACM,\ Vol. 32, No. 1, pp. 111-123, 1989.

40.Mah A. "An empirical model of HTTP network traffic," in INFOCOM, pp. 592-600,1997.

41.Mattern F. "Efficient algorithms for distributed snapshots and global virtual time approximation," J. Parallel Distrib. Comput., Vol. 18, No. 4 pp. 423434, 1993.

42.Mehl H. "Adeterministic tie-breaking scheme for sequential and distributed simulation," in Proc. of the Workshop on Parallel and Distributed Simulation, Society for Computer Simulation, pp. 199-200, 1992.

43.Meyer R.A. and R.L. Bagrodia, "Path lookahead: a data flow view of PDES models," in Proc. 13th Workshop on Parallel and Distributed Simulation, pp. 12-19, 1999.

44.Miller D.C. and J. A. Thorpe, "SIMNET: the advent of simulator networking," in Proc. IEEE, Vol. 83, No. 8, pp. 1114-1123, 1995.

45.Nicol D.M. and X. Liu, "The dark side of risk," in Proc. 11th Workshop on Parallel and Distributed Simulation, pp. 188-195, 1997.

46.Nicol D.M. and P. Heidelberger, "Parallel execution for serial simulators," ACM Trans. Model. Comput. Simul., Vol. 6, No. 3, pp. 210-242, 1996.

47.0SPF IETF, Version 2, IETF RFC 2328, 1998.

48.Palaniswamy A. C. and P. A.Wilsey, "An analytical comparison of periodic checkpointing and incremental state saving," in Proc. 7thWorkshop on Parallel and Distributed Simulation, pp. 127-134, 1993.

49.Perumalla K., R. Fujimoto, and A. Ogielski, "TeD—a language for modeling telecommunications networks," Perform. Eval. Rev., Vol. 25, No. 4, 1998.

50.Perumalla K.S. et al., "Scalable RTI-based parallel simulation of networks," in Proc. 17th Workshop on Parallel and Distributed Simulation, pp. 97-104,

2003.

51.Pham C.D. H. Brunst, and S. Fdida, "Conservative simulation of load-balanced routing in a large ATM network model," in Proc. 12th Workshop on Parallel and Distributed Simulation, pp. 142-149, 1998.

52.Poplawski A.L. and D.M. Nicol, "Nops: a conservative parallel simulation engine for TeD," in 12th Workshop on Parallel and Distributed Simulation, pp. 180-187, 1998.

53.Rao D.M. et al., "Unsynchronized parallel discrete event simulation," in Proc. of the Winter Simulation Conference, pp. 1563-1570, 1998.

54.Riley G.F., M. Ammar, R.M. Fujimoto, A. Park, K. Perumalla, D. Xu, "A Federated Approach to DistributedNetwork Simulation," ACMTransactions on Modeling and Computer Simulation, Vol. 14, No. 1, pp. 116-148, April

2004.

55.Riley G.F., "The Georgia Tech Network Simulator," in Proc. of the ACM SIGCOMM Workshop on Models, Methods and Tools for Reproducible Network Research. Karlsruhe, Germany: ACM Press, 2003

56.Riley G.F., R.M. Fujimoto, and M. Ammar, "Stateless routing in network simulations," in Proc. 10th Int. Symp. on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS'OO), 2000.

57.Samadi B. "Distributed simulation, algorithms and performance analysis,", University of California, Los Angeles, CA, 1985.

58.Sokol L.M. and B. K. Stucky, "MTW: experimental results for a constrained optimistic scheduling paradigm," in Proc. of the SCS Multiconference on Distributed Simulation, pp. 169-173, 1990.

59.Steinman J.S. "SPEEDES: amultiple-synchronization environment for parallel discrete event simulation," Int. J. Comput. Simul., Vol. 2, pp. 251— 286,1992.

60.Szymanski B.K. Szymanski, et al. "Genesis: a system for large-scale parallel network simulation," Workshop on Parallel and Distributed Simulation,Washington D.C., USA, 2002.

61.The Network Simulator - ns2 homepage, http://www.isi.edu/nsnam/ns/.

62.Unger B. "The telecom framework: a simulation environment for telecommunications," in Proc. 1993 Winter Simulation Conference, 1993.

63.Ward Y. and G.F. Riley, "IPA for loss volume and buffer workload in Tandem SFM networks," in Proc. 6th Workshop on Discrete Event Systems (WODES'02), 2002.

64.Wu H., R.M. Fujimoto and M. Ammar. "Time-parallel trace-driven simulation of CSMA/CD," in Proc. Workshop on Parallel and Distributed Simulation, 2003.

65.Xiao Z. et al., "Scheduling critical channels in conservative parallel simulation," in Proc. 13th Workshop on Parallel and Distributed Simulation, pp. 20-28,1999.

66.Yong Liu, Francesco Lo Presti, Vishal Misra, Don Towsley and Yu Gu, Fluid Models and Solutions for Large-Scale IP Networks, Proceedings of ACM

105

International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), 2003 67.Холодов A.C., Холодов Я.А. О критериях монотонности разностных схем для уравнений гиперболического типа. // Журнал выч. математики и мат. физики, 2006, т. 46, № 9, 1560-1588.