маршрутизатор 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. Алгоритм поиска кратчайшего пути

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

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

Концепция кратчайшего пути (shortest path) требует некоторого пояснения. Один из способов измерения длины пути состоит в подсчете количества транзитных участков. В этом случае пути ABC и ABE на илл. 5.7 имеют одинаковую длину. Можно измерять расстояния в километрах. Тогда получается, что ABC гораздо длиннее, чем ABE (предполагается, что рисунок изображен с соблюдением пропорций).

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

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

Известно несколько алгоритмов вычисления кратчайшего пути между двумя узлами графа. Один из них был создан знаменитым Дейкстрой (Dijkstra) в 1959 году. Алгоритм находит кратчайшие пути между отправителем и всеми

Илл. 5.7. Первые шесть шагов вычисления кратчайшего пути от A к D. Стрелка указывает на рабочий узел

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

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

#define MAX_NODES 1024                   /* максимальное количество узлов */

#define INFINITY 1000000000              /* число, превышающее длину максимального пути */

int n, dist[MAX_NODES][MAX_NODES];       /* dist[i][j] – это расстояние от i до j */

void shortest_path(int s, int t, int path[])

{ struct state {                         /* рабочий путь */

      int predecessor;                   /* предыдущий узел */

      int length;                        /* расстояние от источника до этого узла */

      enum {permanent, tentative} label; /* метка состояния */

} state[MAX_NODES];

int i, k, min;

struct state *p;

for (p = &state[0]; p < &state[n]; p++) { /* инициализация состояния */

      p->predecessor = –1;

      p->length = INFINITY;

      p->label = tentative;

}

state[t].length = 0; state[t].label = permanent;

k = t;                                  /* k – начальный рабочий узел */

do {                                    /* Есть ли лучший путь от k? */

      for (i = 0; i < n; i++)            /* У этого графа n узлов */

             if (dist[k][i] != 0 && state[i].label == tentative) {

                    if (state[k].length + dist[k][i] < state[i].length) {

                          state[i].predecessor = k;

                          state[i].length = state[k].length + dist[k][i];

                    }

             }

      /* Поиск узла, предварительно помеченного наименьшей меткой */

      k = 0; min = INFINITY;

      for (i = 0; i < n; i++)

             if (state[i].label == tentative && state[i].length < min) {

                    min = state[i].length;

                    k = i;

             }

      state[k].label = permanent;

} while (k != s);