Автореферат:

"Распределенное моделирование задач оптимизации компьютерных сетей на вычислительном кластере"

Составитель:  Астахов Алексей Вячеславович

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

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

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

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

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

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

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

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

Рисунок 1 – Типовая топология кластерной сети

Обзор существующих исследований

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

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

  Программные средства моделирования могут быть классифицированы на образовательные, коммерческие и специализированные. [1]

  Среди образовательных аналитических средств моделирования можно выделить: DEsign tool LITE (Delite) – инструмент для проектирования глобальной сети, поддерживающий различные типы алгоритмов проектирования; Cappuccino – симулятор в рамках некоммерческого web-проекта для ограниченного числа приложений, позволяющий вычислять различные параметры сети. Коммерческие средства моделирования: XNetMod – инструмент для моделирования локальных сетей, допускающий анализ эффективности настройки сети до ее реализации; TND-Tool (Topologycal Network Design Tool) – средство для поиска эффективного решения проблемы построения топологии сети; NetRule – симулятор, объединяющий лучшие возможности математического анализа и средств моделирования, поддерживает большое количество узлов в сети; XNP (Extensible Network Planner) – сетевое средство проектирования для расширяемых и стандартных сетей, поддерживает большое количество различных алгоритмов. Одним из популярных сетевых симуляторов является ns2. Симулятор полностью написан на языке C++ и распространяется с открытым кодом. В качестве управляющего интерфейса используется язык OTcl. Определять и управлять моделью можно как через интерфейс OTcl, так и с использованием языка C++. Network WorkBench – дискретно-событийный сетевой симулятор, разработанный для учебных исследований интернет протокола IP. Netsim – симулятор, используемый для исследования локальных сетей. MaRS (Maryland Routing simulator) - дискретно-событийный симулятор, предоставляющий гибкую платформу для оценки и сравнения сетевых алгоритмов маршрутизации. PDNS (Parallel/Distributed ns) – расширенная версия ns симулятора для распределенного моделирования. OPNET (Optimised Network Engineering tool), COMNET III, REAL (Realistic And Large), Ted (Telecommunication Description Language), USSF (Ultra-Large Simulation Framework) – коммерческие средство моделирование компьютерных сетей. К специализированным средствам можно отнести ATN-TN (ATM Traffic and Network simulator), который может охарактеризовать поведение сети, и GloMoSim (Global Mobile System simulator) – масштабируемая среда моделирования для беспроводных сетевых систем.

  В своей магистерской работе я использую систему PRIME (Parallel Real-time Immersive Modeling Environment). PRIME – это научно-исследовательский проект, главной целью которого является исследование фундаментальных технологий, допускающих крупномасштабное сетевое моделирование в реальном времени, и разработка сетевой среды моделирования в реальном времени. [3]

  Основным программным инструментом для исследований является симулятор PRIME, написанный преимущественно на языке С++, и выполняющийся в среде Unix. Для его работы необходим Linux, Mac OS или cygwin. Симулятор состоит из двух компонент: PRIME SSF и PRIME SSFNet.

  PRIME SSF – это механизм моделирования для запуска больших моделей на параллельных машинах (хотя это может также выполняться последовательно). SSF – это масштабируемая среда моделирования, которая является API стандартом для разработки моделей. PRIME SSF реализует SSF спецификацию. [4]

  PRIME SSFNet – это симулятор, разработанный на основе PRIME SSF, который связан с моделированием сетевой инфраструктуры, такой, как Internet. В PRIME SSFNet реализованы необходимые сетевые компоненты: маршрутизаторы, соединения, протоколы и др.

  PRIME SSF разработан на основе предыдущих реализаций DaSSF и iSSF, которые обеспечивают высокоэффективное моделирование широкомасштабных систем.

Перечень решаемых в работе задач

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

  1) провести анализ современных средств и подходов в широкомасштабном моделировании;

  2) найти сетевой симулятор, который позволяет моделировать компьютерные сети большой размерности, а также поддерживает параллельное моделирование на распределенной памяти;

  3) организовать запуск системы моделирования на вычислительном кластере Microsoft Windows Compute Cluster Server 2003.

  В качестве средства моделирования была выбрана система PRIME, которая позволяет создавать модели с помощью DML-описаний (Domain Modeling Language), либо, используя конструкции языка C++. С помощью программной надстройки PRIME SSFNet создаются модели компьютерных сетей, используя стандартные классы SSF API. И осуществляется само моделирование на кластере, где связь между узлами организована посредством передачи сообщений по протоколу MPI (Message Passing Interface). [2]

Рисунок 2 – Создание модели сети, используя DML описание

(Анимация: количество кадров - 16, повторов - 10, продолжительность кадров - [20, 80] мс)

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

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

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

  3) Определить порог чувствительности для значений критерия эффективности. Так, производительность сети можно оценивать логическими значениями "Работает"/ "Не работает", и тогда оптимизация сводится к диагностике неисправностей и приведению сети в любое работоспособное состояние. Другим крайним случаем является тонкая настройка сети, при которой параметры работающей сети (например, размер кадра или величина окна неподтвержденных пакетов) могут варьироваться с целью повышения производительности (например, среднего значения времени реакции) хотя бы на несколько процентов. Как правило, под оптимизацией сети понимают некоторый промежуточный вариант, при котором требуется выбрать такие значения параметров сети, чтобы показатели ее эффективности существенно улучшились, например, пользователи получали ответы на свои запросы к серверу баз данных не за 10 секунд, а за 3 секунды, а передача файла на удаленный компьютер выполнялась не за 2 минуты, а за 30 секунд. [2]

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

