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

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

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

• оптимальность – способность алгоритмов маршру­тизации выбирать «наилучший» маршрут;

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

• живучесть и стабильность – надежность функционирования в случае отказов аппаратуры;

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

• гибкость – умение быстро адаптироваться к изменению полосы, размером очереди.

На рис. 4.7 приведена классификация алгоритмов маршрутизации.

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

Рисунок 4.7

При маршрутизации по предыдущему опыту используется информация, которая накапливается в каждом маршрутизаторе (узле коммутации). Каж­дый пакет снабжен счетчиком, который определяет количество узлов, кото­рое он прошел. Накапливание этих данных позволяет создать таблицу, спомощью которой выбирается соответствующий маршрут. Этот алгоритм позволяет приспособиться к изменению топологии сети, но с большой за­держкой. При фиксированной маршрутизации алгоритм работает на основе анализа таблицы маршрутов, которая, как правило, создается сетевым ад­министратором, причем возможно составление таких таблиц с использова­нием альтернативных путей доставки информации к точке назначения. На­личие альтернативных путей позволяет повысить надежность сети при от­казе какого-либо из путей. Естественно, что статическая маршрутизация не позволяет учитывать изменяющуюся нагрузку сети, что приводит к повы­шению времени доставки пакета, если он попадает в перегруженный узел. Динамическая маршрутизация учитывает изменение топологии и состава сети. В этом случае каждый маршрутизатор получает информацию об из­менении топологии и изменении нагрузки в сети. При локальной маршру­тизации используется информация о состоянии не всей сети, а только опре­деленного конечного числа узлов, информация других узлов не учитывает­ся. Распределенная маршрутизация учитывает информацию, которая посту­пает из соседних узлов. Централизованная маршрутизация учитывает ин­формацию, поступающую из главного узла, причем каждый маршрутизатор передает информацию о своем состоянии в центральный узел, который ана­лизирует ее и передает каждому узлу в виде измененной таблицы маршрутизации. Гибридная маршрутизация предполагает использование как цен­трализованной, так и распределенной маршрутизации, чтобы не перегру­жать сеть служебной информацией.