ПРОБЛЕМА МАРШРУТИЗАЦИИ В ИНФОРМАЦИОННЫХ СЕТЯХКонкретный метод маршрутизации обычно реализуется в рамках протокола сетевого уровня, который управляет пакетами при их движении по сети до места назначения. МЕТОДЫ МАРШРУТИЗАЦИИ, ОСНОВАННЫЕ НА ВЫБОРЕ КРАТЧАЙШЕГО ПУТИ Большинство реальных алгоритмов маршрутизации так или иначе базируется на выборе кратчайшего пути в графе о той или иной метрикой. При этом определение кратчайшего пути может осуществляться как централизованно по имеющейся информации о состоянии сети, так и децентрализовано (распределено) на основе имеющейся в узле информации о состоянии ближайших соседей, когда структура всей сети неизвестна (метод "рельефа").
ЦЕНТРАЛИЗОВАННЫЕ АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ
Наиболее распространенными стандартными алгоритмами решения задачи нахождения кратчайшего пути на графе являются: алгоритм Беллмана-Форда, алгоритм Дийкстра и алгоритм Флойда-Уоршела [1],[10]. Первые два алгоритма находят кратчайшие пути от узла источника ко всем другим узлам, а третий алгоритм находит кратчайшие пути от всех узлов ко всем другим узлам. Рассмотрим в качестве примера алгоритм Дийкстра. Этот алгоритм требует, чтобы длины (веса) всех ребер были положительны. Объем вычислений для этого алгоритма значительно меньше, чем у алгоритма Беллмана-Форда. Основная идея алгоритма - отыскание кратчайших путей в порядке возрастания длины пути. Чтобы формально описать процедуру нахождения кратчайшего пути, будем считать, что каждый узел i имеет метку Di, означающую текущую оценку длины кратчайшего пути от узла 1. Когда оценка становится неизменной, будем считать, что узел окончательно помечен, и множество окончательно помеченных узлов обозначим через Р. Узел, который будет добавлен на очередном шаге к Р, является ближайшим к узлу 1 среди всех узлов, еще не вошедших в Р. Алгоритм работает следующим образом. Полагаем Р = {1}, Di = 0 Di = d1j " j¹1 при наличии cвязи узла c1. Шаг I. Поиск следующего ближайшего узла. Находим узел iÏ P такой, что Di minjÏP Dj Полагаем Р: PÈ{1}. Еcли Р содержит вcе узлы, то на этом работа алгоритма заканчивается. Шаг 2. Обновление меток. Для всех jÏP положить Di min {Dj, Di + dij} Перейти к шагу I. Пример использования алгоритма Дийкстра приведен на рис. 2.2. Число операций, выполняемых алгоритмом Дийкстра на каждом шаге, пропорционально N, а шаги итерируются N-1 раз. Таким образом, объем вычислений в худшем случае пропорционален N2, а не N3, как у алгоритма Беллмана-Форда.
|
