2.2.4 Shortest path algorithm
The shortest path algorithm is used by OSPF to determine the best path to a destination.
In this algorithm, the best path is the lowest cost path. The algorithm was discovered by Dijkstra, a Dutch computer scientist, and was explained in 1959. The algorithm considers a network to be a set of nodes connected by point-to-point links.  Each link has a cost. Each node has a name. Each node has a complete database of all the links and so complete information about the physical topology is known. All router link-state databases are identical. The table in Figure shows the information that node D has received. For example, D received information that it was connected to node C with a link cost of 4 and to node E with a link cost of 1.
The shortest path algorithm then calculates a loop-free topology using the node as the starting point and examining in turn information it has about adjacent nodes. In Figure  , node B has calculated the best path to D. The best path to D is by way of node E, which has a cost of 4. This information is converted to a route entry in B which will forward traffic to C. Packets to D from B will flow B to C to E, then to D in this OSPF network.
In the example, node B determined that to get to node F the shortest path has a cost of 5, via node C. All other possible topologies will either have loops or a higher cost paths.
Share with your friends: |
