Алгоритм маршрутизации, основанный на состоянии линий

Алгоритм, основанный на состоянии линий (Line State, LS), знает стоимость всех линий, то есть все эти данные можно подать на вход LS-алгоритма.

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

В результате всех этих широковещательных рассылок все узлы сети получают идентичное и полное представление о сети.

Затем каждый узел может запустить алгоритм, основанный на состояниях линий, и вычислить пути к каждому из узлов.

Широкое применение получил алгоритм Дейкстры, названного по имени его создателя. Алгоритм Дейкстры вычисляет путь с наименьшей стоимостью от одного узла (источника) до всех остальных узлов сети.

Алгоритм Дейкстры является итерационным и после k итераций он определяет пути с наименьшей стоимостью до k узлов-адресатов.

Когда LS-алгоритм завершает свою работу, для каждого становится известен узел-предшественник, через который проходит путь с наименьшей стоимостью к данному узлу. Для каждого узла-предшественника также известен узел-предшественник и т. д.

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

Количество вычислений для нахождения пути с наименьшей стоимостью от источника до всех n адресов определяется формулой n*(n+1)/2.

Таким образом, количество вычислений в алгоритме, основанном на состоянии линий, растет пропорциона-льно квадрату узлов сети.

Кроме этого алгоритму присущи и некоторые другие проблемы, например, осциляция.

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

54. Алгоритм дистанционно – векторной маршрутизации.

В отличие от алгоритма, основанного на состоянии линий и использующего глобальную информацию, дистанционно-векторный (Distance Vector, DV) алгоритм является распределенным, итерационным и асинхронным.

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

Он является итерационным, так как этот процесс продолжается до тех пор, пока соседние узлы не перестанут обмениваться информацией.

(Внимание. Э тот алгоритм сам завершает свою работу. Он не получает «сигнала», требующего остановить работу. Он просто останавливается.)

Алгоритм является асинхронным, так как он не требует, чтобы все узлы работали в жесткой взаимосвязи друг с другом.

Главной структурой данных в дистанционно-векторном алгоритме является таблица расстояний, содержащаяся на каждом узле. В каждой таблице расстояний есть по строке для каждого адресата в сети и по столбцу для каждого ближайшего соседа.

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

Дистанционно-векторный алгоритм также называют алгоритмом Беллмана-Форда, по именам его изобретателей. Он применяется на практике во многих протоколах маршрутизации, включая протоколы Интернета RIP и BGP, является децентрализованным и не пользуется глобальной информацией. Единственной информацией, которой обладает узел, являются стоимости линий, связывающих его с ближайшими соседями, а также сведения, получаемые им от этих ближайших соседей.

Процесс получения от соседей новой информации о стоимости путей, вычисления новых табличных значений и извещения своих соседей об изменениях в стоимости путей продолжается до тех пор, пока стоимости не перестанут изменяться.

С этого момента алгоритм становится статическим, поскольку сообщения с новыми значениями более не посылаются и значения в таблице не пересчитыва-ются; то есть все узлы переходят в состояние ожидания. Алгоритм остается в статическом состоянии до тех пор, пока стоимость какой-либо линии не изменится.

Проблемы алгоритма: «Маршрутная петля» и «счет до бесконечности»