Метод ospf

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

Обозначим кратчайшее расстояние от aкiчерезRi. Разделим узлы на 3 группы:

• перманентные, для которых Riуже рассчитано;

• пробные, для которых получена некоторая промежуточная оценка, возможно, неокончательная;

• пассивные, еще не вовлеченные в итерационный процесс.

Итерационный процесс начинается с отнесения узла aк группе перманентных. Далее определяются узлы, смежные с узломa. Это узлыbиc, которые включаются в группу пробных. Включение в группу пробных отмечается указанием в клетке таблицы, рядом с оценкой, расстояния также имени узла, включаемого в этом шаге в число перманентных. На следующем шаге узел с минимальной оценкой (c) включается в группу перманентных, а узлы, смежные с ним, в группу пробных, и для них оцениваются расстоянияRd=8 иRf=13. Теперь среди пробных узлов минимальную оценку имеет узелb. Он включается в группу перманентных узлов, узелeв группу пробных, и для всех пробных узлов, смежных сb, рассчитываются оценки. Это, в частности, приводит к уменьшению оценки узлаdс 8 на 5. В таблице это отражено, во-первых подчеркиванием, а во-вторых заменой у узлаdметкиcнаb. Если же новая оценка оказывается больше прежней, то она игнорируется. Этот процесс продолжается пока все узлы не окажутся в группе перманентных. Теперь виден кратчайший путь отaк любому другому узлуx, или что тоже самое – отxкa. Это последовательность конечных отметок в строках таблицы, начиная с последнего узлаx. Так для узлаx=n, имея в строкеnотметкуh, в строкеhотметкуg, и окончательно кратчайший путь есть:a-b-d-g-h-n.

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

Таблица. Устройства, реализующие функции маршрутизации