Каким образом маршрутизатор строит таблицу маршрутизации? Какие алгоритмы построения этой таблицы Вы знаете. В чем заключается суть каждого алгоритма?

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

· действительный адрес или множество действительных адресов в сети;

· информацию, вычисленную протоколом маршрутизации или необходимую для его функционирования;

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

Алгоритмы маршрутизации могут быть: 1) статическими или динамическими; 2) одномаршрутными или многомаршрутными; 3) одноуровневыми или иерархическими; 4) внутридоменными или междоменными; 5) одноадресными или групповыми.

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

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

В данном разделе описаны два алгоритма вычисления кратчайших путей [7]: алгоритм, предложенный Э.Дейкстрой (алгоритм А), и алгоритм Флойда (алгоритм В). Оба эти алгоритма, являющиеся централизованными, или их версии применяются в различных действующих сетях для выполнения функций выбора маршрутов.