Что именно может вызвать счет до бесконечности в алгоритме Беллмана-Форда

Насколько я понимаю, счет до бесконечности происходит, когда один маршрутизатор передает другому старую информацию, которая продолжает распространяться по сети до бесконечности. Из того, что я читал, это определенно может произойти, когда ссылка удалена.

введите здесь описание изображения

Итак, в этом примере алгоритм Беллмана-Форда будет сходиться для каждого маршрутизатора, у них будут записи друг для друга. R2 будет знать, что он может добраться до R3 по цене 1, а R1 будет знать, что он может добраться до R3 через R2 по цене 2.

Если связь между R2 и R3 отключена, то R2 узнает, что больше не может получить доступ к R3 по этой ссылке, и удалит ее из своей таблицы. Прежде чем он сможет отправить какие-либо обновления, возможно, что он получит обновление от R1, в котором будет объявлено, что он может получить доступ к R3 по цене 2. R2 может получить доступ к R1 по цене 1, поэтому он обновит маршрут к R3 через R1 по цене 3. Затем R1 получит обновления от R2 позже и обновит свою стоимость до 4. Затем они будут продолжать передавать друг другу неверную информацию до бесконечности.

Одна вещь, о которой я упоминал в нескольких местах, заключается в том, что могут быть и другие причины подсчета до бесконечности, кроме просто перехода ссылки в автономный режим, например, изменение стоимости ссылки. Я задумался об этом, и из того, что я могу сказать, мне кажется, что, возможно, проблема может быть вызвана увеличением стоимости ссылки. Однако я не вижу, чтобы снижение стоимости могло вызвать проблему.

Например, в приведенном выше примере, когда алгоритм сходится и R2 имеет маршрут к R3 по цене 1, а R1 имеет маршрут к R3 через R2 по стоимости 2. Если стоимость между R2 и R3 увеличивается до 5. Тогда это вызовет ту же проблему: R2 может получить обновление от R1, рекламируя стоимость 2, и изменить свою стоимость на 3 через R1, затем R1 изменит свой маршрут через R2 на стоимость 4 и так далее. Однако если стоимость на конвергентном маршруте уменьшится, это не приведет к изменению. Это верно? Это увеличение стоимости между ссылками может вызвать проблему, а не снижение стоимости? Есть ли другие возможные причины? Будет ли отключение маршрутизатора от сети таким же, как отключение ссылки?


networking algorithm routing bellman-ford
person Cory Gross    schedule 23.11.2012    source источник
comment
Вы уверены, что говорите о Беллман-форде?   -  person Jun HU    schedule 23.11.2012
comment
@JunHU: это особый вариант распределенного BF, который обычно используется для маршрутизации.   -  person amit    schedule 23.11.2012
comment
это звучит так: с произвольным количеством узлов"> stackoverflow.com/questions/13509348/.   -  person ashley    schedule 23.11.2012
comment
@ashley, у меня была такая проблема на экзамене в университете, хотя он не спрашивает совсем то же самое, что и здесь. Я до сих пор не нашел много точных источников для ответа на точные случаи, когда это может произойти, но все, что я нашел, указывает на то, что повышение стоимости ссылки вызывает проблему, а снижение не вызывает ее.   -  person Cory Gross    schedule 10.05.2013

Ответы (4)


arrow_upward
27
arrow_downward

Посмотрите на этот пример:

введите здесь описание изображения

Таблица маршрутизации будет:

    R1   R2    R3
R1  0    1     2
R2  1    0     1
R3  2    1     0

Теперь предположим, что связь между R2 и R3 потеряна (может линия оборвалась или средний роутер между ними упал).

После одной итерации отправки информации вы получите следующую таблицу маршрутизации:

    R1   R2    R3
R1  0    1     2
R2  1    0     3
R3  2    3     0

Это происходит из-за того, что R2, R3 больше не подключены, поэтому R2 «думает», что может перенаправить пакеты на R3 через R1, путь которого равен 2, поэтому он получит путь веса 3.

После дополнительной итерации R1 «видит», что R2 дороже, чем раньше, поэтому изменяет свою таблицу маршрутизации:

    R1   R2    R3
R1  0    1     4
R2  1    0     3
R3  4    3     0

и так далее, пока они не сойдутся на правильном значении, но это может занять много времени, особенно если (R1, R3) дорого.
Это называется "счет до бесконечности" (если w(R1,R3)=infinity и это единственный путь - он будет продолжать считать вечно).

