OSPF (Open Shortest Path First) — протокол динамической маршрутизации, основанной на технологии отслеживания состояния канала (link-state technology) и используется для нахождения кратчайшего пути алгоритм Дейкстры. Данный протокол маршрутизации имеет следующие преимущества.
- Высокая скорость сходимости
- Поддержка сетевых масок переменной длины VLSM
- Оптимальное использование пропускной способности с построением дерева кратчайших путей
- Каждый маршрутизатор в домене маршрутизации имеет точную информацию о топологии сети
- Является открытым, поддерживается многими производителями
В основе протокола OSPF лежит алгоритм кратчайшего пути Дейкстры. Алгоритм кратчайшего пути – shortest path algorithm (SPF) Дейкстры работает с графами, состоящими из вершин, соединенных ребрами. Каждое ребро соединяет ровно две вершины в одном направлении. Каждое ребро имеет стоимость, связанную с ним. Каждая вершина может быть связана с любым
числом ребер.
Вершины можно представлять как точки, а ребра – как перемещение между этими точками. Перемещение обеспечивается лишь в одном направлении и за определенную стоимость – в направлении ребра и за стоимость ребра. Например, если ребро соединяет вершину A с вершиной B, это означает, в сущности, что имеется возможность за стоимость этого ребра переместиться из вершины A в вершину B. Это ребро, однако, не позволяет переместиться обратно из вершины B в вершину A. Такое перемещение требует наличия другого ребра – из вершины B в вершину A.
Перемещение обеспечивается в одном направлении за определенную стоимость. Лучший маршрут определяется как минимальная сумма стоимостей всех составляющих ребер. В реальных условиях вершины представляют из себя маршрутизаторы, а ребра — линки между ними. В качестве стоимости ребра могут выступать различные метрики: пропускная способность, задержки канала, загрузка канала, количество хопов и т.д. Метрика — это числовой показатель. Чем ниже метрика, тем лучше.
Рассмотрим работу алгоритма Дейкстры на конкретном примере.
В данном примере имеется граф из шести вершин. Найдем кратчайшие пути до всех вершин для первой вершины. В результате мы должны получить таблицу со значениями кратчайших путей, а также дерево с кратчайшими путями до всех вершин. Найденные вершины будем обозначать зеленым кружком.
При работе с алгоритмом Дейкстры необходимо соблюдать ряд правил:
- В каждом ряду необходимо выбрать путь с наименьшей стоимостью. Вершина до которой найден такой путь будет называться найденной.
- От найденной вершины ищем путь к новым вершинам.
- Если новый путь больше предыдущего, то его в таблицу не ставим, а сносим старое значение.
Этап 1: Находим верхнюю вершину (для нее расстояние будет 0), расстояние до всех остальных вершин неизвестно (принимаем за бесконечность)
1 | 2 | 3 | 4 | 5 | 6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
Этап 2: Для первой вершины находим смежные вершины. Из найденных вершин находим ту, которая имеет наименьшее расстояние. Данную вершину будем считать найденной. От данной вершины будем минимальный путь до других.
1 | 2 | 3 | 4 | 5 | 6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
0 | 2 | 1 | 4 | ∞ | ∞ |
Этап 3: Третья вершина ведет к четвертой, пятой и шестой вершине. К четвертой вершине суммарный путь будет составлять 6. Согласно третьему правилу, мы не имеем право поставить значение 6 в новую строку, так как предыдущее значение равно 4. Значит переносим старое значение в новую строку. К пятой вершине суммарный путь равен 11. До этого была бесконечность. Естественно, 11 меньше бесконечности, значит ставим новый путь в новую строку. Аналогично для шестой вершины.
Из найденных путей выбираем наименьшее в ряду. Наименьшее равно 2 для второй вершины. Помечаем вторую вершину как найденную. Далее будет плясать от нее.
1 | 2 | 3 | 4 | 5 | 6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
0 | 2 | 1 | 4 | ∞ | ∞ |
0 | 2 | 4 | 11 | 5 |
Этап 4: От второй вершины есть два пути: к четвертой и к пятой. К четвертой суммарный путь составит 2+7=9, что меньше ранее найденного 4. Сносим старое значение. К пятой вершине суммарный путь составит 2+2,5=4,5, что меньше ранее записанного 11. Пишем новое значение. Из найденный вершин наименьший вес 4 имеет четвертая вершина. Выбираем ее в качестве найденной.
1 | 2 | 3 | 4 | 5 | 6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
0 | 2 | 1 | 4 | ∞ | ∞ |
0 | 2 | 4 | 11 | 5 |
Этап 5: От четвертой вершины можно попасть только к шестой. При этом суммарный путь составит 4+5=9, что меньше 5. Пишем старое значение в новую строку. Для пятой вершины новых путей нет — сносим старую строку. Наименьшую стоимость имеет пятая вершина. Выбираем ее.
1 | 2 | 3 | 4 | 5 | 6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
0 | 2 | 1 | 4 | ∞ | ∞ |
0 | 2 | 4 | 11 | 5 | |
0 | 4,5 | 5 | |||
0 | 4,5 | 5 |
Этап 6: От пятой вершины есть единственный путь к шестой, стоимость которого 2+2,5+4=8,5. 8,5 больше 4, значит оставляем старое значение. Таким образом, минимальный путь от первой вершины к шестой проходит через третью вершину.
1 | 2 | 3 | 4 | 5 | 6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
0 | 2 | 1 | 4 | ∞ | ∞ |
0 | 2 | 4 | 11 | 5 | |
0 | 4,5 | 5 | |||
0 | 4,5 | 5 | |||
0 | 4,5 | 5 |
На основе полученной таблицы построим дерево с минимальными путями.