22. Маршрутизация по вектору расстояний. Достоинства и недостатки методов.

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

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

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

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

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

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

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

Процесс обновления таблицы проиллюстрирован на рис. 5.7. Слева показана подсеть (рис. 5.7, а). Первые четыре столбца на рис. 5.7, б показывают векторы задержек, полученные маршрутизатором J от своих соседей. Маршрутизатор А считает, что время пересылки от него до маршрутизатора В равно 12 мс, 25 мс -до маршрутизатора С, 40 мс - до D и т. д. Предположим, что маршрутизатор измерил или оценил задержки до своих соседей А,1,Н и К, как 8,10, 12 и 6 мс со­ответственно.

Теперь рассмотрим, как рассчитывает свой новый маршрут к маршрутизато­ру G Он знает, что задержка до А составляет 8 мс, а А думает, что от него до G пакеты для G через А, то задержка составит 26 мс. Аналогично он вычисляет значения задержек для маршрутов от него до G, проходящих через остальных его соседей (/, Н и К), и получает соответственно 41 (31 + 10), 18 (6 + 12) и 37 (31 + 6). Лучшим значением является 18, поэтому именно оно помещается в таблицу в за­пись для получателя G Вместе с числом 18 туда же помещается обозначение ли­нии, по которой проходит самый короткий маршрут до G, то есть Я. Данный метод повторяется для всех остальных адресатов, и при этом получается новая таблица, показанная в виде правого столбца на рисунке.