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

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

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

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

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

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

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

С увеличением количества маршрутизаторов, а, следовательно, и числа подсетей в больших корпоративных сетях, число записей в таблице маршрутизации также увеличивается. Это приводит к возрастанию времени поиска в ней нужной информации, что в свою очередь уменьшает скорость передачи данных и приводит к снижению пропускной способности сети в целом. Рациональным решением данной проблемы является следующий принцип построения таблицы: в нее вносятся только адреса маршрутизаторов, связывающих данную сеть с "соседними" сетями, а все остальные сети идентифицируются в таблице специальной записью - "маршрутизатор по умолчанию", через который пролегает путь ко всем остальным сетям. Пример построения таблицы маршрутизации для сети 1 (рис.5.2) представлен в таблице 5.1

Таблица 5.1. Пример построения таблицы маршрутизации

Наименование сети - получателя пакета

Адрес маршрутизатора

Расстояние до сети получателя

Флаг состояния канала

Сеть 2

1

1

U

По умолчанию

3

-

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

протоколы distant vector, предусматривающие передачу информации о маршрутах периодически, через установленные интервалы времени. Одним из примеров реализации такой технологии является протокол маршрутизации RIP (Routing Information Protocol), применяемый в сетях небольшого размера;

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

Прежде чем пакет будет передан через сеть, необходимо установить виртуальное соединение между абонентами сети. Существует два типа виртуальных соединений - коммутируемый виртуальный канал Switched Virtual Circuit, SVC) и постоянный виртуальный канал (Permanent Virtual Circuit, PVC). При создании коммутируемого виртуального канала коммутаторы сети настраиваются на передачу пакетов динамически, по запросу абонента, а создание постоянного виртуального канала происходит заранее.

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