⚡ Ќовый онлайн курс по —етевым “ехнологи€м

до запуска осталось

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

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

¬ предыдущих лекци€х обсуждалось правило кратчайшего пути и два алгоритма (или, возможно, системы) дл€ поиска путей без петель через сеть. —уществует широкий спектр таких системЧих слишком много, чтобы охватить их в отведенное врем€ дл€ изучени€, - но дл€ сетевых администраторв важно быть знакомыми хот€ бы с некоторыми из этих систем. ¬ этих лекци€х сначала рассматриваетс€ алгоритм поиска кратчайшего пути ƒейкстры, вектор пути и два различных алгоритма непересекающихс€ путей: Suurballe и Maximally Redundant Trees (MRTs). Ќаконец, в этих лекци€х будет рассмотрена еще одна проблема, которую должны решить управл€ющие плоскости: обеспечение двусторонней св€зи через сеть.


јлгоритм ƒейкстры Shortest Path First.

јлгоритм ƒейкстры Shortest Path First (SPF), возможно, €вл€етс€ наиболее широко известной и пон€тной системой дл€ обнаружени€ Loop-Free путей в сети. ќн используетс€ двум€ широко распространенными протоколами маршрутизации и во многих других повседневных системах, таких как программное обеспечение, предназначенное дл€ поиска кратчайшего пути через дорожную сеть или дл€ обнаружени€ соединений и паттернов соединений в социальных сет€х.

јлгоритм ƒейкстры в псевдокоде использует две структуры данных. ѕервый - это предварительный список или TENT; этот список содержит набор узлов, рассматриваемых дл€ включени€ в дерево кратчайшего пути (Shortest Path Tree). ¬торой - PATH; этот список содержит набор узлов (а следовательно, и каналы), которые наход€тс€ в дереве кратчайшего пути.

01 move "me" to the TENT
02 while TENT is not empty {
03 sort TENT
04 selected == first node on TENT
05 if selected is in PATH {
06 *do nothing*
07 }
08 else {
09 add selected to PATH
10 for each node connected to selected in TOPO
11 v = find node in TENT
12 if (!v)
13 move node to TENT
14 else if node.cost < v.cost
15 replace v with node on TENT
16 else
17 remove node from TOPO
18 }
19 }

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

  1. ѕроцесс начинаетс€ с копии базы данных топологии, называемой здесь TOPO; это будет €снее в примере, но это просто структура, содержаща€ исходные узлы, целевые узлы и стоимость св€зи между ними.
  2. TENT - это список узлов, которые можно условно считать кратчайшим путем к любому конкретному узлу.
  3. PATH - это дерево кратчайшего пути (SPT), структура, содержаща€ loop-free путь к каждому узлу и следующий переход от Ђмен€ї к этому узлу.
  4. ѕервым важным моментом в этом алгоритме €вл€етс€ сохранение только узлов, уже каким-то образом св€занных с узлом в списке PATH в TENT; это означает, что кратчайший путь в TENT - это следующий кратчайший путь в сети.
  5. ¬торой важный момент в этом алгоритме - это сравнение между любыми существующими узлами TENT, которые подключаютс€ к одному и тому же узлу; это, в сочетании с сортировкой TENT и отделением TENT от PATH, выполн€ет правило кратчайшего пути.

»ме€ в виду эти моменты, рисунки с 1 по 9 используютс€ дл€ иллюстрации работы алгоритма SPF ƒейкстры.

–ис. 1 Ќебольша€ сеть дл€ демонстрации алгоритма SPF ƒейкстры

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

–ис. 2 ѕервый шаг в расчете SPF ƒейкстры

¬ точке, показанной на рисунке 2, A был перемещен из TOPO в TENT, а затем в PATH. —тоимость исходного узла всегда равна 0; эта лини€ включена дл€ начала расчета SPF. Ёто представл€ет строки с 01 по 09 в псевдокоде, показанном ранее. Ќа рисунке 3 показан второй этап расчета SPF.

Ќа рисунке 3 каждый узел, подключенный к A, был перемещен из TOPO в TENT; это строки с 10 по 17 в псевдокоде, показанном ранее.  огда этот шаг началс€, в TENT была только A, поэтому в TENT нет существующих узлов, которые могли бы вызвать какие-либо сравнени€ метрик. “еперь TENT отсортирован, и выполнение продолжаетс€ со строки 03 в псевдокоде. –исунок 4 демонстрирует это.

–ис. 3 ¬торой шаг в расчете SPF ƒейкстры –ис. 4 “ретий шаг в расчете SPF ƒейкстры

