Компьютерные сети. 6-е изд.

Алгоритмы маршрутизации можно разделить на два основных класса: неадаптивные и адаптивные. Неадаптивные алгоритмы (nonadaptive algorithms) не учитывают текущую топологию и не измеряют трафик. Вместо этого путь для каждой пары станций определяется заранее, в автономном режиме, а список маршрутов загружается в маршрутизаторы во время загрузки сети. Эта процедура называется статической маршрутизацией (static routing). Она не реагирует на сбои, поэтому обычно используется в тех случаях, когда выбор маршрута очевиден. Например, маршрутизатор F на илл. 5.3 должен отправлять пакеты в сеть, на маршрутизатор E, независимо от конечного адреса назначения.

Адаптивные алгоритмы (adaptive algorithms), напротив, реагируют на изменения топологии, а иногда и на загруженность линий. Такие алгоритмы динамической маршрутизации (dynamic routing) различаются по нескольким параметрам. Они могут получать информацию от соседних маршрутизаторов или от всех маршрутизаторов сети. Некоторые меняют путь при смене топологии, другие — через определенные равные интервалы времени по мере изменения нагрузки. Наконец, для оптимизации они используют разные показатели: расстояние, количество транзитных участков (переходов) или ожидаемое время передачи.

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

5.2.1. Принцип оптимальности

Прежде чем перейти к конкретным алгоритмам, сформулируем общее утверждение, описывающее оптимальные маршруты независимо от топологии или трафика, — принцип оптимальности (optimality principle); см. работу Беллмана (Bellman, 1957).

Согласно этому принципу, если маршрутизатор J расположен на оптимальном пути от маршрутизатора I до маршрутизатора K, то оптимальный путь от J до K частично с ним совпадет. Чтобы убедиться в этом, обозначим часть пути от I до J как r1, а остальную часть пути — r2. Если бы существовал более выгодный путь от J до K, чем r2, то его можно было объединить с r1, чтобы улучшить путь от I до K, что противоречит первоначальному утверждению о том, что r1r2 — оптимальный путь.

Применив данный принцип, можно представить набор оптимальных маршрутов от всех источников ко всем обозначенным адресатам в виде дерева с получателем в качестве корня. Оно называется входным деревом (sink tree). На илл. 5.6 (б) изображено такое дерево для сети, показанной на илл. 5.6 (а). Расстояние в этом случае измеряется количеством транзитных участков. Цель любого алгоритма маршрутизации состоит в том, чтобы обнаружить и использовать входные деревья для всех маршрутизаторов.

Илл. 5.6. (а) Сеть. (б) Входное дерево для маршрутизатора B

Обратите внимание, что входное дерево не всегда уникально; у одной сети может быть несколько деревьев с идентичной длиной пути. Если выбрать все возможные маршруты, получится более общая структура под названием направленный ациклический граф (directed acyclic graph, DAG). В таких графах нет циклов. Для удобства мы также будем называть их входным деревом. В обоих случаях предполагается, что пути не мешают друг другу (к примеру, затор на одном маршруте не приводит к изменению другого).

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

5.2.2. Алгоритм поиска кратчайшего пути

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

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