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

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

КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ПОТОКОВ ДАННЫХ В ПАКЕТНЫХ СЕТЯХ НА ОСНОВЕ УРАВНЕНИЙ В ЧАСТНЫХ ПРОИЗВОДНЫХ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2013

6 ИЮН ¿013

005061235

Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного университета)

Научный руководитель: доктор физико-математических наук

профессор, член-корреспондент РАН Холодов Александр Сергеевич

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

профессор

Тормасов Александр Геннадьевич, кафедра теоретической и прикладной информатики Московского физико-технического института (государственного университета), заведующий кафедрой

доктор физико-математических наук профессор

Галанин Михаил Павлович отдел №11

Института прикладной математики им. М.В.Келдыша РАН заведующий отделом

Ведущая организация: Институт радиотехники и электроники

(ИРЭ) им. В.А. Котельникова РАН

Защита состоится «¿7» 2013г. в час. на заседании

диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

Автореферат разослан « "20 »

2013г.

Ученый секретарь

диссертационного совета Д 212.156.05

О.С. Федько

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы

Результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих научных конференциях:

• 48-я и 50-я научные конференции МФТИ, Москва-Долгопрудный, 2005, 2007;

• III European Conference on Computational Mechanics, Lisbon, Portugal, 2006;

• XV международная конференция "Математика. Компьютер. Образование», Дубна, 2008;

• V Всероссийская межвузовская конференция молодых ученых, Санкт-Петербургский государственный университет информационных технологий, механики и оптики, 2008;

• XIV Байкальская Всероссийская конференция с международным участием «Информационные и математические технологии в науке и управлении», Иркутск, 2009.

Публикации

По теме диссертации автором опубликовано восемь работ, три из которых [5-7] - в изданиях из списка, рекомендованного ВАК РФ.

Личный вклад автора в работы с соавторами

Все научные результаты, вынесенные на защиту, получены лично автором. Постановка задачи и результаты расчетов обсуждались с научным руководителем Холодовым A.C.

Объём и структура диссертации

Диссертация состоит из введения, трех глав, заключения, списка использованных источников и трех приложений. Работа изложена на 113 страницах текста, содержит 2 таблицы, 18 рисунков. Библиография включает 66 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

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

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

1) системы динамического моделирования пакетных сетей;

2) особенности динамических систем имитационного моделирования;

3) комплексы имитационного моделирования пакетных сетей;

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

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

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

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

В третьей главе представлена новая математическая модель пакетного потокового моделирования 1Р-сетей передачи данных на основе уравнений сплошной среды. Рассмотрены:

1) структура модели в виде графа;

2) моделируемые величины;

3) моделируемые сессии;

4) ключевые элементы модели.

Сеть передачи данных (см. Рис.1) рассматривается как набор узлов, соединённых каналами связи. Функциональная специализация позволяет выделить два типа узлов. Узлы типа А перенаправляют потоки данных, создаваемые и/или терминируемые узлами другого типа В. Функциональное устройство сети позволяет предложить представление сети в виде направленного графа. Каждая вершина типа Ра, соотнесённая с узлом типа А, реализует правила маршрутизации. Каждая вершина типа РЬ, соотнесённая с узлом типа В, реализует оконечные сетевые протоколы. Каждое ребро графа соотносится с очередью и следующим за ней однонаправленным каналом.

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

Рис. 1. Концептуальная модель IP-сети: А,В - узлы IP-сети, соединённые каналом; А - узел - маршрутизатор с вершиной типа Ра и выходными очередями ; В - конечный узел с вершиной типа Ph.

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

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

очереди - с/. Утрата модельного вещества в результате управления определённой очередью отражается плотностью распределения этой утраты вдоль очереди - у/.

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

Модель сплошной среды

Основу потоковой модели составляют уравнения переноса условных веществ и информации о потере этого вещества

а я (1)

Э/ дх«\ 1 1 5

Здесь \ т = \...М} - индекс очереди в совокупности всех

