Алгоритм диффузного обновления - Diffusing update algorithm

В алгоритм диффузного обновления (ДВОЙНОЙ) это алгоритм использован Cisco с EIGRP[1] протокол маршрутизации, чтобы гарантировать, что данный маршрут пересчитывается глобально, когда это может вызвать петлю маршрутизации. Он был разработан J.J. Гарсия-Луна-Асевес в SRI International. Полное название алгоритма DUAL конечный автомат (ДВОЙНОЙ FSM). EIGRP отвечает за маршрутизацию внутри автономная система, а DUAL реагирует на изменения в топологии маршрутизации и автоматически динамически корректирует таблицы маршрутизации маршрутизатора.

EIGRP использует условие выполнимости чтобы гарантировать выбор только маршрутов без петель. Условие осуществимости является консервативным: когда условие истинно, петли не могут возникнуть, но условие может при некоторых обстоятельствах отклонять все маршруты к месту назначения, хотя некоторые из них не имеют петель.

Когда нет доступного маршрута к пункту назначения, алгоритм DUAL [2] вызывает диффузное вычисление [3] чтобы убедиться, что все следы проблемного маршрута удалены из сети. В этот момент нормальный Алгоритм Беллмана – Форда используется для восстановления нового маршрута.

Операция

DUAL использует три отдельные таблицы для расчета маршрута. Эти таблицы создаются с использованием информации, которой обмениваются маршрутизаторы EIGRP. Информация отличается от той, которой обменивается протоколы маршрутизации по состоянию канала. В EIGRP информация, которой обмениваются, включает маршруты, "метрика "или стоимость каждого маршрута, а также информацию, необходимую для формирования взаимосвязи между соседями (например, номер AS, таймеры и значения K). Три таблицы и их функции подробно описаны ниже:

  • Таблица соседей содержит информацию обо всех других напрямую подключенных маршрутизаторах. Для каждого поддерживаемого протокола (IP, IPX и т. Д.) Существует отдельная таблица. Каждая запись соответствует соседу с описанием сетевого интерфейса и адреса. Кроме того, инициализируется таймер, чтобы запускать периодическое определение активности соединения. Это достигается через «Привет». пакеты. Если пакет «Hello» не получен от соседа в течение определенного периода времени, маршрутизатор считается отключенным и удаляется из таблицы соседей.
  • Таблица топологии содержит метрику (информацию о стоимости) всех маршрутов к любому пункту назначения в автономной системе. Эта информация поступает от соседних маршрутизаторов, содержащихся в таблице Neighbor. Первичный (преемник) и вторичный (возможный преемник) маршруты к пункту назначения будут определены с помощью информации в таблице топологии. Помимо прочего, каждая запись в таблице топологии содержит следующее:
«FD (возможное расстояние)»: расчетная метрика маршрута к пункту назначения в автономной системе.
«RD (сообщаемое расстояние)»: метрика пункта назначения, объявленная соседним маршрутизатором. RD используется для расчета FD и для определения того, соответствует ли маршрут «условию осуществимости».
Статус маршрута: Маршрут отмечен как «активный» или «пассивный». «Пассивные» маршруты стабильны и могут использоваться для передачи данных. «Активные» маршруты пересчитываются и / или недоступны.
  • Таблица маршрутизации содержит лучший маршрут (ы) до пункта назначения (с точки зрения самой низкой «метрики»). Эти маршруты являются наследниками таблицы топологии.

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

Чтобы маршрут стал возможным преемником, его RD должен быть меньше FD преемника. Если это условие выполнимости выполнено, то добавление этого маршрута в таблицу маршрутизации не может вызвать петлю.

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

Пример

Легенда:

+ = Маршрутизатор
- или | = Ссылка
(X) = Метрика ссылки
     A (2) B (1) C + - - - - - + - - - - - + | | (2) | | (3) | | + - - - - - + D (1) E

Теперь клиент на маршрутизаторе E хочет поговорить с клиентом на маршрутизаторе A. Это означает, что маршрут между маршрутизатором A и маршрутизатором E должно быть доступно. Этот маршрут рассчитывается следующим образом:

Непосредственными соседями маршрутизатора E являются маршрутизатор C и маршрутизатор D. DUAL в маршрутизаторе E запрашивает сообщенное расстояние (RD) от маршрутизаторов C и D соответственно до маршрутизатора A. Ниже приведены результаты:

Назначение: Маршрутизатор A
через D: RD (4)
через C: RD (3)

Таким образом, маршрут через C имеет наименьшую стоимость. На следующем этапе расстояние от маршрутизатора E до соседей добавляется к сообщенному расстоянию, чтобы получить допустимое расстояние (FD):

Назначение: Маршрутизатор A
через D: RD (4), FD (5)
через C: RD (3), FD (6)

Таким образом, DUAL считает, что маршрут через D имеет наименьшую общую стоимость. Тогда маршрут через D будет отмечен как «преемник», получит пассивный статус и будет зарегистрирован в таблице маршрутизации. Маршрут через C сохраняется как «возможный преемник», потому что его RD меньше, чем FD преемника:

Назначение: Маршрутизатор A
через D: RD (4), преемник FD (5)
через C: RD (3), FD (6) возможный преемник

Рекомендации

  1. ^ Официальный официальный документ Cisco EIGRP, 9 сентября 2005 г.
  2. ^ J.J. Гарсиа-Лунес-Асевес, «Беспетельная маршрутизация с использованием диффузионных вычислений» IEEE / ACM Transactions on Networking, vol. 1, № 1, стр. 130–141 Февраль 1993 г.
  3. ^ Э. В. Дейкстра и К. С. Шолтен. «Обнаружение окончания для рассеивающих вычислений», Информ. Процесс. Lett., Vol. 11, no, 1, pp. 1–4, август 1980 г. и EWD687a