Алгоритмы маршрутизации. Маршрутизация по вектору расстояний.

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

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

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

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

Установление маршрутов, соответствующих кратчайшим путям, в сети называется конвергенцией.

Недостаток алгоритма: долгое время ожидания поиска правильного ответа и проблема счета до бесконечности.