ћерион Ќетворкс

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

ѕеред началом убедитесь, что ознакомились с материалом про альтернативные пути без петель.

ќбучайс€ в Merion Academy

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

Ќачать

Ќет особой причины, по которой весь SPT должен перестраиватьс€ каждый раз, когда происходит изменение топологии сети или информации о доступности. –ассмотрим рисунок ниже дл€ объ€снени€. ѕредположим, G тер€ет св€зь с 2001: db8: 3e8: 100 :: / 64. ”стройству A не требуетс€ пересчитывать свой путь к любому из узлов сети. ƒоступный пункт назначени€ - это просто лист дерева, даже если это набор хостов, подключенных к одному проводу (например, Ethernet). Ќет причин пересчитывать весь SPT, когда один лист (или любой набор листьев) отключаетс€ от сети. ¬ этом случае только лист (IP-адрес »нтернет-протокола или доступный пункт назначени€) должен быть удален из сети (или, скорее, пункт назначени€ может быть удален из базы данных без каких-либо изменений в сети). Ёто частичный пересчет SPT.

„астичный и инкрементный SPF

ѕредположим, что канал [C, E] не работает. „то делает ј в этом случае? ќп€ть же, топологи€ C, B и D не изменилась, поэтому у A нет причин пересчитывать все дерево. ¬ этом случае A может удалить все дерево за пределами E. „тобы вычислить только измененную часть графа, выполните следующие действи€:

  • ”далите отказавший узел и все узлы, которые нужно достичь через точку E.
  • ѕересчитайте дерево только от предшественника C (в данном случае A), чтобы определить, есть ли альтернативные пути дл€ достижени€ узлов, ранее доступных через E до того, как канал [C, E] не доступен.

Ёто называетс€ инкрементным SPF.


–асчет LFA и rLFA.

¬ предыдущих лекци€х (первой части) по теме Ђѕути одноадресной передачи без петельї рассматриваетс€ теори€, лежаща€ в основе LFA и rLFA. Bellman-Ford не вычисл€ет ни соседей ниже по потоку, ни LFA, и, похоже, не располагает необходимой дл€ этого информацией. DUAL по умолчанию вычисл€ет нисход€щих соседей и использует их во врем€ конвергенции. ј как насчет протоколов на основе ƒейкстры (и, соответственно, аналогичных алгоритмов SPF)? Ќа рисунке ниже показан простой механизм, который эти протоколы могут использовать дл€ поиска LFA и соседних узлов ниже по потоку.

¬ычисление LFA и последующих соседей с помощью алгоритма ƒейкстры

ќпределение нисход€щего соседа - это такое, при котором стоимость достижени€ соседом пункта назначени€ меньше, чем локальна€ стоимость достижени€ пункта назначени€. — точки зрени€ ј:

  • A знает местную стоимость проезда к месту назначени€ на основе SPT, созданного с помощью SPF ƒейкстры.
  • A знает стоимость B и C, чтобы добратьс€ до места назначени€, вычита€ стоимость каналов [A, B] и [A, C] из рассчитанной на местном уровне стоимости.

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

≈сли затраты соседа дл€ Ђмен€ї плюс затраты соседа на достижение пункта назначени€ ниже, чем местные затраты, соседом €вл€етс€ LFA.

¬ернее, учитыва€:

  • NC - это стоимость соседа до пункта назначени€.
  • BC - это стоимость соседа дл€ мен€.
  • LC - местна€ стоимость до места назначени€.

≈сли NC + BC < LC, то соседом €вл€етс€ LFA. ¬ этом случае A знает стоимость каналов [B, A] и [C, A] с точки зрени€ соседа (она будет содержатьс€ в таблице топологии, хот€ не используетс€ при вычислении SPT с использованием алгоритма ƒейкстры). “аким образом, LFA и нисход€щие соседи требуют очень небольшой дополнительной работы дл€ расчета, но как насчет удаленных LFA? ћодель P/Q Space обеспечивает простейший способ дл€ алгоритмов на основе ƒейкстры вычислени€ соседних узлов и LFA. –исунок ниже используетс€ дл€ иллюстрации изнутри P/Q Space.

ќпределение пространства P - это набор узлов, доступных с одного конца защищенного соединени€, а определение пространства Q - это набор узлов, достижимых без пересечени€ защищенного канала. Ёто должно предложить довольно простой способ вычислени€ этих двух пространств с помощью ƒейкстры:

–ассчитайте SPT с точки зрени€ устройства, подключенного к одному концу линии св€зи; удалить линию св€зи без пересчета SPT. ќстальные узлы доступны с этого конца линии.

ѕространство P/Q и вычисление удаленных LFA с помощью алгоритма ƒейкстры

Ќа рисунке E может:

  • ¬ычислите пространство Q, удалив линию [E, D] из копии локального SPT и всех узлов, дл€ достижени€ которых E использует D.
  • ¬ычислите пространство P, вычислив SPT с точки зрени€ D (использу€ D в качестве корн€ дерева), удалив линию [D, E], а затем все узлы, дл€ достижени€ которых D использует E.
  • Ќайдите ближайший узел, достижимый как из E, так и из D, с удаленной линией [E, D].

SPF ƒейкстры - это универсальный, широко используемый алгоритм дл€ вычислени€ Shortest Path Trees через сеть.


 ажетс€, ћарион запуталс€ в сет€х, пока пыталс€ в них разобратьс€!

≈му нужна тво€ помощь! ѕомоги решить задачу, чтобы спасти принцессу

ћаршрутизатор состоит из многих внутренних компонентов.  акой компонент хранит копию файла конфигурации?

 ака€ особенность поддерживает высокую пропускную способность в коммутируемых сет€х, объедин€€ несколько каналов в один?

 акой уровень модели OSI требуетс€ дл€ конфигурировани€ соединени€ между устройствами в различных виртуальных локальных сет€х?

“ы помог ћариону спасти принцессу!

«а это он дарит тебе дополнительные 15% скидки на курс по сет€м!

ѕолучить

”пс, кажетс€ промах. ѕопробуй в следующий раз!

x