Алгоритмы маршрутизации. Принцип оптимальности маршрута. Выбор кратчайшего пути. Заливка

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

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

Известно несколько алгоритмов вычисления кратчайшего пути между двумя узлами графа. Один из них был создан знаменитым Дейкстрой в 1959 году. Он находит кратчайшие пути между отправителем и всеми возможными адресами назначения в данной сети. Каждый узел помечается (в скобках) расстоянием до него от узла отправителя по наилучшему известному пути. Эти расстояния должны быть неотрицательными; если они основаны на реальных величинах (пропускная способность и время задержки) — это условие будет выполнено. Вначале пути неизвестны, поэтому все узлы помечаются символом бесконечности. По мере работы алгоритма и нахождения путей отметки узлов изменяются, показывая оптимальные пути. Отметка может быть постоянной или экспериментальной. Вначале все отметки являются ориентировочными. Когда выясняется, что отметка действительно соответствует кратчайшему возможному пути, она становится постоянной и в дальнейшем не изменяется.

Мы хотим найти кратчайший путь от A к D. Для начала мы черным кружком помечаем узел A как постоянный. Затем мы исследуем все соседние с ним узлы, указывая около них расстояние до узла A. Если отыскивается более короткий путь к какому-либо узлу, то вместе с указанием расстояния в отметке меняется и узел, через который прошел более короткий путь. Таким образом, позднее можно восстановить весь путь. Если бы в сети было более одного кратчайшего пути от A до D и мы хотели бы найти их все, нам нужно было бы запоминать все узлы, которые позволяют дойти до данного узла, пройдя одинаковое расстояние. Рассмотрев все соседние с A узлы, мы помечаем ближайший узел как постоянный. Этот узел становится новым рабочим узлом. Теперь мы повторяем ту же процедуру с узлом B, исследуя все его соседние узлы. Если сумма расстояния от узла B и значения отметки в узле B (расстояния от A до B) оказывается меньше, чем отметка у исследуемого узла (уже найденное другим путем расстояние от A), это значит, что найден более короткий путь, поэтому пометка узла изменяется. После того как все соседние с рабочим узлы исследованы и временные отметки при необходимости изменены, по всему графу ищется узел с наименьшей временной от- меткой. Этот узел помечается как постоянный и становится текущим рабочим узлом.

На данном этапе узел E только что был отмечен как постоянный. Предположим, что существует более короткий путь, нежели ABE, например AXYZE (для некоторых X и Y). В этом случае есть две возможности — либо узел Z уже сделан постоянным, либо еще нет. Если да, значит, узел E уже проверялся, когда узел Z был сделан постоянным и, следовательно, рабочим узлом. В этом случае путь AXYZE уже исследовался. Теперь рассмотрим случай, когда узел Z все еще помечен как временный. Если отметка узла Z больше или равна пометки узла E, путь AXYZE не может быть короче, чем путь ABE. Если же отметка узла Z меньше пометки узла E, то тогда узел Z должен был стать постоянным раньше узла E, и узел E проверялся бы с узла Z.

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

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

Чтобы предотвратить неограниченный рост размера списка, можно снабдить все списки счетчиком k, показывающим, что все порядковые номера вплоть до k уже встречались. И когда приходит пакет, можно очень легко проверить, был ли он уже передан, сравнивая его порядковый номер с k; при положительном ответе такой пакет отвергается. Кроме того, не нужно хранить весь список до k, поскольку этот счетчик очень действенно подытоживает его.

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