Алгоритмы маршрутизации

Процесс маршрутизации включает две основные функции: определение оптимального маршрута и транспортировка порций информацией (обычно называемых пакетами) по сети.

Определение маршрута может быть основано на сравнении различных характеристик маршрутов, называемых метриками (metrics), или сравнениях комбинаций метрик.

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

Поддержка таблиц маршрутизации осуществляется с помощью обмена сообщениями между маршрутизаторами. Одним из таких сообщений является сообщение об изменении маршрутизации (routing update message). Другим видом сообщения является объявление о состоянии канала (link state advertisement). Анализируя эти сообщения, маршрутизатор может построить детальную схему сетевой топологии и определить оптимальный маршрут к адресату.

Алгоритм транспортировки относительно простой и практически одинаков для большинства протоколов маршрутизации. Для описания процесса передачи пакетов ISO разработала иерархическую терминологию.

Термин ES – конечная система (End System) относится к сетевому узлу, не содержащему маршрутизатора, а термин IS – промежуточная система (Intermediate System) относится к маршрутизатору. IS затем подразделяются на внутридоменные IS (intradomain IS) и междоменные IS (interdomain IS).

Для иерархической сети используется следующая терминология:

область (area) – группа смежных сетей и связанных с ними хостов;

домен (domain) – группа связанных между собой областей (домены маршрутизации обеспечивают полный доступ ко всем входящим в них ES);

маршрутизация уровня 1 (level 1 routing) – маршрутизация внутри областей первого уровня;

маршрутизация уровня 2 (level 2 routing) – маршрутизация между областями первого уровня.

Домены маршрутизации называются также AS – автономными системами (Autonomous Systems).

В большинстве случаев, когда ES определяет, что необходимо послать пакет другому ES, он узнает адрес IS и посылает пакет с канальным адресом IS (на подуровне MAC), но с сете­вым адресом ES. IS определяет, знает ли он, как послать пакет в узел назначения. Если мар­шрута к ES нет в таблице маршрутизации, пакет обычно уничтожается, иначе он переда­ется либо в ES (если он непосредственно связан с данным IS), либо другому IS, и процесс по­вторяется.

Классификация алгоритмов маршрутизации и общие сведения

Алгоритмы маршрутизации можно дифференцировать, основываясь на нескольких ключевых характеристиках. Во-первых, на работу результирующего протокола маршрутизации влияют конкретные задачи, которые решает разработчик алгоритма. Во-вторых, существуют различные типы алгоритмов маршрутизации, и каждый из них по-разному влияет на сеть и ресурсы маршрутизации. И, наконец, алгоритмы маршрутизации используют разнообразные показатели, которые влияют на расчет оптимальных маршрутов. В следующих разделах анализиру­ются эти атрибуты алгоритмов маршрутизации.

Цели разработки алгоритмов маршрутизации:

При разработке алгоритмов маршрутизации часто преследуют одну или несколько из перечисленных ниже целей:

· Оптимальность;

· Простота и низкие непроизводительные затраты;

· Живучесть и стабильность;

· Быстрая сходимость;

· Гибкость.

Оптимальность, вероятно, является самой общей целью разработки. Она характеризует способность алгоритма маршрутизации выбирать «наилучший» маршрут. Наилучший маршрут зависит от показателей и от «веса» этих показателей, используемых при проведении расчета. Например, алгоритм маршрутизации мог бы использовать несколько пересылок с определен­ной задержкой, но при расчете «вес» задержки может быть им оценен как очень значитель­ный. Естественно, что протоколы маршрутизации должны строго определять свои алгоритмы расчета показателей.

Дата добавления: 2014-10-15