Особенности протокола EIGRP. Работа №77249

Особенности протокола

EIGRP

Протокол EIGRP является протоколом оценки вектора расстояний DVA и основан на алгоритме диффузии обновлений маршрутизации. Он поддерживает бесклассовую междоменную маршрутизацию CIDR, которая позволяет максимально использовать адресное пространство и маски подсети переменной длины VLSM.

Метрика М отдельного канала связи в протоколе EIGRP вычисляется по формуле:

где M – метрика канала связи; С – пропускная способность канала связи в отсутствии нагрузки (бит/с); ρ – нагрузка канала связи, в диапазоне 0..1; η – надежность канала связи, как доля успешно переданных по каналу связи пакетов; Тзад – задержка передачи в канале связи (c); k1, k2, k3, k4, k5 – коэффициенты, определяющие значимость соответствующих параметров.

Главным компонентом протокола ЕIGRP является алгоритм DUAL. Алгоритм DUAL анализирует все маршруты, анонсированные соседними маршрутизаторами, и использует метрику каждого маршрута для их сравнения. Алгоритм DUAL также гарантирует, что маршруты не содержат петель. После соответствующих вычислений алгоритм DUAL заносит маршруты с наименьшей метрикой в таблицу маршрутизации. Эти ТМ предоставляют алгоритму DUAL маршрутную информацию для расчета альтернативных маршрутов в случае нарушений в работе ТКС СН. Протокол передает основную маршрутную и топологическую информацию сети соседним маршрутизаторам.

Для повышения эффективности и уменьшения времени конвергенции сети протокол EIGRP рассчитывает несколько маршрутов до узла-получателя. Маршрут, выбираемый в качестве основного для достижения определенного узла, называется первичным. Для каждого конкретного узла может быть сформировано до четырех первичных маршрутов. Они могут иметь разные метрики и рассматриваются как наилучшие свободные от петель маршруты к данному узлу-получателю. Копии первичных маршрутов также помещаются в ТМ. Эти маршруты устанавливаются одновременно с первичными маршрутами по проприетарной технологии и также хранятся в ТМ. Наличие нескольких первичных маршрутов для достижения узла-получателя не является обязательным, но увеличивает надежность маршрутизации в сети.

Маршрутизатор рассматривает устройства на резервных маршрутах как устройства, расположенные ближе к узлу-получателю, чем он сам. Если по каким-либо причинам первичный маршрут не может выполнять свои функции, то алгоритм DUAL инициализирует другой первичный маршрут на основе данных ТМ и формирует новый маршрут к узлу назначения. Если резервный маршрут к узлу назначения отсутствует, то алгоритм DUAL переводит маршрут в активное состояние. Статус маршрута в ТМ может иметь одно из двух значений: активное состояние или пассивное. Пассивный статус имеет маршрут, который устойчив и готов к использованию. Активный статус присваивается временно недоступному маршруту, который в настоящий момент пересчитывается алгоритмом DUAL с использованием математического алгоритма Беллмана-Форда.

Пересчет маршрутов происходит в том случае, когда маршрут становится недоступным, и DUAL не может найти другого альтернативного первичного маршрута. В этом случае маршрутизатор должен запросить дополнительные топологические данные у соседних маршрутизаторов.

Если у соседнего маршрутизатора имеется соответствующий маршрут, то он предоставляет данные об имеющихся у него первичных маршрутах. В этом случае маршрут устанавливается без пересчета. В противном случае, соседний маршрутизатор уведомляет о том, что у него также нет маршрута к требуемому узлу назначения. Если один или более маршрутизаторов, которым был разослан запрос, не отвечает в течение времени, равного длительности «застревания» («stuck in active»), то маршрут (маршруты) переводится в состояние «застревания». В этом случае протокол EIGRP исключает из своей ТМ маршрутизаторы, которые не ответили на запрос, и регистрирует в системном журнале сообщение об ошибке для маршрутов, которые ранее были активными.

