OSPF (Open Shortest Path First) – протокол динамической маршрутизации, основанной на технологии отслеживания состояния канала (link-state technology) и используется для нахождения кратчайшего пути алгоритм Дейкстры. Данный протокол маршрутизации имеет следующие преимущества.

1. Высокая скорость сходимости
2. Поддержка сетевых масок переменной длины VLSM
3. Оптимальное использование пропускной способности с построением дерева кратчайших путей
4. Каждый маршрутизатор в домене маршрутизации имеет точную информацию о топологии сети
5. Является открытым, поддерживается многими производителями

В основе протокола OSPF лежит алгоритм кратчайшего пути Дейкстры. Алгоритм кратчайшего пути – shortest path algorithm (SPF) Дейкстры работает с графами, состоящими из вершин, соединенных ребрами. Каждое ребро соединяет ровно две вершины в одном направлении. Каждое ребро имеет стоимость, связанную с ним. Каждая вершина может быть связана с любым
числом ребер.

Вершины можно представлять как точки, а ребра – как перемещение между этими точками. Перемещение обеспечивается лишь в одном направлении и за определенную стоимость – в направлении ребра и за стоимость ребра. Например, если ребро соединяет вершину A с вершиной B, это означает, в сущности, что имеется возможность за стоимость этого ребра переместиться из вершины A в вершину B. Это ребро, однако, не позволяет переместиться обратно из вершины B в вершину A. Такое перемещение требует наличия другого ребра – из вершины B в вершину A.

Перемещение обеспечивается в одном направлении за определенную стоимость. Лучший маршрут определяется как минимальная сумма стоимостей всех составляющих ребер. В реальных условиях вершины представляют из себя маршрутизаторы, а ребра – линки между ними. В качестве стоимости ребра могут выступать различные метрики: пропускная способность, задержки канала, загрузка канала, количество хопов и т.д. Метрика – это числовой показатель. Чем ниже метрика, тем лучше.
Рассмотрим работу алгоритма Дейкстры на конкретном примере.

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

При работе с алгоритмом Дейкстры необходимо соблюдать ряд правил:

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

Этап 1: Находим верхнюю вершину (для нее расстояние будет 0), расстояние до всех остальных вершин неизвестно (принимаем за бесконечность)

Этап 2: Для первой вершины находим смежные вершины. Из найденных вершин находим ту, которая имеет наименьшее расстояние. Данную вершину будем считать найденной. От данной вершины будем минимальный путь до других.

Этап 3: Третья вершина ведет к четвертой, пятой и шестой вершине. К четвертой вершине суммарный путь будет составлять 6. Согласно третьему правилу, мы не имеем право поставить значение 6 в новую строку, так как предыдущее значение равно 4. Значит переносим старое значение в новую строку. К пятой вершине суммарный путь равен 11. До этого была бесконечность. Естественно, 11 меньше бесконечности, значит ставим новый путь в новую строку. Аналогично для шестой вершины.

Из найденных путей выбираем наименьшее в ряду. Наименьшее равно 2 для второй вершины. Помечаем вторую вершину как найденную. Далее будет плясать от нее.

Этап 4: От второй вершины есть два пути: к четвертой и к пятой. К четвертой суммарный путь составит 2+7=9, что меньше ранее найденного 4. Сносим старое значение. К пятой вершине суммарный путь составит 2+2,5=4,5, что меньше ранее записанного 11. Пишем новое значение. Из найденный вершин наименьший вес 4 имеет четвертая вершина. Выбираем ее в качестве найденной.

Этап 5: От четвертой вершины можно попасть только к шестой. При этом суммарный путь составит 4+5=9, что меньше 5. Пишем старое значение в новую строку. Для пятой вершины новых путей нет – сносим старую строку. Наименьшую стоимость имеет пятая вершина. Выбираем ее.

Этап 6: От пятой вершины есть единственный путь к шестой, стоимость которого 2+2,5+4=8,5. 8,5 больше 4, значит оставляем старое значение. Таким образом, минимальный путь от первой вершины к шестой проходит через третью вершину.

На основе полученной таблицы построим дерево с минимальными путями.

Помогла ли вам статья?

Да Нет Стоп

Спасибо! Ваш голос учтен.