Использование алгоритма Белмана-Форда в протоколах маршрутизации

Алгоритм вектора расстояния применяется рядом протоколов маршрутизации, в том числе протоколами RIPv1, RIPv2, IGRP, RIP-IPX. Из описания алгоритма, приведенного выше, ясно, что маршрутизатор в определенных ситуациях должен рассылать свою таблицу маршрутизации всем соседям. Каждый сосед, получив такое сообщение, и обнаружив изменение информации в сравнении с предшествующей рассылкой, выполняет коррекцию своей таблицы и далее сам отправляет аналогичные сообщения. Благодаря этому, все маршрутизаторы объединенной сети узнают о достижимых сетях и вычисляют актуальные маршруты к ним. Поскольку вероятность выхода из строя маршрутизатора, или линии связи, всегда отлична от нуля, требуется механизм индикации этих событий и соответствующий пересчет маршрутов. Эту задачу решают таймер и метка источника информации, связываемые с каждой записью в таблице. Рассылка маршрутных таблиц производится не только при каких-то изменениях в метриках, но и в нормальном режиме, как способ информирования соседей о работоспособности соответствующего узла и актуальности вычисленных маршрутов. Такая рассылка протоколом RIP производится каждые 30 сек. Отсутствие обновлений от определенного узла в течение 180 сек. интерпретируется как сигнал его неработоспособности и необходимости удаления из таблиц тех маршрутов, для которых этот узел являлся следующим. Для повышения скорости информирования соседних узлов об изменениях метрик маршрутов предусматривается возможность немедленной рассылки обновлений (Triggered Update). Вместе с тем, для предотвращения чрезмерного роста сетевой нагрузки в периоды обновлений таблиц устанавливается предел частоты рассылки немедленных обновлений (например, не чаще одного раза в секунду).

Очевидно, что работоспособность описанного механизма существенно зависит от количества маршрутизаторов в сети. Прежде всего, при их большом числе объем служебного трафика также оказывается значительным. Кроме этого, несмотря на принципиальную сходимость алгоритма Белмана-Форда, этот процесс занимает тем большее время, чем более масштабна сеть. Это плохо, поскольку в течение периода сходимости будет рассылаться не вполне достоверная информация о возможных маршрутах. Её использование может приводить к вычислению неэффективных, а иногда и несуществующих, маршрутов. В больших сетях лучшими показателями скорости сходимости и меньшим объемом порождаемого служебного трафика обладают протоколы, базирующиеся на алгоритме Дейкстры.

Алгоритм Дейкстры

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

Построение минимального дерева заключается в последовательном определении узлов, ближайших к корневому, и линий, связывающих путем минимальной длины каждый новый ближайший узел с каким-то из ранее найденных ближайших соседей. Иллюстрацией алгоритма может служить следующая модель.

Пусть существует множество связанных между собой нитями различной длины шаров, лежащих на горизонтальной поверхности. Длины нитей моделируют различную «стоимость» линий связи между узлами сети. Последовательность ближайших соседей можно определить поднимая «корневой» шар и фиксируя номера шаров, последовательно отрывающихся от поверхности стола; нити, связывающие этот шар с множеством уже поднятых шаров дают связи в минимальном дереве. Пусть корневым является «шар 1». При его подъеме, в какой-то момент от поверхности оторвется шар, который связан с шаром 1 нитью минимальной длины. Пусть его номер 2 (здесь важно то, что мы узнали номер этого шара), а расстояние между ними равно длине нити 1-2. По мере дальнейшего подъема шара 1, расстояние между ним и шаром 2 уже не изменится. Когда от поверхности оторвется следующий шар, пусть «шар 3», расстояние между ним и корневым шаром 1 определится либо длиной нити 1 – 3 (а она известна), либо суммой длин нитей 1-2 и 2-3, которые также известны. Минимальная из этих величин даст расстояние от корня до шара 3.