Теоретический анализ

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

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

  SSF API содержит только 5 базовых класса, которые служат для построения сложных имитационных моделей. Ниже кратко описаны их функции.

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

  Процесс (process) рассматривают как часть объекта, который определяет процесс изменения состояния объекта. Каждый процесс моделирования в SSF представлен экземпляром класса Process или класса, полученного на основе базового. Эти процессы, как и процессы Unix, представляют собой независимые потоки управления.

  Входной канал (inСhannel) представляет приемный конец направленной связи между объектами. В SSF связь между объектами обеспечивается передачей сообщений. Объект может получить сообщения с другого объекта только на входной канал. Входной канал принадлежит определенному объекту. Нельзя изменить объект-владельца входного канала после того, как он был создан.

  Выходной канал (outChannel) – отправная точка связи между объектами. Также как и inChannel выходной канал должен принадлежать объекту. Выходной канал объекта может быть отображен на множество входных каналов, которые принадлежат этому или другим объектам. Сообщение, посланное на выходной канал, будет доставлено системой моделирования на все соответствующий входные каналы.

  Событие (event) – базовый класс, который представляет сообщения, посылаемые между объектами через каналы связи. Пользователь определяет его собственные классы на основе базового класса Event. При этом он может добавить определенную информацию, которую нужно передавать между объектами.

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

Собственные разработки

  В процессе выполняемой работы была запущена система PRIME на операционной системе Linux (Ubuntu 5.10) под виртуальной машиной VMware Workstation. В среде PRIME SSF была промоделирована простейшая компьютерная сеть, для которой варьировались различные входные параметры и проводился анализ работы сети за различное время моделирования. В среде PRIME SSFNet была промоделирована компьютерная сеть с 3 хостами, поведение которой было приближено к поведению реальной физической сети.

  В дальнейшем планируется разработать собственную сетевую модель в среде PRIME SSFNet, используя средства SSF API, на которой можно было бы задавать варьируемые параметры компьютерной сети, и по результатам моделирования делать вывод об эффективности модели.

  Запуск модели для большого числа узлов в сети предполагается проводить на вычислительном кластере Microsoft Windows Compute Cluster Server 2003.

Экспериментальные исследования

  Исследования компьютерной сети проводились на модели muxtree и 3hosts.

  Модель muxtree представляет собой упрощенную сеть переключателей. Топология сети – дерево, где листья дерева выступает в качестве источников потока данных. Пакеты генерируются из этих источников и перемещаются через коммутаторы к корню дерева. На каждом коммутаторе переключатели накапливаются в очереди до их обслуживания. Каждый пакет ждет определенное время, до того, как он будет отправлен на следующий уровень, пока не достигнет корня дерева. Если буфер переполнен, то новый пакет будет потерян. Топология примера модели показана на рисунке 3. Существуют 2 параметра для управления топологией дерева: число входных связей и число уровней. В примере сеть состоит из 4 уровней мультиплексоров, у каждого из которых по 2 входа.

Рисунок 3 – Топология модели muxtree

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

Рисунок 4 – Модель 3hosts

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

Обзор результатов и выводы

  В ходе экспериментов изменялись следующие параметры модели: время моделирование, количество уровней дерева коммутаторов, количество входов на каждом коммутаторе, размер очереди, время на передачу сообщения, временной интервал между требованиями, время на обслуживание задачи. Для каждого случае определялось общее число посланных пакетов (Num), число потерь (Lost) и общее количество пакетов, которые достигли корня дерева (Sent).

  Моделирование проводилось за время равное 100 секундам. Количество уровней в модели – 5, входов – 4, размер очереди – 5, время передачи – 5, интервал между требованиями – 5, время обслуживания – 5.

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

Рисунок 5 – Зависимость числа пакетов от времени моделирования

  Увеличение числа уровней в дереве моделирования оказывало экспоненциальный рост числа пакетов. При этом процентное соотношение числа отосланных пакетов к общему числу оставалось почти прежним (23%). Изменение количества входов на каждом коммутаторе, при неизменном размере очереди, приводит к большим потерям пакетов.

Рисунок 6 – Зависимость числа пакетов от количества уровней модели

Рисунок 7 – Зависимость числа пакетов от количества входов на коммутаторах

  Изменения размера очереди на каждом из коммутаторов не влияет на число генерируемых пакетов при длине очереди отличной от 0. С увеличением же размера длины очереди количество потерь значительно сокращается и становится меньше, чем число пакетов, достигших корня дерева, при значении 50.

Рисунок 8 – Зависимость числа пакетов от размера очереди

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

Рисунок 9 – Зависимость числа пакетов от времени передачи пакета

Рисунок 10 – Зависимость числа пакетов от временного интервала между пакетами

Рисунок 11 – Зависимость числа пакетов от времени обслуживания

Перспектива дальнейших исследований

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

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

Литература

1. M.A. Rahman, A. Pakstas, F. Z. Wang. "Network Modelling and Simulation Tools". MESM’2006, Alexandria, Egypt, August 28-30, 2006.

   http://www.cms.livjm.ac.uk/pgnet2007/Proceedings/Papers/2007-011.pdf

2. Н.А. Олифер, В.Г. Олифер. "Средства анализа и оптимизации локальных сетей". Центр Информационных Технологий, 1998.

   http://www.citforum.ru/nets/optimize/index.shtml

3. Jason Liu. "Parallel Real-time Immersive Modeling Environment. User’s manual". Colorado School of Mines, June 9, 2006.

   http://prime.mines.edu/papers/ssfuser.pdf

4. С.В. Рощин, С.М. Аракелян. "Использование специализированных систем моделирования для анализа устойчивости телекоммуникационной инфраструктуры к вирусным и другим атакам".

   http://www.ict.edu.ru/vconf/files/6931.doc

На момент написания данного автореферата магистерская работа еще не завершена.
Работа будет закончена 1 декабря 2008 г.