OSPF Route Determination Using SPF Trees
(Page 1 of 4)
The key data structure maintained by each router in an OSPF autonomous system (AS) is the link-state database (LSDB). The LSDB contains a representation of the topology of either the entire AS (in basic topology) or a single area (in hierarchical topology). As we have seen earlier in this section, each router in the AS or area has the same LSDB, so it represents a neutral view of the connections between routers and networks.
Of course, each router needs to participate in keeping the LSDB up to date, but it also has its own selfish concerns. It needs to be able to determine what routes it should use for datagrams it receives from its connected networksthis is, after all, the entire point of a routing protocol.
To find the best route from any router, it must determine the shortest path between itself and each router or network in the AS or area. For this, it needs not a neutral view of the internetwork but a view of it from its own perspective.
The router creates this perspective by taking the information in the LSDB and transforming it into a shortest path first tree or SPF tree. The term tree refers to a data structure with a root that has branches coming out that go to other nodes, which in turn have branches. The structure as a whole looks like an upside-down tree. In this case, the SPF tree shows the topology information of the AS or area with the router constructing the tree at the top. Each directly-connected router or network is one step down in the tree; each router or network connected to these first-level routers or networks is then connected, and so on, until the entire AS or area has been represented.
Again, the router doesn't really make the tree; it is just an algorithmic calculation performed by the computer within the router. Once this is done, however, this logical construct can be used to calculate the cost for that router to reach any router or network in the AS (or area). In some cases, there may be more than one way to reach a router or network, so the tree is constructed to show only the shortest (lowest-cost) path to the network.
Of course, each router is only responsible for sending a datagram on the next leg of its journey, and not for what happens to the journey as a whole. After the SPF tree is done, the router will create a routing table with an entry for each network, showing the cost to reach it, and also the next hop router to use to reach it.
The SPF tree is created dynamically based on the current state of the LSDB. If the LSDB ever changes, the SPF tree and the routing information are recalculated.
Home - Table Of Contents - Contact Us
The TCP/IP Guide (http://www.TCPIPGuide.com)
Version 3.0 - Version Date: September 20, 2005
© Copyright 2001-2005 Charles M. Kozierok. All Rights Reserved.
Not responsible for any loss resulting from the use of this site.