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

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

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

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

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

ќбучайс€ в Merion Academy

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

Ќачать

ѕравило кратчайшего пути, €вл€етс€ скорее отрицательным, чем положительным экспериментом; его всегда можно использовать дл€ поиска пути без петель среди набора доступных путей, но не дл€ определени€ того, какие другие пути в наборе также могут оказатьс€ свободными от петель. –исунок 4 показывает это.

Ќа рисунке 4 легко заметить, что кратчайший путь от A до пункта назначени€ проходит по пути [A, B, F]. “акже легко заметить, что пути [A, C, F] и [A, D, E, F] €вл€ютс€ альтернативными пут€ми к одному и тому же месту назначени€. Ќо свободны ли эти пути от петель? ќтвет зависит от значени€ слова "без петель": обычно путь без петель - это такой путь, при котором трафик не будет проходить через какой-либо узел (не будет посещать какой-либо узел в топологии более одного раза). ’от€ это определение в целом хорошее, его можно сузить в случае одного узла с несколькими следующими переходами, через которые он может отправл€ть трафик в достижимый пункт назначени€. ¬ частности, определение можно сузить до:

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

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

–ассмотрим, например, путь [A, C, F]. ≈сли A отправл€ет пакет C дл€ пункта назначени€ за пределами F, переправит ли C этот пакет обратно в A? ƒоступные пути дл€ C:

  • [C, A, B, F], общей стоимостью 5
  • [C, A, D, E], общей стоимостью 6
  • [C, F], общей стоимостью 2
Alternate Loop-Free пути

”читыва€, что C собираетс€ выбрать кратчайший путь к месту назначени€, он выберет [C, F] и, следовательно, не будет пересылать трафик обратно в A. ѕревраща€ это в вопрос: почему C не будет перенаправл€ть трафик обратно в A? ѕотому что у него есть путь, стоимость которого ниже, чем у любого пути через A до места назначени€. Ёто можно обобщить и назвать downstream neighbor:

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

»ли, скорее, учитыва€, что локальна€ стоимость представлена как LC, а стоимость соседа представлена как NC, тогда:

≈сли NC LC, то тогда neighbor is downstream.

“еперь рассмотрим второй альтернативный путь, показанный на рисунке 4: [A, D, E, F]. ≈ще раз, если A отправл€ет трафик к пункту назначени€ к D, будет ли D зацикливать трафик обратно к A?

»меющиес€ у D пути:

  • [D, A, C, F], общей стоимостью 5
  • [D, A, B, F], общей стоимостью 4
  • [D, E, F], общей стоимостью 3

ѕредполага€, что D будет использовать кратчайший доступный путь, D будет пересылать любой такой трафик через E, а не обратно через A. Ёто можно обобщить и назвать альтернативой без петель (Loop-Free Alternate -LFA):

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

»ли, скорее, учитыва€, что локальна€ стоимость обозначена как LC, стоимость соседа обозначена как NC, а стоимость обратно дл€ локального узла (с точки зрени€ соседа) - BC:

≈сли NC + BC LC, то сосед - это LFA.

≈сть две другие модели, которые часто используютс€ дл€ объ€снени€ Loop-Free Alternate: модель водопада и пространство P/Q. ѕолезно посмотреть на эти модели чуть подробнее.


ћодель водопада (Waterfall (or Continental Divide) Model).

ќдин из способов предотвратить образование петель в маршрутах, рассчитываемых плоскостью управлени€, - просто не объ€вл€ть маршруты сосед€м, которые пересылали бы трафик обратно мне (отправл€ющему узлу). Ёто называетс€ разделенным горизонтом (split horizon). Ёто приводит к концепции трафика, проход€щего через сеть, действующую как вода водопада или вдоль русла ручь€, выбира€ путь наименьшего сопротивлени€ к месту назначени€, как показано на рисунке 5.

ѕоток трафика от разделени€ пакетов на основе метрик

Ќа рисунке 5, если трафик входит в сеть в точке C (в источнике 2) и направл€етс€ за пределы E, он будет течь по правой стороне кольца. ќднако, если трафик входит в сеть в точке A и предназначен дл€ выхода за пределы E, он будет проходить по левой стороне кольца. „тобы предотвратить зацикливание трафика, выход€щего за пределы E, в этом кольце, одна проста€ вещь, которую может сделать плоскость управлени€, - это либо не позволить A объ€вл€ть пункт назначени€ в C, либо не позволить C объ€вл€ть пункт назначени€ в A. ѕредотвращение одного из этих двух маршрутизаторов от объ€влени€ к другому называетс€ разделенным горизонтом (split horizon), потому что это останавливает маршрут от распространени€ через горизонт, или, скорее, за пределами точки, где любое конкретное устройство знает, что трафик, передаваемый по определенному каналу, будет зациклен.

