27
правок
Изменения
Нет описания правки
Каждая запись таблицы состоит из двух частей: предпочитаемые номер линии для данного адресата и предполагаемое расстояние до него. Будем считать, что каждый маршрутизатор знает расстояние до своих соседей(если расстояние изменяется в транзитных участках то оно равно 1, а если же расстояние измеряется временем задержки распространения, то маршрутизатор может измерить его с помощью специального пакета <tex>ECHO</tex>, в который отправитель помещает время отправления, а получатель отправляет обратно как можно быстрее). Каждые <tex>T</tex> мс все маршрутизаторы посылают свои таблицы всем своим соседям и получают подобные вектора от них. Пусть одна из таких таблиц пришла от соседа <tex>X</tex> и в ней указано расстояние от маршрутизатора <tex>X</tex> до маршрутизатора <tex>Y</tex>, обозначим его <tex>T_{xy}</tex>. Если маршрутизатор знает, что расстояние между ним и маршрутизатором <tex>X</tex> равно <tex>T_x</tex>, то расстояние до маршрутизатора <tex>Y</tex> через маршрутизатор <tex>X</tex> равно <tex>T_x + T_{xy}</tex>. Выполнив такие расчеты для всех своих соседей маршрутизатор может выбрать наилучшие пути и поместить их в соответствующую запись таблицы.
====Проблема счета до бесконечности====
Рассмотрим ситуацию: пусть в сети 5 маршрутизаторов <tex>A, B, C, D, E</tex>, соединенных последовательно. Изначально все они включены и расстояние измеряется в количестве транзитных участков. Внезапно связь между маршрутизаторами <tex>A</tex> и <tex>B</tex> теряется, либо <tex>A</tex> просто отключается. При первом обмене пакетами <tex>B</tex> не слышит ответа от <tex>A</tex>, но маршрутизатор <tex>C</tex> сообщает, что он знает путь до <tex>A</tex> длиной 2. Маршрутизатор <tex>B</tex> изменяет запись в таблице и считает, что теперь у него есть путь длиной 3 до маршрутизатора <tex>A</tex>. Аналогично, при следующей рассылке маршрутизатор <tex>C</tex> установит в своей таблице путь до <tex>A</tex> равным 4, так как получит от маршрутизаторов <tex>B</tex> и <tex>D</tex> таблицы, по которым они знают путь до маршрутизатора <tex>A</tex> длиной 3. С каждой следующей итерацией обновления таблиц расстояние до маршрутизатора <tex>A</tex> будет только увеличивается и через какое-то время уйдет в бесконечность.
====Преимущества====
*относительно небольшой объем хранимых каждым маршрутизатором данных
*простой алгоритм пересчета расстояний на каждой итерации
*быстрое распространение хороших новостей
====Недостатки====
*проблемы счета до бесконечности
