OSPF Discovery, Selection, and Route Maintenance

The best way to understand OSPF discovery, selection, and continuance is to look at OSPF operations in a single-area, broadcast, multi-access scenario. Before anything can happen, OSPF routers must discover one another so they can exchange basic information.

The Hello Protocol

A Hello packet is essentially a multicast packet used by OSPF routers to facilitate neighbor discovery, selection, and maintenance. Neighboring routers can be dynamically discovered with this protocol because Hello leverages the existing broadcast capability of a network. The OSPF designated router (DR), mentioned in the previous bulleted list, is also elected with the Hello protocol. Hello is actually a separate protocol used by several routing protocols to accomplish similar tasks . Hello packets use multicast 224.0.0.5, the AllSPFRouter address, out each OSPF link on the router.

Multicasting is the process in which a host system sends a packet to a collection of hosts that form a multicast group. Each member of the multicast group uses the same multicast address to receive a copy of the packet. Multicast routers copy and deliver packets to those hosts . Membership in a multicast group is dynamic, and a host can join or exit a group at any time. A host can also transmit packets to a multicast group without being a member of that group. Every multicast group has a unique multicast (Class D) address, such as 224.0.0.5 and 224.0.0.6 for OSPF routers.

As you will discover later in this chapter, OSPF can operate over non-broadcast networks in one of two different modes: non-broadcast multi-access (NBMA) such as Frame Relay or point-to-multipoint like in a multipoint serial-link implementation. The option you choose establishes the behavior of the Hello protocol and the flooding process. The choice between NBMA and point-to-multipoint also affects the way that the network is represented in the link-state database. Table 4.1 shows the different fields in the OSPF Hello packet and provides a brief description of each.

Table 4.1. OSPF Hello Protocol Packet Information

Hello Packet Field	Description
Router ID	32-bit number identifying the router in an autonomous system used for establishing neighbor relationships and organizing SPF messages. Router ID is also used in DR/BDR election process.
Hello/dead intervals	The Hello interval is how often the router sends Hello messages. The default on multi-access networks is 10 seconds. Dead interval is the amount of time a router waits to hear from a neighbor before tagging it as down. The default is four times the Hello interval.
Neighbors	Neighbors who have launched a two-way communication channel. This is confirmed when the router sees itself in a neighbor's Hello packet.
Area ID	Numerical area identifier. Routers must be in the same area to communicate. The first area in an OSPF network is backbone Area 0; all other areas extend from there.
Router priority	An 8-bit number that specifies the router priority for electing a DR/BDR.
Designated router IP address	The IP address of the DR if known.
Backup designated router IP address	The IP address of the BDR if known.
Authentication password	Optional authentication password shared by peer routers.
Stub area flag	Designates this as a Hello packet in an area that does not carry external routes, only default, intra-area, and inter-area routes.

The Hello intervals, dead intervals, area-ID, authentication password, and stub area flag entries must match on all neighboring routers if applicable .

OSPF Point-to-Point Operation

We begin tackling the intricacies of the OSFP exchange process by looking at a simple point-to-point network. When two OSPF routers come up at the same time, an exchange process takes place with the Hello protocol. There are several different states that a router transitions through during this process. These states relate to the progression that occurs to establish communications with neighbor routers and create adjacency relationships. Hello packets are exchanged so that the router can populate its adjacency table with the router IDs from neighboring routers. Eventually, the router will enter the full state and begin the data routing activities. Here is a list of the eight possible states that an OSPF router can go through during the initialization process:

• Down

• Attempt

• Init

• Two-way

• Exstart

• Exchange

• Loading

• Full

When an OSPF router is rebooted, it proceeds sequentially through several operational states, culminating with the full state. The full state indicates that the router has successfully exchanged and installed all database updates and has established adjacencies with neighboring routers. The process of reaching the full state begins with the down state, as shown in Figure 4.1. In this state, the routers have received no Hello packets because no information has been exchanged.

Figure 4.1. RouterA is in the down state.

Of the eight OSPF states, only the attempt state is confined to NBMA network implementations . During this state, neighbors on serial links are manually configured to establish communications and create adjacencies. Therefore, the attempt state is not applicable to this simple point-to-point scenario.

After Hello packets have been received, the router enters the init state. During the init state, RouterA sends Hello packets out via multicast address 224.0.0.5 (AllSPFRouters). On physical point-to-point networks, the IP destination is always set to the address AllSPFRouters. RouterB receives the Hello packet from RouterA and adds RouterA to its adjacency table, as shown in Figure 4.2.

Figure 4.2. The init state.

