Пример реализации алгоритма представлен на илл. 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.
Все маршрутизаторы используют и обновляют таблицу с записями обо всех маршрутизаторах сети. Каждая запись состоит из двух частей: оптимальная исходящая линия для данного получателя и предполагаемое расстояние или время передачи пакета. В качестве меры расстояния используется число переходов или другие параметры, которые применяются при вычислении кратчайшего пути.
Предполагается, что маршрутизаторы знают расстояние до каждого соседа. Если единицей измерения являются переходы, то оно равно одному переходу. Если же расстояние измеряется временем задержки распространения, то маршрутизатор может измерить его с помощью специального пакета ECHO (эхо). Адресат добавляет в него время получения и отправляет его обратно как можно скорее.
Допустим, в качестве единицы измерения используется время задержки, и маршрутизатор знает значение этого параметра относительно каждого соседа. Через каждые T мс все маршрутизаторы посылают своим соседям список с приблизительными задержками для каждого получателя. Они, разумеется, также получают подобный список от всех своих соседей. Допустим, одна из таких таблиц пришла от соседа X и в ней указывается, что время распространения от X до i равно Xi. Если маршрутизатор знает, что время передачи до X равно m, тогда задержка при передаче пакета маршрутизатору i через X составит Xi + m. Выполнив такие расчеты для всех своих соседей, маршрутизатор может выбрать наилучшие пути и записать это в новую таблицу. Обратите внимание, что старая таблица маршрутизации в расчетах не используется.
Процесс обновления таблицы проиллюстрирован на илл. 5.9. На илл. 5.9 (а) показана сеть. Первые четыре столбца на илл. 5.9 (б) показывают векторы задержек, полученные маршрутизатором J от своих соседей. Маршрутизатор A считает, что время передачи от него до B равно 12 мс, 25 мс до C, 40 мс до D и т.д. Допустим, J измерил или оценил задержки до своих соседей A, I, H и K как 8, 10, 12 и 6 мс соответственно.
Теперь рассмотрим, как J рассчитывает свой новый маршрут к маршрутизатору G. Он знает, что задержка до A составляет 8 мс, и при этом A думает, что от него до G данные дойдут за 18 мс. Таким образом, J знает, что если он станет
Илл. 5.9. (а) Сеть. (б) Полученные от A, I, H и K векторы и новая таблица маршрутизации для J
отправлять пакеты для G через A, то задержка составит 26 мс. Аналогично он вычисляет значения задержек для маршрутов от него до G, которые проходят через остальных его соседей (I, H и K), и получает, соответственно, 41 (31+10), 18 (6+12) и 37 (31+6). Лучшее значение — 18, поэтому J записывает в таблицу, что задержка до G составляет 18 мс, а оптимальный путь проходит через H. Данный расчет повторяется для всех остальных адресатов, и получается новая таблица (см. правый столбец на илл. 5.9).
Проблема счета до бесконечности
Установление маршрутов согласно кратчайшим путям в сети называется конвергенцией (convergence). Алгоритм маршрутизации по вектору расстояний — простой метод, позволяющий маршрутизаторам совместно вычислять оптимальные пути. Однако на практике он обладает серьезным недостатком: хоть он и находит правильный ответ, поиск длится очень долго. В частности, этот алгоритм быстро реагирует на хорошие новости и очень медленно — на плохие. Рассмотрим маршрутизатор, для которого наилучшее расстояние до X достаточно велико. Допустим, при очередном обмене векторами его сосед A сообщает ему, что от него до X совсем недалеко. Тогда наш маршрутизатор просто переключается на линию, проходящую через A, чтобы отправлять пакеты X. Таким образом, хорошая новость распространилась всего за один обмен информацией.
Чтобы увидеть, как быстро распространяются хорошие известия, рассмотрим линейную сеть из пяти узлов, показанную на илл. 5.10. Расстояние в ней измеряется числом переходов. Предположим, что изначально маршрутизатор A выключен и все остальные маршрутизаторы об этом знают. То есть они считают, что расстояние до A равно бесконечности.
Илл. 5.10. Проблема счета до бесконечности
Когда A появляется в сети, остальные маршрутизаторы узнают об этом с помощью обмена векторами. Для простоты представим, что где-то в сети имеется гигантский гонг, в который периодически ударяют, чтобы инициировать одновременный обмен. После первого обмена B узнает, что у его соседа слева нулевая задержка при связи с A, а B помечает в своей таблице маршрутов, что A находится слева на расстоянии одного перехода. Все остальные маршрутизаторы в этот момент еще полагают, что A выключен. Значения задержек для A в таблицах на этот момент показаны во второй строке на илл. 5.10 (а). При следующем обмене информацией C узнает, что у B есть путь к A длиной 1, поэтому он обновляет свою таблицу, указывая длину пути до A, равную 2, но D и E об этом еще не знают. Таким образом, хорошие новости распространяются со скоростью один переход за один обмен векторами. Если самый длинный путь в сети состоит из N переходов, то через N обменов все маршрутизаторы подсети будут знать о включенных маршрутизаторах и заработавших линиях.