Протоколы Internet



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


  • Устанавливаем множество узлов 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)

    Таблица 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) для коммуникаций между выделенными областями. Протокол работает лишь в пределах автономной системы. В пределах выделенной области может работать свой протокол маршрутизации.




    Содержание  Назад  Вперед