Корпоративные сети →Теория→Основы сетей

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

Diffusing Update Algorithm

Январь 05, 2021 Мерион Нетворкс

6 минут чтения

Перед тем как начать чтение этой статьи, советуем ознакомиться с материалом про расчет пути по алгоритму Bellman - ford.

Обучайся в Merion Academy

Пройди курс по
сетевым технологиям

Начать

Алгоритм диффузного обновления (Diffusing Update Algorithm -DUAL) - один из двух обсуждаемых здесь алгоритмов, изначально предназначенных для реализации в распределенной сети. Он уникален тем, что также удаляет информацию о достижимости и топологии, содержащуюся в конечном автомате алгоритма. Другие обсуждаемые здесь алгоритмы оставляют удаление информации на усмотрение реализации протокола, а не рассматривают этот аспект работы алгоритма внутри самого алгоритма.

К 1993 году Bellman-Ford и Dijkstra были реализованы как распределенные алгоритмы в нескольких протоколах маршрутизации. Опыт, полученный в результате этих ранних реализаций и развертываний, привел ко "второй волне" исследований и размышлений о проблеме маршрутизации в сетях с коммутацией пакетов, что привело к появлению вектора пути и DUAL.

Поскольку DUAL разработан как распределенный алгоритм, лучше всего описать его работу в сети. Для этой цели используются рисунки 8 и 9. Чтобы объяснить DUAL, в этом примере будет прослеживаться поток A, изучающего три пункта назначения, а затем обрабатываются изменения в состоянии доступности для этих же пунктов назначения. В первом примере будет рассмотрен случай, когда есть альтернативный путь, но нет downstream neighbor, второй рассмотрит случай, когда есть альтернативный путь и downstream neighbor.

На рисунке 8 изучение D с точки зрения A:

1. A узнает два пути к D:
   1. Через H стоимостью 3.
   2. Через C стоимостью 4.

2. A не узнает путь через B, потому что B использует A в качестве своего преемника:
   1. A - лучший путь B для достижения D.
   2. Поскольку B использует путь через A для достижения D (пункта назначения), он не будет анонсировать маршрут, который он знает о D (через C) к A.
   3. B выполнит split horizon своего объявления D на A, чтобы предотвратить образование возможных петель пересылки.
3. A сравнивает доступные пути и выбирает кратчайший путь без петель:
   1. Путь через H помечен как преемник.
   2. Возможное расстояние устанавливается равным стоимости кратчайшего пути, равной 3.
4. A проверяет оставшиеся пути, чтобы определить, являются ли какие-либо из них downstream neighbors:
   1. Стоимость C составляет 3.

A знает это, потому что C объявляет маршрут к D со своей локальной метрикой, равной 3.

A сохраняет локальную метрику C в своей таблице топологии.

Следовательно, A знает локальную стоимость в C и локальную стоимость в A.

2. 3 (стоимость в C) = 3 (стоимость в A), поэтому этот маршрут может быть петлей, следовательно, C не удовлетворяет условию выполнимости. C не помечен как downstream neighbors.

Downstream neighbors в DUAL называются возможными преемниками. Предположим, что канал [A, H] не работает. DUAL не полагается на периодические обновления, поэтому A не может просто ждать другого обновления с достоверной информацией. Скорее A должен активно следовать альтернативному пути. Таким образом, это диффузный процесс обнаружения альтернативного пути. Если канал [A, H] не работает, учитывая только D:

1. A проверяет свою локальную таблицу на предмет возможных преемников (Downstream neighbors).
2. Возможных преемников нет, поэтому A должен найти альтернативный путь без петель к D (если он существует).
3. A отправляет запрос каждому соседу, чтобы определить, есть ли какой-либо альтернативный путь без петель к D.
4. В C:
   1. Преемником C является E (не A, от которого он получил запрос).
   2. Стоимость E ниже, чем стоимость A для D. Следовательно, путь C не является петлей.
   3. C отвечает со своей текущей метрикой 3 на A.
5. В B:
   1. А - нынешний преемник Б.
   2. Посредством запроса B теперь обнаруживает, что его лучший путь к D потерпел неудачу, и он также должен найти альтернативный путь.
   3. Обработка B здесь не расписывается, а предоставляется выполнить самостоятельно.
   4. B отвечает A, что у него нет альтернативного пути (отвечает бесконечной метрикой).
6. A получает эти ответы:
   1. Путь через C - единственный доступный, его стоимость 4.
   2. A отмечает путь через C как его преемника.
   3. Других путей к D нет. Следовательно, нет подходящего преемника (downstream neighbor).

На рисунке 9 пункт назначения (D) был перемещен с H на E. Это будет использоваться во втором примере.

В этом примере есть возможный преемник (downstream neighbor).

Изучение D с точки зрения A:

1. A узнает два пути к D:
   1. Через H стоимостью 4.
   2. Через C стоимостью 3.
2. A не узнает никакого пути через B:
   1. У B есть два пути к D.
   2. Через C и A стоимостью 4.
   3. В этом случае B использует как A, так и C.
   4. B выполнит split horizon свого объявления D на A, потому что A помечен как преемник.
3. A сравнивает доступные пути и выбирает кратчайший путь без петель:
   1. Путь через C отмечен как преемник.
   2. Возможное расстояние устанавливается равным стоимости кратчайшего пути, равной 3.
4. A проверяет оставшиеся пути, чтобы определить, являются ли какие-либо из них downstream neighbors:
   1. Стоимость H составляет 2.
   2. 2 (стоимость в H) = 3 (стоимость в A), поэтому этот маршрут не может быть петлей. Следовательно, H удовлетворяет условию выполнимости.
   3. H отмечен как возможный преемник (downstream neighbors).

Если канал [A, C] не работает, просто рассматривая A:

1. A проверит свою таблицу локальной топологии на предмет возможного преемника.
2. Возможный преемник существует через H.
3. A переключает свою локальную таблицу на H как лучший путь.
   1. Распространяющееся обновление не запускалось, поэтому пути не были проверены или пересчитано.
   2. Следовательно, допустимое расстояние изменить нельзя. Он остается на 3.
4. A отправляет обновление своим соседям, отмечая, что его стоимость достижения D изменилась с 3 до 4.

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

На рисунке 10 показан базовый законченный автомат DUAL.

Вещи, входящие в route gets worse (ухудшение маршрута), могут представлять собой:

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