Как алгоритм маршрутизации с вектором расстояния обрабатывает циклы с отрицательным весом?

По этому алгоритму есть довольно много вопросов, но я не смог найти, как он будет обрабатывать циклы с отрицательным весом? Предположим, что маршрутизатор x получает обновление от маршрутизатора y, стоимость которого от y до z равна 5. Позже маршрутизатор x получает обновление от маршрутизатора y, стоимость которого от y до z теперь равна 2. Что делает роутер x? Насколько я понимаю, алгоритм Беллмана Форда утверждает, что в этом случае должна возникать ошибка. Но что делать алгоритму векторной маршрутизации на расстоянии - просто обновлять его, вызывать ошибку или что-то еще?


networking protocols routing bellman-ford graph-algorithm
person mindreader    schedule 08.11.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Не уверен, правильно ли я читаю этот вопрос. Обновления от маршрутизаторов могут указывать новую стоимость пути, будь она выше или ниже, чем раньше. Если x получает обновление от y для пути к z со стоимостью 2 (первоначально 5), то x должен просто обновить свою таблицу пересылки с новым стоимостным путем и использовать этот путь для перехода к z, если это путь с наименьшей стоимостью.

person n2studio    schedule 08.11.2013
comment
Разве это не было бы классифицировано как цикл с отрицательным весом? - person mindreader; 08.11.2013
comment
Цикл с отрицательным весом будет иметь хотя бы одно ребро с весом меньше 0, например -2. Если алгоритм Беллмана-Форда (который используется протоколами маршрутизации с вектором расстояния) обнаруживает цикл с отрицательным весом, он просто прекращает вычисление (выходит из алгоритма). Он попытается выполнить пересчет в следующий раз, когда будет обновление от любого из его соседей. См. здесь. - person n2studio; 09.11.2013

arrow_upward
0
arrow_downward

У вас есть конфликт между более низкой стоимостью Bellman-Ford Algortihm и обновлением стоимости соединения на следующем этапе, первое может быть выполнено между двумя или более разными интерфейсами, чтобы получить более низкую стоимость, например:

** Случай 1: ** Маршрутизатор A имеет 3 соседа N1, N2, N3, а N1, N2, N3 имеют X в качестве соседа

|---2----N1-----4----|
A`--4----N2-----3----X
|---1----N3-----2----|

Для роутера A у нас есть:

 X via N1 =6 
 X via N2=7            the lowest is :**X Via N3=3**
 X Via N3=3

-Здесь A выберет X через N3 (между N1, N2, N3), потому что это самый низкий вариант Случай 2: если стоимость ссылки между (X-N3 = 2 ) были изменены на (X-N3 = 8), как мы предполагаем, из-за конфигурации ссылки (даже 8 больше, чем 2, но это обязательство), N3 должен сообщить об этом A, а A должен обновить стоимость от (X через N3 = 3) до (X через N3 = 9), поэтому мы возвращаемся к случаю (1): выбираем наименьшую стоимость, которая будет через N1

     X via N1 =6 
     X via N2=7            ****the lowest is :**X Via N1=6******
     X Via N3=9
person ibrahim    schedule 28.08.2017