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

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

ѕеред тем как начать: почитайте про перераспределение между плоскост€ми управлени€ в сет€х.

—етевые инженеры обычно думают, что плоскость управлени€ выполн€ет самые разные задачи, от вычислени€ кратчайшего пути через сеть до распределени€ политики, используемой дл€ пересылки пакетов. ќднако иде€ кратчайшего пути проникает в концепцию оптимального пути. “очно так же иде€ политики также проникает в концепцию оптимизации сетевых ресурсов. ’от€ важны и политика, и кратчайший путь, ни один из них не лежит в основе того, что делает плоскость управлени€. «адача плоскости управлени€ - сначала найти набор путей без петель через сеть. ќптимизаци€ - хорошее дополнение, но оптимизаци€ может быть "сделана" только в контексте поиска набора путей без петель.

“аким образом, в этом разделе будет дан ответ на вопрос: как плоскость управлени€ вычисл€ет пути без петель через сеть?

Ётот цикл статей начнетс€ с изучени€ взаимосв€зи между кратчайшим или наименьшим метрическим путем и безцикловыми пут€ми. —ледующа€ рассматриваема€ тема - свободные от циклов альтернативные пути (LFA), которые не €вл€ютс€ лучшими пут€ми, но все же свободны от циклов. “акие пути полезны при проектировании плоскостей управлени€, которые быстро переключаютс€ с наилучшего пути на альтернативный путь без петель в случае сбоев или изменений в топологии сети. «атем обсуждаютс€ два конкретных механизма, используемых дл€ поиска набора безцикловых путей.


 акой путь свободен от петель?

—в€зь между кратчайшим путем, обычно в терминах метрик, и свободными от циклов пут€ми довольно проста: кратчайший путь всегда свободен от циклов. ѕричина этой св€зи может быть выражена наиболее просто в терминах геометрии (или, более конкретно, теории графов, котора€ €вл€етс€ специализированной областью изучени€ в рамках дискретной математики). –исунок 1 используетс€ дл€ объ€снени€ этого.

 акие есть пути из A, B, C и D к месту назначени€?

  • »з A: [B, H]; [C, E, H]; [D, F, G, H]
  • »з B: [H]; [A, C, E, H]; [A, D, F, G, H]
  • »з D: [F, G, H]; [A, C, E, H]; [A, B, H]
ƒоступные пути в сети

≈сли каждое устройство в сети должно выбирать путь, который оно будет использовать к месту назначени€ независимо (без прив€зки на путь, выбранный любым другим устройством), можно сформировать посто€нные петли. Ќапример, A может выбрать путь [D, F, G, H], а D может выбрать путь [A, C, E, H]. «атем устройство A будет перенаправл€ть трафик к пункту назначени€ в D, а D затем перенаправит трафик к пункту назначени€ в A. ƒолжно быть какое-то правило, отличное от выбора пути, реализованного алгоритмом, используемым дл€ вычислени€ пути на каждом устройстве, например, выбрать самый короткий (или самый дешевый) путь. Ќо почему выбор кратчайшего (или самого дешевого) пути предотвращает возникновение петли? –исунок 2 иллюстрирует это.

Ќа рисунке 2 предполагаетс€, что A выбирает путь [D, F, G, H] к месту назначени€, а D выбирает путь через A к месту назначени€. „его D не может знать, поскольку он вычисл€ет путь к месту назначени€, не зна€, что вычислил A, так это того, что A использует путь через D сам дл€ достижени€ места назначени€.  ак может плоскость управлени€ избежать такого цикла? ќбратите внимание на то, что стоимость пути вдоль цикла всегда должна включать стоимость цикла, а также элемент пути без петель. ¬ этом случае путь через A с точки зрени€ D должен включать стоимость от D до места назначени€. —ледовательно, стоимость через A, с точки зрени€ D, всегда будет больше, чем наименьша€ доступна€ стоимость из D. Ёто приводит к следующему наблюдению:

ѕуть с наименьшей стоимостью (или кратчайший) не может содержать путь, который проходит через вычислительный узел или, скорее, кратчайший путь всегда свободен от петель.

