Страница 66

Вычислительные комплексы и сети. Лекции

При «выборочной заливке» пакеты направляются не по всем линиям, а только по тем, которые «приблизительно» идут по выбранному адресатом направлению.

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

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

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

Примером алгоритма такого типа является алгоритм 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.      Маршрутизатор получил от своих соседей таблицы со следующими значениями:

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

Маршрутизация с учетом состояния канала

Идея — выполнение следующих требований:

1. Каждый маршрутизатор должен обнаруживать своих соседей и определять сетевые адреса. Получение информации о соседях осуществляется после загрузки маршрутизатора посылкой пакета HELLO по всем направлениям. Адреса маршрутизаторов уникальны и каждый в ответ посылает свой адрес.
2. Каждый маршрутизатор должен уметь опросить состояние, чтобы измерить задержку или стоимость связи с каждым из своих соседей. Наиболее общий способ измерения — пакет ECHO.
3. Каждый маршрутизатор должен уметь создавать пакет, содержащий всю информацию о соседях. Пакет состоит из идентификатора маршрутизатора, порядкового номера, возраста и списка соседей.