Маршрутизация по состоянию канала

 

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

       Когда состояние канала изменяется, устройство, обнаружившее такое изменение, формирует извещение о состоянии канала (Link-State Andvertisement — LSA), относящееся к этому каналу (маршруту), и рассылает его всем соседствующим маршрутизаторам. Каждый маршрутизатор получает копию извещения о состоянии канала и на этом основании обновляет свою базу состояния каналов (топологическую базу), после чего пересылает копию извещения всем своим соседям. Такая массовая рассылка извещения нужна, чтобы гарантировать, что все маршрутизаторы обновят свои базы данных и создадут обновленную таблицу маршрутизации, которая отражает новую топологию (рис.1).

Рис.1. Протоколы маршрутизации на основе состояния канала

       База данных состояния канала используется для обнаружения наилучшего сетевого пути. Маршрутизация с учетом состояния канала основана на алгоритме первоочередного определения кратчайшего маршрута (Shortest Path First — SPF) Дейкстра  для построения SPF-дерева, на основе которого принимается решение о том, какой маршрут является наилучшим. Наилучший (кратчайший) маршрут выбирается из дерева первоочередного определения кратчайшего маршрута и помещается в таблицу маршрутизации.

Описание алгоритма Дейкстры.

       Алгоритм Дейкстры вычисляет кратчайший путь между двумя точками в сети, используя граф по методу узлов и границ. Алгоритм разделяет узлы на два множества: пробные и постоянные. Он выбирает узлы, делает их пробными, анализирует их и, если они проходят по критериям, делает их постоянными. 

       Работа алгоритма поясняется на рис.2. На рис.2.а. приведен пример сети. Эта же сеть представлена в виде графа. На этом графе нанесена назначенная стоимость прохождения по участкам. Далее на рис.2.б. приводится вычисление накопленной стоимости при прохождении.

Рис.2. Вычисление стоимости наикратчайшего участка

       Сам алгоритм заключается в прохождении графа и вычислении накопленной стоимости. Ниже рассматривается порядок вычисления наикратчайшего пути. Номер следующего узла представляет накопленную стоимость от корневого узла. Заметим, что сеть достигает маршрутизатора E через два направления с накопленной стоимостью 14 и 10. При этом сохраняется направление с накопленной стоимостью 10, а второе удаляется.

       Каждый маршрутизатор применяет метод наикратчайшего пути по дереву для построения своей таблицы маршрутизации. Таблица маршрутизации показывает стоимость достижения каждого узла в зоне, маршрутизатор использует извещения: суммарной линии сети, суммарной линии пограничного маршрутизатора и внешней линии. Табл.1. показывает таблицу маршрутизации для маршрутизатора A согласно результатам вычислений по рис.2.в.

Табл.1. Таблица маршрутизации для маршрутизатора A

Сеть Стоимость Следующий маршрутизатор
N1 5
N2   7 C
N3 10 D
N4 11 B
N5 15 D

 

 

 

 

 

 

 

 

Контрольные вопросы

  1. Принцип маршрутизации по состоянию канала
  2. Какой алгоритм используется в маршрутизации, учитывающая состояние канала?
  3. Суть алгоритма Дейкстры
  4. Что происходит, когда сеть имеет два маршрута с разной накопленной стоимостью?