Ѕолее длинные пути содержат более короткие

¬ этом наблюдении есть два важных момента.

¬о-первых, это наблюдение не говорит о том, что пути с более высокой стоимостью €вл€ютс€ определенно петл€ми, а только о том, что путь с наименьшей стоимостью не должен быть петлей. ћожно расширить правило, чтобы обнаружить более широкий набор путей без петель, помимо пути с наименьшей стоимостью- они называютс€ альтернативами без петель (Loop-Free Alternates).

¬о-вторых, это наблюдение справедливо, только если каждый узел в сети имеет одинаковое представление о топологии сети. ”злы могут иметь разные представлени€ о топологии сети по р€ду причин, например:

  • “опологи€ сети изменилась, и все узлы еще не были уведомлены об изменении; отсюда и микропетли.
  • Ќекотора€ информаци€ о топологии сети была удалена из базы данных топологии путем суммировани€ или агрегировани€.
  • ћетрики настроены так, что путь с наименьшей стоимостью несовместим с разных точек зрени€.

ѕлоскости управлени€, используемые в реальных сет€х, тщательно продуманы, чтобы либо обойти, либо минимизировать вли€ние различных устройств, имеющих разные представлени€ о топологии сети, что потенциально может привести к зацикливанию пути. Ќапример:

  • ѕлоскости управлени€ тщательно настраиваютс€, чтобы минимизировать разницу во времени между изучением изменени€ топологии и изменением пересылки (или отбрасывать трафик во врем€ изменений топологии, а не пересылать его).
  • ѕри обобщении топологии или агрегировании достижимости необходимо позаботитьс€ о сохранении информации о затратах.
  • "Ћучшие общеприн€тые практики" проектировани€ сети поощр€ют использование симметричных метрик, а многие реализации затрудн€ют или делают невозможным настройку каналов с действительно опасными показател€ми, такими как нулева€ стоимость канала.

„асто требуетс€ много работы, чтобы найти, обойти или предотвратить непреднамеренное нарушение правила кратчайшего пути в реальных протоколах плоскости управлени€.

ѕочему бы не использовать список узлов?

Ќа этом этапе должен возникнуть очевидный вопрос: почему бы просто не использовать список узлов дл€ поиска маршрутов без петель? Ќапример, на рисунке 1, если A вычисл€ет путь через D, может ли D каким-то образом получить путь, вычисленный A, обнаружить, что сам D находитс€ на пути, и, следовательно, не использовать путь через A?

ѕерва€ проблема с этим механизмом заключаетс€ в процессе обнаружени€.  ак D должен узнать о пути, выбранном A, и A узнать о пути, выбранном D, не вызыва€ состо€ни€ гонки? ƒва устройства могут выбрать друг друга в качестве следующего перехода к пункту назначени€ в один и тот же момент, а затем информировать друг друга в один и тот же момент, в результате чего оба одновременно выбирают другой путь. –езультатом может быть либо стабильный набор путей без петель, когда два устройства циклически выбирают друг друга и не имеют пути к месту назначени€, либо состо€ние насыщени€, при котором нет пути к месту назначени€.

¬тора€ проблема с этим механизмом - резюмирование - преднамеренное удаление информации о топологии сети дл€ уменьшени€ количества состо€ний, переносимых на уровне управлени€. ѕлоскость управлени€ будет иметь только метрики, с которыми можно работать, везде, где обобщаетс€ топологи€. —ледовательно, лучше использовать правило, основанное на метриках или стоимости, а не на наборе узлов, через которые проходит путь.

ќбратите внимание, что обе эти проблемы решаемы. Ќа самом деле существуют алгоритмы вектора пути, которые полагаютс€ на список узлов дл€ вычислени€ путей без петель через сеть. ’от€ эти системы широко распространены, они часто считаютс€ слишком сложными дл€ развертывани€ во многих ситуаци€х, св€занных с проектированием сетей. —ледовательно, широко используютс€ системы на основе метрик или стоимости.

“еперь почитайте материал про построение деревьев в сет€х