What email address or phone number would you like to use to sign in to Docs.com?
If you already have an account that you use with Office or other Microsoft services, enter it here.
Or sign in with:
Signing in allows you to download and like content, and it provides the authors analytical data about your interactions with their content.
Embed code for: 23.9 SPF Algorithm
Select a size
23.9 SPF Algorithm
SPF Algorithm Section 23: Implementing Dynamic Routing The SPF algorithm places each router at the root of a tree and calculates the shortest path to each node by using the Dijkstra algorithm, which is based on the cumulative cost that is required to reach that destination. LSAs are flooded throughout the area by using a reliable algorithm, which ensures that all the routers in an area have the same topological database. Each router uses the information in its topological database to calculate a shortest path tree, with itself as the root. The router then uses this tree to route network traffic. The figure represents the R1 view of the network, where R1 is the root and calculates the pathways by assuming this view. Each router has its own view of the topology, even though all of the routers build a shortest path tree by using the same linkstate database. The cost, or metric, of an interface is an indication of the overhead that is required to send packets across a certain interface. The interface cost is inversely proportional to the bandwidth, so a higher bandwidth indicates a lower cost. There is more overhead, higher cost, and more time delays involved in crossing a T1 serial line than in crossing a 10Mb/s Ethernet line. The formula used to calculate the OSPF cost is as follows:cost = reference bandwidth / interface bandwidth (in b/s). The default reference bandwidth is 10^8 (10 to the 8 power), which is 100,000,000 or the equivalent of the bandwidth of Fast Ethernet. Therefore, the default cost of a 10Mb/s Ethernet link is 10^8 / 10^7= 10, and the cost of a 100Mb/s link is 10^8 / 10^8 = 1. A problem arises with links that are faster than 100 Mb/s. Because the OSPF cost has to be an integer, all links that are faster than Fast Ethernet have an OSPF cost of 1. In that case, you must change the OSPF cost on an interface manually or adjust the reference bandwidth to be a higher value. To adjust the reference bandwidth for links with bandwidths greater than Fast Ethernet, use the ospf auto-cost reference-bandwidth ref-bw command that is configured in the OSPF routing process configuration mode. The cost to reach a distant network from a router is the cumulative cost of all links on the path from the router to the network. In the example, the cost from router R1 to the destination network via R3 is 40 (20 + 10 + 10), and the cost via router R2 is 30 (10 + 10 + 10). The path via R2 is better because it has a lower cost. R1 SPF Tree Destination Shortest Path Cost Destination Shortest Path Cost R2 LAN R1 to R2 14 R3 LAN R1 to R3 22 R4 LAN R1 to R4 30 LSAs are flooded throughout the area by using a reliable algorithm, which ensures that all routers in an area have the same topological database. As a result of the flooding process, R1 has learned the linkstate information for each router in its routing area. Each router uses the information in its topological database to calculate a shortest path tree, with itself as the root. The tree is then used to populate the IP routing table with the best paths to each network. For R1, the shortest path to each LAN and its cost are shown in the table. The shortest path is not necessarily the best path. Each router has its own view of the topology, even though all of the routers build a shortest path tree by using the same linkstate database. Up Next: Configuring SingleArea OSPF