Маршрутизаторы на протоколе EIGRP активно устанавливают связи со своими соседними устройствами подобно тому, как это делают маршрутизаторы протокола OSPF. Это отличает EIGRP от маршрутизаторов на обычных дистанционно-векторных протоколах, например, RIP, выполняющих только широковещательную рассылку обновлений маршрутов. Маршрутизаторы EIGRP устанавливают отношения смежности с соседними маршрутизаторами путем рассылки пакетов приветствия «Hello». EIGRP предполагает, что до тех пор, пока от известных ему соседних устройств поступают пакеты «Hello», они (и их маршруты) остаются действующими (пассивными).

Маршрутизатор протокола EIGRP сохраняет информацию о соседних устройствах в соответствующей таблице, называемой таблицей соседних устройств. В этой таблице записываются номера последних полученных от устройств пакетов протокола EIGRP, а также имеется поле «времени удержания» (Hold Time), в котором записано время получения последнего пакета. Для того, чтобы у соседнего маршрутизатора сохранялся статус пассивного (достижимого и работоспособного), необходимо, чтобы за время удержания от него поступил хотя бы один пакет «Hello». Если в течение времени удержания от него не поступило пакетов «Hello», то протокол EIGRP рассматривает этот соседний маршрутизатор как неработоспособный и алгоритм DUAL начинает пересчитывать ТМ. По умолчанию, время удержания в три раза больше интервала «Hello», однако его можно, при необходимости, переконфигурировать. Описание временных параметров протокола EIGRP приведено в таблице 1.1 [2].

Протокол EIGRP независим от используемого сетевого протокола, то есть он не использует протокол TCP/IP для обмена сообщениями маршрутизации. Протокол EIGRP использует свой транспортный протокол для гарантированной доставки информации о маршрутах. Так пакеты обновления ТМ всегда рассылаются методом гарантированной доставки, а пакеты «Hello» всегда рассылаются методом негарантированной доставки и не требуют подтверждения.

Для того, чтобы обеспечить гарантированную доставку сообщений, EIGRP использует пакеты подтверждения от принимающего узла для узла-отправителя, представляющие собой пустые пакеты «Hello». В отличие от многоадресатных пакетов «Hello», пакеты-подтверждения являются одноадресатными и посылаются конкретному узлу. Подтверждение также может быть осуществлено путем совмещения передачи прямых и обратных пакетов других типов пакетов EIGRP.

Таблица 1.1 Параметры протокола EIGRP

Временной параметр

Пропускная способность

1,544 Мбит/с и менее

более 1,544 Мбит/с

Интервал приветствий (Hello Time)

60 с

5 с

Время удержания маршрута (Hold Time)

180 с

15 с

Время «застревания» маршрута (Stuck in Active)

180 с

Пакеты с обновлениями маршрутов используются в тех случаях, когда маршрутизатор обнаруживает новое соседнее устройство. В этих случаях маршрутизатор EIGRP посылает одноадресные пакеты обновления маршрутов этому новому соседнему устройству для того, чтобы оно могло добавить эту информацию в свою ТМ. Эти пакеты обновления используются также в тех случаях, когда маршрутизатор обнаруживает изменение топологии сети. В этом случае маршрутизатор рассылает многоадресатные пакеты обновления всем своим соседним устройствам, предупреждая их об изменении топологии.

Схема функционирования маршрутизатора на базе протокола EIGRP приведен на рисунке 1.1.

В основе предлагаемого усовершенствования протокола EIGRP лежит использование модифицированного алгоритма поиска кратчайших путей Беллмана-Форда. Данный модифицированный алгоритм был разработан путем применения общетеоретических положений метода к стандартному алгоритму Беллмана-Форда [3]. В результате был разработан новый модифицированный алгоритм Беллмана-Форда [4].

Для формализации модифицированного алгоритма Беллмана-Форда используем следующие обозначения:

D = {di}, i = 1, …, n – множество расстояний до помеченных вершин от начальной вершины; di – расстояние от вершины U1 до вершины Ui, полученное при использовании алгоритма поиска кратчайших путей;

G(U, V) – ориентированный граф, соответствующий сети ТКС СН; i = 1, …, n – переменная, счетчик вершин; j = 1, …, n – переменная, счетчик вершин;

L – множество смежных помеченных вершин, содержащих множество расстояний от начальной вершины до помеченных вершин;

L = {li}, i = 1, …, n – множество смежных помеченных вершин;

li = Uj – помеченная вершина, через которую достигнута вершина Ui, по окончании работы алгоритма li содержит кратчайшие пути к каждой вершине;

