Адаптивные (динамические) алгоритмы маршрутизации по вектору расстояния

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

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

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

Пример:

Рассматриваем маршрутизатор J.

1. Маршрутизатор измерил задержки до своих соседей, выдав им пакет ECHO, и получил следующие данные: JA=8, JI=10,JH=12,JK=6

2. Маршрутизатор получил от своих соседей таблицы со следующими значениями:

	A	I	H	K	Строится таблица J
A					0+8 = 8 A
B					12+8 = 20 A
C					10+18= 28 T
D					12 + 8 = 20 H
E					7 + 10 = 17 I
F					20+12 = 32 I
G					6+12 = 18 H
H					0+12 = 12 H
I					0 + 10 = 10 I
J					-
K					0 + 6 = 6 K
L					9 + 16 = 15 K

Вывод если приходит пакет на маршрутизатор D то J включает линию H. Если на маршрутизатор F, то включает линию I. Каждый маршрутизатор в узле строит такую таблицу, куда посылать пакеты в соответствии с адресатом. Недостаток: расчет требует много ресурсов (времени).

Дата добавления: 2015-01-03