Введение
Глава 1. Обзор и анализ существующих методов уменьшения размера таблиц маршрутизации 11
1. 1. Маршрутизация, архитектура маршрутизаторов 11
1.2. Обзор методов оптимизации поиска в таблицах маршрутизации 13
1.3. Методы уменьшения размера таблиц маршрутизации 17
1.4. Методы минимизации булевых функций большой размерности 23
1.4.1 Классификация алгоритмов минимизации булевых функций 23
1.4.2 Алгоритмические сложности решения задачи минимизации ДНФ 24
1.4.3 Точные алгоритмы минимизации ДНФ 26
1.4.4 Приближенные алгоритмы 34
Выводы 37
Глава 2. Разработка метода уменьшения таблиц маршрутизации в ІР-сетях 39
2.1. Метод уменьшения размера таблиц маршрутизации 39
2.2 Точный алгоритм минимизации булевых функций в классе ДНФ 45
2.2.1 Двоичные диаграммы решения 46
2.2.2 Генерация всех простых импликант булевой функции 51
2.2.3 Упрощение матрицы покрытия 53
2.2.4 Построение минимального покрытия 58
2.3 Приближенный алгоритм минимизации ДНФ 62
Выводы 65
Глава 3. Компьютерное моделирование и экспериментальная оценка разработанного метода уменьшения таблиц маршрутизации 67
3.1. Выбор средств разработки программного пакета 67
3.2 Программная реализация разработанного метода уменьшения таблиц маршрутизации 69
3.2.2 Описание программного продукта 73
3.3 Применение разработанных методов минимизации ДНФ для уменьшения размера таблиц маршрутизации 77
3.4. Оценка зависимости производительности маршрутизатора от размера таблицы маршрутизации 82
3.5 Экспериментальная оценка эффективности предложенных алгоритмов для задач из набора MCNC Benchmarks 888
Выводы 90
Заключение 91
Список литературы 93
Приложение 101
