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

       

Алгоритм SPF


Алгоритм SPF, основываясь на базе данных состояния связей, вычисляет кратчайшие пути между заданной вершиной S графа и всеми остальными вершинами. Результатом работы алгоритма является таблица, где для каждой вершины V графа указан список ребер, соединяющих заданную вершину S с вершиной V по кратчайшему пути.

Алгоритм SPF был предложен Е.В.Дейкстрой (E.W.Dijkstra).

Пусть

S - заданная вершина (источник путей);

E - множество обработанных вершин, т.е. вершин, кратчайший путь к которым уже найден;

R - множество оставшихся вершин графа (т.е. множество вершин графа за вычетом множества E);

O - упорядоченный список путей.

Описание алгоритма

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


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

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


Алгоритм SPF, основываясь на базе данных состояния связей, вычисляет кратчайшие пути между заданной вершиной S графа и всеми остальными вершинами. Результатом работы алгоритма является таблица, где для каждой вершины V графа указан список ребер, соединяющих заданную вершину S с вершиной V по кратчайшему пути.

Алгоритм SPF был предложен Е.В.Дейкстрой (E.W.Dijkstra).

Пусть

S - заданная вершина (источник путей);

E - множество обработанных вершин, т.е. вершин, кратчайший путь к которым уже найден;

R - множество оставшихся вершин графа (т.е. множество вершин графа за вычетом множества E);

O - упорядоченный список путей.

Описание алгоритма

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


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

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



Содержание раздела