7.6 Дистанционно–векторная маршрутизация

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

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

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

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

Процесс обновления таблицы проиллюстрирован на рисунке 74: первые четыре столбца показывают векторы задержек, полученные маршрутизатором J от своих соседей. Маршрутизатор А утверждает, что время пересылки от него до маршрутизатора В равно 12 мс, 25 мс до маршрутизатора С, 40 мс – до D и т.д.. предположим, маршрутизатор J измерил или оценил задержки до своих соседей A, I, H и К как 8, 10, 12 и 6 мс соответственно.

Рисунок 74 - Рассматриваемая подсеть

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

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

K	A		I		H		K			линия
A	0		24		20		21		8	A
B	12		36		31		28		20	A
C	25		18		19		36		28	I
D	40		27		8		24		20	H
E	14		7		30		22		17	I
F	23		20		19		40		30	I
G	18		31		6		31		18	H
H	17		20		0		19		12	H
I	21		0		14		22		10	I
J	9		11		7		10		0	–
K	24		22		22		0		6	K
L	29		33		9		9		15	K
	3адержка JA = 8		Задержка JI = 10		Задержка JH = 12		Задержка JK = 6		Новая таблица маршрутов для J
	Векторы, полученные от четырех соседей J

Рисунок 75 - Процесс обновления маршрутов

Дистанционно–векторная маршрутизация использовалась в сети ARPANET вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состояния линий. Отказаться от прежнего алгоритма пришлось из-за двух основных проблем. Во-первых, старый алгоритм не учитывал пропускную способность линий. Расстояние между маршрутизаторами измерялось длиной очереди. Вначале все линии имели пропускную способность в 566 Кбит/с, поэтому учитывать пропускную способность не было необходимости. Однако после того, как несколько линий были ускорены до 230 Кбит/с, а затем появились линии со скоростью 1,544 Мбит/с, не принимать во внимание пропускную способность стало невозможным. Конечно, можно было ввести пропускную способность в качестве множителя для единицы измерения, но имелась еще и другая проблема, заключавшаяся в том, что алгоритм слишком долго приходил к устойчивому состоянию, несмотря на применение трюков типа расколотого горизонта. Поэтому он был полностью заменен новым алгоритмом, называющимся маршрутизацией с учетом состояния линий.