Критические режимы работы телекоммуникационной сети и алгоритмы маршрутизации
На правах рукописи
Тухтамирзаев Адхам Юлбарсмирзаевич КРИТИЧЕСКИЕ РЕЖИМЫ РАБОТЫ ТЕЛЕКОММУНИКАЦИОННОЙ СЕТИ И АЛГОРИТМЫ МАРШРУТИЗАЦИИ Специальность 05.12.13 — Системы, сети и устройства телекоммуникаций
Автореферат диссертации на соискание ученой степени кандидата технических наук
Владимир — 2012
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых» (ВлГУ).
Научный консультант: доктор физико-математических наук, профессор, заведующий кафедрой «Алгебра и геометрия» ВлГУ, Дубровин Николай Иванович
Официальные оппоненты: доктор технических наук, профессор, заместитель директора ФГАУ ГНИИ ИТТ «Информика» Скуратов Алексей Константинович кандидат технических наук, доцент кафедры «Управление и информатика в технических и экономических системах» ВлГУ Дерябин Вячеслав Михайлович
Ведущая организация: ФГБОУ ВПО «Ивановский государственный энергетический университет»
Защита состоится 28 декабря 2012 года в 16 00 часов в ауд. 301-3 на заседании диссертационного совета Д 212.025.04 Владимирского государственного университета имени Александра Григорьевича и Николая Григорьевича Столетовых по адресу: 600000, Владимир, ул.
Горького, 87, ВлГУ, ФРЭМТ.
Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 600000, Владимир, ул. Горького, 87, ВлГУ, ФРЭМТ.
С диссертацией можно ознакомиться в научной библиотеке Владимирского государственного университета имени Александра Григорьевича и Николая Григорьевича Столетовых.
Автореферат разослан « 23 » ноября 2012 г.
Ученый секретарь диссертационного совета доктор технических наук, профессор А.Г. Самойлов –3–
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Наблюдаемый в последнее время повышенный интерес к беспроводным вычислительным сетям использующих радио или инфракрасные каналы привело к тому, что такие технологии передачи данных стали одним из наиболее быстро прогрессирующих направлений телекоммуникационного рынка. Таким образом, они начали постепенно вытеснять проводные сети как региональные, так и локальные. При этом одним из наиболее востребованных сегодня направлений является использование т.н. сетей MANET (Mobile Ad Hoc Network, мобильная сеть для изменяющихся ситуаций). Это самостоятельно адаптирующаяся беспроводная сеть для динамически изменяющихся ситуаций, и сеть, обладающая возможностью автоконфигурации мобильных маршрутизаторов (и связанных хостов), использующая в работе соединения по радиоканалу, объединенные в топологию произвольной формы. Они позволяют создавать децентрализованные телекоммуникационные сети произвольной топологии с элементами искусственного интеллекта. Сети MANET не используют фиксированную инфраструктуру и выбирают оптимальный маршрут для передачи трафика в условиях меняющейся конфигурации, благодаря чему их надежность очень высока. Алгоритмы, разработанные специально для решения этой задачи, получили название алгоритмов маршрутизации. Под маршрутизацией понимаем процесс определения в коммуникационной сети пути, по которому вызов, либо блок данных может достигнуть адресата. В процессе работы с такими сетями мобильные маршрутизаторы автоматически настраиваются на доступные ресурсы. Модули сети анализируют структуру трафика и адаптируют топологию системы под текущие нужды. С их помощью можно обеспечить движущуюся наземную и воздушную технику средствами связи дальнего радиуса действия, динамически подключать старые радиокомплексы. Узлы MANET самостоятельно объединяются в сеть, как только включается их питание. Кроме того, пользователи смогут динамически настраивать ширину канала связи, дальность действия сети и зону покрытия.
Проектируемые виртуальные сообщества призваны решать проблемы, возникающие в масштабных операциях спасения и восстановления после крупных бедствий, в ходе военных действий. Предназначены для создания сенсорных сетей (распределенных самоконфигурируемых беспроводных сетей, состоящих из малогабаритных интеллектуальных сенсорных устройств), резервных систем связи и для многих других областей.
В отличие от классических проводных телекоммуникационных сетей, где топология изменяется очень редко, маршрутизация в мобильных сетях –4– имеет свои трудности. Неустойчивая природа MANET не дает возможности применять «проверенные» способы поддержки маршрутной информации, сводя их эффективность к нулю. Так как, маршрутизация является основой функционирования всей сети и должна работать максимально надежно, с самого зарождения MANET начались активные поиски новых, специализированных алгоритмов маршрутизации. Такие алгоритмы должны обладать на порядок большей интеллектуальностью, а подчас и просто основываться на кардинально иных принципах работы. На сегодняшний день актуальным считается проблема создания эффективных методов маршрутизации в сетях MANET.
Объектом исследования данной работы являются высокодинамичные сети передачи данных – мобильные и сенсорные сети, в которых изменение топологии происходит с большой интенсивностью.
Предметом исследования являются алгоритмы маршрутизации для высокодинамичныx сетей с переменной топологией.
Целью данной работы является повышение адаптивности и устойчивости работы алгоритмов маршрутизации в критических режимах функционирования сетей с переменной топологией.
Реализация этой цели выполняется решением следующих задач:
– изучение и анализ условий целевой среды и специализированных алгоритмов маршрутизации;
– выявление критических режимов функционирования целевых сетей;
– формализация модели функционирования каналов передачи данных в сетевой среде;
– обнаружение проблемных параметров, препятствующих эффективному решению задачи маршрутизации в критических режимах функционирования;
– выработка предложений для совершенствования алгоритмов маршрутизации;
– программная реализация и экспериментальное обоснование выдвинутых предложений.
Методы исследования. Для получения достоверных результатов в работе были применены методы теории множеств, теории графов, теории вероятности, математической статистики, теории алгоритмов. Все результаты были подтверждены имитационным моделированием, которое осуществлялось на высокопроизводительном кластере.
Научная новизна 1. Разработана математическая модель структурных особенностей сети для специфического класса телекоммуникационных сетей с ограниченной мобильностью.
–5– 2. На основе разработанной модели создан принципиально новый гибридный проактивно-реактивный алгоритм маршрутизации для сетей с ограниченной мобильностью, работоспособность и эффективность которого подтверждена численными экспериментами.
Практическая значимость работы состоит в непосредственной пригодности разработанных алгоритмов для использования в управляющем программном обеспечении узлов, специализированных ограниченно мобильных беспроводных телекоммуникационных сетей с отключаемыми узлами с целью эффективного использования их ресурсов. Создан прототип программного обеспечения для узлов стационарной беспроводной сети, позволяющий улучшить работу сети в случае приобретения узлами локальной мобильности.
Наиболее перспективным видится применение разработанных алгоритмов в зарождающихся сенсорных сетях с подвижными узлами, практическое внедрение которых в различные сферы жизнедеятельности ожидается в ближайшее время.
Кроме того, непосредственное применение предложенных алгоритмов возможно практически в любых мобильных сетях телекоммуникации, действующих на ограниченной территории, например, в сетевом оборудовании офисных зданий.
Реализация и внедрение результатов Исследования и практические разработки, выполненные в диссертационной работе, являются частью научно-исследовательских работ, выполненных при участии автора в рамках научно-технических программ, выполняемых по заданию министерства образования и науки Российской Федерации.
Результаты исследований были внедрены в следующих организациях:
Владимирский государственный университет.
ООО "ИНРЭКО ЛАН ФИРМА".
Личный вклад автора Выносимые на защиту положения предложены и реализованы автором в ходе выполнения научно-исследовательских работ. Практическая реализация методов и моделирование на ЭВМ проводились при личном участии автора коллективом исследователей.
Достоверность полученных результатов подтверждается полнотой и корректностью теоретических обоснований и результатами проведенных экспериментов.
Апробация работы Основные результаты работы докладывались и экспонировались на следующих научно-технических совещаниях и конференциях:
–6– Научно-практическая конференция «Перспективы развития телекоммуникационных систем и информационные технологии», Санкт Петербург, 2009г.
XVII Международная конференция «Математика. Образование», Чебоксары, 24–31 мая 2009 г.
II Всероссийская научно-практическая конференция «Инновации и информационные технологии в образовании», Липецк, 2009 г.
XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г.
Девятая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах", Владимир, 2 3.11.2009 г.
На защиту выносятся следующие положения:
Метод, позволяющий использовать структурные особенности мобильной телекоммуникационной сети – характер движения или смены состояний узлов, либо их групп – в целях повышения эффективности маршрутизации трафика.
Математическая модель структурных особенностей сети.
Алгоритм маршрутизации с использованием структурных особенностей на основе статических таблиц.
Публикации Основные результаты работы представлены в 10 публикациях, в том числе в 2 статьях журналов из перечня ВАК, а также в научно-технических отчетах НИР, выполненных по заданию Рособразования и Роснауки.
Объем и структура диссертации Текст диссертационной работы изложен на 120 стр. машинописного текста. Содержательная часть включает введение, четыре главы и заключение. Список использованных источников содержит 68 наименований.
Таблиц 3, рисунков 32.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертационной работы, сформулированы цели и задачи исследований, научная новизна и их практическая ценность, а также приводится краткое содержание по главам.
В первой главе проведено исследование существующего положения дел в предметной области диссертационной работы. Рассмотрены основные типы и особенности маршрутизирующих алгоритмов в телекоммуникационных сетях с переменной топологией (в частности, в сенсорных сетях). Особое внимание уделено специфическим характеристикам этих алгоритмов, обусловленным типичными аппаратными возможностями узлов в таких сетях телекоммуникации.
–7– Проанализированы и обоснованы проблемные режимы функционирования сетей, приводящие к неэффективному применению существующих стратегий маршрутизации. Такие «критические» режимы характеризуются высокой интенсивностью смены топологии, существенно превышающей интенсивность полезного трафика.
Проведен обзор ряда методов, предложенных в предшествующих работах и специально предназначенных для подобного рода критических режимов. Данные методы позволяют значительно улучшить показатели служебных затрат на маршрутизацию, однако требуют для корректного функционирования разработки ряда дополнительных служебных механизмов. К таковым, в частности, относится способ быстрого и точного прогнозирования состояния связи (периодов активности) между узлами телекоммуникационной сети.
Вторая глава носит теоретический характер. Задача «огрубления» в ней ставится в чисто математической постановке. По непрерывной случайной величине требуется построить некоторую дискретную случайную величину - «огрубление»;
при этом, количество её значений невелико и заранее обговорено. Дискретная случайная величина и определяет «шкалу» или разбиение диапазона изменения исходной случайной величины на классы.
Пусть – натуральное число. - огрублением случайных величин назовем алгоритм, в силу которого случайной величине, принимающая значения на отрезке [ ] с функцией распределения ( ) ставится в соответствие дискретная случайная величина ( ) принимающая возможных значений (назовем эту последовательность шкалой). Шкала есть функция алгоритма и случайной величины, но она не завит от конкретных реализаций случайной величины Чаще всего алгоритм выбирается так, чтобы обеспечить минимальное отличие от ( ) в смысле некоторого заданного критерия отличия. Выбирается число -- степень огрубления («число уровней») и число - точность. Перебираем наборы из точек. Считаем а также считаем Вводится p-критерии оптимальности. Считается, что «огрубление» оптимально, если расстояние, между функциями распределения исходной и дискретной случайных величин, минимально в метрике.
() Для заданного сформулируем критерий | () ( )|, ( ) – функция распределения случайной величины ( ).
где Случай критерия.
() () () ( ).
–8– Словесно, этот критерий означает, что надо стремиться минимизировать каждый из отрезков на вертикальной оси, на которые горизонтальные пунктирные прямые разбивают единичный квадрат (см. рис. 1.).
F(x) F(a3) F(a2) F(a1) 0 q1 a1 q2 a2 q3 a3 q4 1 x ( ) при Рис. 1. Графическое представление критерия.
Случай критерия.
( [ ( ) ( )] [ ( ) ( )] ) Иными словами, мы минимизируем суммарную площадь заштрихованных криволинейных треугольников.
Случай критерия.
( [ ( ) ( )] [ ( ) ( )] ) В общем случае оптимизация достигается итерационным методом.
–9– Был построен алгоритм огрубления методом итераций:
( ) на [ ] 1 Задаем функцию распределения ( ) на [ ] 2 Задаем обратную функцию 3 Задаем натуральное число Задаем массивы [ ]и [ ] Полагаем [ ] Задаем начальный отрезок [ ] для [ ] (можно, ) Начало итераций: пока [ ] не станет 1 с заданной точностью выполнять следующее [] ( ) (*) Цикл по от 1 до [] ( [ ]) ([ ])) ( Если [ ] [ ] и возврат к, то началу итераций(*) Иначе [ ] [] [ ] Конец если Если [ ] [ ] и возврат к, то началу итераций ( ). Конец если Конец цикла Считаем [ ] ( [ ]) ([ ])) ( Если [ ] [ ], Конец если Если [ ] [] Иначе стоп, выход из итераций, Конец если Возврат к началу итераций ( ) полученные в итоге итераций массивы [ ] и [ ] 8 Результат () ( [ ]), 9 Огрубленная функция распределения если [ ] [] – 10 – На языке программирования Visual Basic этот алгоритм можно оформить в виде следующей программы:
Sub Rouf() Const Dim ( ) As Single Dim ( ) As Single Dim, As Single Const () : :
(( ) ) Do Until () ( ) Line1:
To – For () ( ( )) (( ))) ( If ( ) Then ( ): GoTo Line Else ( ) () () End If If ( ) ( ): GoTo Line Then Next () ( ( )) (( ))) ( If ( ) () Then If ( ) () Then Loop Cells ( ).Value = ( ) End Sub Function ( As Single) As Single End Function Function ( As Single) As Single () End Function Подсчитаны огрубления для следующих функций,,, ( ),, ( ),,. Для некоторых специальных распределений получены аналитические методы огрубления.
– 11 – Предложена, без моделирования сетевого взаимодействия, методика использования «огрубления» применительно к рассматриваемой в диссертации задаче:
В текущем режиме узел наблюдает окрестность и выделяет связи, которые должны участвовать в формировании маршрутных таблиц, вычисляет их параметры, в частности, «основной параметр связи» вероятность её активности.
В итоге предполагается, что каждый узел содержит информацию, достаточно общего характера, о сети в целом – интегральную функцию распределения «основного параметра» по выделенным связям. Эта информация накапливается в результате некоторого периода наблюдений в сети, путем обмена между узлами.
Обладая такой информацией, каждый узел сам способен рассчитать оптимальную «шкалу» и определить класс связей. После чего снова происходит обмен информацией между узлами, в результате чего и формируются таблицы.
Считается, что коррекция таблиц, если в этом возникает необходимость, происходит одним из стандартных методов.
В третьей главе рассмотрены вопросы, связанные с работой реактивных алгоритмов в телекоммуникационной сети с экстремальным характером изменения топологии, то есть сети телекоммуникации, характеризующиеся большой степенью интенсивности смены состояния связей (активная – неактивная). Реактивный поиск маршрутов в подобной ситуации, сталкивается с высоким уровнем отказов построенных маршрутов.
В итоге возникает большой объем накладных расходов на маршрутизацию трафика, сопоставимый с расходами на полную лавину. Предлагается сократить эти расходы, воспользовавшись дополнительно некоторым специальным алгоритмом (проактивного типа), использующим такие данные о связях, которые изменяются относительно медленно. Этот алгоритм должен обладать следующими свойствами:
1. Доведение до адресата, носит вероятностный характер (то есть пакет может и не достигнуть адресата) В этом, аварийном, случае применяется дополнительный метод доведения, например, базовый реактивный алгоритм или просто лавина и.т.д.
2. Он должен быть построен на других (по сравнению с базовыми проактивными и реактивными алгоритмами) принципах. Например, если он использует маршрутную таблицу, она должна быть:
a) статична;
b) корректироваться не напрямую от изменения топологии сети (существенно реже).
– 12 – Дополнительные алгоритмы мы собираемся строить на основе информации о «структурных особенностях сети». То есть изначально ясно, что предлагаемые нами алгоритмы будут носить не универсальный характер.
Тем не менее, в достаточно большом списке приложений их использование приведет к существенному улучшению функционирования телекоммуникационной сети.
«Структурные особенности сети» - это достаточно широкое понятие, но мы будем использовать его в двух следующих смыслах:
1. «Структурные особенности сети» - информация о положении или движении узлов сети.
2. «Структурные особенности сети» - информация о характере переключении связи между узлами.
Конкретизируя понятие «структурные особенности сети», мы получаем возможность перейти к задаче «формализации» некоторых классов сетей, которые естественным образом не только решают проблему «расплывчатости» (и невыполнимости) требований к маршрутизирующим алгоритмам, определяя наиболее значимые их качества, но и (что гораздо важнее) позволяют указать способы и методы создания таких алгоритмов наиболее эффективным образом.
Кроме того, мы сузим круг наших исследований по характеру получения информации.
1. «Структурные особенности сети» - как информация о положении или движении узлов сети (чаще всего приблизительная).
Предполагается, что она известна априорно и на её основании могут быть построены специальные маршрутные таблицы, которые предоставляются узлам перед началом функционирования сети.
2. «Структурные особенности сети» - информация о характере переключении связи между узлами. Эта информация получается динамическим путем в результате наблюдения и обработки статистики переключения некоторых специально выделенных связей (то есть не является априорной).
Подобная информация не может быть получена точно. Целью экспериментов как раз и является изучение вопросов чувствительности алгоритма маршрутизации к неточностям статистической информации.
Предложен подход имитационного моделирования мобильных телекоммуникационных сетей, основанный на применении параллельного сетевого симулятора (ПСС). Это комплекс программ для моделирования сетей, представляющий собой консольное ядро с подключаемыми модулями расширения.
– 13 – Основной особенностью ПСС, являющейся залогом его высокой универсальности, является обеспечение расширяемости симулятора за счёт унифицированной архитектуры модулей расширения. Это в частности позволяет минимизировать время, необходимое на разработку и реализацию на основе данного симулятора специализированных систем симуляции для проведения различных экспериментов. В частности, добавление и изменение состава используемых модулей расширения не потребует перекомпиляции ядра симулятора.
В архитектуре ПСС собственно симулятор представляет собой базовый элемент, обеспечивающий сервисные функции (транспортировку пакетов между узлами, сохранение статистики), а вся остальная функциональность реализована с помощью подключаемых модулей (модулей расширения), имеющих унифицированный интерфейс. Графическая иллюстрация данной концепции приведена на Рис..
Модуль расширения (сборщик статистики) Модуль Модуль расширения 2 расширения (генератор (генератор топологии) трафика) Модуль Модуль Ядро расширения 1 расширения (протокол (модификатор симулятора маршрутизации) состояния узла) Рис. 2. Модульная архитектура ПСС.
При этом возможно подключение к ПСС произвольного количества модулей расширения различных типов. Все они получают управление по очереди и им передаются данные для обработки.
При необходимости один модуль расширения может выполнять функции модулей нескольких типов, в этом случае получается комбинированный модуль расширения.
Модули расширения ПСС представляют собой динамически подключаемые библиотеки операционной системы семейства UNIX (файлы с префиксом lib и расширением имени so). Благодаря гибкой модульной – 14 – архитектуре ПСС модули независимы, имеют единую структуру, могут общаться друг с другом, изменяя расширяемые свойства структуры, представляющей узел (PeerState).
Все модули работают над единой структурой буферов входных и выходных пакетов, что означает: любой пакет, который не обработан одним из модулей, может быть обработан последующими.
Поэтому структура вызовов модулей логически должна быть примерно такой:
1. Генерирование топологии (однократно).
2. Модификация топологии.
3. Генерирование трафика.
4. Последовательность модулей маршрутизации. Если маршрутизация по одному из них невозможна, то пакет оставляется в буфере и подхватывается следующим модулем. Если вся последовательность модулей не переместила пакет в буфер выходящих пакетов, то он уничтожается ПСС. Пакет возможно оставить на узле, для чего необходимо выполнить посылку его самому себе.
Для проведения экспериментов использованы и сконфигурированы все необходимые для моделирования сетевого взаимодействия модули.
Модуль генерирования топологии Для каждого узла сети заполняет его список смежности таким образом, что бы минимальное число соседей по всей сети было равно, ( ).
максимальное –, среднее – Модуль изменений топологии Для каждой связи осуществляет процесс переключение согласно процессу «обобщенная телеграфная волна» с интенсивностью и вероятностью активности, создавая таким образом, динамическую топологию. Параметр процесса f разыгрывается случайно для каждой связи и является случайной величиной со степенным распределением (показатель ), параметр одинаков для всех связей.
Модуль классификации связей Осуществляет классификацию связей по равномерному или степенному алгоритму с M уровнями.
Модуль генерирования таблиц Создание на каждом узле таблиц (проактивной) маршрутизации на основе метрики d0 или d1. В последнем случае используются «огрубленные» величины (т.е. результаты классификации).
– 15 – Модуль генерирования трафика Имитирует возникновение в сети пользовательских пакетов, которые необходимо доставить от одного узла к другому. Пакет генерируется с заданной вероятностью p на каждом шаге моделирования. Узел-получатель – любой случайный несмежный с данным узел сети.
Модуль проактивной маршрутизации Извлекает пакеты из буфера входящих пакетов, анализирует их и принимает решение о передаче (на основе таблиц маршрутизации) Модуль реактивной процедуры поиска маршрута Имитирует реактивную процедуру поиска маршрута (дистанционно векторный алгоритм AODV без кеширования).
Модуль лавинной рассылки Моделирует лавинную рассылку: копирует и рассылает пакеты из буфера входящих пакетов всем активным смежным узлам.
В четвертой главе был проведен анализ результатов, полученных с помощью имитационной модели телекоммуникационной сети, параметры которой были подобраны таким образом, что бы можно было говорить о наличии экстремальной топологии (а именно: имела место высокая доля неактуальных маршрутов полученных с помощью AODV).
Доля особых ситуаций для AODV:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, успех RREQ успех RREP успех доставки Рис. 3. Доля особых ситуаций алгоритма AODV в зависимости от интенсивности изменения состояния связи.
RREQ («route request») – пакет запроса маршрута.
RREP («route reply») – пакет с сообщением-ответом.
– 16 – Доля доставленных проактивной компонентой пакетов:
0, 0, 0, 0, 0, 0, 0,3 0,4 0,5 0,6 0, лавина гибридный по d1 гибридный по d Рис. 4. Доля доставленных проактивной компонентой пакетов в зависимости от интенсивности.
Доля доставленных проактивной компонентой пакетов 0, 0, 0, 0, 0, 4 5 6 7 8 гибридный по d1 гибридный по d Рис. 5. Доля доставленных проактивной компонентой пакетов в зависимости от – числа соседей узла.
{ – естественная метрика.
( ) – вероятностная метрика, – вероятность активности связи.
– 17 – Влияние классификации связей на долю пакетов, доставляемых с помощью проактивной компоненты в зависимости от числа уровней и параметра надежности связей. Рассматривается случай отсутствия классификации, равномерная и согласованная (степенная) классификации.
Доля доставленных проактивной компонентой пакетов 0, 0, 0, 0, 0, 0, 0, 0, 1 2 3 4 5 6 7 8 9 без классификации M-равномерная Рис. 6. Доля доставленных проактивной компонентой пакетов в ( ).
зависимости от параметра надежности связи 0, 0, 0, 0, 0, 0, 0, 0, 0, 12345 6 7 8 9 без классификации M-равномерная степенная с p=2. Рис. 7. Доля доставленных проактивной компонентой пакетов в ( ).
зависимости от параметра надежности связи – 18 – 0, 0, 0, 0, 0, 0, 1 2 3 4 5 6 7 8 9 без классификации M-равномерная степенная с p=3. Рис. 8. Доля доставленных проактивной компонентой пакетов в ( ).
зависимости от параметра надежности связи Основной результат: введение классификации связей с относительно небольшим и приемлемым на практике числе уровней сказывается на результатах маршрутизации незначительным образом. Конкретно: уже в случае десяти уровней различие между маршрутизаций с равномерной классификацией и идеальной маршрутизаций, выраженное в доле доставленных пакетов, составляют не более 4-5%. Согласованная шкала дает лучшие результаты в области малого числа уровней (от 4 до 10), однако согласованная шкала требует наличия некоторых априорных знаний о распределении связей.
Как показывают эксперименты, предложенная во второй главе вероятностная маршрутизация (проактивно-реактивный алгоритм, основанный на статистической информации), успешно справляется с задачей обеспечения большой доли трафика по постоянным таблицам. В зависимости от параметров сети от 45% дл 75% трафика можно направлять по таблицам, построенным по метрике и от 25% до 40% по таблицам, построенным по метрике. Полученные результаты демонстрирует главную сильную сторону подхода: простым наблюдением за статистикой связи можно добиться существенной выгоды при маршрутизации. Еще раз подчеркнем тот факт, что проактивная часть в комбинации алгоритмов носит опциональный характер.
В заключении представлены основные результаты и выводы.
1. Предложена методика разбиения диапазона изменения «основного параметра связи» на классы, по различным критериям. В – 19 – предположении, что известно распределение значений «основного параметра», по совокупности связей, строится оптимальное, в смысле выбранного критерия, разбиение. Для некоторых классов распределений получены аналитические оценки таких разбиений.
2. Создан испытательный стенд для численных расчетов, представляющий собой компьютерную имитационную модель, реализованную с помощью стороннего параллельного сетевого симулятора.
3. Численным экспериментом подтверждается обоснованность предлагаемого подхода – «разбиение на классы». А именно:
a) вероятностный подход (т.е. использование статистики вероятности активности связи) действительно позволяет улучшить такие характеристики маршрутизации, как надежность и время доставки пакетов. Таким образом, исследование проблемы огрубления статистики оправдано;
b) введение классификации связей (огрубление) с относительно небольшим и приемлемым на практике числе уровней сказывается на результатах маршрутизации незначительным образом.
СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Милованов, Д.С. Проблемы маршрутизации в сети с быстро меняющейся топологией / Д.С.Милованов, А.Ю. Тухтамирзаев, П.Ю. Шамин // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. – 2009. – № 1. – С. 28 – 32.
2. Аракелян, С.М. Об организации интеллектуальной маршрутизации в сети с динамической топологией с использованием статистических характеристик связей / С.М. Аракелян, Д.С. Милованов, В.Г. Прокошев, А.Ю. Тухтамирзаев, П.Ю. Шамин // Информатизация образования и науки. -2010. -№ 5. -С. 43-55.
3. Тухтамирзаев, А.Ю. Прогнозирование вероятности активности связи /А.Ю.Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г. – С.
384-387.
4. Тухтамирзаев, А.Ю. Огрубление случайных величин его применение в сетях передачи данных / А.Ю. Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г. – С. 381-384.
5. Аракелян, С.М. Некоторые вопросы оценки качества связей в сетях с переменной топологией / С.М. Аракелян, В.Г. Прокошев, М.Ю. Звягин, Д.С. Милованов, А.Ю. Тухтамирзаев // II Всероссийской научно практической конференции «Инновации и информационные технологии в образовании», Липецк, 2009. – С. 140-144.
– 20 – 6. Дубровин, Н.И. Огрубление распределения нагрузки в сетях передачи данных / Н.И. Дубровин, А.Ю. Тухтамирзаев // XVII Международная конференция «Математика. Образование», Чебоксары, 2009. – С. 257.
7. Дубровин, Н.И. Оценка минимального сечения взвешенного графа / Н.И. Дубровин, А.Ю. Тухтамирзаев // Девятая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах", Владимир, 2-3.11.2009 г. – С. 155 158.
8. Дубровин, Н.И. Связность коммуникационных сетей с переменной топологией / Н.И. Дубровин, А.Ю. Тухтамирзаев // II Всероссийской научно-практической конференции «Инновации и информационные технологии в образовании», Липецк, 2009. – С. 170-173.
9. Дубровин, Н.И. Дублирование информации при передаче по широкополостному каналу / Н.И. Дубровин, Т.В. Дубровина, А.Ю. Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г. – С. 257-260.
10. Милованов, Д.С. Вопросы маршрутизации в сети с быстро изменяющейся топологией на основе её статистических характеристик / Д.С. Милованов, А.Ю. Тухтамирзаев, П.Ю. Шамин // Перспективы развития телекоммуникационных систем и информационные технологии: тр.
междунар. конф. – СПб, 2008. – С. 23 – 33. – ISBN 978-5-7422-2141-8.
Подписано в печать 22.11.2012.
Формат 6084/16.
Усл. печ. л. 1,16. Тираж 100 экз.
Заказ Издательство Владимирского государственного университета.
600000, Владимир, ул. Горького, 87.