Введение к работе
Актуальность работы
Новейшие телекоммуникационные технологии являются необходимым условием развития современной экономики. В связи с внедрением сетевых технологий во многие сферы человеческой деятельности наблюдается повышенный интерес к вопросам моделирования и проектирования сетей и систем передачи данных. Моделирование используется практически повсеместно для предварительных исследований новых сетевых алгоритмов, предшествующих их внедрению в качестве управляющего программного обеспечения в узлы сети. Зачастую моделирование является единственным способом разработки новых принципов построения и работы систем, сетей, устройств связи, проверки качества предлагаемых решений, изучения их свойств, выявления зависимостей между параметрами и т.п. Моделирование также используется при изучении явлений в уже существующих системах телекоммуникаций.
На сегодняшний день существуют десятки моделирующих программ (симуляторов) сетей различного назначения. За рубежом программное обеспечение такого рода разрабатывается оборонным агентством США DARPA (проект VINT), группой Калифорнийского университета (проф. Р. Багродиа) в сотрудничестве с Национальной лабораторией в Беркли, группой Технологического института Джорджии (проф. Р. Фуджимото), а также производителями сетевого оборудования (Cisco). Эти и другие программы отличаются по степени универсальности (от достаточно универсальных систем до систем, ориентированных на конкретные модели оборудования) и расширяемости (от систем с фиксированной функциональностью до систем, позволяющих программирование на том или ином языке). В России вопросами моделирования и проектирования сетей и систем телекоммуникаций занимается множество научных коллективов (под руководством Г.П. Башарина, Г.Г. Яновского, К.Е. Самуйлова, В.М. Вишневского, Б.С. Гольдштейна, А.Е. Кучерявого, Е.Б. Алексеева, В.В. Крылова, В.А. Ершова, Е.Н. Таруты, СМ. Аракеляна и др.)
В связи с бурным развитием вычислительной техники становится возможной программная реализация распределенных программ моделирования сетей и систем телекоммуникаций с привлечением суперкомпьютерных вычислений. Такие программы отличает возможность моделирования очень больших сетей (от нескольких десятков тысяч узлов и выше), возможность поддержания объемных структур данных, а также более высокая сложность (программирования, расширения и т.д.) Примерами объектов имитационного моделирования в этом случае могут служить сенсорные сети, осуществляющие мониторинг большой территории, большие сети с ограниченно подвижными устройствами, одноранговые децентрализованные компьютерные сети распределенного
хранения данных, корпоративные сети, подсети сети Интернет и т.п. и, соответственно, все новые алгоритмы разных уровней в этих сетях. Среди алгоритмов управления потоком данных в таких сетях выделим алгоритмы, использующие приложения теории перколяции (в частности, вероятностный подход к использованию узлов и каналов связи при маршрутизации).
Распределенных симуляторов значительно меньше обычных, и лишь один из них не является коммерческим программным продуктом (что, помимо остальных недостатков, затрудняет или делает невозможным их использование в образовательном процессе). В этом свете не вызывает сомнений то, что разработка распределенного симулятора и проведение численных экспериментов на имеющемся в ВлГУ кластере «СКИФ Мономах» является перспективной и актуальной задачей.
Целью диссертационной работы является разработка концепции и последующая программная реализация универсальной распределенной расширяемой системы моделирования сетей и систем телекоммуникаций. Разрабатываемый моделирующий пакет должен быть лишен большинства недостатков существующих программных продуктов, позволять гибкое единообразное расширение возможностей, а также содержать базовый набор компонент, ориентированных на моделирование наиболее распространенных сетей (проводных компьютерных, сенсорных, мобильных) и сетевых алгоритмов. Разработка концепции и архитектуры должна быть основана на результатах обзора существующих средств и методов имитационного моделирования.
В ходе работы решались следующие задачи:
Разработка архитектуры и алгоритмов работы программного пакета для распределенного моделирования сетей и систем телекоммуникаций: алгоритма цикла моделирования и алгоритма динамической балансировки нагрузки на процессоры. Реализация сетевого симулятора в виде комплекса программ.
Разработка и реализация модулей расширения для моделирования:
регулярных сетей (с оптическими или проводными каналами связей),
сенсорных сетей (с радиоканалами связей),
статических одноранговых децентрализованных сетей с заданными степенями узлов (с проводными каналами связей),
сетей класса МАКЕТ с ограниченно подвижными узлами (с радиоканалами связей).
3. Проведение на основе разработанного моделирующего пакета
имитационного моделирования с целью:
исследования трафика в статической сенсорной сети и сенсорной сети с переключающимися узлами;
исследования базового и модифицированного алгоритма перколяционного поиска в компьютерных сетях распределенного
хранения данных («пиринговых» сетях) со степенной функцией плотности распределения числа соседних узлов (т.н. PL-сети);
исследования перколяционных свойств сети с неустойчивыми связями и структурными особенностями (мобильной телекоммуникационной сети), моделирование перколяционной маршрутизации методом «лавина»;
определения порога перколяции в трехмерной регулярной сети, состоящей из узлов, соединенных оптическими связями и формирующими мультикомпьютер.
Методы исследования. Достоверность полученных в работе результатов обеспечивается применением методов теории множеств, теории графов, теории перколяции, теории вероятности и математической статистики, теории алгоритмов, теории параллельных и распределенных вычислений и подтверждается результатами имитационного моделирования.
Научную новизну работы определяют следующие положения.
Разработана параллельная версия алгоритма генерирования топологии проводной телекоммуникационной сети с заданной функцией плотности распределения степеней узлов.
Модифицирован алгоритм перколяционного (вероятностного) поиска в одноранговых сетях распределенного хранения данных (разработан алгоритм направленного внедрения данных и запросов).
Установлено соотношение между порогами перколяции мобильных телекоммуникационных сетей для задачи связей в статическом и динамическом случаях.
Предложен алгоритм сокращения накладных расходов (числа копий пакетов) при лавинной рассылке в мобильных сетях с независимо переключающимися связями.
Практическая ценность работы заключается в том, что в ней предложен и программно реализован моделирующий пакет, ориентированный на распределенное высокоуровневое моделирование сетей и систем телекоммуникаций, состоящих из большого числа узлов. На его основе получены новые результаты в области алгоритмов для управления потоком данных в компьютерных телекоммуникационных сетях. Алгоритмы реализованы в программном обеспечении узлов реальных сетей, получены акты внедрения.
Предложенная модификация алгоритма перколяционного (вероятностного) поиска в распределенных компьютерных сетях хранения данных (пиринговых сетях) позволяет сократить в 1.5 ч- 7.0 раз число служебных пакетов в пересчете на 1 запрос при сохранении того же уровня успешных запросов.
Алгоритм перколяционной (вероятностной) лавинной рассылки позволяет сократить число копий пакетов данных в мобильной сети с
неустойчивыми каналами связи, для которой известен статический порог перколяции и может быть оценена средняя вероятность активности связей (величина сокращения числа копий пакетов зависит от этих двух параметров).
Разработанный алгоритм рабочего процесса симулятора обеспечивает ускорение s(P) = 0.93Р(Р - число процессов). Алгоритм распараллеливания генерирования топологии сенсорной сети позволяет строить модель сети за время Г(Р) ~ р~213. Алгоритм распараллеливания генерирования топологии проводной сети с заданной плотностью распределения создает модель сети за время Г(Р) ~ р~3-94. Полученные оценки свидетельствуют о высокой эффективности распараллеливания, заключающейся в значительном сокращении времени экспериментов при увеличении числа используемых процессов (процессоров).
Личный вклад
В работах, опубликованных в соавторстве, автором предложены алгоритмы программ, имитационные модели, выполнены лично основные расчеты, проведено моделирование, произведен анализ результатов.
Внедрение результатов работы
На разработанный программный комплекс получена государственная регистрация программы для ЭВМ №2009610991.
Моделирующий пакет программ используется для выполнения госбюджетных и хоздоговорных научно-исследовательских работ в рамках ряда ФЦП Минобразования.
Программное обеспечение и результаты работы внедрены в следующих организациях:
Владимирский государственный университет им. А.Г. и Н.Г. Столетовых;
ООО «Фирма «Инрэко ЛАН», г. Владимир;
ООО «ФС Сервис», г. Владимир.
Апробация работы
Основные результаты работы докладывались на следующих научно-технических совещаниях и конференциях:
П-я Международная научно-практическая конференция «Прогрессивные технологии и перспективы развития», Тамбов, 5 ноября 2010г.
XVII Всероссийская научно-методическая конференция «Телематика-2010», Санкт-Петербург, 21-24 июня 2010 г.
IX международная конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах», Владимир, 2-3 ноября 2009 г.
XVI Всероссийская научно-методическая конференция «Телематика-2009», Санкт-Петербург, 22-25 июня 2009 г.
5. VIII Международная научно-техническая конференция «Физика и радиоэлектроника в медицине и экологии» ФРЭМЭ'2008, Владимир, 2-4 июля 2008 г.
На защиту выносятся:
Архитектура и алгоритмы функционирования комплекса программ для распределенного моделирования сетей и систем телекоммуникаций.
Модификация алгоритма перколяционного (вероятностного) поиска в компьютерной пиринговой сети.
Алгоритм перколяционной (вероятностной) маршрутизации методом «лавина» в мобильной телекоммуникационной сети с изменяющейся топологией и структурными особенностями.
Компьютерные имитационные модели, с помощью которых проводились исследования сетей и сетевых алгоритмов.
Публикации
Основные результаты работы представлены в 12 публикациях, в том числе в 2 статьях в реферируемых изданиях из перечня ВАК.
Объем и структура диссертации
Диссертация изложена на 148 страницах машинописного текста. Состоит из введения, трех глав, заключения и приложений. Список литературы содержит 92 наименования. Таблиц 27, рисунков 36.
