Алгоритмы нахождения кратчайшего пути

Большинство адаптивных алгоритмов маршрутизации являются алгоритмами кратчайшего пути в том смысле, что они определяют оптимальный маршрут на основе минимизации выбранной целевой функции. При этом «длинной» («стоимостью») каждого элемента маршрута может быть:

· условная единица; в этом случае, кратчайшим будет маршрут, сформированный из наименьшего числа таких элементов (переходов);

· величина, обратная пропускной способности линии связи; в этом случае, кратчайшим будет маршрут, сформированный на линиях с максимально возможной пропускной способностью;

· величина, пропорциональная сумме средней задержки обработки пакета маршрутизаторами; в этом случае кратчайшим становится маршрут с наименьшими задержками доставки пакетов от источника до узла назначения;

· величина, пропорциональная степени загруженности участка сети (например, относительный уровень трафика на соответствующем интерфейсе, размер выходной очереди и т.д.); в этом случае, кратчайший маршрут не будет включать участки, уже испытывающие перегрузки.

Наиболее широкое применение в протоколах маршрутизации нашли алгоритмы Беллмана-Форда и Дейкстры.

Алгоритм Беллмана-Форда

Алгоритм поиска кратчайшего пути Беллмана-Форда (иногда его называют алгоритмом Форда-Фулкерсона) относится к классу алгоритмов длины вектора расстояния и базируется на следующем очевидном принципе. Если узел А непосредственно связан линиями «длинной» с узлами , а расстояния от последних до целевого узла Z равны соответственно D_B, D_C и D_F, то кратчайший маршрут от узла A до узла Z будет проходить через узел , для которого .

Например, определим кратчайший путь от узла 2 к узлу 6 в сети, топология которой представлена на рис. 5.5. Для того, чтобы из узла 2 пакет мог прийти в узел назначения (узел 6), он должен быть передан одному из трех узлов 1, 4, или 5. Предположим, что «стоимость» путей от каждого из этих узлов к узлу 6 уже известна и составляет 3, 3 и 2 соответственно. Тогда полная «длина» путей от узла 2 к узлу 6 равна:

· 6 - по маршруту через узел 1,

· 4 - по маршруту через узел 4,

· 6 - по маршруту через узел 5.

Таким образом, кратчайший путь к узлу 6 пролегает через узел 4. Одновременно с нахождением длины кратчайшего пути определяется и следующий узел маршрута (в данном случае – узел 4).

 

Проведем более формальное рассмотрение алгоритма. Пусть D_j – текущая оценка кратчайшего пути от узла j до сети назначения и C_ij – «длина» («стоимость») линии между узлами i и j. При этом C_ii = 0, C_ij= C_ji и, если узлы i и j непосредственно не соединены, то C _ij = ∞. В этих обозначениях, выражение для кратчайшего пути от узла 2 к узлу 6 имеет вид

. (5.1)

Одним из существенных ограничений таких вычислений является предположение о том, что длины кратчайших путей (D₁, D_4, D₅ )от узлов 1, 4 и 5 до целевой сети известны. В общем случае, эти величины неизвестны и для их определения необходимы дополнительные вычисления. Например,

(5.2)

и

. (5.3)

Аналогичные выражения можно записать и для расстояний D₃ и D₅. Хорошо видно, что эти выражения в своей совокупности образуют систему линейных уравнений относительно D₁ – D₅. Алгоритм Беллмана-Форда собственно и является итерационной процедурой нахождения решения этой системы. В общем виде он описывается следующим образом.

1. {Инициализация }

2. {Обновление оценок расстояний до узла назначения}

На каждом узле сети вычисляется

3. ЕСЛИ То конец ИНАЧЕ и перейти к шагу 2.

Проиллюстрируем работоспособность алгоритма на примере рассматренной выше сети. Вычислим кратчайшие пути от каждого маршрутизатора сети к сетям, непосредственно подключенных к узлу 6. Дуплетом (n, D_i) будем обозначать: следующий узел n на кратчайшем пути от узла i к узлу 6и текущеезначение кратчайшего пути D_i. Если следующий узел на текущей итерации не определен, то принимаем . Результаты вычислений сведены в таблицу 5.1.

Таблица 5.1.

k	Узел 1	Узел 2	Узел 3	Узел 4	Узел 5
	(-1, ∞)	(-1, ∞)	(-1, ∞)	(-1, ∞)	(-1, ∞)
	(-1, ∞)	(-1, ∞)	(6,1)	(3,3)	(6,2)
	(3,3)	(4,4)	(6,1)	(3,3)	(6,2)
	(3,3)	(4,4)	(6,1)	(3,3)	(6,2)

 

Видим, что алгоритм сошелся достаточно быстро и его результат позволяет записать в таблице маршрутизации узла 1 строку

Узел (сеть) назначения	Следующий узел	Расстояние

Аналогично, узел 2 сформирует в своей маршрутной таблице строку

Узел (сеть) назначения	Следующий узел	Расстояние

и т.д.

Приведенный пример наглядно иллюстрирует важнейшее свойство алгоритма Беллмана-Форда, а именно его распределенный характер – каждый узел для проведения расчета текущей оценки требует информацию о результатах вычислений расстояний до целевой сети , выполненных на других узлах. Вместе с тем, результаты этих вычислений (вектор ) должны быть распространены только к соседним узлам, т.е. маршрутизаторы могут иметь неполную информацию о связях в сети.

