Универсальная распределенная расширяемая система высокоуровневого моделирования сетей
На правах рукописи
Милованов Денис Сергеевич Универсальная распределенная расширяемая система высокоуровневого моделирования сетей Специальность 05.12.13 – «Системы, сети и устройства телекоммуникаций»
Автореферат диссертации на соискание ученой степени кандидата технических наук
Владимир 2011
Работа выполнена во Владимирском государственном университете им. А.Г. и Н.Г. Столетовых на кафедре «Физика и Прикладная Математика».
Научный консультант: доктор физико-математических наук, профессор, Аракелян Сергей Мартиросович
Официальные оппоненты: доктор технических наук, профессор Жигалов Илья Евгеньевич кандидат технических наук, профессор Медведев Юрий Алексеевич
Ведущая организация: ФГУ ГНИИ ИТТ «Информика», г. Москва
Защита диссертации состоится 27.04.11г. в 1400 на заседании диссертационного совета Д 212.025.04 Владимирского государственного университета им. А.Г. и Н.Г. Столетовых по адресу: 600000, Владимир, ул.
Горького, 87, ФРЭМТ.
С диссертацией можно ознакомиться в библиотеке Владимирского государственного университета им. А.Г. и Н.Г. Столетовых.
Автореферат разослан..2011 г.
Ученый секретарь диссертационного совета доктор технических наук, А.Г. Самойлов профессор -2
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы Новейшие телекоммуникационные технологии являются необходимым условием развития современной экономики. В связи с внедрением сетевых технологий во многие сферы человеческой деятельности наблюдается повышенный интерес к вопросам моделирования и проектирования сетей и систем передачи данных.
Моделирование используется практически повсеместно для предварительных исследований новых сетевых алгоритмов, предшествующих их внедрению в качестве управляющего программного обеспечения в узлы сети. Зачастую моделирование является единственным способом разработки новых принципов построения и работы систем, сетей, устройств связи, проверки качества предлагаемых решений, изучения их свойств, выявления зависимостей между параметрами и т.п.
Моделирование также используется при изучении явлений в уже существующих системах телекоммуникаций.
На сегодняшний день существуют десятки моделирующих программ (симуляторов) сетей различного назначения. За рубежом программное обеспечение такого рода разрабатывается оборонным агентством США DARPA (проект VINT), группой Калифорнийского университета (проф. Р.
Багродиа) в сотрудничестве с Национальной лабораторией в Беркли, группой Технологического института Джорджии (проф. Р. Фуджимото), а также производителями сетевого оборудования (Cisco). Эти и другие программы отличаются по степени универсальности (от достаточно универсальных систем до систем, ориентированных на конкретные модели оборудования) и расширяемости (от систем с фиксированной функциональностью до систем, позволяющих программирование на том или ином языке). В России вопросами моделирования и проектирования сетей и систем телекоммуникаций занимается множество научных коллективов (под руководством Г.П. Башарина, Г.Г. Яновского, К.Е.
Самуйлова, В.М. Вишневского, Б.С. Гольдштейна, А.Е. Кучерявого, Е.Б.
Алексеева, В.В. Крылова, В.А. Ершова, Е.Н. Таруты, С.М. Аракеляна и др.) В связи с бурным развитием вычислительной техники становится возможной программная реализация распределенных программ моделирования сетей и систем телекоммуникаций с привлечением суперкомпьютерных вычислений. Такие программы отличает возможность моделирования очень больших сетей (от нескольких десятков тысяч узлов и выше), возможность поддержания объемных структур данных, а также более высокая сложность (программирования, расширения и т.д.) Примерами объектов имитационного моделирования в этом случае могут служить сенсорные сети, осуществляющие мониторинг большой территории, большие сети с ограниченно подвижными устройствами, одноранговые децентрализованные компьютерные сети распределенного -3 хранения данных, корпоративные сети, подсети сети Интернет и т.п. и, соответственно, все новые алгоритмы разных уровней в этих сетях. Среди алгоритмов управления потоком данных в таких сетях выделим алгоритмы, использующие приложения теории перколяции (в частности, вероятностный подход к использованию узлов и каналов связи при маршрутизации).
Распределенных симуляторов значительно меньше обычных, и лишь один из них не является коммерческим программным продуктом (что, помимо остальных недостатков, затрудняет или делает невозможным их использование в образовательном процессе). В этом свете не вызывает сомнений то, что разработка распределенного симулятора и проведение численных экспериментов на имеющемся в ВлГУ кластере «СКИФ Мономах» является перспективной и актуальной задачей.
Целью диссертационной работы является разработка концепции и последующая программная реализация универсальной распределенной расширяемой системы моделирования сетей и систем телекоммуникаций.
Разрабатываемый моделирующий пакет должен быть лишен большинства недостатков существующих программных продуктов, позволять гибкое единообразное расширение возможностей, а также содержать базовый набор компонент, ориентированных на моделирование наиболее распространенных сетей (проводных компьютерных, сенсорных, мобильных) и сетевых алгоритмов. Разработка концепции и архитектуры должна быть основана на результатах обзора существующих средств и методов имитационного моделирования.
В ходе работы решались следующие задачи:
Разработка архитектуры и алгоритмов работы программного пакета 1.
для распределенного моделирования сетей и систем телекоммуникаций:
алгоритма цикла моделирования и алгоритма динамической балансировки нагрузки на процессоры. Реализация сетевого симулятора в виде комплекса программ.
Разработка и реализация модулей расширения для моделирования:
2.
регулярных сетей (с оптическими или проводными каналами связей), сенсорных сетей (с радиоканалами связей), статических одноранговых децентрализованных сетей с заданными степенями узлов (с проводными каналами связей), сетей класса MANET с ограниченно подвижными узлами (с радиоканалами связей).
Проведение на основе разработанного моделирующего пакета 3.
имитационного моделирования с целью:
исследования трафика в статической сенсорной сети и сенсорной сети с переключающимися узлами;
исследования базового и модифицированного алгоритма перколяционного поиска в компьютерных сетях распределенного -4 хранения данных («пиринговых» сетях) со степенной функцией плотности распределения числа соседних узлов (т.н. PL-сети);
исследования перколяционных свойств сети с неустойчивыми связями и структурными особенностями (мобильной телекоммуникационной сети), моделирование перколяционной маршрутизации методом «лавина»;
определения порога перколяции в трехмерной регулярной сети, состоящей из узлов, соединенных оптическими связями и формирующими мультикомпьютер.
Методы исследования. Достоверность полученных в работе результатов обеспечивается применением методов теории множеств, теории графов, теории перколяции, теории вероятности и математической статистики, теории алгоритмов, теории параллельных и распределенных вычислений и подтверждается результатами имитационного моделирования.
Научную новизну работы определяют следующие положения.
Разработана параллельная версия алгоритма генерирования 1.
топологии проводной телекоммуникационной сети с заданной функцией плотности распределения степеней узлов.
Модифицирован алгоритм перколяционного (вероятностного) поиска 2.
в одноранговых сетях распределенного хранения данных (разработан алгоритм направленного внедрения данных и запросов).
Установлено соотношение между порогами перколяции мобильных 3.
телекоммуникационных сетей для задачи связей в статическом и динамическом случаях.
Предложен алгоритм сокращения накладных расходов (числа копий 4.
пакетов) при лавинной рассылке в мобильных сетях с независимо переключающимися связями.
Практическая ценность работы заключается в том, что в ней предложен и программно реализован моделирующий пакет, ориентированный на распределенное высокоуровневое моделирование сетей и систем телекоммуникаций, состоящих из большого числа узлов. На его основе получены новые результаты в области алгоритмов для управления потоком данных в компьютерных телекоммуникационных сетях. Алгоритмы реализованы в программном обеспечении узлов реальных сетей, получены акты внедрения.
Предложенная модификация алгоритма перколяционного (вероятностного) поиска в распределенных компьютерных сетях хранения данных (пиринговых сетях) позволяет сократить в 1.5 7.0 раз число служебных пакетов в пересчете на 1 запрос при сохранении того же уровня успешных запросов.
Алгоритм перколяционной (вероятностной) лавинной рассылки позволяет сократить число копий пакетов данных в мобильной сети с -5 неустойчивыми каналами связи, для которой известен статический порог перколяции и может быть оценена средняя вероятность активности связей (величина сокращения числа копий пакетов зависит от этих двух параметров).
Разработанный алгоритм рабочего процесса симулятора обеспечивает ускорение (P – число процессов). Алгоритм распараллеливания генерирования топологии сенсорной сети позволяет строить модель сети за время Алгоритм распараллеливания генерирования топологии проводной сети с заданной плотностью распределения создает модель сети за время. Полученные оценки свидетельствуют о высокой эффективности распараллеливания, заключающейся в значительном сокращении времени экспериментов при увеличении числа используемых процессов (процессоров).
Личный вклад В работах, опубликованных в соавторстве, автором предложены алгоритмы программ, имитационные модели, выполнены лично основные расчеты, проведено моделирование, произведен анализ результатов.
Внедрение результатов работы На разработанный программный комплекс получена государственная регистрация программы для ЭВМ №2009610991.
Моделирующий пакет программ используется для выполнения госбюджетных и хоздоговорных научно-исследовательских работ в рамках ряда ФЦП Минобразования.
Программное обеспечение и результаты работы внедрены в следующих организациях:
Владимирский государственный университет им. А.Г. и Н.Г.
Столетовых;
ООО «Фирма «Инрэко ЛАН», г. Владимир;
ООО «ФС Сервис», г. Владимир.
Апробация работы Основные результаты работы докладывались на следующих научно технических совещаниях и конференциях:
Международная научно-практическая конференция 1. II-я «Прогрессивные технологии и перспективы развития», Тамбов, 5 ноября 2010г.
Всероссийская научно-методическая конференция 2. XVII «Телематика-2010», Санкт-Петербург, 21–24 июня 2010 г.
IX международная конференция-семинар «Высокопроизводительные 3.
параллельные вычисления на кластерных системах», Владимир, 2– ноября 2009 г.
XVI Всероссийская научно-методическая конференция «Телематика 4.
2009», Санкт-Петербург, 22–25 июня 2009 г.
-6 VIII Международная научно-техническая конференция «Физика и 5.
радиоэлектроника в медицине и экологии» ФРЭМЭ'2008, Владимир, 2– июля 2008 г.
На защиту выносятся:
Архитектура и алгоритмы функционирования комплекса программ 1.
для распределенного моделирования сетей и систем телекоммуникаций.
Модификация алгоритма перколяционного (вероятностного) поиска 2.
в компьютерной пиринговой сети.
Алгоритм перколяционной (вероятностной) маршрутизации методом 3.
«лавина» в мобильной телекоммуникационной сети с изменяющейся топологией и структурными особенностями.
Компьютерные имитационные модели, с помощью которых 4.
проводились исследования сетей и сетевых алгоритмов.
Публикации Основные результаты работы представлены в 12 публикациях, в том числе в 2 статьях в реферируемых изданиях из перечня ВАК.
Объем и структура диссертации Диссертация изложена на 148 страницах машинописного текста.
Состоит из введения, трех глав, заключения и приложений. Список литературы содержит 92 наименования. Таблиц 27, рисунков 36.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертационной работы и ее научная новизна, сформулированы цель и основные задачи исследования, защищаемые положения, их практическая значимость, обсуждается также реализация и внедрение результатов работы.
В первой главе проводится обзор и классификация существующих средств моделирования телекоммуникационных сетей. Обзор проводится с целью формирования представлений о возможностях современных симуляторов, требований, которые к ним предъявляются, возможных архитектурах, принципах и т.д.
Обсуждаются общие вопросы моделирования, подтверждается необходимость компьютерного эксперимента. Вводится понятие и проводится классификация средств моделирования. Рассмотрены наиболее популярные средства моделирования сетей телекоммуникаций, не использующие распределенные вычисления (моделирующие программы ns-2, PeerSim, OpNET и т.д.) Выполнен обзор распределенных средств (симуляторы pdns, Glomosim, SSF, USSF, TeD). Проводится обобщение сведений о недостатках существующих программных средств (невозможность расширения функциональности, сложность в запуске серии экспериментов, отсутствие графического интерфейса и т.п.) Во второй главе рассматривается концепция универсальной распределенной расширяемой системы высокоуровневого моделирования -7 сетей и систем телекоммуникаций, архитектура и реализация комплекса программ. Сформулированы и подтверждены принципы минимальной базы, максимальной расширяемости и максимальной масштабируемости.
Рассмотрена архитектура и программная реализация ядра симулятора – ключевой программы, осуществляющей базовые операции моделирования. Согласно принципу минимальной базы в состав объектов модели включены объекты «узел» и «пакет», содержащие минимум фиксированных свойств. Согласно принципу максимальной расширяемости ядро симулятора предоставляет унифицированный интерфейс для собственного расширения (т.н. API — интерфейс программирования приложений). Объекты модели поддерживают методы для неограниченного собственного расширения в соответствии с логикой модели, протокола и т.п. Расширение производится в рамках модуля расширения – программного модуля в виде динамической библиотеки.
Модули разрабатываются отдельно и независимо от ядра и реализуют обычно некоторую независимую часть модели, например, генерируют топологию или осуществляют маршрутизацию. Помимо расширения функциональности симулятора с точки зрения модели имеется возможность задать пользовательскую вычислительную топологию (шаблон взаимодействия процессов), пользовательское разделение топологии (разбиение узлов по процессам).
Согласно принципу максимальной масштабируемости ядро симулятора работает в циклическом (пошаговом) режиме (как и, например, симулятор SSF). Это сделано потому, как известно, что алгоритмы управления временем при дискретно-событийном подходе плохо распараллеливаются и масштабируются. Известно также, что для многих высокоуровневых протоколов, на которые, прежде всего, и ориентирован симулятор, допущение о квантовании времени является приемлемым и не сказывается на логике их работы. При этом достигается максимальная производительность модели за счет некоторой не критичной потери реалистичности (не моделируются задержки на передачу пакетов по физическим каналам).
Предложен Алгоритм 1 (выполнения шага моделирования (цикла) на одном процессе):
вызвать очередь модулей расширения для каждого узла сети, 1) моделируемого данным процессом (собственно моделирование) очистить буферы входящих пакетов;
перенести выходящие пакеты 2) одного узла в буфер входящих пакетов узла-приемника (если тот обрабатывается этим же процессом);
собрать пакеты, требующие отправки узлам, моделируемым другими процессами;
очистить буферы исходящих пакетов (обработка пакетов);
отправить требуемые пакеты другим процессам с помощью 3) неблокирующей передачи (передача);
-8 принять пакеты от других процессов с помощью блокирующей 4) операции приема (прием).
С целью оптимизации времени выполнения распределенного приложения предложен Алгоритм 2 (динамической балансировки).
(Первый шаг) Занумеруем пары так, что 1.
бы Здесь и далее: – количество узлов, моделируемых в данный момент процессом – время, затрачиваемое на моделирование процессом измеренное за некоторое количество наблюдаемых циклов, Пусть из второго (в новой нумерации) процесса моделируемых узлов отправляются первому процессу. Тогда,,, Имеем на выходе первого шага.
Теперь занумеруем процессы так, что бы и перейдем к шагу 2.
с номером На входе имеем пары 2. (Шаг K) занумерованные так, что. Пусть из K+1-го процесса узлов распределяется между первыми процессами пропорционально. Это требование обеспечит одинаковый прирост времени работы на каждом процессе:
,, На выходе имеем, причем. Шаги проделываются до тех пор, пока не будут перебраны все процессы. Таким образом, все процессы получают данные о том, в каком количестве и кому отправить моделируемые узлы для того, что бы уравнять временные затраты.
Также во второй главе приведены сведения о системе управления экспериментами. Система управления разработана на основе модели клиент-сервер и позволяет управлять ходом экспериментов с локальной и удаленной машины. Клиент системы управления предоставляет возможность авторизации пользователя, создание и редактирование параметров независимых экспериментов, пакетный запуск, мониторинг и останов, вызов любой внешней программы анализа выходных данных (программа такого рода также разработана и включена в состав комплекса) и программы визуализации. Структура системы моделирования представлена на рис. 1.
Здесь же рассматриваются уже реализованные и отлаженные модули расширения симулятора, которые будут применяться в ходе имитационного моделирования. Данный набор модулей является -9 достаточно универсальным и может применяться для построения широкого класса моделей, а также с целью последующей модификации и адаптации.
Эксперимент:
ядро программа- программа фрагмент клиент визуализации моделируемой Головной узел кластера сети модули модули модули модули Узел кластера...
программа- эксперименты сервер ядро фрагмент моделируемой репозиторий программа сети модули модули модули модулей анализа модули Узел кластера Рисунок Описаны модули генерирования топологии. Рассматривается топология регулярной трехмерной решетки, топология сенсорной сети («пуассоновский ансамбль») и топология с заданной функцией плотности распределения степеней узлов. Последовательные алгоритмы построения топологии по заданному вектору степеней узлов, встречающиеся в литературе, применяются только для небольших сетей в виду их большой вычислительной сложности. В случае больших сетей применяются другие соображения (например, во всех экспериментах используется одна предварительно заданная сеть, которая хранится в файле). В диссертационной работе предлагается алгоритм распределенного генерирования топологии именно по заданному вектору степеней узлов.
Пусть есть некоторая плотность распределения, согласно которой строится вектор распределения, который для каждого показывает, сколько в сети существует узлов со степенью. Вектор распределения назовем далее просто распределением.
Предложен Алгоритм 3 (построения процессом распределения для своего подмножества узлов на основе вектора глобального распределения ). Реализуется формула Здесь – случайная величина, равномерно распределенная на [0, 1], – индикатор события, - дробная часть величины, – доля узлов, моделируемых процессом. Получившийся целочисленный вектор используется как распределение фрагмента сети — субраспределение.
Предложен Алгоритм (распараллеливания алгоритма генерирования топологии с заданной функцией плотности распределения):
- 10 на основе своего субраспределения каждый процесс генерирует 1) топологию своего фрагмента сети (известным последовательным алгоритмом);
в каждом фрагменте отыскивается множество связей, удаление 2) которых из фрагмента оставляет подсеть, в которой максимальная степень узла равна данному значению («порогу»);
это множество связей равномерно делится по числу соседних 3) процессов, происходит обмен множествами между соседними процессами;
фрагменты сети склеиваются в общую топологию с помощью 4) операции «разрыв-соединение» на этих множествах связей: каждая пара процессов разрывает свои связи A–B (первый) и С–D (второй) и устанавливает связи A–C (первый) и B–D (второй) (см. рис. 2);
вероятность того, что степени узла при этом изменятся, крайне мала (сама операция возможна, поскольку каждый процесс после обмена с соседними процессами знает свое множество таких связей и чужое).
С помощью разработанного алгоритма становится возможным генерирование сетей в частных случаях. Например, если, то имеют место т.н. PL-сети.
Они представляют особый интерес, поскольку показано, что многие реальные одноранговые сети организуются примерно по этому закону.
Также в главе описываются модули маршрутизации. Базовым алгоритмом маршрутизации является маршрутизация Рисунок методом «лавина» (лавинная рассылка), которая реализована в двух вариантах – с ожиданием («отложенная») и без ожидания. Важным моментом является моделирование ошибок, возникающих во время передачи пакетов. Поскольку симулятор ориентирован в основном на высокоуровневое моделирование сетей физическая сторона вопросов передачи данных подробно не моделируется.
В таком случае обычно прибегают к коэффициентам, связывающим модель и реальный объект. В данном случае используется простая модель:
любой пакет доходит до адресата с фиксированной заданной вероятностью.
Процедура перколяционного поиска в сетях распределенного хранения данных (компьютерные файлообменные сети) рассмотрена в одном из источников и заключается в следующем: 1) узлы с помощью случайного блуждания длины распространяют сведения о своих данных (внедрение контента);
2)при необходимости поиска данных в сети узел также инициирует случайное блуждание длины (внедрение запроса);
3)каждый узел, участвующий во внедрении запроса начинает - 11 перколяционный поиск (ветвящиеся случайные блуждания с вероятностью длины ). Показано, что случайные блуждания выходят на узлы с большой степенью связности (суперузлы) с вероятностью близкой к 1.
Перколяционный поиск данных в кластере суперузлов даже с небольшим параметром гарантирует то, что данные будут найдены. Такой алгоритм поиска эффективен (по сравнению с прямым поиском) с точки зрения числа копий служебных пакетов. Дополнительно повысить эффективность и качество поиска предлагается с помощью следующей модификации.
Алгоритм (направленного кэширования и направленного запроса).
(Подготовительный этап). Каждый узел узнает число соседей у 1.
каждого своего соседа и сохраняет эти данные (таким образом, алгоритм уже не опирается только на локальные данные). Пусть узел обладает вектором, где - число соседей у i-го соседа.
При необходимости кэширования контента или перенаправления 2.
запроса, пакет отправляется:
соседу с максимальным (если отправка ему еще не a) производилась), соседу со вторым, третьим и т.д. по величине числом (если отправка узлу с большим числом соседей приведет к зацикливанию) или соседу с вероятностью (предпочтительно);
b) узлу-отправителю, если блуждание заходит в тупик.
c) Рассмотрены вопросы, связанные с перколяционными свойствами динамических телекоммуникационных сетей. Рассматриваются мобильные сети со структурными особенностями (в качестве примера можно привести сети с ограниченно подвижными узлами). Показано, что в таких сетях процесс переключения связей (если не учитывать помехи), носит периодический характер, и для каждой связи можно оценить – вероятность ее активности. В работе ставится вопрос о достижимости узлов второго множества из узлов первого множества (по активным связям). Пусть для такой сети возможно вычислить — статический порог перколяции в задаче связей, т.е. такую минимальную долю активных связей, при которой сеть все еще связывает оба множества. Тогда основное утверждение состоит в том, что полная лавина, запускаемая узлами первого множества, доходит до узлов второго множества только в случае, где – среднее по сети значение. Кроме того, если строго, то в сети существует избыток связей (с точки зрения «проводимости») и имеется возможность сократить число копий пакетов за счет использования каждой связи с вероятностью 1. Эта формула служит оценкой порога перколяции динамической сети, которую необходимо проверить с помощью эксперимента, и одновременно представляет основу для алгоритма перколяционной маршрутизации.
- 12 Алгоритм (перколяционной (вероятностной) маршрутизации методом «лавина» в телекоммуникационной сети с переключающимися связями):
узлы оценивают вероятность активности каждой своей связи с 1) другими узлами;
полученные данные собираются выделенными узлами;
выделенные узлы рассчитывают среднее и порог перколяции, 2) полученные данные рассылаются всем узлам;
при необходимости маршрутизации пакета с данными методом 3) «лавина» он пересылается каждому соседу с вероятностью.
В важном частном случае, предложенный алгоритм позволяет осуществлять доставку пакета данных от одного узла до всех остальных, при этом число возникающих копий пакетов сокращается в раз.
Для моделирования сети с изменяющейся топологией рассмотрены модели переключения узлов по встроенному расписанию, а также переключения связей согласно случайному процессу «обобщенная телеграфная волна», которая, помимо параметра позволяет задавать еще и интенсивность изменений топологии.
В заключение рассмотрен вопрос генерирования трафика.
Рассмотрены несколько простых моделей трафика: генерирование пакетов с фиксированной вероятностью, генерирование при включении, генерирование согласно пуассоновскому процессу.
Все предложенные модели и алгоритмы программно реализованы в ядре симулятора или в модулях расширения.
В третьей главе в рамках разработанного программного комплекса проводится имитационное моделирование телекоммуникационных сетей.
Логика всех экспериментов заключена в ранее разработанных модулях расширения: эксперимент заключается в выборе модулей, конфигурировании системы управления в соответствии с планом эксперимента и запуске моделирования.
Рассматриваются численные эксперименты по определению порога перколяции в регулярной сетевой структуре, реальным прототипом которой является трехмерная регулярная сеть с узлами, связанными оптическими каналами связи и формирующими мультикомпьютер. В силу ряда причин узлы выходят из строя («выключаются»). Требуется определить минимальную долю (в терминах теории перколяции — концентрацию) включенных узлов, которая обеспечивает «проводимость» от первого слоя сети к последнему. Выполнена серия численных экспериментов, направленная на численное определение такой минимальной концентрации (порога перколяции). Для этого в регулярной топологии генерируется трафик и исследуется его доставка методом «лавина». Также рассмотрен случай, когда включенные узлы образуют последовательности длины. В ходе экспериментов в сети из 24 млн.
узлов показано наличие явления перколяции — фазового перехода - 13 связанного с ростом концентрации (см. рис. 3). Показано также, что для обеспечения связности требуется порядка 10% (0.098±0.001) включенных узлов. Кроме того показано, что в случае протяженных групп узлов (d 1) порог перколяции существенно ниже. Использование симулятора позволило существенно сократить время проведения серии экспериментов (на рис. 4 представлено время выполнения одного эксперимента в зависимости от числа используемых процессов).
Доля экспериментов, в которых имело место формирование Время выполнения стягивающего кластера узлов эксперимента, с 1 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 8 12 Концентрация Число процессов d=1 d=10 d= работающих узлов Рисунок Рисунок Далее рассматриваются численные эксперименты по моделированию алгоритма перколяционной лавины в статических сенсорных сетях.
Перколяционная лавина – это такая модификация лавинного процесса, при котором каждый узел принимает решение о копировании пакетов с вероятностью, уменьшающейся с ростом числа его соседей:
.
Здесь – степень узла, – фиксированный параметр. С помощью численных экспериментов на сети из 100 000 узлов (радиус действия устройства ) установлено, что в достаточно связной сети, существует такое значение, которое служит порогом перколяции. А именно, при всех вероятностная лавинная рассылка покрывает всю сеть как и обычная лавина, т.е. величина, равная доле доставленных пакетов, равна 1. При лавинная рассылка быстро прекращается. При этом также установлено, что не зависит от среднего числа соседей узлов сети (а значит и радиуса ). Этот результат представлен на рис. 5. Абсолютная погрешность в измерении равна 0. (доверительная вероятность 0.95). Также получены данные о том, что маршруты удлиняются в 1.2 1.7 раза, число копий пакетов сокращается в 2.5 7.0 раз.
Сокращение времени проведения одного эксперимента представлено на рис. 6. Отметим, что по этим данным нельзя судить об ускорении - 14 вычислений (в классическом понимании), поскольку генерирование топологии сенсорной сети имеет сложность.
Доля доставленных пакетов Время работы, с 1 0. 0. 0. 0.2 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10. 4 9 r = 4.0 r = 8.0 kmin Число процессов r = 12.0 r = 14. Рисунок 5 Рисунок Далее рассматриваются численные эксперименты по моделированию базового и модифицированного перколяционного поиска в одноранговых телекоммуникационных PL-сетях распределенного хранения данных.
Прежде всего, исследован вопрос параллельного генерирования топологии.
Рассмотрим степенное распределение с = 2.0 и сеть из 10 000 узлов.
Результаты представлены в таблице: сравнивается ожидаемое и полученное среднее число соседей по сети, а также указывается расстояние между векторами распределений (по метрике L1).
Число Время Ожидаемое Полученное Расстояние между процессов выпол- среднее число среднее число распределениями нения соседей соседей (погрешность, %) 1272.3 с 3. 8 3.251 148 (1.5%) 252.6 с 12 3.308 3.254 168 (1.7%) 81.0 с 16 3.308 3.298 152 (1.5%) Время генерирования сокращается как, где – число процессов. Аналогичные данные получены и для других значений параметров и распределений. Полученные результаты свидетельствуют о корректности и эффективности алгоритма распределенного генерирования топологии. Ошибка составляет не более 2% при допустимом уровне в 10%.
В генерируемых PL-топологиях исследовался базовый и модифицированный перколяционный поиск данных (контента).
Рассмотрена модель PL-сети из 20 000 узлов ( = 2.0), в которой задавались параметры внедрения контента, запроса и поиска.
Моделировалось 20 000 распространений контента и столько же запросов.
Основной выходной параметр — доля успешных запросов (абсолютная погрешность ее измерения равна 0.04 при доверительной вероятности 0.95). На рис. 7 и 8 представлены результаты по базовому и модифицированному алгоритмам соответственно, параметр = 0.025.
Эксперименты, которые проводились на PL-сетях с = 1.5 2.5, позволяют - 15 обобщить полученные данные следующим образом: при фиксированных число успешных запросов вырастает в 1.0 9.0 раз, при фиксированном уровне успешных запросов базовый алгоритм требует в 1.5 7.0 раз больше служебных пакетов.
Доля успешных запросов Доля успешных запросов 0. 0. 0. 0. 0. 0. 0.2 0. 0 2 4 6 8 10 12 2 4 6 8 10 L=2 L= L=2 L=4 Lp Lp L=6 L= L=6 L= L = 10 L = L = 10 L = Рисунок 7 Рисунок Далее проведены численные эксперименты по моделированию медленного трафика в сенсорных сетях с переключающимися узлами. Не синхронизированное и независимое друг от друга переключение узлов из активного состояния в неактивное и наоборот является инженерным решением, которое можно применить в сенсорной сети для сокращения расходов энергии. Оповещением называется процесс распространения данных от узла всем остальным, узел получивший оповещение не выключается до тех пор, пока не оповестит всех соседей. Среднее время оповещения всех узлов зависит от параметров переключения (например, от среднего времени неактивного состояния t0). При проектировании сети необходимо выбрать такой параметр t0, при котором среднее время оповещения будет требуемым. В одном из источников аналитически показано, что среднее время оповещения узлов линейно относительно времени неактивного состояния t0 (при равномерном и экспоненциальном распределении промежутков времени в расписании). Проведена серия экспериментов с моделью сенсорной сети из 100 000 узлов (среднее число соседей равно 5), которая подтвердила данное утверждение. На рис. представлен процесс роста числа оповещенных узлов в зависимости от t 0, среднее время оповещения представлено на рис. 10.
В ходе пятой серии экспериментов проверялась корректность оценки порога перколяции в телекоммуникационных сетях с переключающимися связями. Рассмотрены две сети, для которых порог перколяции в задаче связей известен. В каждой сети = 100 000 узлов. «Сеть 1» представляет собой сеть с базовой топологией прямоугольной решетки с использованием диагональных связей, порог перколяции такой сети - 16 получен аналитически: = 0.25. «Сеть 2» имеет базовое пуассоновское распределение, среднее число соседей 7.82. Порог перколяции такой сети вычислен предварительно = 0.50±0.01). Пусть связи переключаются так, что – средняя вероятность активности связи. Сравним прогнозное значение порога для такой сети с получаемым в ходе эксперимента порогом перколяции (верхним). Результаты представлены на рис. 11 и 12. Абсолютная погрешность в измерении верхнего порога перколяции не превосходит 0.02. При очень большом разбросе входных параметров погрешность оценки (прогноза) не превосходит 8%, значит, с соответствующей поправкой это значение может применяться при перколяционной маршрутизации методом «лавина».
Доля оповещенных узлов Среднее время оповещения, ед.
1 0.8 0. 0. 0.2 0 0 5000 10000 15000 0 20 40 60 80 Время неактивного t0 = 10 t0 = 50 Время, ед состояния t0, ед t0 = Рисунок 9 Рисунок Пороги перколяции Пороги перколяции 0. 0. 0. 0. 0. 0. 0.2 0. Mf Mf 0 0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8 p* (прогноз) p (верхний) p* (прогноз) p (верхний) Рисунок 11 Рисунок В заключение сведения о быстродействии алгоритмов, лежащих в основе ядра и модулей расширения, можно обобщить в следующей таблице. Здесь же указан максимум коэффициента осцилляции значений вектора который представляет собой суммарное время выполнения операции моделирования процессом с номером p. Это значение нигде не превосходит заданного как параметр порогового значения 0.1 (которое выбрано из эмпирических соображений), что свидетельствует о требуемой - 17 сбалансированности работы процессов. Приведенные в таблице соотношения могут служить основой для выбора числа процессоров при проведении численных экспериментов.
Номер Число Среднее время Ускорение Коэф.
или серии узлов сети проведения осцилляции оценка времени эксперимента основного алгоритма 24 000 000 130 с 1 0. 350 с 2 100 000 0. 120 с 3 20 000 0. 280 с 4 100 000 0. 190 с 5 100 000 0. В заключении сформулированы основные результаты работы, которые сводятся к следующему.
Проведены серии экспериментов с имитационными моделями сетей 1.
и систем телекоммуникаций (проводные компьютерные сети, сенсорные сети, мобильные сети).
Исследован процесс распространения данных в компьютерной a.
сети с топологией трехмерной решетки. Вычислены пороги перколяции в задаче узлов для данной топологии.
Исследован алгоритм адаптивной перколяционной b.
(вероятностной) лавинной маршрутизации в сенсорных сетях.
Показано, что в любой сенсорной сети существует критическое значение параметра, не зависящее от связности, при котором такая лавина эквивалентна полной.
Исследован вопрос распространения данных в сенсорной сети c.
с переключающимися узлами. Показано, что среднее время оповещения всех узлов такой сети линейно растет с ростом времени неактивного состояния узлов.
Исследован алгоритм модифицированного перколяционного 2.
(вероятностного) поиска в компьютерных сетях распределенного хранения данных. Показано, что при его использовании: при одной и той же глубине блужданий число успешных запросов возрастает в 1.0 9.0 раз, при фиксированном уровне успешных запросов требуется в 1.5 7.0 раз меньше служебных пакетов.
Исследовано перколяционное свойство телекоммуникационных 3.
сетей с неустойчивыми связями (мобильных сетей). Показано, что в таких сетях при проведении лавинной рассылки можно использовать каждую связь с вероятностью, которая оценивается как, и, соответственно, сократить число используемых связей в раз. Здесь — статический порог перколяции, — средняя по сети вероятность активности связей. При этом достигается тот же эффект, что и при полной лавине. Ошибка оценки составляет не более 8%.
- 18 В ходе экспериментов подтверждены заявленные качества 4.
разработанного программного обеспечения.
Универсальность симулятора подтверждена моделированием a.
реальных сетей различной природы (с проводными, радио- и оптическими каналами связи) с использованием общераспространенных моделей.
Расширяемость и модульность симулятора подтверждены тем b.
фактом, что разные имитационные модели собраны из базового набора модулей расширения. Все модули расширения имеют унифицированный интерфейс и разрабатывались независимо от других модулей и ядра симулятора.
Подтверждена работоспособность, корректность и c.
эффективность распределенных алгоритмов генерирования топологий, положенных в основу модулей расширения. Пусть – число процессов. Алгоритм распараллеливания генерирования топологии сенсорной сети позволяет строить модель сети за время Алгоритм распараллеливания генерирования топологии проводной сети с заданной плотностью распределения создает модель сети за время. Ошибка при этом не превосходит 2% при допустимом уровне в 10%. Разработанный алгоритм рабочего процесса обеспечивает ускорение, что свидетельствует о высокой эффективности работы ядра симулятора.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ В рецензируемых журналах из перечня ВАК Аракелян С.М., Звягин М.Ю., Милованов Д.С., Прокошев В.Г., 1.
Шамин П.Ю. Многоцелевая маршрутизация с использованием механизма самоорганизации в мобильных сетях с ограниченно подвижными отключаемыми узлами // Информатизация образования и науки, №2(6), 2010. — С.52–62.
Голубев А.С., Звягин М.Ю., Милованов Д.С. Применение 2.
структурной информации о топологии для снижения ресурсоемкости протоколов маршрутизации в мобильных сетях // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление, №2(76), 2009. — С.43–48.
В других изданиях Аракелян С.М., Милованов Д.С., Прокошев В.Г., Тухтамирзаев 3.
А.Ю., Шамин П.Ю. Об организации интеллектуальной маршрутизации в сети с динамической топологией с использованием статистических - 19 характеристик связей // Информатизация образования и науки, №1(5), 2010. — С.43–55.
Милованов Д.С. Генерирования графа с заданным распределением в 4.
условиях распределения топологии // Материалы II-ой Международной научно-практической конференции «Прогрессивные технологии и перспективы развития», Тамбов, 2010. — С.45.
Голубев А.С., Звягин М.Ю., Милованов Д.С., Шамин П.Ю. К 5.
вопросу об огрублении статистических данных при вероятностной маршрутизации в мобильных сетях с высоким уровнем изменчивости топологии // Материалы XVII Всероссийской научно-методической конференции «Телематика-2010», СПб, 2010. — С. 250–251.
Аракелян С.М., Милованов Д.С., Прокошев В.Г., Повышение 6.
эффективности лавинной маршрутизации для сетей с экстремально быстро изменяющейся топологией за счет проактивного принципа // Материалы XVI Всероссийской научно-методической конференции «Телематика 2009», СПб, 2009. — С. 255–256.
Голубев А.С., Милованов Д.С., Звягин М.Ю. Эффект перколяции в 7.
информационных сетях с неустойчивыми связями // Материалы Девятой международной конференции-семинара «Высокопроизводительные параллельные вычисления на кластерных системах», Владимир, 2009. — С.101–105.
Аракелян С.М., Милованов Д.С., Прокошев В.Г., Шамин П.Ю.
8.
Методы оценки параметров линии связи в сети с ограниченно подвижными отключаемыми узлами // Материалы XV Всероссийской научно-методической конференции «Телематика-2008», СПб, 2008. — С.133–134.
Милованов Д.С., Шамин П.Ю. Организация устойчивого канала 9.
связи в сети с ограниченно подвижными отключаемыми узлами // VIII Международная научно-техническая конференция «Физика и радиоэлектроника в медицине и экологии», Владимир, 2008. — С.318–320.
10. Звягин М.Ю., Милованов Д.С., Прокошев В.Г. Алгоритмы сбора информации, маршрутизации и агрегации в мобильных сетях // Материалы международного форума по проблемам науки, техники и образования «III тысячелетие – новый мир», М., 2007. – Т.2. — С.91–93.
ЛР № 020275. Подписано в печать.. Формат 60х84/16. Бумага для множит. техники. Гарнитура Таймс.
Печать на ризографе. Усл. печ. л. 0,93. Уч.-изд. л. 0,98. Тираж 100 экз.
Заказ.
Издательство Владимирского государственного университета.
600000, Владимир, ул.Горького, 87.