The Link-State Algorithm
An OSPF router uses a
1.When OSPF is started, or when a change in the routing information changes, the router generates a
2.This
3.When the
4.Once the
The Shortest Path Algorithm
The Shortest Path to a destination is calculated using the Dijkstra algorithm. Each router is places at the root of a tree and then calculates the shortest path to each destination based on the cumulative cost to reach that destination over multiple possible routes. Each router will then have its own Shortest Path Tree (from the perspective of its location in the network area) even though every router in the area will have and use the exact same
The following sections describe the information used to build the Shortest Path Tree.
OSPF Cost
Each OSPF interface has an associated cost (also called “metric”) that is representative of the overhead required to send packets over that interface. This cost is inversely proportional to the bandwidth of the interface (i.e. a higher bandwidth interface has a lower cost). There is then a higher cost (and longer time delays) in sending packets over a 56 Kbps
Cost = 100,000,000 / bandwidth in bps
As an example, the cost of a 10 Mbps Ethernet line will be 10 and the cost to cross a 1.544 Mbps T1 line will be 64.
Shortest Path Tree
To build Router A’s shortest path tree for the network diagramed below, Router A is put at the root of the tree and the smallest cost link to each destination network is calculated.
67
