<<
>>

Проблема счета до бесконечности

Алгоритм маршрутизации по вектору расстояний работает в теории, но обладает серьезным недостатком на практике: хотя правильный ответ в конце концов и находится, процесс его поиска может занять довольно много времени.
В частности, такой алгоритм быстро реагирует на хорошие новости и очень лениво — на плохие. Рассмотрим маршрутизатор, у которого задержка до маршрутизатора X велика. Если при очередном обмене векторами его сосед сообщит ему, что от него до маршрутизатора X совсем недалеко, наш маршрутизатор просто переключится Для передач маршрутизатору X на линию, проходящую через этого соседа. Таким образом, хорошая новость распространилась всего за один обмен информацией.

Чтобы увидеть, как быстро распространяются хорошие известия, рассмотрим линейную подсеть из пяти узлов, показанную на рис. 5.8, в которой мерой расстояния служит количество транзитных участков. Предположим, что вначале маршрутизатор А выключен и все остальные маршрутизаторы об этом знают.

То есть они считают, что расстояние до А равно бесконечности.

Когда в сети появляется А, остальные маршрутизаторы узнают об этом с помощью обмена векторами. Для простоты будем предполагать, что где-то в сети имеется гигантский гонг, в который периодически ударяют, чтобы инициировать одновременный обмен векторами. После первого обмена В узнает, что у его соседа слева нулевая задержка при связи с А, а В помечает в своей таблице маршрутов, что А находится слева на расстоянии одного транзитного участка. Все остальные маршрутизаторы в этот момент еще полагают, что А выключен. Значения задержек для А в таблицах на этот момент показаны во второй строке на рис. 5.8, я. При следующем обмене информацией С узнает, что у В есть путь к А длиной 1, поэтому он обновляет свою таблицу, указывая длину пути до А, равную 2, но П и Е об этом еще не знают.

Таким образом, хорошие вести распространяются со скоростью один транзитный участок за один обмен векторами. Если самый длинный путь в подсети состоит из N транзитных участков, то через N обменов все маршрутизаторы подсети будут знать о включенных маршрутизаторах и заработавших линиях.

Теперь рассмотрим ситуацию на рис. 5.8, б, в которой все линии и маршрутизаторы изначально находятся во включенном состоянии. Маршрутизаторы В, С, Пи Е находятся от А на расстоянии 1, 2, 3 и 4 соответственно. Внезапно А отключается или, возможно, происходит обрыв линии между А V. В, что с точки зрения В одно и то же.

При первом обмене пакетами В не слышит ответа от А. К счастью, С говорит: «Не волнуйся. У меня есть путь к А длиной 2». В не знает, что путь от С к Л проходит через В. В может только предполагать, что у С около 10 выходных линий с независимыми путями к А, кратчайшая из которых имеет длину 2. Поэтому теперь В думает, что может связаться с А через С по пути длиной 3. При этом первом обмене маршрутизаторы Ои£не обновляют свою информацию об А.

При втором обмене векторами С замечает, что у всех его соседей есть путь к А длиной 3. Он выбирает один из них случайным образом и устанавливает свое расстояние до А равным 4, как показано в третьей строке на рис. 5.8, б. Результаты последующих обменов векторами также показаны на этом рисунке.

Теперь должно быть понятно, почему плохие новости медленно распространяются — ни один маршрутизатор не может установить значение расстояния, более чем на единицу превышающее минимальное значение этого расстояния, хранящееся у его соседей. Таким образом, все маршрутизаторы будут до бесконечности увеличивать значение расстояния до выключенного маршрутизатора. Количество необходимых для завершения этого процесса обменов векторами можно ограничить, если установить значение этой «бесконечности» равным длине самого длинного пути плюс 1. Если расстояния в подсети измеряются во временных задержках, такую верхнюю границу выбрать сложнее. Следует выбирать достаточно большое ограничивающее значение, чтобы линия с большой задержкой не была сочтена совсем не работающей. Неудивительно, что эта проблема называется счетом до бесконечности. Было сделано несколько попыток решить ее (например, алгоритм расколотого горизонта, весьма бесполезный во многих случаях, но внесенный в RFC 1058), но все они оказались безуспешными. Суть проблемы заключается в том, что когда X сообщает У о том, что у него есть какой-то путь, у У нет никакой возможности узнать, входит ли он сам в этот путь.

<< | >>
Источник: Э. ТАНЕНБАУМ. КОМПЬЮТЕРНЫЕ СЕТИ 4-Е ИЗДАНИЕ. 2003

Еще по теме Проблема счета до бесконечности:

  1. Бесконечные возможности человека
  2. Бесконечная жизнь духа
  3. Глава 1 Бесконечные отсрочки
  4. Статья 1069. Кредитование счета
  5. ШИШКА См. статью ОТЕК, ШИШКОВИДНАЯ ЖЕЛЕЗА (ПРОБЛЕМЫ) См. ЭПИФИЗ (ПРОБЛЕМЫ).
  6. § 3. Договор банковского счета
  7. 2. Договор расчетного счета
  8. «Проблема» в том виде, в каком мы ее себе представляем, редко оказывается настоящей проблемой
  9. § 1. Понятие договора банковского счета
  10. § 3. Виды договоров банковского счета
  11. ГЛАВА 41. ДОГОВОР БАНКОВСКОГО СЧЕТА
  12. БОЛЬШОЙ ПАЛЕЦ (ПРОБЛЕМЫ) См. статью ПАЛЬЦЫ (ПРОБЛЕМЫ).
  13. Статья 1066. Договор банковского счета
  14. Статья 1067. Заключение договора банковского счета
  15. 3. Договор текущего счета
  16. 4. Расторжение договора банковского счета
  17. § 2. Содержание и исполнение договора банковского счета
  18. 2. Субъекты договора банковского счета