Ясно, что алгоритм построения минимального дерева на графе множества шаров должен решать задачу: «шар с каким номером будет очередным ближайшим соседом и какая линия, из числа связывающих его с множеством уже найденных ближайших соседей, должна быть включена в минимальное дерево?». Пусть последним из оторвавшихся от поверхности был шар с номером k и расстояние между ним и шаром 1 равно D_k. При этм существуют D_k+i - оценки расстояний от шара 1 ко всем шарам с номерами k+i, i=1,2,…. Возможно, что после отрыва от поверхности стола шара k какие-то из них надо будет заменить на величины D_k+C_ki, (C_ki – длины нитей, связывающих шар k с еще остающимися на поверхности шарами). Так, если расстояние D_k+C_ki окажется меньше, чем ранее вычисленная оценка D_k+i, то последняя заменяется этим меньшим значением, в противном случае величина D_k+i сохраняется неизменной. Сравнение обновленных значений D_k+i по критерию минимума даст номер шара (k+i), который оторвется от поверхности следующим и, следовательно, станет очередным «ближайшим соседом».

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

Пусть узел s является корневым узлом; оценки минимального расстояние от узла s до узлов i обозначим D_i, а «длины» линий, непосредственно связывающих узлы i и j, обозначим C_ij. Еслиузлы i и j не имеют непосредственной связи, то . В этих обозначения алгоритм Дейкстры записыввается следующим образом.

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

2. {Нахождение «ближайшего соседа»}

Вычислить .

Добавить i в N.

3. {Найти новую ветвь (i,k) минимального дерева}

4. ЕСЛИ N содержит все узлы сети, ТО «Конец»

5. {Обновление оценок минимальных расстояний}

Для всех вычислить

.

Перейти к шагу 2.

Проиллюстрируем работу алгоритма на примере сети, граф которой представлен на рис. 5.5., предполагая, что узел 1 является корневым. Таблица 5.4. содержит результаты всех шагов алгоритма. Ее первая строка соответствует выполнению процедуры инициализации алгоритма. Жирным шрифтом выделено найденное на текущей итерации значение длины пути от «ближайшего соседа» до корневого узла. Последняя строка содержит набор кратчайших расстояний от узла 1 до всех узлов сети.

Таблица 5.4

Итерация	N	D2	D3	D4	D5	D6
	{1}
	{1, 3}
	{1, 3, 2}
	{1, 3, 2, 6}
	{1, 3,2, 6,4}
	{1, 3, 2, 6, 4, 5}

В ходе реализаци алгоритма ведется построение дерева кратчайших путей с корнем в узле-источнике (узел 1 в рассматриваемом примере). На каждой итерации определяется линия, которая связывает найденный очередной «ближайший» узел (пусть узел i) с его предшественниками, т.е. с тем узлом k из множества N, для которого D_k+C_ki имеет минимальное значение. Заметим, что этот путь полностью проходит через узлы множества N. Так, на второй итерации в качестве «ближайшего соседа» определен узел 2, который становится очередной вершиной минимального дерева. В множестве N уже находятся узлы 1 и 3 и найденный новый узел может быть соединен с деревом посредством линий 2-1, или 2-3. Проверив D₁+C₂₁ и D₃+С₂₃ определяем, что узел 2 должен соединятся с минимальным деревом посредством линии 2-1. Наконец на 5-й итерации найден ближайший сосед - узел 5. К этому моменту в множестве N уже содержатся узлы 1,2,3,4,6. Узел 5 не имеет непосредственной связи с узлом 1. Проверка значений D_k+С_5k, где k=1,2,3,4,6 показывает, что в дерево должна быть включена линия 5-6, как обеспечивающая минимальное расстояние от узла 1 до узла 5. Таким образом, на каждой итерации минимальное дерево пополняется одной ветвью, как это показано на рис.5.7.

На основании построенного минимального дерева узел 1 формирует таблицу маршрутизации, которая для дейтограммного режима будет иметь вид представленный ниже.

Таблица 5.5.

Сеть назначения	Следующий узел	Длина маршрута

Перечислим существенные характеристики алгоритма Дейкстры.

1. Необходимость получения каждым узлом информации о топологии и составе сети.

2. Независимость расчета оптиального маршрута каждым узлом.

3. Для инициализации обновления таблицы маршрутизации узлу нет необходимости рассылать всю известную ему топологическую информацию, достаточно лишь сообщить об изменениях в состоянии линий и составе непосредственно присоединенных сетей.

4. Отсутствие необходимости обмена таблицами маршрутизации существенно сокращает объем служебного трафика, а знание всей топологии сети способствует повышению скорости сходимости алгоритма и гарантирует нахождение действительно кратчайших путей.