Unicast IP Routing

Previous Topic Next Topic

Synchronizing the LSDB Through Adjacencies

Link-state routing algorithms rely on the synchronization of LSDB information between routers in the AS. Rather than each router verifying synchronization with every other router in the AS, each router is only required to synchronize with its neighboring routers. The relationship between neighboring routers for the purposes of synchronizing the LSDB is called an adjacency. Adjacencies are required to compile the proper entries in the LSDB before the calculation of the SPF Tree and the entries in the routing table. Failure to establish adjacencies is one of the main problems in converging OSPF internetworks. For information about troubleshooting OSPF adjacencies, see "Troubleshooting OSPF" later in this chapter.

Forming an Adjacency

When an OSPF router initializes, it sends out a periodic OSPF Hello packet. The OSPF Hello packet contains configuration information such as the router's Router ID and the list of neighboring routers for which the router has received a Hello packet. Initially, the neighbor list in the OSPF Hello packet does not contain any neighbors.

The initializing OSPF router also listens for neighboring routers' Hello packets. From the incoming Hello packets, the initializing router determines the specific router or routers with which an adjacency is to be established. Adjacencies are formed with the designated router (DR) and backup designated router (BDR) which are identified in the incoming Hello packets. Designated routers and backup designated routers are discussed in more detail later in this chapter.

To begin the adjacency, the routers forming the adjacency describe the contents of their LSDBs through a sequence of Database Description Packets. This is known as the Database Exchange Process during which the two neighboring routers form a master/slave relationship. The contents of each router's LSDB is acknowledged by its neighboring router.

Each router compares its LSAs with the LSAs of its neighbor and notes which LSAs need to be requested from the neighbor to synchronize the LSDB. The missing or more recent LSAs are then requested through Link State Request packets. Link State Update packets are sent in response to the Link State Request packets and their receipt is acknowledged. When all Link State Requests of both routers have been satisfied, the LSDBs of the neighboring routers are fully synchronized and an adjacency is formed.

After the adjacency has formed, each neighboring router sends a periodic Hello packet to inform its neighbor that the router is still active on the network. The lack of Hello packets from a neighbor is used to detect a downed router.

If an event occurs such as a downed link or router or the addition of new network which changes the LSDB of one router, the LSDB of adjacent routers are no longer synchronized. The router whose LSDB has changed sends Link State Update packets to its adjacent neighbor. The receipt of the Link State Update packets is acknowledged. After the exchange, the LSDBs of the adjacent routers are once again synchronized.

Neighbor States

The neighboring routers go through a series of states during the establishment of an adjacency. Table 3.2 lists these states in the adjacency relationship in progressive order.

Table 3.2 Neighbor States for Adjacent Routers

Neighbor State Description
Down The initial state. No information has been received from the neighbor router.
Attempt No information has been received despite attempts to contact the neighbor (for NBMA networks only).
Init A Hello packet has been received from the neighbor, but the router does not appear in the neighbor list of the neighboring router's Hello packet.
2-Way A Hello packet has been received from the neighbor, and the router does appear in the neighbor list of the neighboring router's Hello packet.
ExStart Master and slave roles for the Database Exchange Process are being negotiated. This is the first phase of the adjacency relationship.
Exchange The router is sending Database Description packets to its neighbor.
Loading Link State Request packets are being sent to the neighbor requesting missing or more recent LSAs.
Full The neighboring routers' LSDBs are synchronized, and the two routers are fully adjacent.

To view the neighbor state of neighboring routers

Because of the election of designated routers (DRs) and backup designated routers (BDRs), each OSPF router might not form an adjacency with each other router.

For those neighbor routers where an adjacency is established, Full should appear in the State column. For those neighbor routers where an adjacency is not established nor will be established because the router is not a DR or BDR, 2-way should appear in the State column. Designated routers and backup designated routers are discussed later in this chapter.

Adjacency Configuration Parameters

A common OSPF problem is that an adjacency which should form between two neighboring routers does not. The following parameters must match between the two routers in order for an adjacency to be established:

The Router ID of the two neighboring routers must not match in order for an adjacency to be established. Router IDs are designed to be globally unique to the AS. Duplicate Router IDs prevent an adjacency.

Adding a Router to a Converged OSPF Internetwork

When a new OSPF router initializes on an existing and converged OSPF internetwork, the LSA for the new OSPF router must be propagated to all the OSPF routers in the internetwork through flooding. After the new LSA is received, each router must perform Dijkstra's algorithm, recalculate the SPF Tree, and create new routing table entries. After all the routing tables on all the routers are updated, the internetwork has converged.

Figure 3.15    New Adjacency Propagation
Enlarge figure

Figure 3.15 New Adjacency Propagation

Figure 3.15 illustrates the convergence process for a new router and new adjacency propagation in a sample OSPF internetwork.

  1. Router R1 initializes and begins sending periodic Hello packets across the point-to-point WAN link. Router R2 also sends periodic Hello packets across the link. R1 and R2 decide to form an adjacency.
  2. R1 and R2 exchange Database Description Packets. R1's Database Description Packet contains only information about itself. R2's Database Description Packet contains the latest LSAs of all the routers in the internetwork (except R1).
  3. R1 sends a Link State Request packet to R2 requesting the LSAs of all the routers on the internetwork. R2 sends the requested LSAs to R1 as Link State Update packets.
  4. R2 sends a Link State Request packet to R1 requesting its LSA. R1 sends its LSA to R2 as a Link State Update packet. R1 and R2 now have synchronized LSDBs. Upon receipt of the LSAs, R1 and R2 calculate their respective SPF trees and routing tables.
  5. Once synchronized with R1, R2 sends a Link State Update packet to all other OSPF routers to which it is adjacent (routers R3 and R4). The Link State Update packet contains the LSA learned from R1. Upon receipt of the LSA from R2, R3 and R4 calculate their respective SPF trees and routing tables.
  6. R3 and R4 flood the information in a separate Link State Update packet to their adjacent routers (routers R5 and R6). Upon receipt of the flooded LSA for R1, R5 and R6 calculate their respective SPF trees and routing tables.

