Введення в Алгоритм 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, як показано в таблицях.