Принципы и протоколы маршрутизации в составных сетях

Важнейшей задачей сетевого уровня является маршрутизация — передача пакетов между двумя конечными узлами в составной сети.

Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности.

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

Алгоритмы маршрутизации включают процедуры:

1. измерение и оценивание параметров сети;
2. принятие решения о рассылке служебной информации;
3. расчет таблиц маршрутизации (ТМ);
4. реализация принятых маршрутных решений.

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

Простейший алгоритм - изолированный, статический.

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

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

Наиболее широко используемые протоколы маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). Метод RIP иначе называется методом рельефов. Он основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии.

OSPF - алгоритм динамической маршрутизации, в котором информация о любом изменении в сети рассылается лавинообразно.

Алгоритм Беллмана-Форда относится к алгоритмам DVA (Distance Vector Algorithms). В DVA рельеф Ra(d) - это оценка кратчайшего пути от узла a к узлу d. Оценка (условно назовем ее расстоянием) может выражаться временем доставки, надежностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. В ТМ узла а каждому из остальных узлов отводится одна строка со следующей информацией:

1. узел назначения;
2. длина кратчайшего пути;
3. номер N ближайшего узла, соответствующего кратчайшему пути;
4. список рельефов от а к d через каждый из смежных узлов.

Рассмотрим принципы маршрутизации на примере рисунка.

В этой сети 8 маршрутизаторов объединяют 8 сетей в общую сеть; SI, S2, ... , S8 — это номера сетей. Маршрутизаторы имеют по несколько портов (минимум по два), к которым присоединяются сети. Каждый порт маршрутизатора можно рассматривать как отдельный узел сети: он имеет собственный сетевой адрес и собственный локальный адрес в той подсети, которая к нему подключена. Например, маршрутизатор под номером 1имеет три порта, к которым подключены сети SI, S2, S3. На рисунке сетевые адреса этих портов обозначены как Ml(l), Ml(2) и М1(3). Порт М1(1) имеет локальный адрес в сети с номером S1, порт Ml(2) — в сети S2, а порт М1(3) — в сети S3. Таким образом, маршрутизатор можно рассматривать как совокупность нескольких узлов, каждый из которых входит в свою сеть. Как единое устройство маршрутизатор не имеет ни отдельного сетевого адреса, ни какого-либо локального адреса.

В сложных составных сетях почти всегда существует несколько альтернативных маршрутов для передачи пакетов между двумя конечными узлами. Маршрут — это последовательность маршрутизаторов, которые должен пройти пакет от отправителя до получателя. Так, пакет, отправленный из узла А в узел В, может пройти через маршрутизаторы 8, 5, 4 и 1 или маршрутизаторы 8,7 и 3.