⚡ ѕ–ќ…ƒ» Ќќ¬џ… ќЌЋј…Ќ  ”–— ѕќ —≈“≈¬џћ “≈’ЌќЋќ√»яћ —ќ — »ƒ ќ… 50%

до конца скидки осталось

Ќачать обучение 🚀
ћерион Ќетворкс

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

ѕерва€ часть тут.

ќбучайс€ в Merion Academy

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

Ќачать

¬ектор пути основан на хранении списка узлов, через которые проходит путь. Ћюбой узел, который получает обновление с самим собой в пути, просто отбрасывает обновление, поскольку это не жизнеспособный путь. –исунок 12 используетс€ в качестве примера. Ќа рисунке 12 каждое устройство объ€вл€ет информацию о местах назначени€ каждому соседнему устройству; дл€ пункта назначени€, прикрепленного к E:

  • E будет анонсировать F с самим собой в источнике, поэтому с путем [E], как B, так и D.
  • ќт B: B анонсирует F к A с путем [E, B].
  • »з D: D анонсирует F в C с путем [E, D].
  • ќт C: C анонсирует F к A с путем [E, D, C]

 акой путь предпочтет A? ¬ системе вектора пути может быть р€д метрик, включа€ длину пути, предпочтени€ политики и т. д. Ќапример, предположим, что есть метрика, котора€ устанавливаетс€ локально на каждом узле, переносимом с каждым маршрутом. Ёта локальна€ метрика переноситс€ между узлами, но никак не суммируетс€ при прохождении через сеть, и каждый узел может устанавливать эту метрику независимо от других узлов (при условии, что узел использует одну и ту же метрику по отношению к каждому соседу). Ќапример, локальна€ метрика E объ€вл€етс€ B, который затем устанавливает свою собственную локальную метрику дл€ этого пункта назначени€ и объ€вл€ет результирующий маршрут A и т. д.

–ис. 12 ѕример операции с вектором пути

„тобы определить лучший путь, каждый узел может затем

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

≈сли каждый узел в сети всегда будет следовать этим трем правилам, то петл€ не образуетс€.

Ќапример:

  • E объ€вл€ет F в B с путем [E] и метрикой 100.
  • B объ€вл€ет F к A с путем [E, B] и метрикой 100.
  • E объ€вл€ет F в D с путем [E] и метрикой 100.
  • D объ€вл€ет F в C с путем [E, D] и метрикой 100.
  • C объ€вл€ет F в A с путем [E, D, C] и метрикой 100.

” A есть два пути, оба с одинаковой метрикой, и, следовательно, будет использовано второе правило, чтобы выбрать один путь, который €вл€етс€ наиболее коротким. ¬ этом случае A выберет путь через [E, B]. A будет объ€вл€ть маршрут, который он использует, к C, но если C следует тому же набору правил, у него также будет два пути с доступной метрикой 100, один с путем [E, B, A], а второй с путем [E, D, C]. ¬ этом случае должен быть механизм разрешени€ конфликтов, который C использует внутри дл€ выбора между двум€ маршрутами. Ќеважно, что это за механизм разрешени€ конфликтов, если он посто€нно примен€етс€ в узле. Ќезависимо от того, какой путь выберет C, трафик к F не будет закольцован. ѕредположим, однако, несколько иное стечение обсто€тельств:

  • E объ€вл€ет F в B с путем [E] и метрикой 100.
  • B объ€вл€ет F к A с путем [E, B] и метрикой 100.
  • E объ€вл€ет F в D с путем [E] и метрикой 50.
  • D объ€вл€ет F в C с путем [E, D] и метрикой 50.
  • C объ€вл€ет F в A с путем [E, D, C] и метрикой 50.

” A есть два пути: один с метрикой 100, а другой с метрикой 50.

—ледовательно:

  • A выберет более высокую из двух метрик, путь через [E, B], и объ€вит этот маршрут C
  • C выберет более высокую из двух метрик, путь через [E, B, A], и объ€вит этот маршрут D.
  • D выберет более высокий из двух метрик, путь через [E, B, A, C], и объ€вит этот маршрут E.
  • E отбросит этот маршрут, поскольку E уже находитс€ на пути.

—ледовательно, даже если метрика перекрывает длину пути в (почти) каждом узле, цикл не образуетс€.


ѕроблемы метрик

 аждый алгоритм, обсуждавшийс€ до этого момента, использовал одну метрику дл€ вычислени€ путей без петель, за исключением вектора пути, а вектор пути использует две метрики очень ограниченным образом, причем одна всегда предпочтительнее другой. ѕуть, по сути, можно рассматривать как Ђфактор разрешени€ конфликтовї, который вступает в игру только тогда, когда основна€ метрика, котора€ никак не св€зана с путем (поскольку она не суммируетс€ шаг за шагом в сети), не соответствует предотвратить петлю. Ќекоторые протоколы могут использовать несколько метрик, но они всегда будут каким-то образом комбинировать эти метрики, поэтому дл€ поиска путей без петель используетс€ только одна комбинированна€ метрика. ѕочему?

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

