алгоритмы предложены Дикстрой) является альтернативой
4.4.11.2 Протокол OSPF (алгоритм Дикстры)
Семенов Ю.А. (ГНЦ ИТЭФ)
Протокол OSPF (Open Shortest Pass First, RFC-1245-48, RFC-1583-1587, алгоритмы предложены Дикстрой) является альтернативой RIP в качестве внутреннего протокола маршрутизации. OSPF представляет собой протокол состояния маршрута (в качестве метрики используется - коэффициент качества обслуживания). Каждый маршрутизатор обладает полной информацией о состоянии всех интерфейсов всех маршрутизаторов (переключателей) автономной системы. Протокол OSPF реализован в демоне маршрутизации gated, который поддерживает также RIP и внешний протокол маршрутизации BGP.
Автономная система может быть разделена на несколько областей, куда могут входить как отдельные ЭВМ, так и целые сети. В этом случае внутренние маршрутизаторы области могут и не иметь информации о топологии остальной части AS. Сеть обычно имеет выделенный (designated) маршрутизатор, который является источником маршрутной информации для остальных маршрутизаторов AS. Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. Если к месту назначения ведут два или более эквивалентных маршрута, информационный поток будет поделен между ними поровну. Переходные процессы в OSPF завершаются быстрее, чем в RIP. В процессе выбора оптимального маршрута анализируется ориентированный граф сети. Ниже описан алгоритм Дикстры по выбору оптимального пути. На иллюстративном рис. 4.2.11.2.1 приведена схема узлов (A-J) со значениями метрики для каждого из отрезков пути. Анализ графа начинается с узла A (Старт). Пути с наименьшим суммарным значением метрики считаются наилучшими. Именно они оказываются выбранными в результате рассмотрения графа (“кратчайшие пути“).
Рис. 4.2.11.2.1 Иллюстрация работы алгоритма Дикстры
Ниже дается формальное описание алгоритма. Сначала вводим некоторые определения.
Пусть D(v) равно сумме весов связей для данного пути.
Пусть c(i,j) равно весу связи между узлами с номерами i и j.
Далее следует последовательность шагов, реализующих алгоритм.
- Устанавливаем множество узлов N = {1}.
- Для каждого узла v не из множества n устанавливаем D(v)= c(1,v).
- Для каждого шага находим узел w не из множества N, для которого D(w) минимально, и добавляем узел w в множество N.
- Актуализируем D(v) для всех узлов не из множества N
D(v)=min{D(v), D(v)+c(w,v)}. - Повторяем шаги 2-4, пока все узлы не окажутся в множестве N.
Топология маршрутов для узла a приведена на нижней части рис. 4.2.11.2.1. В скобках записаны числа, характеризующие метрику отобранного маршрута согласно критерию пункта 3.
Таблица 4.2.11.2.1. Реализация алгоритма
| Множество | Метрика связи узла a с узлами | |||||||||
| Шаг | 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) |
- пропускной способностью канала;
- задержкой (время распространения пакета);
- числом дейтограмм, стоящих в очереди для передачи;
- загрузкой канала;
- требованиями безопасности;
- типом трафика;
- числом шагов до цели;
- возможностями промежуточных связей (например, многовариантность достижения адресата).
Определяющими являются три характеристики: задержка, пропускная способность и надежность. Для транспортных целей OSPF использует IP непосредственно, т.е. не привлекает протоколы UDP или TCP. OSPF имеет свой код (89) в протокольном поле IP-заголовка. Код TOS (type of service) в IP-пакетах, содержащих OSPF-сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF.
