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

Предполагается, что маршрутизаторы знают расстояние до каждого соседа. Если единицей измерения являются переходы, то оно равно одному переходу. Если же расстояние измеряется временем задержки распространения, то маршрутизатор может измерить его с помощью специального пакета 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 обменов все маршрутизаторы подсети будут знать о включенных маршрутизаторах и заработавших линиях.

Теперь рассмотрим ситуацию на илл. 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 превышающее минимальное значение, о котором сообщают его соседи. В итоге все маршрутизаторы будут бесконечно увеличивать значение расстояния до выключенного