2.2.4 This page will explain how OSPF uses the shortest-path algorithm to determine the best path to a destination.
In this algorithm, the best path is the lowest cost path. Edsger Wybe Dijkstra, a Dutch computer scientist, formulated the shortest path-algorithm, also known as Dijkstra's algorithm. 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, within a given area, 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, through node C. All other possible topologies will either have loops or a higher cost paths.
The next page will explain the concept of OSPF networks.
No comments:
Post a Comment