Курсовые и лабораторные работы Математика решение задач Электротехника Лабораторные работы по электронике Физика Информатика На главную
Реализация сервиса виртуальные каналы Алгоритмы маршрутизации Метод заливки Маршрутизация Иерархическая маршрутизация Широковещательная маршрутизация Многоадресная рассылка Борьба с флуктуациями

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

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

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

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

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

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

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


Определить координаты центра тяжести однородной пластины
Сетевой уровень Управление доступом У каждого хоста и маршрутизатора в Интернете есть IP-адрес