Алгоритмы маршрутизации. Цели разработки

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

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

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

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

Живучесть и стабильность - д четко функционировать в случае неординарных или непредвиденных обстоятельств: отказ аппаратуры, условия высок нагрузки, некорректные реализации.

Быстрая сходимость - это процесс соглашения между всеми роутерами по оптимальным маршрутам. Когда какое-нибудь событие в сети приводит к тому, что маршруты или отвергаются, или становятся доступными, роутеры рассылают сообщ об обновлении маршр-ции. Алгоритмы маршрутизации, кот сходятся медленно, м привести к образованию петель маршр-ии или выходам из строя сети. На Рис. изображена петля маршрутизации. В момент времени t1 к роутеру 1 прибывает пакет. Роутер 1 уже был обновлен и поэтому знает, что оптим маршрут к пункту назначения требует, чтобы след остановкой был роутер 2. Роутер 1 пересылает пакет в роутер 2. Роутер 2 еще не был обновлен, поэтому он полагает, что след оптимальной пересылкой д б роутер 1.

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

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

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

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

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

Одноуровневые или иерархические алгоритмы

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

Алг с интеллектом в главной вычисл машине / в роутере

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

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

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

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

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

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