очередей модели, а {.уи | п = 1К - индекс сессии в совокупности всех сессий модели.

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

П1 хч

/ 1р^хд,ич г О

Здесь, где О4 - номинальная пропускная

интерфейса на выходе очереди д, рч = ^ р

■г

очереди д, измеренная в единицах пакетов.

ах*

х"-Х1

(2)

способность Хч- длина

Здесь uq = uq

, a ir - скорость продвижения данных сессии s

поступающей на вход очереди q .

Сходным образом определяются граничные условия для уравнений (1) на входной границе хя = О

ч=е1> d4s

= dq

xq=0

(4)

Здесь pq и d] относятся к сессии s поступающей на вход очереди q . На выходной границе хЧт = ХЧт, граничные условия не требуются, а значения рЧт(t,X4m), dqm(t,Xqm), однозначно

sn sn

определяются из соотношений (1), благодаря ограничению (2).

В данной работе в качестве политики активного управления очередью (AQM - active queue management) был выбран алгоритм случайного раннего обнаружения (RED -Random Early Detection), при этом сброс происходит из хвоста очереди.

úrtV-l0-^ (5)

Здесь ¿j - случайная величина с равномерным распределением на отрезке [0;1], a Pq{t) - вероятность сброса пакета, которая в терминах RED AQM определяется следующим образом

О,

РНО

РЧО =

min

1;-

2-Dq{t)Pq{t) 1,

Dq(t)= f üq{T)dT tq

drop

Dq{t)Pq(t)<\ \<.Dq{t)Pq{t)^2 2 á Dq(t)Pq(t)

(6)

Здесь tqdrop - момент последнего сброса данных в очереди q

xq < xL_

Pq(t) =

Х"~Х1п (8)

„ „ max' min max

max ~ min - q q

i Л max

Здесь Xq(t) - переменная ожидаемая (прогнозируемая) длина очереди, а Хчтт, Хчтт, PJax постоянные параметры RED AQM. dXq Ina9 / _ я v

-—--—(хчо-хчо) (9)

Последнее уравнение интерпретирует дискретное выражение скользящего среднего Xq{t+6q) = (\-a4)Xq(j) + aqXq{t).

Безразмерный постоянный параметр oft е [1,10] определяет

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

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

Рассматриваемые модели каналов и сессий являются однонаправленными. Поэтому для представления двунаправленного канала моделируемой сети, с парой очередей на его входах, потребуются два ребра сетевого графа. Отметим

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

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

Здесь ру, £/", и" — выходные значения, рг, <Г, г/ — входные, ра - значение, соответствующее размеру квитанции,

модели. Зависимость выходных потоков TCP - источника от входных задается версией NewReno протокола TCP.

Алгоритм численного решения задачи

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

1. учёт притока данных в хвост очереди;

2. вычисление действительной и ожидаемой длин очередей;

3. определение вероятности сброса очереди;

4. учёт сброса очереди;

5. сохранение значений переменных состояния очереди;

6. определение значений выходного потока очереди.

(10)

индекс вершины в совокупности всех вершин

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

1. изменение переменных состояния протокола TCP в зависимости от режима и количества поступивших квитанций;

2. накопление оцениваемого времени задержки сессии (туда и обратно);

3. изменение режима в зависимости от поступившей информации о потерях, текущего режима и оценки времени задержки;

4. определение значений выходного потока.

Результаты расчетов

Для сравнительной оценки пакетной модели, реализованной в ns-2, и предложенной нами ПСС-модели проводилось моделирование как простейших сетей (см. Рис.2), так и более сложных конфигураций (см. Рис.3).

Рис. 2. Различные конфигурации простейших сетей, (а) одиночная 4 Кбит/пакет, (б) сонаправленные 8 Кбит/пакет, (в) встречные 8 Кбит/пакет.

Рис. 3. Сложная кольцевая конфигурация сети, моделировалось 1280 сессий, при этом имело место одна загруженная очередь на пути каждой сессии. Использовались следующие характеристики сети: пропускная способность магистрали — 20 Мбит/с; хорды подсети - 5 Мбит/с; размер пакетов — 8 Кбит/пакет. Трафик был организован так, чтобы половина пакетов отправлялась по магистрали в соседнюю подсеть, а вторая половина по хорде подсети.

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

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

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

-Очередь ЭБ .............Окно 1 ЭБ ----Окно 2 РБ

Рис. 4. Пакетное моделирование (пз-2). Две сонаправленные сессии. Синяя линия - размер общей очереди; красная и зеленая - размеры двух ТСР-окон.

Секунды

