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

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

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

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

Операция

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

Таблица соседей содержит информацию обо всех других напрямую подключенных маршрутизаторах. Для каждого поддерживаемого протокола (IP, IPX и т. д.) существует отдельная таблица. Каждая запись соответствует соседу с описанием сетевого интерфейса и адреса. Кроме того, инициализируется таймер, запускающий периодическое определение активности соединения. Это достигается с помощью пакетов «Hello» . Если пакет «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. Ниже приведены результаты:

Назначение: Маршрутизатор А

через D: RD(4)

через C: RD(3)

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

Назначение: Маршрутизатор А

через D: RD(4), FD(5)

через C: RD(3), FD(6)

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

Назначение: Маршрутизатор А

через D: преемник RD(4), FD(5)

через C: возможный преемник RD(3), FD(6)

Ссылки

[1] Официальный технический документ Cisco EIGRP, 9 сентября 2005 г.

[2] Дж. Дж. Гарсия-Лунес-Асевес, «Маршрутизация без петель с использованием диффузных вычислений», Транзакции IEEE / ACM в сети, том. 1, № 1, стр. 130–141 февраль 1993 г.

[3] Э. В. Дейкстра и К. С. Схолтен. Обнаружение завершения диффузионных вычислений // Информ. Процесс. Летт., т. 11, вып. 1, стр. 1–4, август 1980 г. и EWD687a.

[1]

[2]

[3]