Definition of Shortest Path First (SPF) in Network Encyclopedia.
What is Shortest Path First (SPF)?
Also called the Dijkstra algorithm, SPF is a routing algorithm in which a router computes the shortest path between each pair of nodes in the network. The Open Shortest Path First (OSPF) Protocol is based on the Shortest Path First (SPF) algorithm.
How SPF Works?
When an OSPF router is initialized, it sends a Hello message to determine whether it has any neighbors (routers that have an interface on the same network). Neighbors respond to the initiating router by using the same Hello packets. In fact, these Hello packets also serve to tell other routers that the transmitting router is still alive (keep-alive function).
If more than two OSPF routers are on the internetwork, the Hello protocol causes one of the routers to be designated as the one to send out link state advertisements (LSAs) to all other routers on the network.
Neighbors then synchronize their topological databases with each other to become “adjacent” routers. Each router periodically floods the network with cost information for its adjacent nodes in the form of LSAs, allowing them to compile complete tables of network connections and calculate the path of least cost between any two nodes.
Finally, each router analyzes its own database of network topology information and uses it to determine a shortest-path tree using itself as the root; from this tree, it derives a routing table for itself.
See also
External references
- OSPF-2 Protocol Overview
- OSPF: Anatomy of an Internet Routing Protocol, by John T. Moy (see details in Amazon store)
- Cisco OSPF Command and Configuration Handbook, by William R. Parkhurst Ph.D. CCIE® (see details in Amazon store)
