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