Split horizon реализуетс€ только за счет того, что устройству разрешаетс€ объ€вл€ть о доступности через интерфейсы, которые оно не использует дл€ достижени€ указанного пункта назначени€. ¬ этом случае:

  • D использует E дл€ достижени€ пункта назначени€, поэтому он не будет объ€вл€ть о доступности в направлении E
  • C использует D дл€ достижени€ пункта назначени€, поэтому он не будет объ€вл€ть о доступности D
  • B использует E дл€ достижени€ пункта назначени€, поэтому он не будет объ€вл€ть о доступности в направлении E
  • A использует B дл€ достижени€ пункта назначени€, поэтому он не будет объ€вл€ть о доступности B

—ледовательно, A блокирует B от знани€ альтернативного пути, который он имеет к месту назначени€ через C, а C блокирует D от знани€ об альтернативном пути, который он имеет к месту назначени€ через A. јльтернативный путь без петель пересекает этот разделенный горизонт. точка в сети. Ќа рис. 12-5 A может вычислить, что стоимость пути C меньше стоимости пути A, поэтому любой трафик A, направл€емый в C к месту назначени€, будет перенаправлен по какому-то другому пути, чем тот, о котором знает A. C, в терминах LFA, €вл€етс€ нижесто€щим соседом A.

—ледовательно, A блокирует B от знани€ об альтернативном пути, который он имеет к месту назначени€ через C, и C блокирует D от знани€ об альтернативном пути, который он имеет к месту назначени€ через A. јльтернативный путь без петли будет пересекать эту точку split horizon в сети. Ќа рисунке 5 A может вычислить, что стоимость пути C меньше стоимости пути A, поэтому любой трафик A, направленный в C к месту назначени€, будет перенаправлен по какому-то другому пути, чем тот, о котором знает A. ¬ терминах LFA, — €вл€етс€ нижесто€щим соседом (downstream neighbor) A.


P/Q пространство

≈ще одна модель, описывающа€, как работают LFA, - это пространство P / Q.

–исунок 6 иллюстрирует эту модель.

ѕроще всего начать с определени€ двух пространств.

ѕредполага€, что лини€ св€зи [E, D] должна быть защищена от сбо€:

  • –ассчитайте Shortest Path Tree из E (E использует стоимость путей к себе, а не стоимость от себ€, при вычислении этого дерева, потому что трафик течет к D по этому пути).
  • ”далите линию св€зи [E,D] вместе с любыми узлами, доступными только при прохождении через эту линию.
  • ќстальные узлы, которых может достичь E, - это пространство Q.
P-пространство и Q-пространство
  • –ассчитайте Shortest Path Tree из D.
  • ”далите канал [E, D] вместе со всеми узлами, доступными только при прохождении по линии.
  • ќстальные узлы, которых может достичь D, наход€тс€ в пространстве P.

≈сли D может найти маршрутизатор в пространстве Q, на который будет перенаправл€тьс€ трафик в случае отказа канала [E, D]- это LFA.


”даленные (remote) Loop-Free Alternates

„то делать, если нет LFA? »ногда можно найти удаленную альтернативу без петель (remote Loop-Free Alternate - rLFA), котора€ также может передавать трафик к месту назначени€. RLFA не подключен напр€мую к вычисл€ющему маршрутизатору, а скорее находитс€ на рассто€нии одного или нескольких переходов. Ёто означает, что трафик должен передаватьс€ через маршрутизаторы между вычисл€ющим маршрутизатором и remote next hop. ќбычно это достигаетс€ путем туннелировани€ трафика.

Ёти модели могут объ€снить rLFA, не обраща€ внимани€ на математику, необходимую дл€ их расчета. ѕонимание того, где кольцо "разделитс€" на P и Q, или на две половины, разделенные split horizon, поможет вам быстро пон€ть, где rLFA можно использовать дл€ обхода сбо€, даже если LFA отсутствует. ¬озвраща€сь к рисунку 6, например, если канал [E, D] выходит из стро€, D должен просто ждать, пока сеть сойдетс€, чтобы начать пересылку трафика к месту назначени€. Ћучший путь от E был удален из дерева D из-за сбо€, и E не имеет LFA, на который он мог бы пересылать трафик.

¬ернитесь к определению loop-free path, с которого началс€ этот раздел-это любой сосед, к которому устройство может перенаправл€ть трафик без возврата трафика. Ќет никакой особой причины, по которой сосед, которому устройство отправл€ет пакеты в случае сбо€ локальной линии св€зи, должен быть локально подключен. ¬ разделе "виртуализаци€ сети" описываетс€ возможность создани€ туннел€ или топологии наложени€, котора€ может передавать трафик между любыми двум€ узлами сети.

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

  1. ¬ычислите ближайшую точку в сети, где трафик может быть туннелирован и не вернетс€ к самому C.
  2. —формируйте туннель к этому маршрутизатору.
  3. »нкапсулируйте трафик в заголовок туннел€.
  4. ѕеренаправьте трафик.

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

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


>