11) Маршрутизация в сетях, маршрутизаторы.

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

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

Алгоритмы маршрутизации по вектору расстояний(distance vector routing)

работают, опираясь на таблицы (то есть векторы), поддерживаемые всеми маршрутизаторами и содержащие сведения о кратчайших известных путях к каждому из возможных адресатов и о том, какое соединение следует при этом использовать. Для

400 Глава 5. Сетевой уровень

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

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

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

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

Предположим, что в качестве единицы измерения используется время задержки

иэтот параметр относительно каждого из соседей известен маршрутизатору. Через каждые T мс все маршрутизаторы посылают своим соседям список с приблизительными задержками для каждого получателя. Они, разумеется, также получают подобный список от всех своих соседей. Допустим, одна из таких таблиц пришла от соседаX

ив ней указывается, что время распространения от маршрутизатора X до маршрутизатораi равноXi. Если маршрутизатор знает, что время пересылки до маршрутизатораX равноm, тогда задержка при передаче пакета маршрутизаторуi через маршрутизаторX составитXi +m. Выполнив такие расчеты для всех своих соседей, маршрутизатор может выбрать наилучшие пути и поместить соответствующие записи в новую таблицу. Обратите внимание, что старая таблица в расчетах не используется.

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

(I,H иK), и получает соответственно 41 (31+10), 18 (6+12) и 37 (31+6). Лучшим значением является 18, поэтому именно оно помещается в таблицу в запись для получателяG. Вместе с числом 18 туда же помещается обозначение линии, по которой

5.2. Алгоритмы маршрутизации 401

проходит самый короткий маршрут до G, то естьH. Данный метод повторяется для всех остальных адресатов, и при этом получается новая таблица, показанная в виде правого столбца на рисунке.

Рис. 5.7. Сеть (а); полученные отA,I,H иK векторы и новая таблица маршрутов дляJ (б)

Проблема счета до бесконечности

Установление маршрутов, соответствующих кратчайшим путям, в сети называетсяконвергенцией (convergence). Алгоритм маршрутизации по вектору расстояний — простой метод, позволяющий маршрутизаторам совместно вычислять кратчайшие пути. Однако на практике он обладает серьезным недостатком: хотя правильный ответ в конце концов и находится, процесс его поиска может занять довольно много времени. В частности, такой алгоритм быстро реагирует на хорошие новости и очень лениво — на плохие. Рассмотрим маршрутизатор, для которого расстояние до маршрутизатораXдостаточно велико. Если при очередном обмене векторами его соседA сообщит ему, что от него до маршрутизатораX совсем недалеко, наш маршрутизатор просто переключится для передач маршрутизаторуX на линию, проходящую через этого соседа. Таким образом, хорошая новость распространилась всего за один обмен информацией.

Чтобы увидеть, как быстро распространяются хорошие известия, рассмотрим линейную сеть из пяти узлов, показанную на рис. 5.8, в которой мерой расстояния служит количество транзитных участков. Предположим, что вначале маршрутизаторA выключен, и все остальные маршрутизаторы об этом знают. То есть они считают, что расстояние доA равно бесконечности.

402 Глава 5. Сетевой уровень

Рис. 5.8. Проблема счета до бесконечности

Когда в сети появляется A, остальные маршрутизаторы узнают об этом с помощью обмена векторами. Для простоты будем предполагать, чтогде-тов сети имеется гигантский гонг, в который периодически ударяют, чтобы инициировать одновременный обмен векторами. После первого обменаB узнает, что у его соседа слева нулевая задержка при связи сA, аB помечает в своей таблице маршрутов, чтоA находится слева на расстоянии одного транзитного участка. Все остальные маршрутизаторы в этот момент еще полагают, чтоA выключен. Значения задержек дляA в таблицах на этот момент показаны во второй строке на рис. 5.8,а. При следующем обмене информациейC узнает, что уB есть путь кA длиной 1, поэтому он обновляет свою таблицу, указывая длину пути доA, равную 2, ноD иE об этом еще не знают. Таким образом, хорошие вести распространяются со скоростью один транзитный участок за один обмен векторами. Если самый длинный путь в сети состоит изN транзитных участков, то черезN обменов все маршрутизаторы подсети будут знать о включенных маршрутизаторах и заработавших линиях.

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

Теперь должно быть понятно, почему плохие новости медленно распространяются — ни один маршрутизатор не может установить значение расстояния, более чем на

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

Неудивительно, что эта проблема называется счетом до бесконечности (count-to-infinity). Было сделано много попыток решить ее, например можно запретить маршрутизатору сообщать о своих кратчайших путях соседям, от которых они получили эту информацию, с помощью правила расколотого горизонта с «отравляющим» ответом внесенного в RFC 1058. Однако на практике все эти эвристические правила с красивыми названиями оказались абсолютно бесполезными. Суть проблемы заключается в том, что когдаХ сообщаетY о том, что у него естькакой-топуть, уY нет никакой возможности узнать, входит ли он сам в этот путь.