RouterB sends a Hello reply back to RouterA with all of its accumulated information in the neighbor field of the Hello packet. This next stage, the two-way stage, indicates that the routers have established two-way communications and their router IDs have been entered into their adjacency tables, as shown in Figure 4.3.

Figure 4.3. The two-way state.

The ip unnumbered command is applied to serial lines in point-to-point connections. The ip unnumbered command allows you to enable IP processing on a serial interface without actually assigning it in an IP address. The type and number keywords are used to map to any of the other IP addresses belonging to the router. For this reason, at least one IP address must be assigned to the router. Here is an example of what you could do on RouterA in Figure 4.1. You could assign IP address 192.168.1.1 /24 to Ethernet0 and use ip unnumbered to map address 192.168.1.1 /24 to Serial0, instead of assigning it directly to the physical interface like so:

  Router(config)# interface Ethernet0   Router(config-if)# ip address 192.168.1.1 255.255.255.0   !   Router(config)# interface Serial0   Router(config-if)# ip unnumbered Ethernet0  

In addition, a loopback address is often used to map to an unnumbered interface. A loopback address is a virtual interface that always remains active and does not go down as a physical interface is known to do.

From this point on, the exchange and subsequent discovery operations depend upon the topology being implemented. On physical point-to-point networks and point-to-multipoint networks, neighboring routers become adjacent whenever they can communicate directly. The previous figures show a point-to-point network joining a pair of routers over a serial interface such as a T1 link. These neighboring routers become adjacent by direct communication and no DR or BDR election takes place. As a matter of fact, the concept of DR and BDR is nonexistent in point-to-point mode.

The next phase is the exstart state, in which database description (DD) packets are swapped so that the router with the highest router ID becomes the master in the neighbor relationship. Next, DD and link-state request (LSR) packets are exchanged during the next exchange state. New LSAs, if applicable, trigger the loading state. During the loading state, LSRs are sent to neighbors requesting the new advertisements. After all LSA information is reclaimed, the router finally enters the full state. The OSPF router state of full characterizes a router that has exchanged all the necessary information to establish adjacencies with neighbors. The full state is shown in Figure 4.4.

Figure 4.4. The full state.

OSPF Broadcast Multi-Access Operation

In a broadcast multi-access environment such as Ethernet, the OSPF router must elect a DR and a BDR on the network for OSPF operations. OSPF DRs and BDRs consolidate the process of forwarding and synchronizing updates to reduce the traffic on multi-access network segments. To establish adjacencies among every OSPF router in the multi-access network, it would require nx(n1) adjacency relationships. For example, in Figure 4.5, it would take 20 adjacency relationships to service OSPF Area 0 (5x4=20). As you scale this network up to dozens of routers, the relationships also scale proportionately.

Figure 4.5. OSPF broadcast multi-access mode.

Therefore, OSPF uses a single DR to function as the information clearinghouse for the entire network. As link-state information changes, it is forwarded to the DR, which in turn propagates the changes to all other OSPF routers on the Ethernet segment. This effectively reduces the number of relationships needed between OSPF routers, lessens update traffic overhead on the network, and cuts down on the number of potential routing errors.

The BDR passively accepts all the updates received by the DR without actively forwarding or synchronizing the update traffic. However, if the DR fails to transmit LSAs before the holdtime interval expires (40 seconds on multi-access networks), because of being offline or a malfunction, the BDR takes over the process of forwarding and synchronizing updates.

Referring back to the exchange states, after the routers get to the two-way state and have each other in their tables, the routers must determine who the DR and BDR will be. This must take place before link-state information can be exchanged in a multi-access environment. The multi-access exstart state is where the DR and BDR are elected and master-slave relationships are established between every router and its adjacent DR and BDR. (Refer back to Figure 4.5.)

To choose the DR and BDR, the routers view each other's priority values during the original exchange of Hello packets. The following steps are used to determine the election:

1. The router with highest priority value is DR.

2. The router with the next highest priority value is BDR.

3. In case of a tie (which is likely because the default priority on all OSPF routers is 1), the router ID value is used instead to elect the DR and BDR. The highest IP address on an active router interface (often a loopback address) is typically used.

4. Any router with a manually configured priority of 0 is disqualified from the election.

5. Any router that is not elected DR or BDR is known as a DROther router.

6. If a router is added to the network and it has a higher priority value, the DR and BDR routers do not change unless one goes down. Refer to the following note.

