Сети с маршрутизаторами. Виды алгоритмов маршрутизации. Структура таблицы маршрутизации.

Маршрутизатор имеет несколько портов и должен для каждого поступающего пакета решить — отфильтровать его или передать на какой-то другой порт.

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

Каждый порт маршрутизатора рассматривается, как отдельный узел сети. Другие узлы должны знать его адрес и направлять пакеты для передачи в другие подсети на этот адрес, а не просто выдавать их в канал (как при прозрачных мостах).

Рассмотрим принципы маршрутизации на примере сети, изображенной на рис. 1. Здесь S1..S10 — подсети, M1..M13 — маршрутизаторы. Порты маршрутизаторов будем обозначать сочетанием имени маршрутизатора и сети, например, M5/S2 — порт маршрутизатора M5, подключенный к сети S2.

Таблица маршрутизации для маршрутизатора M7 приведена в табл. 1

Рис. 1. Составная сеть с маршрутизаторами.

Таблца №1. Таблица маршрутизации для маршрутизатора М7.

Алгоритм маршрутизации — правило назначения выходной линии связи (порта) на основе данных, содержащихся в заголовке пакета, данных, описывающих состояние маршрутизатора и сети в целом.

Эффективность алгоритмов характеризуется:

— временем доставки пакетов,

— нагрузкой на сеть,

— затратами ресурсов маршрутизаторов (времени и памяти).

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

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

Алгоритмы одношаговой маршрутизации бывают простые, фиксированные и адаптивные. Решение, принимаемое при простой маршрутизации не зависит ни от топологии, ни от состояния сети. Основные варианты простой маршрутизации:

— случайная — передача пакета на любой порт, кроме исходного;

— по кратчайшей очереди — передача пакета на порт с самой короткой очередью; - лавинная — передача пакета на все порты, кроме исходного;

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

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

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

— локальная — только на основе информации о состоянии своих выходных каналов и очередях пакетов;

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

— на основе векторов расстояний (или дистанционно-векторная, англ. Distance Vector Algorithms) — рассылается вектор из метрик соседних сетей;

— на основе состояния связей (англ. Link State Algorithms) — каждый узел строит полный граф сети (передаются ребра графа маршрутизатор-маршрутизатор и маршрутизатор-сеть);

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

— гибридная — централизованная+локальная (если путь в таблице один, то пакет отправляется по нему, иначе — на порт с самой короткой очередью).