То, что точно может привести к бесконечности в алгоритме bellman-ford

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

Итак, в этом примере алгоритм Bellman-Ford будет сходиться для каждого маршрутизатора, они будут иметь записи друг для друга. 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 и т.д., Однако, если стоимость уменьшается на конвергентном маршруте, это не будет приводить к изменению. Это верно? Это растущая стоимость между ссылками, которые могут вызвать проблему, а не снижать затраты? Есть ли другие возможные причины? Будет ли прием маршрутизатора в автономном режиме таким же, как выход ссылки?

Ответ 1

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

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

    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) стоит дорого.
Это называется "count to infinity" (если w(R1,R3)=infinity и является единственным путем - он будет продолжать считать вечно).

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

Ответ 2

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

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

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

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

Ответ 3

Это не подтверждает часть алгоритма Bellman-Ford Algorithm, но это упрощенный ответ. Здесь идет.

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

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

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

Пример:

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

Маршрутизатор 1 делает какую-то простую математику: "Если мне требуется один прыжок, чтобы добраться до Router 2, а Router 2 делает два прыжка, чтобы добраться до Router 3, мне нужно три прыжка, чтобы добраться до Router 3. Великолепно!" Маршрутизатор 2 выполняет аналогичную математику и добавляет один прыжок к этому маршруту и т.д.

Так работает цикл.

Ответ 4

Удерживает нажатие:

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

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

Задержка конвергенции Отсутствие цикла
Полная информация о пути в рекламе маршрута
Явные запросы для циклов (например, DUAL) Разделение горизонта
Никогда не рекламируйте пункт назначения через свой следующий прыжок
- A не рекламирует C к B
Отравление звука: Отправлять отрицательную информацию при рекламе адресата через следующий скачок.
А рекламирует C на B с метрикой ∞
- Ограничение: работает только для "петли" размера 2