Topology and Routing Databases

The topology database, which sometimes referred to as the link-state database, is the router's view of the network within the area. It includes every OSPF router within the area and all the connected networks. This database is a routing table for which no path decisions have been made. The topology database is updated by link-state advertisements (LSAs). Each router within the area has exactly the same topology database. The synchronization of the topology maps is ensured by the use of sequence numbers in the LSA headers.

A routing database is constructed from the topology map. This database is unique to each router, which creates a routing database by running the shortest path first (SPF) algorithm to determine the best path to each network and creates an SPF tree on which it places itself at the top. If there are equal metrics for a remote network, OSPF includes all the paths and load balances the routed data traffic among them.

Like distance vector protocols, link-state protocols use routing tables that are populated with the currently-best routes. Link-state protocols, however, differ from Distance vector protocols in the methods they use to build their routing tables. The biggest difference between the two is that distance vector protocols advertise little information.

Unlike distance vector protocols, link-state protocols do not receive metrics in the routing table updates. Instead they must calculate the metric form the topology information learned by a router, which includes a cost associated with each link in the network. A router totals the cost associated with each link in each route to find the metric associated with that route. Link-state protocols use the Shortest Path First (SPF) algorithm, which is also called the Dijkstra SPF algorithm, to calculate route metrics.

When a new router that is configured with a link-state protocol is booted for the first time, it does not start broadcasting topology information out every interface. Instead, the router uses the Hello protocol to send and receive a small Hello packet to discover neighbors, i.e., other routers that use the same link-state protocol and share a common subnet. It has a source address of the router and a multicast destination address set to AllSPFRouters (224.0.0.5). All routers running OSPF or the SPF algorithm listen for the hello packet and send their own hello packets periodically. Once a router identifies a neighbor, the two routers exchange routing information, which is called the topology database, and then run the SPF algorithm to calculate new routes. When their topology databases are synchronized, the neighbors are said to be fully adjacent. The Hello protocol continues to transmit the Hello packets periodically. The transmitting router and its networks reside in the topology database for as long as the other routers receive the Hello protocol. This provides another mechanism for determining that a router has gone down, i.e., when the neighbor no longer sends Hello packets.

The routing updates sent by an OSPF router are called link-state updates (LSUs), and the items sent in an LSU include individual link-state advertisements (LSAs). OSPF uses a reliable protocol to exchange routing information, ensuring that lost LSU packets are retransmitted. OSPF routers can, thus, determine whether a neighbor has received all the LSAs.

Section 5.1: Building Routing Table on New OSPF-Configured Routers

Five packets are used to build the routing table on a new OSPF-configured router. These are the Hello protocol; the database descriptor, which is used to send summary information to neighbors to synchronize topology databases; the link-state request, which works as a request for more detailed information that is sent when the router receives a database descriptor that contains new information; the link-state update, which works as the link-state advertisement (LSA) packet issued in response to the request for database information in the link-state request packet; and the link-state acknowledgement, which acknowledges the link-state update.

When the new OSPF-configured router router is connected to the network, it must leam the network from the routers that are up and running. The router goes through three stages while exchanging information: the down state, the init stage, and the two-way state. You can check what stage an interface running OSPF is in by using the show ip ospf neighbor command or the debug ip ospf adjacency command.

The new router starts in a down state. It transmits its own Hello packets to introduce itself to the segment and to find any other OSPF-configured routers. This is sent out as a Hello to the multicast address 224.0.0.5 (AllSPFRouters). It sets the designated router (DR) router and the backup designated router (BDR) routerin the Hello to 0.0.0.0.
While the new router waits for a reply, which usually is four times the length of the Hello timer, the router is in the init state. Within the wait time, the new router hears a Hello from another router and learns the DR and the BDR. If there is no DR or BDR stated in the incoming Hello, an election takes place.
Once the new router sees its own router ID in the list of neighbors, and a neighbor relationship is established, it changes its status to the two-way state.

The DR and the BDR

The designated router (DR) is a router on broadcast multi-access network that is responsible for maintaining the topology table for its segment. This router can be dynamically elected through use of the Hello protocol, or can be designated by the network administrator. Redundancy is provided by the Backup Designated Router (BDR).

The new router and the DR have now established a neighbor relationship and need to ensure that the new router has all the relevant information about the network. The DR must update and synchronize the topology database of the new router. This is achieved by using the exchange protocol with the database description packets (DDPs). There are four different stages that the router goes through while exchanging routing information with a neighbor: the exstart state, the exchange state, the loading state, and the full state.

During the exstart state, one of the routers will take seniority and become the master router, based on highest IP interface address.
Both routers will send out database description packets, changing the state to the exchange state. At this stage, the new router has no knowledge and can inform the DR only of the networks or links to which it is directly connected. The DR sends out a series of DDPs containing the networks, referred to as links that are held in the topology database. Most of these links have been received from other routers via link-state advertisements (LSAs). The source of the link information is referred to by the router ID. Each link will have an interface ID for the outgoing interface, a link ID, and a metric to state the value of the path. The DDPs will contain a summary rather than all the necessary information. When the router has received the DDPs from the neighboring router, it compares the received network information with that in its topology table. In the case of a new router, all the DDPs are new.
If the new router requires more information, it will request that particular link in more detail using the link-state request packet (LSR). The LSR will prompt the master router to send the link-state update packet (LSU) . This is the same as a LSA used to flood the network with routing information. While the new router is awaiting the LSUs from its neighbor, it is in the loading state.
When these LSRs are received and the databases are updated and synchronized, the neighbors are fully adjacent. This is the full state.