Чтобы увидеть, как быстро распространяются хорошие известия, рассмотрим линейную сеть из пяти узлов, показанную на илл. 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 обменов все маршрутизаторы подсети будут знать о включенных маршрутизаторах и заработавших линиях.
Теперь рассмотрим ситуацию на илл. 5.10 (б). Все линии и маршрутизаторы изначально находятся в рабочем состоянии. Маршрутизаторы B, C, D и E расположены на расстоянии 1, 2, 3 и 4 переходов от A соответственно. Внезапно либо A отключается, либо происходит обрыв линии между A и B (что с точки зрения B одно и то же).
При первом обмене пакетами B не слышит ответа от A. К счастью, C говорит: «Не волнуйся. У меня есть путь к A длиной 2». B вряд ли догадывается, что путь от C к A проходит через B. B может только предполагать, что у C около 10 выходных линий с независимыми путями к A, кратчайшая из которых имеет длину 2. Поэтому теперь B думает, что может связаться с A через C по пути длиной 3. При этом обмене маршрутизаторы D и E не обновляют свою информацию об A.
При втором обмене векторами C замечает, что у всех его соседей есть путь к A длиной 3. Он выбирает один из них случайным образом и устанавливает свое расстояние до A равным 4, как показано в третьей строке на илл. 5.10 (б). Результаты последующих обменов векторами также показаны на этом рисунке.
Теперь понятно, почему плохие новости медленно распространяются: ни один маршрутизатор не может установить расстояние, более чем на 1 превышающее минимальное значение, о котором сообщают его соседи. В итоге все маршрутизаторы будут бесконечно увеличивать значение расстояния до выключенного маршрутизатора. Число обменов, необходимых для завершения этого процесса, можно ограничить, если задать значение этой «бесконечности» равным длине самого длинного пути плюс 1.
Неудивительно, что эту проблему называют счетом до бесконечности (count-to-infinity). Предпринималось много попыток решить ее. Например, было предложено запретить маршрутизатору сообщать о своих кратчайших путях тем соседям, от которых они получили эту информацию. Метод расщепления горизонта с «отравляющим» ответом обсуждался в RFC 1058. Однако на практике все эти эвристические правила с красивыми названиями оказались абсолютно бесполезными. Суть проблемы в том, что, когда Х сообщает Y о том, что у него есть какой-то путь, Y никак не может узнать, является ли он сам частью этого пути.
5.2.5. Маршрутизация с учетом состояния линий
Маршрутизация на основе векторов расстояний использовалась в сети ARPANET вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состояния линий. Отказаться от прежнего метода пришлось в первую очередь потому, что при изменении топологии сети он слишком долго стабилизировался (из-за проблемы счета до бесконечности). В результате ему на смену пришел совершенно новый алгоритм — маршрутизация с учетом состояния линий (link state routing). Сегодня в крупных сетях и в интернете используются его варианты — алгоритмы маршрутизации IS-IS и OSPF.
В основе этого метода лежит относительно простая идея, которую можно изложить в пяти требованиях к маршрутизатору. Он должен сделать следующее:
1. Обнаружить своих соседей и узнать их сетевые адреса.
2. Задать параметр расстояния или стоимости связи с каждым соседом.
3. Создать пакет, содержащий всю собранную информацию.
4. Разослать его на все маршрутизаторы и принять отправленные ими пакеты.
5. Вычислить кратчайший путь ко всем маршрутизаторам.
В результате каждый маршрутизатор получает полную топологию. После этого он может найти кратчайший путь ко всем остальным, применив алгоритм Дейкстры. Далее мы подробно изучим эти шаги.
Знакомство с соседями
Когда маршрутизатор загружается, его первая задача — получить информацию о соседях. Для этого он посылает специальный пакет HELLO по всем линиям «точка-точка». Маршрутизатор на другом конце линии в ответ сообщает свое имя. Имена должны быть уникальными. Если маршрутизатор слышит, что три других маршрутизатора напрямую соединены с F, то должно быть абсолютно ясно — все они имеют в виду один и тот же F.
Если два или более маршрутизатора соединены с помощью широковещательной связи (например, коммутатора, кольцевой сети или классического Ethernet), ситуация несколько усложняется. На илл. 5.11 (а) изображена широковещательная LAN, к которой напрямую подключены три маршрутизатора: A, C и F. Каждый из них соединен с одним или несколькими дополнительными маршрутизаторами.
Илл. 5.11. Широковещательная LAN. (а) Девять маршрутизаторов и широковещательная LAN. (б) Графовая модель той же системы
Широковещательная LAN обеспечивает связь между каждой парой подключенных маршрутизаторов. Однако моделирование такой сети в виде системы связей «точка-точка» увеличивает топологию и ведет к неэкономной передаче. Существует более подходящая модель, в которой LAN представляет собой узел графа. На илл. 5.11 (б) она изображена в виде нового, искусственного узла N, с которым соединены A, C и F. Один из маршрутизаторов сети — отмеченный маршрутизатор (designated router) — выполняет роль N в протоколе маршрутизации. Маршрут от A до C по LAN в этом случае выглядит как путь ANC.
Определение стоимости связи
Алгоритм маршрутизации с учетом состояния линии требует, чтобы у каждого соединения был параметр расстояния или стоимости, необходимый для вычисления кратчайшего пути. Стоимость пути до соседних маршрутизаторов может быть задана автоматически или определена оператором сети. Чаще всего она обратно пропорциональна пропускной способности. Так, сеть Ethernet со скоростью 1 Гбит/с может иметь стоимость 1, а Ethernet со скоростью 100 Мбит/с — 10. Благодаря этому в качестве наилучшего выбирается путь с более высокой пропускной способностью.
Если узлы сети находятся далеко друг от друга, определить стоимость пути можно на основе задержки соединения. В этом случае наилучшим считается более короткий путь. Самый простой способ определения задержки — отправка специального пакета ECHO. Другая сторона обязана немедленно на него ответить. Измерив время прохождения пакета в оба конца и разделив его на два, отправитель получает приблизительное значение задержки.