ѕроблема с множественными метриками классифицируетс€ как NP-complete, и, следовательно, хот€ и разрешима, она никоим образом не решаема, что позвол€ет использовать ее в коммуникационных сет€х, близких к реальному времени.


јлгоритмы непересекающихс€ путей

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

¬ таких ситуаци€х часто требуетс€ передать две копии каждого пакета, а затем позволить получателю выбрать пакет, наилучшим образом соответствующий характеристикам качества обслуживани€ (QoS) и потер€м пакетов, необходимым дл€ поддержки приложени€. ќднако все системы, рассмотренные до сих пор, могут найти только один путь без циклов и потенциально альтернативный путь (LFA и / или rLFA). “аким образом, с помощью алгоритмов непересекающихс€ путей решаетс€ следующа€ проблема:

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

¬ этой части лекций мы начнем с описани€ концепции двухсв€зной сети, а затем рассмотрим два разных (но, казалось бы, св€занных) способа вычислени€ непересекающихс€ топологий в двухсв€зных сет€х.


ƒвухсв€зные сети

ƒвусв€зна€ сеть - это люба€ сеть, в которой есть как минимум два пути между источником и местом назначени€, которые не используют одни и те же устройства (узлы) или каналы (ребра). ќбратите внимание на:

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

„асто проще всего пон€ть двусв€зность на реальном примере. Ќа рисунке 13 показана сеть, с выделенными блоками.

–ис. 13 ѕример двусторонней подключенной сети

¬ блоке A есть как минимум два разных непересекающихс€ пути между X и F:

  • [X, A, B, E, F] и [X, C, F]
  • [X, A, B, F] и [X, C, F]

¬ блоке B есть одна пара непересекающихс€ путей из G в L: [G, K, L] и [G, H, L]. Ќепересекающихс€ путей к Z нет, так как этот узел односв€зен. ћежду F и G также нет непересекающихс€ путей, так как они односв€зны.  анал [F, G] можно рассматривать как узкую точку между этими двум€ блоками топологии. ¬ сети, показанной на рисунке 13, невозможно вычислить два непересекающихс€ пути между X и Z.


јлгоритм непересекающегос€ пути —уурбалле

¬ 1974 году ƒж. —уурбалле опубликовал статью, описывающую, как использовать несколько запусков SPF-алгоритма ƒейкстры дл€ поиска нескольких непересекающихс€ топологий в сети. јлгоритм по существу вычисл€ет SPF один раз, удал€ет подмножество линий, используемых в SPT, а затем вычисл€ет второй SPF по оставшимс€ лини€м. јлгоритм —уурбалле труднее объ€снить, чем проиллюстрировать на примере, поскольку он опираетс€ на направленный характер св€зей, вычисл€емых с помощью SPT. ¬ качестве примеров используютс€ рисунки 14-18.

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

–ис. 14 »спользование алгоритма —уурбалле дл€ поиска непересекающихс€ путей, шаг 1

–ебра (или св€зи) на SPT называютс€ ребрами дерева, а ребра (или св€зи), не вход€щие в результирующий SPT, называютс€ ребрами не деревьев. Ќа рис. 14 кра€ дерева отмечены сплошным черным цветом со стрелками направлени€, а ребра не деревьев - более светлыми серыми пунктирными лини€ми.

¬торой шаг показан на рисунке 15.

Ќа рисунке 15 показано каждое звено с измененными затратами; кажда€ лини€, котора€ была частью исходного SPT (каждое ребро дерева, показано сплошной линией), имеет две стоимости, по одной в каждом направлении, в то врем€ как линии, которые изначально не были частью SPT (ребра, не вход€щие в состав дерева, показаны пунктирными лини€ми), имеют свои исходные расходы. ќбратите внимание на стрелки, показывающие направление стоимости в каждом случае; это будет важно на следующем этапе расчета. ƒл€ расчета стоимости двух направленных линий дл€ каждого ребра дерева:

  • »менуем один конец линии символом u, а другой конец линии символом v. ќбратите внимание, что уравнение выполн€етс€ в обоих направлени€х.
  • ¬ычтем стоимость источника до v из стоимости линии от u до v.
  • ƒобавим стоимость из источника к u.
–ис. 15 »спользование алгоритма —уурбалле дл€ поиска непересекающихс€ путей, шаг 2

≈сли источник s: d[sp](u,v) = d(u,v) ? d(s,v) + d(s,u)

