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


         

в Е, то кратчайший путь


P=DBA, следовательно V=(2) . Так как V не находится в Е, то кратчайший путь (3) ->
(2) есть P. Добавляем этот факт в таблицу результатов, изымаем P из O, переносим V из R в Е.
Строим новые пути: согласно базе данных из V=(2) существует один односегментный путь A. Добавив его к P=DBА, получим путь DBAА с метрикой 6. Этот путь добавляется в упорядоченный список О.
E={(3) ,(4) ,(1) ,(2) }, R={}, O={DBC,DBAA}.
Результаты: ((4) : D;(1) :DB,(2) :DBA)
Итерации 7 и 8
На этих итерациях из списка О будут удалены оставшиеся пути, так как они ведут к вершинам, уже находящимся в множестве Е, больше никаких изменений не произойдет.
Итерация 9
Так как список О пуст и множество R пусто, то кратчайшие пути из S до всех вершин графа построены, недостижимых вершин нет. Работа алгоритма закончена.
Результатом работы является таблица кратчайших путей от маршрутизатора (3) до всех остальных маршрутизаторов:
(3) ->
(1) :DB
(3) ->
(2) :DBA
(3) ->
(4) :D
На основе этой информации в узле (3) строится таблица маршрутов, ведущих ко всем узлам OSPF-системы. Для этого из вышеприведенной таблицы нужно взять первую связь каждого пути. Маршрутизатор, к которому ведет эта связь, будет являться следующим маршрутизатором для данного маршрута. При этом алгоритм SPF гарантирует, что и следующий маршрутизатор построил кратчайшие пути, соответствующие путям маршрутизатора (3) , т.е. если кратчайший путь из (3) в (2) (DBA) лежит через узел (4) , в который ведет связь D, то кратчайший путь из (4) в (2) будет ВА.
Таким образом, таблица маршрутов в узле (3) будет выглядеть:
(3) ->
(1) : через (4) , линия D
(3) ->
(2) : через (4) , линия D
(3) ->
(4) : через линию D

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