Метод уменьшения размера таблиц маршрутизации в IP-сетях

• Автор: Шиготаров, Андрей Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Ульяновск
• Количество страниц: 127 с.

Содержание
Содержание

Список сокращений

Введение

Глава 1. Обзор и анализ существующих методов уменьшения

размера таблиц маршрутизации

1.1. Маршрутизация, архитектура маршрутизаторов.

1.2. Обзор методов оптимизации поиска в таблицах маршрутизации

1.3. Методы уменьшения размера таблиц маршрутизации.

1.4. Методы минимизации булевых функций большой размерности

1.4.1 Классификация алгоритмов минимизации булевых функций

1.4.2 Алгоритмические сложности решения задачи минимизации ДНФ
1.4.3 Точные алгоритмы минимизации ДНФ
1.4.4 Приближенные алгоритмы
Глава 2. Разработка метода уменьшения таблиц
маршрутизации в 1Рсетях
2.1. Метод уменьшения размера таблиц маршрутизации.
2.2 Точный алгоритм минимизации булевых функций в классе ДНФ
2.2.1 Двоичные диаграммы решения
2.2.2 Генерация всех простых импликант булевой функции
2.2.3 Упрощение матрицы покрытия
2.2.4 Построение минимального покрытия
2.3 Приближенный алгоритм минимизации ДНФ
Глава 3. Компьютерное моделирование и экспериментальная оценка разработанного метода уменьшения таблиц
маршрутизации
3.1. Выбор средств разработки программного пакета
3.2 Программная реализация разработанного метода уменьшения таблиц
маршрутизации.
3.2.2 Описание программного продукта
3.3 Применение разработанных методов минимизации ДНФ.дляуменьшения размера таблиц маршрутизации
3.4. Оценка зависимости производительности маршрутизатора от размера
таблицы маршрутизации.
3.5 Экспериментальная оценка эффективности предложенных алгоритмов
для задач из набора
Заключение
Список литературы


Разработан точный алгоритм построения минимальной дизъюнктивной нормальной формы булевых функций, соответствующих множествам записей таблицы маршрутизации, основанный на использовании двоичных диаграмм решения и метода ветвей и границ, отличающийся более высокой скоростью работы, по сравнению с известными подходами. Разработан приближенный алгоритм построения минимальной дизъюнктивной нормальной формы булевых функций, соответствующих множествам записей таблицы маршрутизации, основанный на двухуровневом представлении множества импликант функции и эвристическом алгоритме генерации простых импликант. Показана возможность применения предложенного алгоритма для сокращения размера таблиц маршрутизации большой размерности в режиме реального времени. Алгоритмическая модель процесса уменьшения размера таблиц маршрутизации, основанная на использовании разработанных алгоритмов минимизации булевых функций и метода ветвей и границ. Метод уменьшения таблиц маршрутизации, основанный на использовании эвристического алгоритма выборочной генерации простых импликант булевых функций, который обладает большей скоростью вычислений, по сравнению с известными подходами, и позволяет обрабатывать таблицы большой размерности в режиме реального времени. Программный комплекс, реализующий разработанные алгоритмы, компьютерное моделирование и экспериментальная оценка эффективности методов уменьшения таблиц маршрутизации. Практическая и теоретическая значимость исследовании. Результаты диссертационной работы могут найти применение при разработке программных систем, предназначенных для повышения экономичности маршрутизаторов. Разработанные алгоритмы также могут быть использованы в системах автоматизации проектирования интегральных схем. Достоверность результатов обеспечивается строгостью постановок задач, корректностью выбранного математического аппарата и подтверждается результатами компьютерного моделирования. Личный вклад автора. Постановка задач исследования осуществлена совместно с научным руководителем Л. А.Смагиным. Основные теоретические и практические исследования проведены автором самостоятельно. Телекоммуникационные технологии и сети» УлГУ. Публикации. По теме диссертации опубликовано 7 работ, в том числе 2 - в изданиях из перечня ВАК. Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из наименований и одного приложения. Основной текст диссертации изложен на 0 страницах. Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из наименований и одного приложения. Основной текст диссертации изложен на страницах. Первая глава посвящена обзору и анализу существующих методов уменьшения размера таблиц маршрутизации. Отмечается, что большинство методов, приводимых в литературе, основано на минимизации булевых функций. Построена классификация методов сжатия таблиц маршрутизации. На основе проведенного анализа показано, что возможность использования известных схем уменьшения размера таблиц маршрутизации ограничена задачами небольшой размерности. Вторая глава посвящена разработке метода уменьшения размера таблиц маршрутизации в ГР-сетях. Метод основан на представлении адресной части таблиц маршрутизации с помощью булевых функций. Разработаны два алгоритма минимизации булевых функций - точный, основанный на применении двоичных диаграмм решения и метода ветвей и границ, и приближенный, главными чертами которого является использование двухуровневой структуры данных для представления импликант и эвристического алгоритма выборочной генерации простых импликант. В третьей главе рассматриваются вопросы компьютерной реализации предложенных алгоритмов, а также полученные экспериментальные оценки их качества. Приводится описание разработанного программного пакета. Показано, что предложенные методы минимизации дают выигрыш в быстродействии по сравнению с существующими подходами. Результаты компьютерного моделирования показывают, что за счет использования предлагаемого метода достигается повышение скорости поиска записей в таблице маршрутизации, а также сокращается его энергопотребление. В заключении изложены основные результаты диссертационного исследования. Приложение 1 содержит листинг программной реализации разработанных алгоритмов.