Автореферат — Шишкин Е. С. — Кластерная система распределенного моделирования компьютерных сетей

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

На сегодняшний день существует ряд средств для моделирования компьютерных сетей. К ним относятся такие системы моделирования, как COMNET III производства Caci Products Co., BONeS Designer производства Cadence Inc., OPNET Modeler производства Mil3 Inc, а также NS2 на основе проекта VINT.

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

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

В своей работе я использую систему моделирования NS2, так как она является полностью бесплатной и распространяется с открытым исходным кодом. Пользователь может самостоятельно дописывать все необходимые модули и классы для работы с моделирующей системой. Еще одним преимуществом данной системы являются очень незначительные системные требования — 250 Мб пространства на жестком диске и 8 Мб оперативной памяти. Таким образом, эту систему моделирования можно запускать даже на компьютерах с процессором 486. Это очень удобно, так как можно организовать параллельную вычислительную сеть для моделирования, используя очень слабые компьютеры. Существующие аналоги NS требуют меньше места на жестком диске, но для работы им необходим больший объем оперативной памяти. NS поддерживается практически всеми операционными системами — Windows 95/98/Me/NT/2000/XP, Solaris, SunOS, Linux, FreeBSD, HP-UX.

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

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

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

Риcунок 1. Пример сети, промоделированной с помощью NS2. Анимация, 8 кадров, 58.5 Кб. Для повторения анимации обновите страницу.

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

Для реализации распределенного моделирования, взаимодействия между компьютерами и синхронизации работы между ними используется подключаемый модуль PDNS — Parallel Distributed Network Simulator, который, в свою очередь, для распределенной обработки использует библиотеку LibSynk, в которой реализованы все необходимые функции для функционирования распределенной системы моделирования.

Рассмотрим моделируемые алгоритмы маршрутизации в беспроводных сетях — AntHocNet и AODV.

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

AODV (Ad-hoc On-demand Distance Vector) — это алгоритм, основанный на построении таблиц маршрутизации на каждом узле сети для минимизации времени передачи информации между узлами. Первым шагом этого алгоритма является построение таблиц маршрутизации на каждом узле. В таблице содержится длина кратчайшего пути к каждому узлу в сети через каждый соседний узел. На первом шаге в таблице содержится информация только о доступе к соседним узлам в сети. На каждом следующем шаге каждый узел обменивается с соседними узлами информацией о каждом известном ему кратчайшем пути к каждому узлу сети. После некоторого количества шагов, зависящего от количества узлов в сети, таблицы маршрутизации на узлах перестают изменяться, после чего начинается передача данных по кратчайшему найденному пути. При сбое узла сети из таблицы берется следующий кратчайший маршрут.

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

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

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

Планируется написание программной оболочки для запуска данной системы моделирования на кластерной сети с использованием Windows Compute Cluster Server 2003. Данная оболочка будет распределять исходные данные по узлам сети, запускать процесс моделирования и собирать и предоставлять результаты моделирования для дальнейшего анализа.

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

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

Планируется провести порядка 10-20 экспериментов для сетей трех размеров — малых сетей (площадью до 500х500 м) с малым количеством узлов (до 15 шт), средних сетей (площадью от 500х500 до 1500х1500 м) и средним количеством узлов (от 15 до 150 шт) и больших сетей (площадью более 1500х1500 м.) и большим количеством узлов (более 150 шт). Для каждого алгоритма маршрутизации будет проводиться отдельная серия экспериментов, позволяющая определить преимущества и недостатки каждого из алгоритмов маршрутизации, а также определить общие закономерности функционирования беспроводных сетей для дальнейшего анализа и прогнозирования возможных результатов на сетях других размеров.

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

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

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

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

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

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

Литература

1. Ke Liu. Network Simulator 2: Introduction.
   http://www.cs.binghamton.edu/~kang/teaching/cs580s/ns2pre.pdf
2. Sally Floyd. Validation Experiences with the NS Simulator.
   http://www.icir.org/floyd/papers/NIST.Apr99.pdf
3. Gianni Di Caro, Frederick Ducatelle, Luca Maria Gambardella. AntHocNet: an Ant-Based Hybrid Routing Algorithm for Mobile Ad Hoc Networks.
   http://www.idsia.ch/~luca/anthocnetppsn.pdf
4. Ian D. Chakeres, Elizabeth M. Belding-Royer. AODV Routing Protocol Implementation Design.
   http://moment.cs.ucsb.edu/pub/wwan_chakeres_i.pdf