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

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

Bellman-Ford - один из наиболее простых дл€ понимани€ протоколов, поскольку он обычно реализуетс€ путем сравнени€ недавно полученной информации о пункте назначени€ с существующей информацией о том же пункте назначени€. ≈сли вновь обнаруженный маршрут лучше, чем известный в насто€щее врем€, маршрут с более высокой стоимостью просто замен€етс€ в списке путей - в соответствии с правилом кратчайшего пути дл€ поиска путей без петель в сети. “аким образом, перебира€ всю топологию, можно найти набор кратчайших путей к каждому месту назначени€. –исунок 7 используетс€ дл€ иллюстрации этого процесса.

ѕример сети дл€ запуска Bellman-Ford
ѕримечание. ’от€ Bellman-Ford в основном известен своим распределенным вариантом, реализованным в широко распространенных протоколах, таких как Routing Information Protocol (RIP), он изначально был разработан как алгоритм поиска, выполн€емый в единой структуре, описывающей топологию узлов и ребер. Ѕеллман-‘орд рассматриваетс€ здесь как алгоритм.

јлгоритм Bellman-Ford

Bellman-Ford рассчитывает Shortest Path Tree к каждому достижимому пункту назначени€ в наихудшем случае O (V * E), где V - количество узлов (вершин) в сети, а E - количество каналов (ребер). ѕо сути, это означает, что врем€, необходимое Bellman-Ford дл€ работы с топологией и вычислени€ Shortest Path Tree, линейно зависит от количества устройств и каналов. ”двоение количества любого из них удвоит врем€, необходимое дл€ выполнени€. ”двоение обеих одновременно увеличит врем€ работы в 4 раза.

“аким образом, алгоритм Bellman-Ford €вл€етс€ умеренно медленным при использовании против более крупных топологий, когда узлы в таблице топологии начинаютс€ в пор€дке от самого дальнего от корн€ до ближайшего к корню. ≈сли таблица топологии отсортирована от ближайшего к корню до самого дальнего, Bellman-Ford может завершить работу за O(E), что намного быстрее. ¬ реальном мире трудно обеспечить любой пор€док, поэтому фактическое врем€, необходимое дл€ построени€ Shortest Path Tree, обычно находитс€ где-то между O(V * E) и O(E).

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

‘актическое врем€ выполнени€ любого алгоритма, используемого дл€ расчета Shortest Path Tree, обычно ограничиваетс€ количеством времени, требуемым дл€ передачи информации об изменени€х топологии по сети. –еализации всех этих протоколов, особенно в их распределенной форме, будут содержать р€д оптимизаций, чтобы сократить врем€ их выполнени€ до уровн€, намного меньшего, чем наихудший случай, поэтому, хот€ наихудший случай даетс€ в качестве контрольной точки, он часто имеет мало вли€ющие на производительность каждого алгоритма в реальных развернутых сет€х.

„тобы запустить алгоритм Bellman-Ford в этой топологии, ее необходимо сначала преобразовать в набор векторов и рассто€ний и сохранить в структуре данных, такой как показано в “аблице 1.

“опологи€, или грани, представленные в виде таблицы дл€ алгоритма Bellman-Ford

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

// создаем набор дл€ хранени€ ответа, по одной записи дл€ каждого узла
// первый слот в результирующей структуре будет представл€ть узел 1,
// второй узел 2 и т. д.
define route[nodes] {
predecessor // как узел
cost // как целое число
}
// установите дл€ источника (мен€) значение 0
// позици€ 1 в массиве - это запись исходной точки.
route[1].predecessor = NULL
route[1].cost = 0
// таблица 1, приведенна€ выше, содержитс€ в массиве под именем topo
// ќбходим таблицу вершин (граней) один раз дл€ каждой записи в маршруте
// (результаты) таблица, замены более длинных записей на более короткие
i = nodes
while i > 0 {
j = 1
while j <= nodes { // перебирает каждую строку в топологии
table
source_router = topo[j].s
destination_router = topo[j].d
link_cost = topo[j].cost
if route[source_router].cost == NULL {
source_router_cost = INFINITY
} else {
source_router_cost = route[source_router].cost
}
if route[destination_router].cost == NULL {
destination_router_cost = INFINITY
} else {
destination_router_cost = route[destination_router].cost
}
if source_router_cost + link_cost <= destination_router_cost {
route[destination_router].cost = source_router_cost + link_
cost
route[destination_router].predecessor = source_router
}
j = j + 1 //or j++ depending on what pseudocode this is
representing
}
i = i - 1
}

