Сети ЭВМ и телекоммуникации. Баканов В.М. - 37 стр.

  5 Лабораторная работа 5. Изучение   алгоритма   маршрутизации   OSPF
    (Open Shortest Path First)

  5.1 Цель работы – практическое изучение функционирования одного из
наиболее мощных алгоритмов маршрутизации OSPF (Open Shortest Path
First).

   5.2 Теоретические основы. Конечная цель маршрутизации состоит в дос-
тавке пакетов в пункт назначения при максимальной эффективности [1]. Ко-
личественно эффективность может быть выражена, например, средневзве-
шенной суммой времен доставки сообщений (при нижнеограниченной веро-
ятности доставки). Выбор одного из возможных в маршрутизаторе направле-
ний зависит от топологии сети (а она обычно динамична вследствие, напр.,
неизбежного временного выхода из строя некоторых узлов), длин очередей в
узлах коммутации, интенсивности потоков данных и т.п.
   Алгоритм маршрутизации неизбежно должен включать процедуры [1,3]:

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

   Если при расчете TM используется информация только о состоянии дан-
ного узла, то алгоритм маршрутизации является изолированным; при исполь-
зовании данных о всей сети – глобальным. Если ТМ (динамически) отслежи-
вает состояние сети – алгоритм является адаптивным, иначе – фиксирован-
ным (статическим), а при редких изменениях в ТМ – квазистатическим
(при статическом маршрутизировании изменения в ТМ вносит администра-
тор сети).
   Невозможно представить более простого алгоритма маршрутизации, чем
обладающий свойством изолированности и статичности. При использовании
анализа длины очереди сообщений в каждом маршрутизаторе алгоритм на-
зывается алгоритмом кратчайшей очереди (пакеты посылаются по направ-
лению, в котором для данного узла длина очереди минимальна). Лавинный
алгоритм является многопутевым и основан на рассылке копий пакета по
всем возможным направлениям (если в данном направлении данный пакет
уже проходил, вторичное прохождение не допускается – пакет уничтожает-
ся).
   Широко используются протоколы маршрутизации RIP (Routing Informa-
tion Protocol, RFC 1058, RFC 1388) и OSPF (Open Shortest Path First, RFC
1247). Первый использует метод рельефов, основан на алгоритме Беллмана-
                                      37