i = 0; k = s;

do {path[i++] = k; k = state[k].predecessor; } while (k >= 0);

}

Илл. 5.8. Алгоритм Дейкстры для вычисления кратчайшего пути по графу

Проверив все соседние с A узлы, мы просматриваем временно помеченные узлы во всем графе и делаем узел с наименьшей меткой постоянным (илл. 5.7 (б)). Он становится новым рабочим узлом.

Теперь мы повторяем ту же процедуру с узлом B, исследуя все ближайшие узлы. Сначала складываем расстояние от B до соседнего узла и значение метки B (то есть расстояние от A до B). Если полученная сумма меньше, чем метка исследуемого узла (то есть расстояние от A, уже найденное на предыдущем этапе), значит, обнаружен более короткий путь, поэтому метка узла меняется.

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

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

Теперь рассмотрим ситуацию, когда узел Z все еще помечен как временный. Если метка узла Z больше или равна метке узла E, путь AXYZE не может быть короче, чем путь ABE. Если же метка узла Z меньше метки узла E, тогда узел Z стал бы постоянным раньше узла E и узел E проверялся бы с узла Z.

Пример реализации алгоритма представлен на илл. 5.8. Глобальные переменные n и dist описывают граф и инициализируются до вызова функции shortest_path. Единственное отличие программы от описанного выше алгоритма заключается в том, что вычисление кратчайшего пути в программе начинается не с узла-источника s, а с конечного узла t.

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

5.2.3. Лавинная адресация

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

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

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

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

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

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

5.2.4. Маршрутизация по вектору расстояний

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

Алгоритмы маршрутизации по вектору расстояний (distance vector routing) работают, опираясь на таблицы (то есть векторы), поддерживаемые всеми маршрутизаторами. Эти таблицы содержат сведения об известных кратчайших путях к каждому из возможных адресатов и о том, какое соединение следует использовать. Для обновления содержимого таблиц производится обмен информацией с соседними маршрутизаторами. В результате любой маршрутизатор знает кратчайший путь до всех получателей.

Метод маршрутизации по вектору расстояний иногда называют в честь его авторов распределенным алгоритмом Беллмана — Форда (Bellman — Ford); см. работы Беллмана (Bellman, 1957), а также Форда и Фалкерсона (Ford and Fulkerson, 1962). Изначально он применялся в сети ARPANET, а в интернете был известен под названием RIP.

Все