Протоколы Internet


Протокол OSPF (алгоритм Дикстры) - часть 2


  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 приведена на нижней части рис. 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)

Таблица 4.2.11.2.1 может иметь совершенно иное содержимое для какого-то другого вида сервиса, выбранные пути при этом могут иметь другую топологию. Качество сервиса (QoS) может характеризоваться следующими параметрами:

  • пропускной способностью канала;
  • задержкой (время распространения пакета);
  • числом дейтограмм, стоящих в очереди для передачи;
  • загрузкой канала;
  • требованиями безопасности;
  • типом трафика;
  • числом шагов до цели;
  • возможностями промежуточных связей (например, многовариантность достижения адресата).

Определяющими являются три характеристики: задержка, пропускная способность и надежность. Для транспортных целей OSPF использует IP непосредственно, т.е. не привлекает протоколы UDP или TCP. OSPF имеет свой код (89) в протокольном поле IP-заголовка. Код TOS (type of service) в IP-пакетах, содержащих OSPF-сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF. Маршрутизация в этом протоколе определяется IP-адресом и типом сервиса. Так как протокол не требует инкапсуляции пакетов, сильно облегчается управление сетями с большим количеством бриджей и сложной топологией (исключается циркуляция пакетов, сокращается транзитный трафик). Автономная система может быть поделена на отдельные области, каждая из которых становится объектом маршрутизации, а внутренняя структура снаружи не видна (узлы на рис. 4.2.11.2.1 могут представлять собой как отдельные ЭВМ или маршрутизаторы, так и целые сети). Этот прием позволяет значительно сократить необходимый объем маршрутной базы данных. В OSPF используется термин опорной сети (backbone) для коммуникаций между выделенными областями. Протокол работает лишь в пределах автономной системы. В пределах выделенной области может работать свой протокол маршрутизации.




Начало  Назад  Вперед



Книжный магазин