23. Маршрутизация с учетом состояния линий

Маршрутизация на основе векторов расстояний использовалась в сети ARPANET вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состоя­ния линий. Отказаться от прежнего алгоритма пришлось по двум причинам. Во-первых, старый алгоритм при выборе пути не учитывал пропускную способность линий. Пока все линии имели пропускную способность 56 Кбит/с, в учете пропу­скной способности не было необходимости. Однако стали появляться линии со скоростью 230 Кбит/с, а затем и 1,544 Мбит/с, и не принимать во внимание про­пускную способность стало невозможно. Конечно, можно было ввести пропуск­ную способность в качестве множителя для единицы измерения, но имелась еще и другая проблема, заключавшаяся в том, что алгоритм слишком долго приходил к устойчивому состоянию (проблема счета до бесконечности). Поэтому он был заменен полностью новым алгоритмом, который сейчас называется маршрутиза­цией с учетом состояния линий. Варианты этого алгоритма широко применяют­ся в наши дни.

• В основе алгоритма лежит простая идея, ее можно изложить в пяти требова­ниях к маршрутизатору. Каждый маршрутизатор должен:

1.          Обнаруживать своих соседей и узнавать их сетевые адреса.

2.          Измерять задержку или стоимость связи с каждым из своих соседей.

3.          Создавать пакет, содержащий всю собранную информацию.

4.          Посылать этот пакет всем маршрутизаторам.

5.          Вычислять кратчайший путь ко всем маршрутизаторам.

В результате каждому маршрутизатору высылаются полная топология и все измеренные значения задержек. После этого для обнаружения кратчайшего пути к каждому маршрутизатору может применяться алгоритм Дейкстры.