ѕодпишитесь на наш Telegram-канал Ѕудьте в курсе последних новостей 👇 😉 ѕодписатьс€
ѕоддержим в трудное врем€ —пециальное предложение на техническую поддержку вашей »“ - инфраструктуры силами наших экспертов ѕодобрать тариф
ѕоставка оборудовани€ √аранти€ и помощь с настройкой. —кидка дл€ наших читателей по промокоду WIKIMERIONET  упить
»нтерфейс статистики Merion Mertics показывает ключевые диаграммы и графики по звонкам, а также историю звонков в формате, который легко поймет менеджер ѕопробовать бесплатно
¬недрение
офисной телефонии
Ўаг на пути к созданию доступных унифицированных коммуникаций в вашей компании ¬недрить
»нтеграци€ с CRM ѕомогаем навести пор€док с данными
и хранить их в единой экосистеме
ѕодключить
»“ Ѕезопасность ”мна€ информационна€ безопасность дл€ вашего бизнеса «аказать
ћерион Ќетворкс

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

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

јлгоритм диффузного обновлени€ (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.
ѕерва€ сеть дл€ демонстрации алгоритма диффузного обновлени€ ¬тора€ сеть дл€ демонстрации алгоритма диффузного обновлени€
  1. A не узнает путь через B, потому что B использует A в качестве своего преемника:
    1. A - лучший путь B дл€ достижени€ D.
    2. ѕоскольку B использует путь через A дл€ достижени€ D (пункта назначени€), он не будет анонсировать маршрут, который он знает о D (через C) к A.
    3. B выполнит split horizon своего объ€влени€ D на A, чтобы предотвратить образование возможных петель пересылки.
  2. A сравнивает доступные пути и выбирает кратчайший путь без петель:
    1. ѕуть через H помечен как преемник.
    2. ¬озможное рассто€ние устанавливаетс€ равным стоимости кратчайшего пути, равной 3.
  3. A провер€ет оставшиес€ пути, чтобы определить, €вл€ютс€ ли какие-либо из них downstream neighbors:
    1. —тоимость C составл€ет 3.

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

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

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

  1. 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 (ухудшение маршрута), могут представл€ть собой:

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