-Очередь N3 .............Окно 1 N5 ----Окно 2 N3

Рис. 5. Потоковое моделирование. Две сонаправленные сессии. Синяя линия - размер общей очереди; красная и зеленая - размеры двух ТСР-окон.

Очередь ЭЭ .............Окно 1 ЭЭ ----Окно 2 ЭБ

Рис. 6. Пакетное моделирование (пз-2). Две противонаправленные сессии. Синяя линия - размер общей очереди; красная и зеленая - размеры двух ТСР-

окон.

-Очередь ЫБ .............Окно 1 N8 ----Окно 2 ЫБ

Рис. 7. Потоковое моделирование. Две противонаправленные сессии. Синяя линия - размер общей очереди; красная и зеленая - размеры двух ТСР-окон.

Для сравнения интегрального поведения модельной компьютерной сети в целом по гистограммам усреднённой производительности и усреднённого времени оборота соединений ШТ рассмотрен случай относительно сложной

кольцевой конфигурация сети (Рис.3). Соответствующие усредненные результаты производительности сети и задержки в зависимости от сессии показаны на (Рис.8) и (Рис.9). Усреднение результатов выполнялось за период времени в 200 сек.

25 -

О 4— -,----г-------

1 251 501 751 1001 1251 .............NS -DS № сессии

Рис. 8. Гистограммы производительностей сессий.

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

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

1001 № сессии

Рис. 9. Гистограммы временных задержек сессий.

1251

20 40 60 80 100 количество подсетей

20 40 60 80 100 количество подсетей

Рис.10. Потребление вычислительных ресурсов в зависимости от количества

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

В заключении приведены основные результаты работы.

В Приложении 1 приведён список сокращений, в Приложении 2 - список определений, в Приложении 3 -

список обозначений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

Публикации автора по теме диссертации.

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

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 сетей на основе сетевых потоков данных. // Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды L научной конференции. / Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2007. - Том 2 -С.140-142.

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

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

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

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

8. Свид. о гос. per. прог. для ЭВМ 2011617671 Российская Федерация. Программный комплекс для численного моделирования компьютерных сетей с использованием высокопроизводительных вычислительных алгоритмов / Холодов Я.А, Северов Д.С., Холодов A.C. - № 2011615991 заявл. 9.08.11 ; опубл. 03.10.11.

/

I,' '

Северов Дмитрий Станиславович

КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ПОТОКОВ ДАННЫХ В ПАКЕТНЫХ СЕТЯХ НА ОСНОВЕ УРАВНЕНИЙ В ЧАСТНЫХ ПРОИЗВОДНЫХ

АВТОРЕФЕРАТ

Подписано в печать 16.05.2013 Формат 60 х 84 Vie. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 894. Федеральное государственное бюджетное образовательное высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9.

Московский физико-технический институт (государственный университет) Кафедра вычислительной математики

На правах рукописи УДК 519.876.5+519.622

04201357931

СЕВЕРОВ Дмитрий Станиславович

КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ПОТОКОВ ДАННЫХ В ПАКЕТНЫХ СЕТЯХ НА ОСНОВЕ УРАВНЕНИЙ В ЧАСТНЫХ ПРОИЗВОДНЫХ

Специальность: 05.13.18 «Математическое моделирование, численные методы и комплексы программ»

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель член- корреспондент РАН доктор физико-математических наук,

профессор A.C. Холодов

МОСКВА-2013 г.

Содержание

ВВЕДЕНИЕ...........................................................................................................................................4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.................................................................................................................................................................69

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

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

2

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

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

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

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

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

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

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

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

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

Заключение......................................................................................................................................98

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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. Методология имитационного моделирования

В этой и следующей главе использованы материалы [23].

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

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

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

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

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

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

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

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

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

• Автоматическое управление сетью. Группа технологий, условно объединённая понятием «программно-конфигурируемые сети» (Software Definable Networks) декларирует возможность автоматического управления параметрами комплекса сетевых элементов, образующих контролируемую сеть. При этом, в составе контроллера программно-конфигурируемой сети фактически создаётся модель сети, абстрагированная от деталей реализации сетевых элементов. В контуре автоматического управления сетью информация о поведении такой встроенной модели может дополнять информацию о поведении контролируемой сети.

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

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

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

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

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

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