Обратите внимание, что при увеличении стоимости между двумя маршрутизаторами вы столкнетесь с той же проблемой (предположим, что w(R2,R3) увеличивается до 50 в приведенном выше примере). Произойдет то же самое — R2 попытается направить маршрут к R3 через R1, не «понимая», что это также зависит от (R2,R3), и вы получите те же самые первые шаги и сойдетесь, как только найдете правильную стоимость.
Однако, если стоимость снизится, этого не произойдет, так как новая стоимость лучше, чем текущая, и маршрутизатор R2 будет придерживаться той же маршрутизации с уменьшенной стоимостью и не будет пытаться маршрутизировать через R1.

person amit    schedule 23.11.2012
comment
+1 Я думаю, что понимаю проблему, поскольку она возникает здесь, ваш пример очень помогает, поскольку он более подробный, чем большинство других, которые я видел. Однако, насколько я понимаю, это также может произойти, если стоимость ссылки возрастет? Но не тогда, когда стоимость между двумя маршрутизаторами уменьшается? - person Cory Gross; 23.11.2012
comment
@CoryGross: Вы правы. Когда стоимость между двумя маршрутизаторами увеличивается, вы столкнетесь с той же проблемой (предположим, что w(R2,R3) увеличивается до 50 в приведенном выше примере). Произойдет то же самое — R2 попытается направить маршрут к R3, не осознавая, что это также зависит от R2,R3, и вы получите те же первые шаги и сойдетесь, как только найдете правильную стоимость. Однако, если стоимость снизится, этого не произойдет, поскольку новая стоимость лучше, чем текущая, и маршрутизатор R2 будет придерживаться той же маршрутизации с уменьшенной стоимостью и не будет пытаться маршрутизировать через R1. (добавит его к самому ответу) - person amit; 23.11.2012

arrow_upward
2
arrow_downward

Согласно Википедии:

RIP использует метод разделения горизонта с обратным ядом, чтобы уменьшить вероятность образования петель, и использует максимальное количество переходов для решения проблемы «счета до бесконечности». Эти меры позволяют избежать образования петель маршрутизации в некоторых, но не во всех случаях. Добавление времени удержания (отказ от обновлений маршрута в течение нескольких минут после сокращения маршрута) позволяет избежать образования петель практически во всех случаях, но приводит к значительному увеличению времени сходимости.

Совсем недавно был разработан ряд протоколов вектора расстояния без петель — яркими примерами являются EIGRP, DSDV и Babel. Во всех случаях они избегают образования петель, но страдают повышенной сложностью, а их развертывание замедляется успехом протоколов маршрутизации на основе состояния канала, таких как OSPF.

http://en.wikipedia.org/wiki/Distance-vector_routing_protocol#Workarounds_and_solutions

person Anand Srinivasan    schedule 20.07.2014

arrow_upward
1
arrow_downward

Это не признает часть вопроса алгоритма Беллмана-Форда, но это упрощенный ответ. Вот оно.

Обратите внимание на изображение на оригинальном постере. Есть R1, R2 и R3; представляющие маршрутизаторы 1, 2 и 3 соответственно.

Каждая ссылка стоит 1, а каждый переход стоит 1. Для перехода между двумя маршрутизаторами (например, с R1 на R3) требуется стоимость 2.

Каждый маршрутизатор отслеживает расходы и обновляет информацию. Однако, если есть отсутствующее значение (например, отсутствует связь между маршрутизаторами), счетчик переходов удаляется и заполняется другим маршрутизатором при обновлении таблиц маршрутизации.

Пример:

Если связь маршрутизатора 3 с маршрутизатором 2 прервется, маршрутизатор 2 удалит маршрут из своей таблицы. Маршрутизатор 1 по-прежнему считает, что для доступа к маршрутизатору 3 требуется два перехода. Это реплицируется на маршрутизатор 2, и теперь оба маршрутизатора считают, что для доступа к маршрутизатору 3 требуется два перехода.

Маршрутизатор 1 выполняет простые математические действия: «Если мне требуется один переход, чтобы добраться до маршрутизатора 2, а маршрутизатору 2 требуется два перехода, чтобы добраться до маршрутизатора 3, мне потребуется три перехода, чтобы добраться до маршрутизатора 3. Великолепно!» Маршрутизатор 2 выполняет аналогичные расчеты и добавляет к своему маршруту один прыжок и так далее.

Вот как работает петля.

person BlitzThunderWolf93    schedule 09.03.2014

arrow_upward
0
arrow_downward

Удержание:

  • По мере увеличения метрики задержка распространения информации

Ограничения:

  • Задерживает конвергенцию Избегание петель
  • Полная информация о пути в объявлении маршрута
  • Явные запросы для циклов (например, DUAL) Разделить горизонт
  • Never advertise a destination through its next hop
    • A doesnʼt advertise C to B
  • Ядовитый реверс: отправляйте негативную информацию при рекламе пункта назначения через его следующий переход.
  • A advertises C to B with a metric of ∞
    • Limitation: Only works for “loop”s of size 2
person kosai    schedule 18.01.2016