Алгоритмы маршрутизации. 
Информатика

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

Рассмотрим некоторые классификационные признаки алгоритмов маршрутизации, которые отражают их свойства и особенности.

По степени обновляемости маршрутов выделяют:

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

По количеству используемых маршрутов различают:

• • одномаршрутные алгоритмы, обеспечивающие передачу пакетов по одному и тому же маршруту;
• • многомаршрутные алгоритмы, в которых каждому из возможных маршрутов в зависимости от его пропускной способности и других показателей назначается приоритет. Пакет пересылается по маршруту, обладающему наивысшим приоритетом. Этот маршрут обычно является основным, а остальные — резервными. Многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям.

Классификационным признаком алгоритмов может служить используемая структура маршрутизации, при этом:

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

Задачу выбора маршрута решают не только маршрутизаторы, но и оконечные узлы, поэтому выделяют два вида алгоритмов:

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

По способу обмена информацией о маршрутах различают:

• • дистанционно-векторные алгоритмы или алгоритмы Бэлмана — Форда, которые обеспечивают пересылку всей или части маршрутной таблицы маршрутизатора своим ближайшим соседям;
• • алгоритмы состояния канала, направляющие только ту часть маршрутной таблицы, которая описывает состояние собственных каналов маршрутизатора во все узлы объединенной сети. Их также называют алгоритмами первоочередности наикратчайшего маршрута. Отличительная особенность алгоритмов — более быстрая сходимость, меньшая склонность к образованию петель маршрутизации по отношению к дистанционно-векторным. Однако алгоритмы состояния канала характеризуются более сложными расчетами, требуя большей процессорной мощности и памяти.

Сведения о протоколах маршрутизации

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