OSPF Operation in a Single Area 193
Table 6-3 The Hello Packet Fields (Continued)
OSPF Operation in a Single Area
OSPF operates as a classic link-state routing protocol. It uses topology tables as well as the SPF tree as the basis of the SPF algorithm. This algorithm, created by Edsger Wybe Dijkstra, creates an SPF tree from the topology table. After calculating the algorithm on the SPF tree, the forwarding table is created. The forwarding table is, in fact, the routing table by another name. This section considers and describes how routes are entered into and removed from the routing table.
Creating and Maintaining the OSPF Routing Table
As discussed in the section “OSPF Neighbors,” after a neighbor is discovered in OSPF, an adjacency is formed. It is important to understand how the neighbor adjacency is formed and, in this context, to understand the other messages that the routers receive.
Routing tables are built in two different ways. Either established databases have to adjust to a change in the network, or a new router has to create the topology and forwarding databases when it enters the network.
Different techniques are used for these different routing table requirements. Essentially, the difference between the two techniques is simple:
■ If a new router connects to a network, it will ﬁnd a neighbor using the Hello protocol and will exchange routing information.
■ If a change occurs in an existing network, the router that sees the change will flood the area with the new routing information.
Both of these events must occur as stated because, although the new router must learn the network topology, its addition is a change to the rest of the network.
These two requirements for updating the routing table use different technologies and OSPF protocols. These technologies and protocols are often confused, so the next sections take a moment to distinguish them. Understanding the distinction makes the OSPF operation much clearer.
How OSPF Builds the Routing Table on a New Router
When a new router is added to the network, it builds a routing table by listening to the established routers with complete routing tables. Remember that every router within an area will have the same database and will know of every network within the area. The routing table built from this database is unique to the router because the decisions depend on the individual router’s position within the area, relative to the remote destination network.
Five packet types are used to build the routing table for the ﬁrst time:
■ Hello protocol —Used to ﬁnd neighbors and to determine the designated and BDR. The continued propagation of the Hello protocol maintains the transmitting router in the topology database of those that hear the message.
■ Database descriptor —Used to send summary information to neighbors to synchronize topology databases.
■ LSR—Works as a request for more detailed information, which is sent when the router receives a database descriptor that contains new information.
■ LSU—Works as the LSA packet issued in response to the request for database information in the LSR packet. The different types of LSA are described in Chapter 8 in the section “Link- State Advertisements.”
■ Link-state acknowledgement —Acknowledges the LSU.
OSPF Operation in a Single Area 195
Consider the case of a router joining the OSPF network for the ﬁrst time. In Figure 6-3, the 2500 router in Building A at the San Francisco campus has just been connected.
Figure 6-3 Joining an OSPF Network
The next sections detail what happens when a router joins a network.
Finding Neighbors with the Exchange Process
When it is connected to the network and has been conﬁgured to run OSPF, the new router must learn the network from the systems that are up and running. The method described in this section is the same as for a stable network.
The process in this section shows the stages that the systems go through while exchanging information. You can see what stage an interface running OSPF is in with the command show ip ospf neighbor as well as the command debug ip ospf adjacency . Care should be taken with the debug command because it can be CPU-intensive.
The different stages or states that the router goes through while creating a neighbor relationship are shown in the following list:
196 Chapter 6: Using OSPF in a Single Area
1. The down state —The new router is in a down state. The 2500 router transmits its own hello packets to introduce itself to the segment and to ﬁnd any other OSPF-conﬁgured routers. This is sent out as a hello to the multicast address 126.96.36.199 (AllSPFRouters). It sets the DR and BDR in the hello to be 0.0.0.0.
2. The init state —The new router waits for a reply. Typically this 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. However, in accordance with the description of the Hello protocol, the DR has been elected: It is the 7200 router, which connects the campus to the campus backbone.
Upon hearing the Hello protocol from the 2500 router, a router on the segment adds the router ID of the 2500 and replies as a multicast (188.8.131.52) with its own ID and alist of any other neighbors.
3. The two-way state—The new router sees its own router ID in the list of neighbors, and a neighbor relationship is established. The new router changes its status to the two-way state.
The 2500 router and the designated router have now established a neighbor relationship and need to ensure that the 2500 has all the relevant information about the network. The 7200 router must update and synchronize the topology database of the 2500. This is achieved by using the exchange protocol with the database description packets.
The different stages or states that the router goes through while exchanging routing information with a neighbor are shown in the following list:
1. The exstart state —One of the routers will take seniority, becoming the master router. This is the exstart state. The two neighbors determine a master/slave relationship based on highest IP interface address. This designation is not signiﬁcant; it just determines which router starts the communication.
2. The exchange state —Both routers will send out database description packets, changing the state to the exchange state.
In this example, the 2500 router has no knowledge and can inform the 7200 router only of the
networks or links to which it is directly connected. The 7200 sends out a series of database
description packets containing the networks held in the topology database. These networks are
referred to as links.
Most of the information about the links has been received from other routers (via LSAs). The router ID refers to the source of the link information.
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 database description packet will not contain all the necessary information, but just a summary (enough for the receiving router to determine whether more information is required or whether it already contains that entry in its database). 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, such as the 2500, all the DDPs are new. Remember that the DDPs are simply a summary of the routes that the neighbor knows about. The different stages or states that the router goes through gathering routing information to update the topology database from a neighbor are shown in the following list:
3. The loading state —If the receiving router, the 2500, requires more information, it will request that particular link in more detail using the LSR packet. The LSR will prompt the master router to send the LSU packet. For example, if there is a discrepancy between the information in the received DDPs and the router’s topology database, the router requests more detailed information from its neighbor about those routes of which it was unaware.
This process is the same as an LSA used to ﬂood the network with routing information.
While the 2500 is awaiting the LSUs from its neighbor, it is in the loading state.
4. The full state —When these LSRs are received and the databases are updated and synchronized, the neighbors are fully adjacent.
All the stages in updating a router’s databases, as described in the numbered list, are illustrated in Figure 6-4.
Now that you understand how OSPF learns about the connected network by forming adjacencies, the second stage is to learn how the neighbors ﬂood information about their links throughout the network. The next section describes how the topology database, sometimes referred to as the linkstate database, learns about the entire OSPF domain, or autonomous system.