Диффундирующий алгоритм обновления ( ДВОЙНОЙ ) является алгоритмом , используемым Cisco «ы EIGRP [1] маршрутизация протокола , чтобы гарантировать , что данный маршрут пересчитывается в глобальном масштабе всякий раз , когда это может привести к петле маршрутизации. Его разработал Дж. Дж. Гарсия-Луна-Асевес из SRI International . Полное название алгоритма - ДВОЙНОЙ конечный автомат (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) = Метрика ссылки
А (2) В (1) С + - - - - - + - - - - - + | | (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) возможный преемник
Рекомендации
- ^ Cisco EIGRP официальная белая бумага, сентябрь 09, 2005
- ^ Дж. Дж. Гарсия-Лунес-Асевес, «Беспеточная маршрутизация с использованием диффузионных вычислений» IEEE / ACM Transactions on Networking, vol. 1, № 1, стр. 130–141 Февраль 1993 г.
- ^ EW Dijkstra и CS Scholten. «Обнаружение окончания для рассеивающих вычислений», Информ. Процесс. Lett., Vol. 11, no, 1, pp. 1–4, август 1980 г. и EWD687a