Ќа рисунке 4 один из двух путей с кратчайшей стоимостью - к B и F, каждый со стоимостью 1 - был выбран и перемещен в PATH (строки 05Ц09 в псевдокоде, показанном ранее).  огда B перемещаетс€ из TENT в PATH, любые узлы с началом B в TOPO перемещаютс€ в TENT (строки 10-17 в псевдокоде). ќбратите внимание, что C еще не был в TENT, прежде чем он был задействован посредством перехода B к PATH, поэтому сравнение показателей не выполн€етс€. —тоимость дл€ C - это сумма стоимости его предшественника в PATH (который равен B со стоимостью 1) и св€зи между двум€ узлами; следовательно, C добавл€етс€ к TENT со стоимостью 2. TENT сортируетс€ (строка 3 псевдокода), поэтому процесс готов к повторному запуску. Ќа рисунке 5 показан следующий шаг в этом процессе.

–ис. 5 „етвертый шаг в вычислении SPF ƒейкстры

Ќа рисунке 5 был выбран кратчайший путь к TENT, и F переместилс€ от TENT к PATH. ћежду F и E существует св€зь (показанна€ на предыдущих иллюстраци€х как [E, F]), но путь через F к E имеет ту же стоимость, что и путь [A, E], поэтому эта лини€ не добавл€етс€ в TENT. —корее он остаетс€ неактивным, поскольку не рассматриваетс€ дл€ включени€ в SPT, и удал€етс€ из TOPO. Ќа рисунке 6 показан следующий шаг в процессе, который переместит один из путей метрики 2 в PATH.

–ис. 6 ѕ€тый шаг в расчете SPF ƒейкстры
ѕримечание. Ѕольшинство реальных реализаций поддерживают перенос нескольких путей с одинаковой стоимостью из TENT в PATH, поэтому они могут пересылать трафик по всем каналам с одинаковой метрикой. Ёто называетс€ многолучевым распространением с равной стоимостью или ECMP. ƒл€ этого есть несколько различных способов, но они в этих лекци€х не рассматриваютс€.

Ќа рисунке 6 путь к C через B со стоимостью 2 был перемещен в PATH, а путь к D через [A, B, C, D] перемещен в TENT. ќднако при перемещении этого пути к TENT строка 11 в псевдокоде находит существующий путь к D в TENT, путь [A, D], со стоимостью 5. ћетрика нового пути, 3, ниже чем метрика существующего пути, 5, поэтому путь [A, D] удал€етс€ из TENT, когда добавл€етс€ путь [A, B, C, D] (строка 15 в псевдокоде). Ќа рисунке 7 показан следующий шаг, на котором лини€ оставшейс€ стоимости 2 перемещаетс€ из TENT в PATH.

Ќа рисунке 7 путь к E стоимостью 2 был перемещен из TENT в PATH. G был перемещен в TENT стоимостью 4 (сумма [A, E] и [E, G]). ƒругой сосед E, F, исследуетс€, но он уже находитс€ в PATH, поэтому не рассматриваетс€ дл€ включени€ в TENT. Ќа рисунке 8 показан следующий шаг, который перемещает D в PATH.

–ис. 7 Ўестой шаг в расчете SPF ƒейкстры –ис. 8 —едьмой шаг в расчете SPF ƒейкстры

Ќа рисунке 8 D общей стоимостью 3 перемещен из TENT в PATH. Ёто учитывает соседа D, G, последнюю запись в TOPO, дл€ TENT. ќднако уже существует путь к G с общей стоимостью 4 через [A, E, G], поэтому строка 14 в псевдокоде завершаетс€ ошибкой, и путь [D, G] удал€етс€ из TOPO. Ёто последний SPT.

ќсновна€ трудность в понимании алгоритма ƒейкстры заключаетс€ в том, что правило кратчайшего пути не выполн€етс€ в одном месте (или на одном маршрутизаторе), как это происходит с Bellman-Ford или Diffusing Update Algorithm (DUAL).  ратчайший путь (по-видимому) провер€етс€ только при перемещении узлов из TOPO в TENT - но на самом деле сортировка самого TENT выполн€ет другую часть правила кратчайшего пути, и проверка по PATH дл€ существующих узлов составл€ет еще один шаг в процесс, делающий процесс трехступенчатым:

  1. ≈сли путь к узлу длиннее, чем любой из TENT, то путь к TENT €вл€етс€ более коротким путем по всей сети.
  2. ѕуть, который подн€лс€ к вершине TENT через сортировку, €вл€етс€ самым коротким к этому узлу в сети.
  3. ≈сли путь перемещаетс€ к PATH от вершины TENT, это кратчайший путь к этому узлу в сети, и любые другие записи в TOPO к этому узлу следует отбросить.

ѕри наличии базового алгоритма полезно рассмотреть некоторые оптимизации и расчет Loop-Free Alternates (LFAs) и remote Loop-Free Alternates (rLFAs).


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

Ќет особой причины, по которой весь SPT должен перестраиватьс€ каждый раз, когда происходит изменение топологии сети или информации о доступности. –ассмотрим рисунок 9 дл€ объ€снени€.

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

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

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

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

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


–асчет LFA и rLFA.

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

–ис. 10 ¬ычисление 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. –исунок 11 используетс€ дл€ иллюстрации изнутри P/Q Space.

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

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

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

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

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

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


>