Unicast IP Routing
Unicast IP Routing |
|
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.
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.
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
The OSPF Neighbors window displays all 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.
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.
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
Figure 3.15 illustrates the convergence process for a new router and new adjacency propagation in a sample OSPF internetwork.
The OSPF internetwork has reconverged after adding R1 and its associated network.
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
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
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.
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
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
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.
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.
