Введение в Алгоритм SPF
Алгоритм Дейкстры обычно упоминается как алгоритм предпочтения кратчейшего пути (SPF).
Этот алгоритм SPF накапливает затраты вдоль каждого пути от источника до места назначения. Хотя, алгоритм Дейкстры известен как алгоритм предпочтения кратчейшего пути, это - фактически цель каждого алгоритма маршрутизации.
На рисунке каждый путь маркируется случайным значением стоимости. Стоимость кратчайшего пути для R2, чтобы отправить пакеты LAN, присоединенной к R3, равна 27. Заметьте, что эта стоимость не равна 27 для всех маршрутизаторов, чтобы достигнуть LAN, присоединенную к R3. Каждый маршрутизатор определяет свою собственную стоимость до каждого места назначения в топологии. Другими словами каждый маршрутизатор вычисляет алгоритм SPF и определяет стоимость со своей собственной перспективы. Это станет более очевидным позже в этой рубрике.
Щелкните 2 на рисунке.
Для R1 кратчайший путь к каждой LAN - вместе со стоимостью - показан в таблице. Кратчайший путь не обязательно является путем с наименьшим количеством транзитных участков. Например, посмотрите на путь к LAN R5. Вы могли бы подумать, что R1 будет передавать непосредственно к R4, а не к R3. Однако, стоимость, чтобы достигнуть R4 непосредственно (22), выше чем стоимость, чтобы достигнуть R4 через R3 (17).
Продолжайте переключать кнопки 3, 4, 5, 6 на рисунке.
Проследите кратчайший путь для каждого маршрутизатора, чтобы достигнуть каждой из LAN, как показано в таблицах.