Ниже дается формальное описание алгоритма. Сначала вводим некоторые определения.
Пусть D (v) равно сумме весов связей для данного пути. Пусть c (i, j) равно весу связи между узлами с номерами i и j.
Далее следует последовательность шагов, реализующих алгоритм.
- 1. Устанавливаем множество узлов N = {1}.
- 2. Для каждого узла v не из множества n устанавливаем D (v)= c (1, v).
- 3. Для каждого шага находим узел w не из множества N, для которого D (w) минимально, и добавляем узел w в множество N.
- 4. Актуализируем D (v) для всех узлов не из множества N D (v)=min {D (v), D (v)+c (w, v)}.
- 5. Повторяем шаги 2−4, пока все узлы не окажутся в множестве N.
Топология маршрутов для узла a приведена на нижней части рисунка 1. В скобках записаны числа, характеризующие метрику отобранного маршрута согласно критерию пункта 3.
Таблица 1 Реализация алгоритма.
|
Множество. | Метрика связи узла a с узлами. |
Шаг. | N. | B. | C. | D. | E. | F. | G. | H. | I. | J. |
| {A}. | | ; | | ; | ; | ; | ; | ; | ; |
| {A, B}. | (3). | | | | ; | | ; | ; | ; |
| {A, B, C}. | | (4). | | | | | | ; | |
| {A, BC, D}. | | | (6). | | | | | | |
| {A, B, C, D, E}. | | | | (6). | | | | | |
| {A, B, C, D, E, H}. | | | | | | | (8). | | |
| {A, B, C, D, E, H, I}. | | | | | | | | (9). | |
| {A, B, C, D, E, H, I, F}. | | | | | (10). | | | | |
| {A, B, C, D, E, H, I, F, G}. | | | | | | (10). | | | |
| {A, B, C, D, E, H, I, F, G, J}. | | | | | | | | | (14). |
Таблица 1 может иметь совершенно иное содержимое для какого-то другого вида сервиса, выбранные пути при этом могут иметь другую топологию. Качество сервиса (QoS) может характеризоваться следующими параметрами:
- · пропускной способностью канала;
- · задержкой (время распространения пакета);
- · числом дейтограмм, стоящих в очереди для передачи;
- · загрузкой канала;
- · требованиями безопасности;
- · типом трафика;
- · числом шагов до цели;
- · возможностями промежуточных связей (например, многовариантность достижения адресата).
Определяющими являются три характеристики: задержка, пропускная способность и надежность. Для транспортных целей OSPF использует IP непосредственно, т. е. не привлекает протоколы UDP или TCP. OSPF имеет свой код (89) в протокольном поле IP-заголовка. Код TOS (type of service) в IP-пакетах, содержащих OSPF-сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF. Маршрутизация в этом протоколе определяется IP-адресом и типом сервиса. Так как протокол не требует инкапсуляции пакетов, сильно облегчается управление сетями с большим количеством бриджей и сложной топологией (исключается циркуляция пакетов, сокращается транзитный трафик). Автономная система может быть поделена на отдельные области, каждая из которых становится объектом маршрутизации, а внутренняя структура снаружи не видна. Этот прием позволяет значительно сократить необходимый объем маршрутной базы данных. В OSPF используется термин опорной сети (backbone) для коммуникаций между выделенными областями. Протокол работает лишь в пределах автономной системы. В пределах выделенной области может работать свой протокол маршрутизации.