ѕо сути, это устанавливает стоимость ребер дерева равной 0, как можно увидеть, выполнив математические вычислени€ дл€ ссылки [B, E]:

  • B - есть u, E - есть v, A - есть s
  • d(u,v) = 2, d(s,v) = 3, d(s,u) = 1
  • 2 ? 3 + 1 = 0

ќднако дл€ всех ребер, не вход€щих в дерево, будет установлена некотора€ (обычно больша€) ненулева€ стоимость. ƒл€ сети на рисунке 15:

ƒл€ линии [B, A] (примечание [A, B] не €вл€етс€ линией в вычисл€емом дереве направлений):

  • B - есть u, A - есть v, A - есть s
  • d(u,v) = 0, d(s,v) = 0, d(s,u) = 1
  • 0 ? 0 + 1 = 1

ƒл€ линии [E,B]:

  • E Ц есть u, B Ц есть v, A - есть s
  • d(u,v) = 2, d(s,v) = 1, d(s,u) = 3
  • 2 ? 1 + 3 = 4

ƒл€ линии [C,A]:

  • C Ц есть u, A Ц есть v, A Ц есть s
  • d(u,v) = 2, d(s,v) = 0, d(s,u) = 2
  • 2 ? 0 + 2 = 4

ƒл€ линии [F,D]:

  • F Ц есть u, D Ц есть v, A Ц есть s
  • d(u,v) = 1, d(s,v) = 4, d(s,u) = 5
  • 1 ? 4 + 5 = 2

ƒл€ линии [D,B]:

  • D Ц есть u, B Ц есть v, A Ц есть s
  • d(u,v) = 1, d(s,v) = 1, d(s,u) = 2
  • 1 ? 1 + 2 = 2

—ледующий шаг, показанный на рисунке 16, состоит в том, чтобы удалить все направленные ребра, указывающие на источник, который лежит вдоль исходного SPT к определенному месту назначени€ (в данном случае Z), изменить направление ребер с нулевой стоимостью (линий) вдоль этого же пути, а затем снова запустить SPF ƒейкстры, создав второй SPT на той же топологии.

¬озвраща€сь к исходному SPT, путь от X до Z проходил по пути [A,B,D,F]. “аким образом, четыре ненулевых ребра (пунктирные линии), указывающие назад к источнику, ј, вдоль этого пути были удалены. ¬доль того же пути [A, B,D,F] направление каждого ребра было изменено. Ќапример, [A,B] первоначально указывало от A к B, а теперь указывает от B к A. —ледующий шаг-запустить SPF по этому графику, помн€, что трафик не может течь против направлени€ линии. ѕолученное дерево показано на рисунке 17.

Ќа рисунке 17 показано исходное дерево и вновь вычисленное дерево, наложенные на исходную топологию в виде двух различных пунктирных линий. Ёти две топологии все еще имеют общую св€зь [B,D], так что они еще не совсем разобщены. ¬ этой точке есть два кратчайших пути от X до Z:

  • [A,B,D,F]
  • [A,C,D,B,E,F]
–ис. 16 »спользование алгоритма —уурбалле дл€ поиска непересекающихс€ путей, шаг 3 –ис. 17 »спользование алгоритма —уурбалле дл€ поиска непересекающихс€ путей, шаг 4

Ёти два графа объедин€ютс€, образу€ набор ребер, и любые св€зи, которые включены в оба графа, но в противоположных направлени€х, отбрасываютс€; комбинированный набор выгл€дит так: [A->B, B->E, E->F, A->C, C->D, D->F]

ќбратите внимание на направленность каждой линии св€зи еще раз - очень важно отсечь перекрывающуюс€ линию, котора€ будет указана как [B-> D] и [D-> B]. — помощью этого подмножества возможных ребер на графе можно увидеть правильный набор кратчайших путей: [A, B, E, F] и [A, C, D, F].

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


ћаксимально избыточные деревь€

Ѕолее простой альтернативой алгоритму —уурбалла дл€ вычислени€ непересекающихс€ деревьев €вл€етс€ вычисление максимально избыточных деревьев (Maximally Redundant Trees-MRT). „тобы лучше пон€ть MRT - это изучить Depth First Search (DFS), особенно нумерованный DFS. –исунок 18 используетс€ в качестве иллюстрации.

–ис. 18  ѕример  Depth First Search

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

01 main {
02 dfs_number = 1
03 root.number = dfs_number
04 recurse_dfs(root)
05 }
06 recurse_dfs(current) {
07 for each neighbor of current {
08 child = left most neighbor (not visited)
09 if child.number == 0 {
10 dfs_number++
11 child.number = dfs_number
12 if child.children > 0 {
13 recurse_dfs(child)
14 }
15 }
16 }
17 }

