Телекоммуникационные технологии.Сети TCP-IP



Поддержка множественных маршрутов - часть 2


Избежать этого явления позволяет следующее правило.

Если узел Х отправляет данные в узел Y, он может пересылать их через узел Q только в том случае, если Q ближе к Y, чем Х.

В разобранном выше примере, следуя этому правилу, (1) не может посылать данные в (3) через (2) , поскольку (2) не ближе к (3) , чем (1) . Однако такая посылка возможна, если связи между узлами имеют метрики, например, как изображено на следующем рисунке.


Рис. 5.1.6. Пример корректной ситуации при поддержке множественных маршрутов

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

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

1. Инициализировать E={S}, R={все вершины графа, кроме S}. Поместить в О все односегментные (длиной в одно ребро) пути, начинающиеся из S, отсортировав их в порядке возрастания метрик.
2. Если О пуст или первый путь в О имеет бесконечную метрику, то отметить все вершины в R как недостижимые и закончить работу алгоритма.
3. Рассмотрим P - кратчайший путь в списке О. Удалить P из О. Пусть V - последний узел в P.
Если V принадлежит E, перейти на шаг 3А;
иначе P является кратчайшим путем из S в V; перенести V из R в E. Перейти на шаг 4.


3А. Рассмотрим W, узел, предшествующий V в пути Р. Если расстояние от S до W меньше расстояния от S до V, обозначить Р как приемлемый альтернативный путь к V. В любом случае перейти на шаг 2.


4. Построить набор новых путей, подлежащих рассмотрению, путем добавления к пути P всех односегментных путей, начинающихся из V. Метрика каждого нового пути равна сумме метрики P и метрики соответствующего односегментного отрезка, начинающегося из V. Добавить новые пути в упорядоченный список О, поместив их на места в соответствии со значениями метрик. Перейти на шаг 2.




Содержание  Назад  Вперед