Рисунок. 1.1. Схема функционирования маршрутизатора на основе протокола EIGRP

n – количество вершин в графе;

P – множество помеченных вершин;

t – переменная, определяющая последнюю помеченную вершину;

U1 – начальная вершина;

V(Ui, Uj) – вес ребра, соединяющего i-ую и j-ую вершины;

R = {r} – множество вершин потенциальных резервных путей (в это множество вносятся достигнутые вершины, смежные рассматриваемой. В дальнейшем, элементы множества используются при нахождении резервных путей);

C = {c} – множество весов ребер потенциальных резервных путей (в это множество вносятся веса ребер, исходящих из вершин, вносимых в множество R, и входящих в рассматриваемую вершину);

Z = {z} – множество резервных путей в вершину, содержит резервные пути в рассматриваемую вершину, сформированные в результате проведения логических операций над входящими в него элементами и элементами множествами R и L;

S = {s} – множество весов резервных путей к вершине (это множество содержит веса путей из множества Z и используется для ранжировки резервных путей при выводе результатов работы модифицированного алгоритма).

Схема модифицированного алгоритма Беллмана-Форда приведена на рисунках 1.2, 1.3. К новым элементам модифицированного алгоритма Беллмана-Форда относятся блоки 7, 8, 17–22, 24.

В блоках 7, 8 реализуется формирование элементов множества вершин потенциальных резервных путей R к текущей рассматриваемой вершине. Далее, в блоках 17–22, путем пересечения элементов множества R и L, а также множества Z, осуществляется формирование элементов множества резервных путей в вершину Z. В блоке 24 осуществляется ранжирование резервных путей, находящихся в множестве Z по сумме весов, входящих в их состав ребер, которые в свою очередь находятся в множестве S.

Протокол EIGRP является проприетарным, при этом алгоритм DUAL в части формирования основных путей не является полностью открытым. В связи с этим совершенствование протокола EIGRP фактически заключается к разработке на его основе нового протокола, в котором исключены «закрытые» проприетарные операции.

В рамках совершенствования протокола EIGRP предлагается реализовать несколько направлений его доработки:

а) необходимо исключить «проприетарные операции» формирования четырех основных путей и заменить их на расчет маршрутов по модифицированному алгоритму поиска кратчайших путей Беллмана-Форда, впервые разработанному в данном исследовании, который одновременно с кратчайшими путями формирует и множество резервных путей;

б) в ТМ вместо четырех основных путей предлагается хранить как кратчайшие, так и непересекающиеся резервные маршруты, ранжированные по уровню увеличения суммарной метрики маршрута;

в) при поступлении от других маршрутизаторов сообщения об изменении топологии ТКС СН или метрики КС, а также в случае самостоятельного выявления подобных фактов маршрутизатор сразу же переходит на резервный маршрут, а уже потом производит оповещение ответственного маршрутизатора, смежных маршрутизаторов, ведет пересчет кратчайших путей и формирование новых маршрутов.

Схема усовершенствованного протокола EIGRP относительно стандартного протокола EIGRP представлена на рисунке 1.3.

К измененным функциям усовершенствованного протокола EIGRP относятся блоки 6, 9–10 и 14-15 на рисунке 1.3. К функциям, которые были удалены, относятся блоки 9–10, 23–24, 26 на рисунке 1.2.

Блок 6 выступает своеобразным «логическим вентилем», который на начальном этапе работы маршрутизатора позволяет сформировать ТМ из кратчайших и резервных путей, а в дальнейшем, при любых изменениях в сети, перенаправляет потоки трафика, на которые влияют произошедшие изменения, на резервные пути (блоки 14, 15). Переход передачи трафика на резервные пути позволяет не прерывать передачу данных при выполнении операций, представленных в блоках 16–20 и 7–10.

Блок 9 отличается тем, что в нем вместо вычисления метрики по стандартному алгоритму Беллмана-Форда реализуется вычисление кратчайших и резервных путей по модифицированному алгоритму Беллмана-Форда.

В блоке 10 реализуется функция добавления в ТМ помимо кратчайших путей еще и резервных путей. Таким образом, маршрут передачи изменяется с резервного пути, введенного в блоке 15, на текущий кратчайший путь.