Протоколы маршрутизации по состоянию канала.
Протокол OSPF.
Тема № 10
•Основы протокола OSPF
•Метрики маршрута в OSPF
•Планирование маршрутизации в ЛВС на базе протокола OSPF.
•Основы конфигурирования протокола.
•Конфигурирование маршрутов на базе зон.
Казаков Ф.А. |
2 |
Маршрутизация по состоянию канала
Основные принципы:
•Пересылка информации о состоянии интерфейсов маршрутизатора;
•Сбор информации о всей топологии сети
•Расчет метрик для всех доступных сетей (интерфейсов);
•Поиск кратчайшего пути для каждой сети (интерфейса)
Казаков Ф.А. |
3 |
Протокол OSPF
Открытый протокол, базирующийся на алгоритме поиска наикратчайшего пути (Open Shortest Path Fisrt - OSPF);
Разработан в середине 1980 гг для сетей IP рабочей группой Internet Engineering Task Force (IETF), занимающейся разработкой протоколов для внутрисистемных роутеров (interior gateway protocol - IGP). Рабочая группа была образована в 1988 г. для разработки протокола IGP, базирующегося на алгоритме "поиска наикратчайшего пути" (shortest path first - SPF).
Казаков Ф.А. |
4 |
Протокол OSPF
OSPF является протоколом маршрутизации с об'явлением состояния о канале (link-state).
Это значит, что он требует отправки об'явлений о состоянии канала (link-state advertisement - LSA) во все роутеры, которые находятся в пределах одной и тойже иерархической области. В oб'явления LSA протокола OSPF включается информация о подключенных интерфейсах, об использованных показателях и о других переменных.
По мере накопления роутерами OSPF информации о состоянии канала, они используют алгоритм SPF для расчета наикратчайшего пути к каждому узлу.
Казаков Ф.А. |
5 |
Описание протокола OSPF
Протокол OSPF поддерживает возможность разделения локальной сети (AS) на несколько областей. В этом случае внутренние маршрутизаторы области могут и не иметь информации о топологии остальной части AS.
Сеть обычно имеет выделенный маршрутизатор, который является источником маршрутной информации для остальных маршрутизаторов AS. Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. Если к месту назначения ведут два или более эквивалентных маршрута, информационный поток будет поделен между ними поровну.
Впроцессе выбора оптимального маршрута анализируется ориентированный граф сети. Пути с наименьшим суммарным значением метрики считаются наилучшими. Именно они оказываются выбранными в результате рассмотрения графа (“кратчайшие пути“).
Казаков Ф.А. |
6 |
Пример топологии сети
Казаков Ф.А. |
7 |
Алгоритм поиска оптимального пути
Определения:
1.Пусть D(v) равно сумме весов связей для данного пути.
2.Пусть c(i,j) равно весу связи между узлами с номерами i и j.
Казаков Ф.А. |
8 |
Алгоритм поиска оптимального пути
1.Устанавливаем множество узлов N = {1}.
2.Для каждого узла v не из множества n устанавливаем D(v)= c(1,v).
3.Для каждого шага находим узел w не из множества N, для которого D(w) минимально, и добавляем узел w в множество N.
4.Актуализируем D(v) для всех узлов не из множества N
5.D(v)=min{D(v), D(v)+c(w,v)}.
6.Повторяем шаги 2-4, пока все узлы не окажутся в множестве N.
Казаков Ф.А. |
9 |
Пример реализации алгоритма поиска пути
Шаг |
N |
B |
C |
D |
E |
F |
G |
H |
I |
J |
0 |
{A} |
3 |
- |
9 |
- |
- |
- |
- |
- |
- |
1 |
{A,B} |
(3) |
4 |
9 |
7 |
- |
10 |
- |
- |
- |
2 |
{A,B,C} |
3 |
(4) |
6 |
6 |
10 |
10 |
8 |
- |
14 |
3 |
{A,BC,D} |
3 |
4 |
(6) |
6 |
10 |
10 |
8 |
9 |
14 |
4 |
{A,B,C,D,E} |
3 |
4 |
6 |
(6) |
10 |
10 |
8 |
9 |
14 |
5 |
{A,B,C,D,E,H} |
3 |
4 |
6 |
6 |
10 |
10 |
(8) |
9 |
14 |
6 |
{A,B,C,D,E,H,I} |
3 |
4 |
6 |
6 |
10 |
10 |
8 |
(9) |
14 |
7 |
{A,B,C,D,E,H,I,F} |
3 |
4 |
6 |
6 |
(10) |
10 |
8 |
9 |
14 |
8 |
{A,B,C,D,E,H,I,F,G} |
3 |
4 |
6 |
6 |
10 |
(10) |
8 |
9 |
14 |
9 |
{A,B,C,D,E,H,I,F,G,J} |
3 |
4 |
6 |
6 |
10 |
10 |
8 |
9 |
(14) |
Казаков Ф.А. |
10 |