Телекоммуникационные технологии.Сети 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



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