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

По числу уровней алгоритмы делятся на одноуровневые и иерархические.

Одноуровневые алгоритмы принимают все маршрутизаторы равными по отношению друг к другу.

Иерархические алгоритмы маршрутизации разбивают сеть на логические группы.

По интеллектуальности, т.е. в зависимости от того, какой компонент сети – маршрутизатор или узел - принимает решение о пути продвижения пакета, различают одношаговую и многошаговую маршрутизацию (маршрутизация от источника, source routing).

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

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

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

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

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

Выделяют следующие типы простой маршрутизации:

• Случайная - пакет посылается в любом направлении, кроме исходного,

• По кратчайшей очереди - пакет посылается в направлении с самой короткой очередью,

• Лавинная - пакет широковещательно посылается по всем возможным направлениям, кроме исходного,

• по предыдущему решению – пакет посылается в том направлении, куда отправлялись предыдущие пакеты от этого источника (если пакет - первый, то случайно или по кратчайшей очереди).

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

Фиксированная маршрутизация может быть одномаршрутной (однопутевой) и многомаршрутной (многопутевой).

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

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

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

Различают следующие виды адаптивной маршрутизации:

• Локальная – осуществляется маршрутизатором на основе информации о состоянии своих выходных каналов и очередях пакетов,

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

• Централизованная – в сети существует выделенным центром маршрутизации, собирающем информацию о состоянии узлов и каналов и рассылающем ее всем узла,

• Гибридная – сочетание централизованной и локальной маршрутизации,

• На основе векторов расстояний (дистанционно-векторная, Distance Vector Algorithms, DVA) – каждый маршрутизатор периодически широковещательно рассылает по сети вектор расстояний от данного маршрута до известных ему узлов, а возможно и время прохождения пакетов. При получении данного вектора каждый маршрутизатор корректирует содержащуюся в нем информацию, наращивая расстояния до узлов на расстояние до того маршрутизатора, от которого пришел вектор.

• На основе состояния связей (Link State Algorithms LSA) - каждый маршрутизатор обеспечивается информацией, достаточной для построения точного графа связей сети.