The OSPF internetwork has reconverged after adding R1 and its associated network.

Designated Routers

On a point-to-point link (such as a dedicated WAN link), the adjacency must occur between the two routers on either side of the link. However, on multi-access networks (such as broadcast or NBMA networks) the adjacencies must be controlled. Consider a broadcast network with 6 OSPF routers. Without controlling the adjacency behavior, each router could establish an adjacency with each other router for a total of 15 adjacency relationships. On a broadcast network with n routers, a total of n*(n-1)/2 adjacencies would be formed. The number of adjacencies scales as O(n2). In addition, unneeded flooding traffic would occur as each router attempts to synchronize with all of its adjacent routers.

To solve this scaling problem, every multi-access network (broadcast and NBMA) elects a Designated Router (DR). The DR forms adjacencies with all other routers on the network. On a broadcast network with n routers, a total of (n-1) adjacencies need to be formed. Because the DR is adjacent with all other routers, it acts as a hub for the distribution of link state information and the LSDB synchronization process.

The DR is elected through the exchange of OSPF Hello packets. Each Hello packet contains the current DR (if elected), the sending router's Router ID, and the sending router's Router Priority. The Router Priority is an interface-specific OSPF configuration parameter that is used to elect the DR. The router with the highest Router Priority is elected the DR. The default Router Priority is 1. A Router Priority of 0 means that the router does not become a DR. If multiple routers have the same highest Router Priority, the router with the highest Router ID is elected the DR.


caution-icon

Caution

Router Priorities must be assigned so that at least one router on the multi-access network (broadcast or NBMA) is configured with a Router Priority of 1 or greater. If all routers on a multi-access network are configured with a Router Priority of 0, no router becomes the DR and no adjacencies are established. Without adjacencies, the LSDB cannot be synchronized and no transit traffic (traffic across that network) can be passed.


note-icon

Note

If a DR is already elected for a network, an initializing router on the network does not become the DR if it has a higher Router Priority than the current DR.

DRs on Broadcast Networks

Figure 3.16 illustrates the utility of the DR on a broadcast network. Without a
DR, six separate adjacencies would be formed on a broadcast network containing four routers. The redundant adjacencies consume local and network resources maintaining the adjacencies and propagating changes to the LSDB.

With a DR, only three adjacencies are needed to maintain synchronization of the LSDB.

Figure 3.16    Designated Routers on Broadcast Networks
Enlarge figure

Figure 3.16 Designated Routers on Broadcast Networks

DRs on NBMA Nets

For NBMA networks, such as a Frame Relay network in a hub and spoke configuration, the DR must be the hub router because only the hub router can communicate with all the other routers. To ensure that the hub router is the DR, set its Router Priority to 1 (or greater). To ensure that no spoke router becomes a DR, set spoke router Router Priorities to 0.

Figure 3.17 illustrates a DR in a Frame Relay network.

Figure 3.17    Designated Routers on a Frame Relay Network
Enlarge figure

Figure 3.17 Designated Routers on a Frame Relay Network

Backup Designated Router

The DR acts as a central distribution point for topological changes on a multi-access network. If the DR becomes unavailable, all new adjacencies must be formed with a new DR. Until the adjacencies form and the internetwork converges, a temporary loss of connectivity for transit traffic might result.

To prevent the loss in connectivity associated with the loss of a DR, a Backup Designated Router (BDR) is also elected for each multi-access network. Like the DR, the BDR is adjacent to all routers on the network. When the DR fails, the BDR immediately becomes the DR by sending LSAs to all of its adjacent routers announcing its new role. There is a very short period of time where transit traffic could be impaired as the BDR takes over the role of the DR.

Like the DR, the BDR is elected by the exchange of Hello packets. Each Hello packet contains a field for the BDR of the network. If the BDR is not specified, the router with the highest Router Priority that is not already the DR becomes the BDR. If there are multiple routers with the highest Router Priority, the router with the highest Router ID is elected the BDR.

Interface States

Each OSPF interface can be in one of several states after forming adjacencies. Table 3.3 lists the possible interface states.

Table 3.3 Interface States for Adjacent Routers

Interface State Description
Down The initial interface state. No Hello packets have been sent or received.
Loopback The interface to the network is looped back (internally configured so that no packets are sent) through hardware or software.
Waiting The interface is sending and receiving Hello packets to determine the DR and BDR for the network.
Point-to-Point The interface is adjacent to its neighbor on a point-to-point network or through a virtual link.
Other The interface is on a multi-access network and is not the DR or BDR.
Designated Router The interface is the DR for the attached network.
Backup Designated Router The interface is the BDR for the attached network.

To view the interface state for an OSPF interface on a Windows 2000 OSPF router, in the Routing and Remote Access snap-in, in the IP Routing container, click OSPF. The contents pane displays the OSPF interfaces. The State column indicates the interface's current state. By viewing the interface state for each OSPF interface on a given network, you can determine the DR and the BDR for the network.

© 1985-2000 Microsoft Corporation. All rights reserved.