Ћучший способ пон€ть этот код-пройти рекурсию несколько раз, чтобы увидеть, как она работает. »спользу€ рисунок 18:

  • ѕри первом вызове recurse_dfs в качестве текущего узла устанавливаетс€ A или root.
  • ќказавшись внутри recurse_dfs, выбираетс€ крайний левый узел A или B.
  • B не имеет номера при входе в цикл, поэтому оператор if в строке 09 верен.
  • B назначаетс€ следующий номер DFS (строка 11).
  • ” B есть дочерние элементы (строка 12), поэтому recurse_dfs вызываетс€ снова с B в качестве текущего узла.
  • ќказавшись внутри (второго уровн€) recurse_dfs, выбираетс€ крайний левый сосед B, которым €вл€етс€ E.
  • E не имеет номера DFS, поэтому оператор if в строке 09 верен.
  • E назначаетс€ следующий номер DFS (3)
  • E не имеет дочерних элементов, поэтому обработка возвращаетс€ к началу цикла.
  • F теперь €вл€етс€ крайним левым соседом B, который не был посещен, поэтому он назначен дочернему элементу.
  • F не имеет числа, поэтому оператор if в строке 09 верен.
  • F назначаетс€ следующий номер DFS (4).
  • ” B больше нет дочерних элементов, поэтому цикл for в строке 07 завершаетс€ ошибкой, и программа recurse_dfs завершаетс€.
  • ќднако на самом деле recurse_dfs не выходит - он просто Ђвозвращаетс€ї к предыдущему уровню рекурсии, то есть к строке 14. Ётот уровень рекурсии все еще обрабатывает соседей A.
  • C - следующий сосед A, который не был затронут, поэтому дочерний элемент установлен в C.
  • » так далее

»зучение номеров узлов в правой части рисунка 18 приводит к следующим интересным наблюдени€м:

  • ≈сли A всегда следует за возрастающим числом, чтобы достичь D,оно будет следовать по пути [A, C,G,D].
  • ≈сли D всегда следует за уменьшающимс€ числом DFS, чтобы достичь A,он будет следовать по пути [D, A].
  • Ёти два пути на самом деле не пересекаютс€.

Ёто свойство сохран€етс€ дл€ всех топологий, которым были присвоены номера в результате поиска DFS: путь, следующий за посто€нно увеличивающимис€ числами, всегда будет не пересекатьс€ с путем, который всегда следует за убывающими числами. Ёто именно то свойство, на котором MRT стро€т непересекающиес€ пути. ќднако проблема с нумерацией DFS заключаетс€ в том, что это трудно сделать почти в реальном времени. ƒолжен быть какой-то избранный корень, трафик на локальном уровне неоптимален (во многом как Minimum Spanning Tree или MST), и любые изменени€ в топологии требуют перестройки всей схемы нумерации DFS. „тобы обойти эти проблемы, MRT строит непересекающиес€ топологии, использу€ тот же принцип, но другим способом. –исунок 19 используетс€ дл€ по€снени€.

ѕервым шагом в построении MRT €вл€етс€ поиск короткого цикла в топологии от корн€ (обычно эти петли обнаруживаютс€ с помощью алгоритма SPF ƒейкстры). ¬ этом случае в качестве корн€ будет выбран A, а цикл будет [A, B, C, D]. Ётот первый цикл будет использоватьс€ как перва€ из двух топологий, скажем, красна€ топологи€. ќбращение цикла к [A, D, C, B] создает непересекающуюс€ топологию, скажем, синюю топологию. Ёта перва€ пара топологий через этот короткий цикл называетс€ Ђухомї.

ƒл€ расширени€ диапазона ћ–“ к первому добавл€етс€ второе ухо. ƒл€ этого открываетс€ второй цикл, на этот раз через [A, D, F, E, B], а непересекающа€с€ топологи€ - [A, B, E, F, D]. ¬озникает вопрос: какое из этих двух расширений топологии следует добавить к красной топологии, а какое - к синей? «десь вступает в игру форма нумерации DFS.

–ис. 19 ѕример сети дл€ построени€ MRT

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

”читыва€ эти уникальные идентификаторы и возможность вычисл€ть нижнюю точку, каждый узел в сети может быть упор€дочен так же, как ему был присвоен номер в процессе нумерации DFS.  люч в том, чтобы знать, как пор€док соответствует существующей красной и синей топологи€м. ѕредположим, что нижн€€ точка B выше, чем C, если топологи€ [A, B, C, D] €вл€етс€ частью красной топологии. ƒл€ любого другого Ђухаї или петли в топологии, котора€ проходит через B и C, направление Ђухаї, в котором B меньше C, должно быть помещено в красную топологию. ѕетл€ в обратном направлении должна быть размещена на синей топологии. Ёто объ€снение €вл€етс€ довольно поверхностным, но оно дает вам представление о том, как MRT образуют непересекающиес€ топологии.


ƒвусторонн€€ св€зь

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

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

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

”ровень управлени€ может решить эту проблему несколькими способами:

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

>