Изменения в маршрутных таблицах инициируются любым узлом посредством рассылки им на все свои порты нового вектора минимальных расстояний до известных ему сетей. Этот механизм называют инициированным обновлением, а его реализуемость является следствием свойства сходимости алгоритма Беллмана-Форда к верным результатам при весьма мягких требованиях. Можно показать, что алгоритм сходится за конечное число шагов, начиная с некоторых неотрицательных оценок , т.е., если ситуация в сети изменилась («стоимости» путей изменились), то это обстоятельство не приведет к невозможности вычисления правильных кратчайших путей. Обратимся, например, к сети, рассматренной выше (рис.5.5) и предположим, что после завершения работы алгоритма (состояние представленное таблицей 5.1.) линия, соединяющая узлы 3 и 6 вышла из строя. Вычислим минимальные расстояния от всех узлов к узлу 6 в этих новых условиях, предполагая, что каждый узел немедленно после обнаружения изменения в топологии сети приступит к пересчету своих оценок минимальных расстояний и будет сообщать их своим соседям. Как только узел 3 обнаружит выход из строя линии 3-6, он вычислит новое минимальное расстояние к узлу 6 (равное 5) и следующий узел на пути (4). Он отправит это обновленное значение вектора расстояний своим соседям (узлам 1 и 4). Эти узлы пересчитают свои минимальные расстояния и разошлют их своим соседям (узел 1 - к узлам 2, 3, 4 и узел 4 – к узлам 1,2,3,5). Получение этих сообщений инициализирует пересчет минимального расстояния в узлах 2 и 5. Описанный процесс представлен в первой строке таблице 5.3. Далее, для простоты, будем считать, что процессы пересчета происходят синхронно на всех узлах. После трех итераций изменений в минимальных расстояниях более не происходит – алгоритм сошелся за 4 шага

Таблица 5.3.

k	Узел 1	Узел 2	Узел 3	Узел 4	Узел 5
	(3,3)	(4,4)	(6,1)	(3,3)	(6,2)
	(2,7)	(5,6)	(4,5)	(2,5)	(6,2)
Далее считаем, что вычисления на всех узлах производятся синхронно
	(3,7)	(4,6)	(4,7)	(5,5)	(6,2)
	(2,9)	(4,6)	(4,7)	(5,5)	(6,2)
	(2,9)	(4,6)	(4,7)	(5,5)	(6,2)

Хотя алгоритм Беллмана Форда и сходится к правильным значениям кратчайших расстояний, этот процесс может быть в определенных условиях чрезвычайно медленным. На рис. 5.6. приведен пример возникновения такой ситуации.

 

 

Узлом назначения здесь является узел 3. Если канал 2-3 выходит из строя, то алгоритм дает последовательность значений минимального расстояния от узла 2: 1, 3, 5, …..101, ….., сходящуюся к значению 100 лишь на 49 итерации. Для узла 1 получаем такую же последовательность минимальных расстояний до узла 3: 2, 4, 6, 8, 10,... Последствиями медленной сходимости алгоритма могут быть:

· увеличение объема служебных данных, которыми обмениваются маршрутизаторы и, соответственно, уменьшение реальной производительности сети;

· образование петель маршрутизации.

Для предотвращения подобных явлений были предложены несколько усовершенствований к алгоритму Беллмана-Форда, но эффект их применения был ограничен конкретными топологиями и не снял проблему его медленной сходимости. Одно из таких усовершенствований получило название ассиметричного объявления. Часто егоназывают «расщепление горизонта», что является буквальным переводом англоязычного названия этого приема split horizon (не очень удачное название, по крайней мере, для говорящих на русском языке). Суть этого усовершенствования заключается в запрещении узлу транслировать информацию о минимальном расстоянии до сети назначения через тот порт, который ведет к ней. Это ограничение упрощенно может быть сформулировано следующим образом: «Не надо сообщать узлу K о расстояни до целевой сети, если он является следующим узлом на этом маршруте, поскольку имено на основе его информации это расстояние и было вычислено». Другой прием, называемый ложной неудачей (poison reverse), служит тем же целям и заключается в отсылке на этот порт заведомо неверной информации, а именно, бесконечного расстоянии до целевой сети. Проиллюстрируем принципиальную применимость последнего приема для ускорения процедуры сходимости алгоритма Беллмана-Форда в ситуаци, представленной рис.7.6.

1. После возникновения разрыва узел 2 вычислит:
и следующий узел – узел 1. Однако, на порт, связывающий его с узлом 1, будет передано D₂ = ∞.

2. Узел 1 в свою очередь определит

и следующий узел – 3.

Эта информация будет передана узлу 2 и он пересчитает свое минимальное расстояние.

3. и следующий узел 1, куда снова будет передано D₂ = ∞

4. В узле 1 снова вычисляется

и следующий узел 3.

5. В свою очередь, узел 2 вновь вычислит

, т.е. величина D₂ не изменилась, процесс сошелся.

Все эти изменения состояния вектора кратчайших расстояний представлены в таблице 5.4.

Таблица 5.4

k	Узел 1	Узел 2
Вычислено	Объявлено
До выхода из строя линии 2-3	(2,2)	(3,1)	(3,1)
	(3,100)	(1, 3)
	(3,100)	(1,101)
	(3,100)	(1,101)