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

• Автор: Кринкин, Кирилл Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Санкт-Петербург
• Количество страниц: 147 с.

СОДЕРЖАНИЕ

1 МЕТОДЫ МАРШРУТИЗАЦИИ В КОМПЬЮТЕРНЫХ СЕТЯХ

1.1 Классификация методов маршрутизации

1.1.1 Основные принципы маршрутизации.

1.1.2 Статические алгоритмы.

1.1.3 Динамические алгоритмы

1.2 Глобальная и локальная оптимизация.

1.2.1 Алгоритмы на основе БРР

1.2.2 Локальная оптимизация.

1.3 Выводы.

2 ИСТОЧНИКИ ОШИБОК И МЕТОДЫ ИХ УСТРАНЕНИЯ В СИСТЕМАХ ПЕРЕДАЧИ ДАННЫХ

2.1 Виды неопределенностей в системах передачи данных . .
2.2 Методы устранения неопределенности
2.3 Использование локальной оптимизации
2.4 Уменьшение сложности системы.
3 МАРШРУТИЗАЦИЯ В УСЛОВИЯХ НЕПОЛНЫХ ДАННЫХ
3.1 Модель динамической компьютерной сети
3.1.1 Маршрутизация в сети с постоянной структурой .
3.1.2 Маршрутизация в сети с динамической структурой
3.1.3 Область эффективной маршрутизации .
3.1.4 Маршрутные записи.
3.1.5 Факторы, влияющие на выбор маршрутов
3.1.6 Учет загрузки сетевых компонентов.
3.1.7 Оценка динамики Яг
3.1.8 Формирование внешних маршрутных записей .
3.1.9 Оценка эффективности маршрутизатора
3.1. Локальный выбор маршрутов
3.2 Алгоритмы маршрутизации в условиях
неполных данных
3.2.1 Функционирование маршрутизаторов.
3.2.2 Построение Л г, .
3.2.3 Проверка состояния Лг.
3.2.4 Обновление при отказе
3.2.5 Синхронизация времени .
3.2.6 Обновление внешних маршрутных данных
3.2.7 Подготовка к сбросу
3.2.8 Процедура передачи данных
3.2.9 Объем служебного трафика
3.3 Выводы.
4 КАЧЕСТВО МАРШРУТОВ И ОБЪЕМ СЛУЖЕБНОГО
ТРАФИКА
4.1 Задача оценки качества маршрутов.
4.1.1 Функция качества маршрутов.
4.1.2 Область значений Л .
4.1.3 Выбор параметров Л
4.2 Объем служебного трафика.
4.2.1 Объем служебного трафика при лавинной адресации
4.2.2 Объем служебного трафика при маршрутизации
с использованием неполных данных
4.2.3 Сравнение объемов служебного трафика
при различных методах маршрутизации
4.3 Снижение качества путей при отказах
4.3.1 Выбор маршрутов
4.3.2 Распространение обновлений.
4.3.3 Область эффективной маршрутизации
как передающий элемент
4.4 Выводы
5 МОДЕЛИРОВАНИЕ И СРАВНЕНИЕ АЛГОРИТМОВ
5.1 Выбор имитационной модели
5.1.1 Структура имитационной модели .
5.1.2 Выбор оцениваемых параметров.
5.2 Моделирование алгоритмов маршрутизации.
5.2.1 Сеть с постоянными характеристиками
5.2.2 Динамическая сеть с отказами.
5.2.3 Объем служебного трафика и размеры ОЭМ
5.2.4 Оценка качества путей
5.3 Выводы.
Литература


На основе анализа поставленной задачи делаются рекомендации по выбору значения в различных условиях. Анализируются общие объемы служебного трафика и приводится практический пример расчета. В заключение, рассматриваются вопросы распространения информации при использовании предложенного алгоритма маршрутизации с целью обозначения путей для дальнейших исследований. В частности, предлагается подход к анализу функционирования областей эффективной маршрутизации как к передающим элементам с изменяемой пропускной способностью. В пятой главе описываются численные эксперименты для получения характеристик алгоритма маршрутизации на неполных данных. Обосновывается выбор имитационных моделей и средств для моделирования. Производится сравнение некоторых важных свойств построенного алгоритма с аналогичными свойста алгоритма на основе БРР. Описаны основные задачи и цель моделирования. Описан численный эксперимент. Опытным путем получены параметры функционирования алгоритма на узлах сети. На основе полученных данных сделаны выводы об их согласованности с теоретическими положениями, приведенным в четвертой главе. Определяется область использования разработанного алгоритма. В процессе работы над диссертацией, автор принимал участие в создании методической базы, для обеспечения учебного процесса по специальности [,,,-,1]. Сети и телекоммуникации", "Сети ЭВМ", "Сетевые технологии" для студентов специальностей "Программное обеспечение вычислительной техники и автоматизированных систем", "Прикладная математика" в СПбГЭТУ. В данной главе рассматриваются основные принципы маршрутизации, используемые в настоящее время для передачи информации в корпоративных сетях, производится их сравнительный анализ. Выявляются недостатки, используемых методов маршрутизации, а также предлагаются способы устранения этих недостатков. В настоящее время корпоративные вычислительные сети - одна из активно развивающихся областей. Рост внимания к распределенной обработке, хранению и предоставлению информации потребителям обусловлен изменением роли сетевых коммуникаций в производственном процессе. Помимо чисто производственных задач, современные сети являются основой для совершенно новых областей коммерческой деятельности. Мы наблюдаем тотальное внедрение сетевых технологий во все сферы производственной, коммерческой и другой деятельности, причем не вызывает сомнения тенденция к объединению всех создаваемых сетей в рамках единого информационного пространства, которым является Internet. Для интеграции множества различных составляющих необходимо прибегать к использованию технологий всех уровней организации сетей, начиная от локальных (Local Area Network, LAN), заканчивая глобаль-^ ными (Wide Area Network, WAN). Ее использование позволяет организовать группировку различных сетевых компонентов (узлов, каналов связи, маршрутизаторов, мостов и пр. Их называют подсетями или сегментами сети (в ряде источников [7,8] используется термин "сеть”, для их обозначения). Далее работе будут использоваться общепринятые термины, определенные в [,,]. Маршрутизацией называют механизм, позволяющий осуществлять передачу пользовательской информации между конечными системами, расположенными в различных сегментах сети. Основными требованиями, предъявляемыми к этому механизму, являются обеспечение связности выбираемого пути между источником сообщения и адресатом, а также удовлетворение некоторому критерию качества, называемому метрикой [,0]. Впервые, данная проблема в общем виде была сформулирована Веллманом в [4] в и в последствии развита Кантором (D. G. Cantor) и Гирла (М. Gerla), применительно к компьютерным сетям [8]. В механизмах маршрутизации необходимо уделять внимание следующим основным аспектам: способу представления информации о топологии сети, алгоритму поиска маршрута, оптимизации процесса передачи информации. Существует множество различных классификаций стратегий маршрутизации. Фульц (Fultz G. F.) и Клейнрок (Kleinrock L. Стохастическая предполагает лавинообразное заполнение сети сообщениями, которые всегда достигают адресата.