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

• Автор: Зайнуллина, Эльмира Шаукатовна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Казань
• Количество страниц: 119 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. ЗАДАЧА МАРШРУТИЗАЦИИ ДАННЫХ ИЗ

УДАЛЕННЫХ УЗЛОВ В ЦЕНТРАЛЬНЫЙ УЗЕЛ ИНФОРМАЦИОННОЙ СИСТЕМЫ

1.1. Постановка задачи.

1.2. Анализ технологии маршрутизации данных

1.3. Анализ алгоритмов маршрутизации данных

Выводы

ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ

ОПТИМИЗАЦИИ МАРШРУТА ТРАНСПОРТИРОВКИ ДАННЫХ

2.1. Анализ задач, связанных с нахождением оптимального маршрута.

2.2. Математические модели задачи транспортировки данных
2.2.1. Дискретная модель задачи.
2.2.2. Нейросетевая модель задачи
2.2.2.1. Общий вид нейросетевой модели Хопфилда.
.2.2. Нейросетевая модель Хопфилда для исходной задачи.
2.2.2.З. Нейросетевой метод и алгоритм решения
Выводы
ГЛАВА 3. МЕТОД УЛУЧШЕНИЯ СХОДИМОСТИ НЕЙРОСЕТИ К ДОПУСТИМЫМ СОСТОЯНИЯМ.
3.1. Экспериментальный анализ влияния коэффициентов штрафных членов функции энергии на сходимостьнейронной сети.
3.2. Достаточное условие устойчивости допустимых состояний
3.3. Метод и алгоритм вычисления коэффициентов штрафных функций для задачи транспортировки данных
3.4. Примеры решения задачи
Выводы
ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЙ АНАЛИЗ НЕЙРОСЕТЕВОГО
МЕТОДА
4.1. Исследование законов, описывающих динамику сети.
4.1.1. Модели динамики функционирования сети Хопфилда
4.1.2. Сравнение функционирования сети с синхронной и асинхронной динамикой.
4.2. Исследование влияния начальных состояний сети на решение задачи
4.3. Сравнение решений задачи транспортировки данных методом
ветвей и границ и нейросетевым методом.
Выводы
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


Туполевские чтения» (Казань, ) [], XVI Международная научно-техническая конференция: «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, ) [], VIII Международная научно-практическая конференция «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» (Москва, ) [], IV Общероссийская конференция с международным участием «Новейшие технологические решения и оборудование» (Москва, ) [], Всероссийская научная конференция студентов и аспирантов. Вологда, ) []; XV Международная молодежная научная конференция «Туполевские чтения» (Казань, ) [, ]. Публикации. По теме диссертации опубликовано 8 научных работ, включая 2 статьи и 6 тезисов докладов. Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка и двух приложений. Работа содержит 9 страниц машинописного текста, рисунок и таблицы. Список литературы включает наименований. Содержание работы. Первая глава посвящена постановке задачи, анализу технологий и алгоритмов маршрутизации данных в компьютерных сетях. Рассматривается корпоративная распределенная информационная система, в которой имеется узел, являющийся центром обработки информации, и удаленные узлы, данные из которых должны быть переданы в центральный узел для обработки. В процессе передачи информации из удаленных узлов в центральный узел может выйти из строя канал, соединяющий удаленный узел с центром, поэтому объем данных, находящийся в этом узле, необходимо передать в центр через другие удаленные узлы. Процесс маршрутизации в сети обобщенно можно представить следующим образом. Необходимо передать пакет данных из одной вычислительной машины — «источника» в другую — «пункт назначения». Передача информации от источника к пункту назначения осуществляется с помощью транзитных сетевых устройств - маршрутизаторов. Каждое сетевое устройство (компьютер или маршрутизатор) имеет свою таблицу маршрутизации, в которой содержится информация о возможных направлениях дальнейшей передачи пакета информации. Процесс передачи пакета от одного сетевого устройства другому состоит из двух частей: определение сетевого IP-адреса устройства, для. Преобразование IP-адресов в физические осуществляется с помощью протокола разрешения адресов ARP (Address Resolution Protocol). Для этого просматривается специальная ARP-таблица узла отправителя. Если физический адрес в ARP-таблице найден, то пакет передается по этому адресу [,]. Основным назначением маршрутизатора является выбор маршрута следования пакета и организация физической его передачи. В работе был осуществлен анализ алгоритмов маршрутизации, которые были классифицированы в соответствии со следующими критериями: по способу заполнения таблиц маршрутизации можно выделить статические и динамические алгоритмы; по виду процесса передачи пакета -одномаршрутные и многомаршрутные; но виду архитектуры сети -одноуровневые или иерархические; по методу вычисления маршрута -алгоритмы с поузловым или полным вычислением маршрута; в соответствии с используемым протоколом — внутридоменные и междоменные; по виду алгоритма поиска пути - алгоритм состояния канала или вектора расстояний [, ,,,, ]. В статических алгоритмах маршрутизации маршрут от отправителя к адресату фиксирован, в динамических алгоритмах маршрут может изменяться в зависимости от состояния сети [5, 7]. Многомаршрутные алгоритмы маршрутизации обеспечивают несколько маршрутов к одному и тому же пункту назначения [, 7]. Алгоритмы одноуровневой организации предполагают равенство всех маршрутизаторов по отношению друг к другу []. При использовании алгоритмов иерархической организации маршрутизаторы, разделяются- по* уровням. Алгоритмы с поузловым вычислением маршрута предполагают в каждом узле вычисление очередного узла маршрута. Алгоритмы с полным вычислением маршрута определяют весь маршрут полностью []. Внутридоменные алгоритмы маршрутизации действуют только в пределах доменов, междоменные - как в пределах доменов, так и между ними. Алгоритм состояния канала определяет кратчайшие маршруты с помощью алгоритма Дейкстры []. В основе алгоритма маршрутизации по вектору расстояний лежит алгоритм Беллмана-Форда или Форда-Фалкерсона [].