Ётот код обманчиво выгл€дит сложнее, чем есть на самом деле.  лючевой строкой €вл€етс€ сравнение if route [topo [j] .s] .cost + topo [j] .cost route [topo [j] .d] .cost. ѕолезно сосредоточитьс€ на этой строке в примере. ѕри первом прохождении внешнего цикла (который выполн€етс€ один раз дл€ каждой записи в таблице результатов, здесь называетс€ маршрутом):

  • ƒл€ первой строки topo-таблицы:
    • j равно 1, поэтому topo[j] .s - это узел 6 (F), источник вектора в таблице граней
    • j равно 1, поэтому topo[j] .d - это узел 7 (G), адресат вектора в таблице граней.
    • route[6].cost = infinity, topo[1].cost = 1, and route[7].cost = infinity (где infinity - бесконечность)
    • infinity + 1 == infinity, поэтому условие не выполн€етс€ и больше ничего не происходит
  • Ћюба€ запись в topo-таблице с исходной стоимостью infinity даст тот же результат, что и infinity + все, что всегда будет равно infinity. ќстальные строки, содержащие источник со стоимостью infinity, будут пропущены.
  • ƒл€ восьмой строки topo-таблицы (восьма€ грань):
    • j равно 8, поэтому topo[j].s - это узел 1 (A), источник вектора в таблице граней
    • j равно 8, поэтому topo[j].d - это узел 2 (B), место назначени€ вектора в таблице граней.
    • route [1].cost = 0, topo[8].cost=2 и route[2].cost = infinity.
    • 0 + 2 = infinity, поэтому условие выполн€етс€
    • route[2].predecessor установлен на 1, а route [2].cost установлен на 2
  • ƒл€ дев€той строки topo -таблицы (дев€та€ грань):
  • j равно 9, поэтому topo[j].s - это узел 1 (A), источник вектора в таблице граней
  • j равно 9, поэтому topo[j].d - это узел 3 (C), место назначени€ вектора в таблице граней.
  • route[1].cost=0, topo[9].cost=1 и route[3].cost = infinity.
  • 0 + 1 = infinity, поэтому условие выполн€етс€
  • route[3].predecessor установлен на 1, а route[3].cost установлен на 1

¬о втором прогоне внешнего цикла:

  • ƒл€ п€той строки topo-таблицы (п€та€ грань):
  • j равно 5, поэтому topo[j].s - это узел 2 (B), источник вектора в таблице граней
  • j равно 5, поэтому topo[j].d - это узел 6 (F), место назначени€ вектора в таблице граней.
  • route[2].cost=2,topo[5].cost=1 и route[6].cost = infinity.
  • 2 + 1 = infinity, поэтому условие выполн€етс€
  • route[6].predecessor установлен на 2, а route[6].cost установлен на 3

ƒл€ шестой строки topo -таблицы (шеста€ грань):

  • j равно 6, поэтому topo[j].s равно 2 (B), источник вектора в таблице граней
  • j равно 6, поэтому topo[j].d равно 5 (E), место назначени€ вектора в таблице граней
  • route[2].cost=2, topo[6].cost=2 и route[5].cost = infinity.
  • 2 + 2 = infinity, поэтому условие выполн€етс€
  • route[5].predecessor установлен на 2, а route[5].cost установлен на 4
  • ќкончание этого прогона показан в “аблице 2.

¬ третьем прогоне внешнего цикла узел 8 представл€ет особый интерес, поскольку есть два пути к этому месту назначени€. ƒл€ второй строки topo -таблицы (втора€ грань):

  • j равно 2, поэтому topo[j].s - это узел 5 (E), источник вектора в таблице граней
  • j равно 2, поэтому topo[j].d - это узел 8 (H), место назначени€ вектора в таблице граней
  • route[5].cost=4, topo[2].cost=1 и route[8].cost = infinity.
  • 4 + 1 = infinity, поэтому условие выполн€етс€
  • route[8].predecessor установлен на 5, а route[8].cost установлен на 5

ƒл€ третьей строки topo -таблицы (треть€ грань):

  • j равно 3, поэтому topo[j].s - это узел 4 (D), источник вектора в в таблице граней
  • j равно 3, поэтому topo[j].d - это узел 8 (H), источник вектора в таблице граней
  • route[4].cost=2,topo[3].cost=2 и route[8].cost = 5.
  • 2 + 2 = 4, поэтому условие выполн€етс€
  • route[8].predecessor установлен на 4, а route[8].cost установлен на 4

»нтересным моментом в третьем цикле в topo-таблице €вл€етс€ то, что запись дл€ грани [5,8] обрабатываетс€ первой, котора€ устанавливает передатчик 8 (H) на 5 и стоимость на 5. ќднако когда обрабатываетс€ следующа€ строка в таблице topo [4,8], алгоритм обнаруживает более короткий путь к узлу 8 и замен€ет существующий. “аблица 2 показывает состо€ние таблицы маршрутов при каждом проходе через таблицу topo.

÷иклы Ѕеллмана-‘орда по выборочной сети

¬ таблице 2 верхн€€ строка представл€ет запись в таблице маршрутизации и узел, доступный в сети. Ќапример, A (1) представл€ет лучший путь к A, B (2) представл€ет лучший путь к B и т. д. —толбец P представл€ет предшественника или узел, через который A должен пройти, чтобы достичь указанного пункта назначени€. C представл€ет собой стоимость достижени€ этого пункта назначени€. –ассмотренный пример сети может быть завершен за три цикла, если алгоритм настроен так, чтобы обнаруживать завершение дерева. ѕсевдокод, как показано, не имеет никакого теста дл€ этого завершени€ и в любом случае будет выполн€ть полные 8 циклов (по одному дл€ каждого узла).

“еперь почитайте про алгоритм диффузного обновлени€ DUAL.