7.7.3 Создание пакетов состояния линий
После того как информация, необходимая для обмена, собрана, следующий шаг, выполняемый каждым маршрутизатором, заключается в построении пакета, содержащего все эти данные. Пакет начинается с идентификатора отправителя, за которым следует порядковый номер и возраст, а также список соседей. Для каждого соседа указывается соответствующая ему задержка. Пример подсети приведен на рисунке 79, на котором приведены задержки для каждой линии. Соответствующие пакеты состояния линий для всех шести маршрутизаторов показаны на рисунке 80.
Создать пакеты состояния линий несложно. Самая сложная часть заключается в выборе момента времени их создания. Их можно создавать периодически через равные интервалы времени. Другой вариант заключается в создании пакетов, когда происходит какое–ни будь значительное событие, например, линия или соседний маршрутизатор выходят из строя или, наоборот, снова появляются в сети, либо существенно изменяют свои свойства.
Рисунок 79 - Пример подсеть
|
ПАКЕТЫ СОСТОЯНИЯ ЛИНИЙ | ||||||||||||||||
|
A |
|
B |
|
C |
|
D |
|
E |
|
F | ||||||
|
Порядко-вый номер |
|
Порядко-вый номер |
|
Порядко-вый номер |
|
Порядко-вый номер |
|
Порядко-вый номер |
|
Порядко-вый номер | ||||||
|
Возраст |
|
Возраст |
|
Возраст |
|
Возраст |
|
Возраст |
|
Возраст | ||||||
|
B |
4 |
|
A |
4 |
|
B |
2 |
|
C |
3 |
|
A |
5 |
|
B |
6 |
|
E |
5 |
|
C |
2 |
|
D |
3 |
|
F |
7 |
|
C |
1 |
|
D |
7 |
|
|
|
F |
6 |
|
E |
1 |
|
|
|
F |
8 |
|
E |
8 | ||
Рисунок 80 - Пакеты состояния линий для нашей подсети
7.7.4 Вычисление новых маршрутов
Собрав полный комплект пакетов состояния линий, маршрутизатор может построить полный граф подсети, т.к. он располагает данными обо всех линиях. На самом деле, каждая линия представлена даже дважды, по одному значению для каждого направления. Эти два значения могут быть усреднены или использоваться по отдельности.
Теперь может быть локально применен алгоритм Дийкстра для построения кратчайшего пути ко всем возможным адресатам. Результат вычислений может быть установлен в таблицах маршрутов, после чего может быть возобновлена нормальная работа маршрутизатора.
В подсети, состоящей из n маршрутизаторов, у каждого из которых k соседей, количество памяти, необходимой для хранения входной информации, пропорционально kn. Кроме того, может потребоваться много времени на обработку информации. В больших подсетях это может составлять проблему. Тем не менее, во многих практических ситуациях маршрутизация с учетом состояния линий работает вполне удовлетворительно.
Однако неисправное оборудование или программное обеспечение может привести к очень серьезным проблемам при использовании данного алгоритма. Например, если маршрутизатор заявит о существовании линии, которой у него нет, или, наоборот, забудет о существовании имеющейся у него линии, граф подсети будет неверным. Если маршрутизатор не сможет переслать пакеты или повредит их при пересылке, также возникнет проблема. Наконец, если у маршрутизатора закончится свободная память или он ошибется в расчетах маршрутов, также возможны различные неприятности. При увеличении размера подсети до несколько десятков или сотен тысяч маршрутизаторов вероятность выхода из строя одного из них перестает быть пренебрежимо малой. Все, что можно здесь сделать – это попытаться ограничить вред, наносимый практически неизбежным выходом из строя оборудования.
Маршрутизация с учетом состояния линий широко применяется в современных сетях. Одним из использовавших этот алгоритм является протокол – OSPF, все чаще применяемый в Интернет.