If you add another router to an Ethernet segment that has a higher router priority value than the current DR, no election occurs, and the current DR continues to act as the DR for the Ethernet segment as long as the current DR remains online. For example, you may have purchased a newer , more powerful router that you want to force into being the DR no matter what the other assigned addresses are. If the DR goes down, however, the BDR takes over and a new DR is chosen. If the BDR fails, a new BDR is chosen .

The ip ospf priority 0 command can be used to modify the default OSFP interface priority to prohibit participation in DR/BDR elections . For example, you may want to explicitly prevent this router from ever becoming the DR or BDR because it is an older, lower-end model with fewer resources.

Continuing with the exstart state, the DR and BDR have now been elected according to the previous steps and you are ready to discover the link-state data concerning the network. Again, the goal is to get to the full state of operations.

First, in the exstart phase, the DR and BDR routers establish adjacency relationships with all the other routers on the network. These relationships remain intact until a change occurs in the full state. A master-slave relationship is formed between each DROther router and its adjacent DR and BDR. As shown in Figure 4.6, the router with the highest router ID is the master, assuming that all routers have the default priority of 1.

Figure 4.6. OSPF broadcast multi-access mode exstart state.

In the exchange state, OSPF master and slave routers exchange database description (DBD) packets, which have LSA summary information from the master's link-state database. The different LSA types are covered in Chapter 5, "Interconnecting OSPF Areas." When the slave, RouterA in Figure 4.7, gets the DBD packets from the master, RouterB, it sends an acknowledgement echo message (LSAck). This process is shown in Figure 4.7.

Figure 4.7. OSPF broadcast multi-access mode exchange state.

Next, in the loading state, RouterA compares the update to its own table. If the slave has a more recent entry in its link-state table, it sends an LSR to the master, RouterB. RouterB answers with a link-state update (LSU) containing complete information, and RouterA acknowledges this update. All the routers propagate their link-state databases with the new link-state information during the loading state as shown in Figure 4.8.

Figure 4.8. OSPF broadcast multi-access mode loading state.

After all the link-state requests have been addressed, the adjacent routers are in the synchronized full state. Now that the routers have complete link-state databases, they can choose the best routes and inject them into their routing tables to generate route traffic. The OSPF packet header contains a lot of information used for complex routing processes. Table 4.2 explains the contents of the 24-byte OSPF packet header.

Table 4.2. The OSPF Routing Protocol 24-byte Packet Header

OSPF Header Data Entry	Length (bytes)	Description
Version Number	1	The OSPF version type
Type	1	Type of OSPF packet, that is, Hello, DD, LSR, LSU, or LSAck
Packet Length	2	The length of the OSPF packet, including the header, in bytes
Router ID	4	Identifies the source of the packet
Area ID	4	The area to which the packet belongs
Checksum	2	Checks for corruption to packet while in transit
Authentication Type	2	Type0: no authentication, Type1: clear-text, or Type2: MD5
Authentication	8	Authentication data
Data	variable	Encapsulated upper-layer routing information

The OSPF Routing Process Revisited

RIP protocols select the optimum path based on hop count, and link-state protocols use a cost metric based on the Dijkstra algorithm. Generally speaking, cost is an arbitrary value used by the routing protocol to compare paths through an internetwork. In Cisco OSPF implementations, however, the default cost metric is a value assigned to a connection based on the media speed (bandwidth). The OSPF cost is a metric assigned to the interface represented by a number between 1 and 65535 (16-bit).

Cisco routers use the following formula to calculate the path cost:

 10  8  bandwidth (in bps) 

For example, the default cost for Ethernet would be 10 and the default cost for a 1.544Mbps T1 link would be 64. In other words a 10Mbps Ethernet link has a lower cost than a T1 line because it is faster. Using the link-state database as the data source, Cisco routers then run the algorithm to construct a routing table. The Dijkstra algorithm simply adds up the total costs between the local (root) router and each destination network. This is known as the path cost . If multiple paths to a destination exist, then the lowest -cost path is preferred.

For load balancing purposes, OSPF stores up to four equi-cost routes to the same destination in the routing by default. You can use the maximum-paths command in router configuration mode to utilize up to six equal routes to the same target.

In the case of link-state changes or flapping interfaces, a number of LSUs might be spawned. Changes to the link-state database can occur when routing devices are added or removed from the network or when bandwidths change. Flapping can occur when there are intermittent interface failures. This forces OSPF routers into a relentless state of routing table computations . Flapping can become so severe that convergence will never happen. OSPF routers wait for a default interval of five seconds every time an LSU is received before recalculating to curtail this problem. You can set these timers in the router configuration mode of the Cisco IOS by using the following syntax:

  RouterA(config-router)# timers spf   spf-delay spf-holdtime