Классификация алгоритмов маршрутизации.

Протоколы маршрутизации могут быть реализованы с помощью алгоритмов маршрутизации, которые классифицируются по следующим классификационным признакам:

1. По способу выбора наилучшего маршрута

Все алгоритмы маршрутизации делятся на 2 группы:

1. Одношаговые алгоритмы маршрутизации

Каждый маршрутизатор при выборе маршрута определяет только одно звено этого маршрута. Ответственность только за один шаг этого маршрута.

Одношаговые алгоритмы реальней на этапе инициализации

2. Многошаговые алгоритмы маршрутизации (алгоритм маршрутизации от источника)

Весь маршрут задается в уже отправленном пакете узлом источника. Многошаговые алгоритмы считаются перспективней

2. По способу построения таблиц маршрутизации

   1. Алгоритмы простой маршрутизации

Таблиц маршрутизации как правило нет, или таблицы являются очень примитивными (они не передают никакой маршрутной информации)

1. Алгоритмы случайной маршрутизации – пакет посылается в случайном направлении

2. Лавинная маршрутизация (алгоритмы заполнения) – пакеты посылаются во все выходные направления, во все порты

3. Алгоритмы скорейшей передачи (алгоритм горячей картошки) – как только маршрутизатор поучает пакет – он старается скорее его отослать

4. Алгоритмы кратчайшей очереди (наименьшей загрузки) – информация идет на порт, который наименее загружен

5. Алгоритм по предыдущему опыту – таблица маршрутизации очень примитивна, есть запись, дублирующая предыдущую передачу

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

2. Алгоритмы фиксированной и статической маршрутизации

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

1. Однопутевые (одномаршрутные, безальтернативные)

2. Многопутевые (многомаршрутные, допускающие альтернативу)

3. Адаптивные алгоритмы, = алгоритмы динамической маршрутизации

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

К Адаптивным алгоритмам предъявляются следующие требования:

1. Адитивность – скорость адаптивности алгоритма к изменениям в сети. Для достижения скорости алгоритмы должны быть простыми

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

3. Сходимость алгоритма – это когда алгоритм после некоторого времени приводит к однозначному результату.

1. По месту выбора маршрутов (маршрутного решения)

По месту выбора маршрутного решения все алгоритмы маршрутизации делятся на три класса:

1. Изолированные алгоритмы (локальные) – нет никакого обмена маршрутной информацией и каждый маршрутизатор принимает решение на основании той информации, которую он сам собрал.

2. Централизованные – вся маршрутная информация со всех маршрутизаторов стекается в сетевой маршрутный центр – он ответственный за определение оптимальных маршрутов и сбор маршрутной информации. Возможны 2 подхода:

1. Подход виртуального канала – маршрут определяется на основе оптимальной информации, посылаемой во все промежуточные маршрутизаторы. Недостатком является уязвимость маршрутного центра

2. Подход формирования по таблице для каждого маршрутизатора.

3. Распределенные – это самые распространенные алгоритмы, где все маршрутизаторы участвуют в сборе и распространении маршрутной информации и работа по выбору наилучшего маршрута распределена между всеми маршрутизаторами.

4. По виду информации которой обмениваются маршрутизаторы

Все алгоритмы делятся на 2 класса:

1. Дистанционно-векторные алгоритмы – RIP протокол (протокол маршрутной информации). В дистанционно-векторном: каждый маршрутизатор периодически всем своим соседям передаёт вектор сообщения, где указывает адреса всех известных ему подсетей и расстояние до них, в качестве (расстояния используется промежуточные узлы). Недостатки плохая адаптация к отказам маршрутизаторов, возможность возникновения маршрутных петель.

Каждый маршрутизатор периодически всем своим соседям передает вектор сообщений, где указывается адреса известных ему подсетей и расстояния до них от данного маршрутизатора.

В качестве метрики расстояний используется метрика Hap-ов (промежуточный приемников) и метрика надежности. Для RIP-протокола период Т_период= 30 сек

Недостатки:

1. Плохая адаптация к отказам маршрутизаторов, интерфейсов, подсетей.

2. Возможность возникновения маршрутных петель

3. Данный алгоритм используется для небольших сетей (количество ХАП-ов не больше 15 единиц)

Для устранения этих недостатков каждому маршруту присваивается время жизни (TTL=180 сек) за которое если информация не обновляется – то маршрут «умирает», прекращает действовать.

Если маршрутизатор вышел из строя – то в качестве расстояния указывается 16, то есть ∞

Главная причина всех недостатков – это получение информации через соседних маршрутизаторов, а не напрямую (это называется отсутствием полной нужной информации).

2. Алгоритмы состояния связи – OSPF протокол

OSPF протокол – Open Shortest Path First – открытый протокол кратчайшего маршрута – в стеке протокола TCP/IP.

NLSP протокол – Netware Link Services Protocol – используется для сетевых служб, указанных в различных подсетях, с целью управления – принадлежит стеку протоколов IPX/SPX.

IS-IS – Intermediate System to Intermediate System – подмножество модели OSI

Каждый маршрутизатор обеспечивается необходимой и точной (достаточной) информацией для построения адекватной (точной) топологии сети. Для точного построения графа-связи сети в данной топологии вершинами выступают маршрутизаторы и подсети.

Принцип действия:

Каждый маршрутизатор распространяет соседям о всех своих близких соседях:

1. Адрес соседней подсети

2. Тип интерфейса (М-М (маршрутизатор – марш) и М-S (марш – сеть) )

3. Метрика интерфейса (пропускные способности каждого из путей, время задержки и метрика надежности)

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

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

Существует три таблицы маршрутизации (каждый маршрутизатор и каждая подсеть имеют свой вес

Маршрутизатор не имеет сетевого адреса!!

Для проверки в каждый маршрутизатор пересылается сообщение каждые 10 сек и если ответа нет, то таблица корректируется без учета вышедшего из строя маршрутизатора (в т.ч. поэтому – адаптивный алгоритм).

Топология сети в течении длительной работы сети не меняется, информационные потоки тоже не меняются после их распределения, однако реально при стабильной топологии потоки могут меняться, именно поэтому более оптимальным является адаптивный алгоритм.

Cm = f (Функциональные сетевые компоненты ФСК)