OSPF Fundamentals
OSPF route calculation involves the following processes:
- Adjacency establishment
The adjacency establishment process is as follows:
The local and remote routers use OSPF interfaces to exchange Hello packets to establish a neighbor relationship.
The local and remote routers negotiate a master/slave relationship and exchange Database Description (DD) packets.
The local and remote routers exchange link state advertisements (LSAs) to synchronize their link state databases (LSDBs).
- Route calculation
OSPF uses the shortest path first (SPF) algorithm to calculate routes to implement fast route convergence.
OSPF Neighbor States
To exchange routing information on an OSPF network, neighbor routers must establish adjacencies. The differences between neighbor relationships and adjacencies are described as follows:
Neighbor relationship: After the local router starts, it uses an OSPF interface to send a Hello packet to the remote router. After the remote router receives the packet, it checks whether the parameters carried in the packet are consistent with its own parameters. If the parameters carried in the packet are consistent with its own parameters, the remote router establishes a neighbor relationship with the local router.
Adjacency: After the local and remote routers establish a neighbor relationship, they exchange DD packets and LSAs to establish an adjacency.
OSPF has eight neighbor states: Down, Attempt, Init, 2-way, Exstart, Exchange, Loading, and Full. Down, 2-way, and Full are stable states. Attempt, Init, Exstart, Exchange, and Loading are unstable states, which last only several minutes. Figure 5-3 shows the eight neighbor states.
OSPF Neighbor State |
Meaning |
|---|---|
Down |
This is the initial state of a neighbor conversation. This state indicates that a router has not received any Hello packets from its neighbors within a dead interval. |
Attempt |
In the Attempt state, a router periodically sends Hello packets to manually configured neighbors. NOTE:
This state applies only to non-broadcast multiple access (NBMA) interfaces. |
Init |
This state indicates that a router has received Hello packets from its neighbors but the neighbors did not receive Hello packets from the router. |
2-way |
This state indicates that a router has received Hello packets from its neighbors and neighbor relationships have been established between the routers. If no adjacency needs to be established, the neighbors remain in the 2-way state. If adjacencies need to be established, the neighbors enter the Exstart state. |
Exstart |
In the Exstart state, routers establish a master/slave relationship to ensure that DD packets are sequentially exchanged. |
Exchange |
In the Exchange state, routers exchange DD packets. A router uses a DD packet to describe its own LSDB and sends the packet to its neighbors. |
Loading |
In the Loading state, a router sends Link State Request (LSR) packets to its neighbors to request their LSAs for LSDB synchronization. |
Full |
In the Full state, a router establishes adjacencies with its neighbors and all LSDBs have been synchronized. |
The neighbor state of the local router may be different from that of the remote router. For example, the neighbor state of the local router is Full, but the neighbor state of the remote router is Loading.
Adjacency Establishment
Adjacencies can be established in either of the following situations:
Two routers have established a neighbor relationship and communicate for the first time.
The designated router (DR) or backup designated router (BDR) on a network segment changes.
The adjacency establishment process is different on different networks.
Adjacency establishment on a broadcast network
On a broadcast network, the DR and BDR establish adjacencies with each router on the same network segment, but DR others establish only neighbor relationships.
Figure 5-4 shows the adjacency establishment process on a broadcast network.
The adjacency establishment process on a broadcast network is as follows:
Neighbor relationship establishment
Router A uses the multicast address 224.0.0.5 to send a Hello packet to Router B through the OSPF interface connected to a broadcast network. The packet carries the DR field of 1.1.1.1 (ID of Router A) and the Neighbors Seen field of 0. A neighbor router has not been discovered, and Router A regards itself as a DR.
After Router B receives the packet, it returns a Hello packet to Router A. The returned packet carries the DR field of 2.2.2.2 (ID of Router B) and the Neighbors Seen field of 1.1.1.1 (Router A's router ID). Router A has been discovered but its router ID is less than that of Router B, and therefore Router B regards itself as a DR. Then Router B's state changes to Init.
After Router A receives the packet, Router A's state changes to 2-way.
The following procedures are not performed for DR others on a broadcast network.
Master/Slave negotiation and DD packet exchange
Router A sends a DD packet to Router B. The packet carries the following fields:
Seq field: The value x indicates the sequence number is x.
I field: The value 1 indicates that the packet is the first DD packet, which is used to negotiate a master/slave relationship and does not carry LSA summaries.
M field: The value 1 indicates that the packet is not the last DD packet.
MS field: The value 1 indicates that Router A declares itself a master.
To improve transmission efficiency, Router A and Router B determine which LSAs in each other's LSDB need to be updated. If one party determines that an LSA of the other party is already in its own LSDB, it does not send an LSR packet for updating the LSA to the other party. To achieve the preceding purpose, Router A and Router B first send DD packets, which carry summaries of LSAs in their own LSDBs. Each summary identifies an LSA. To ensure packet transmission reliability, a master/slave relationship must be determined during DD packet exchange. One party serving as a master uses the Seq field to define a sequence number. The master increases the sequence number by one each time it sends a DD packet. When the other party serving as a slave sends a DD packet, it adds the sequence number carried in the last DD packet received from the master to the Seq field of the packet.
After Router B receives the DD packet, Router B's state changes to Exstart and Router B returns a DD packet to Router A. The returned packet does not carry LSA summaries. Because Router B's router ID is greater than Router A's router ID, Router B declares itself a master and sets the Seq field to y.
After Router A receives the DD packet, it agrees that Router B is a master and Router A's state changes to Exchange. Then Router A sends a DD packet to Router B to transmit LSA summaries. The packet carries the Seq field of y and the MS field of 0. The value 0 indicates that Router A declares itself a slave.
After Router B receives the packet, Router B's state changes to Exchange and Router B sends a new DD packet containing its own LSA summaries to Router A. The value of the Seq field carried in the new DD packet is changed to y + 1.
Router A uses the same sequence number as Router B to confirm that it has received DD packets from Router B. Router B uses the sequence number plus one to confirm that it has received DD packets from Router A. When Router B sends the last DD packet, it sets the M field of the packet to 0.
LSDB synchronization
After Router A receives the last DD packet, it finds that many LSAs in Router B's LSDB do not exist in its own LSDB, so Router A's state changes to Loading. After Router B receives the last DD packet from Router A, Router B's state directly changes to Full, because Router B's LSDB already contains all LSAs of Router A.
Router A sends an LSR packet for updating LSAs to Router B. Router B returns an LSU packet to Router A. After Router A receives the packet, it sends an LSAck packet for acknowledgment.
The preceding procedures continue until the LSAs in Router A's LSDB are the same as those in Router B's LSDB. Router A's state changes to Full. After Router A and Router B exchange DD packets and update all LSAs, they establish an adjacency.
Adjacency establishment on an NBMA network
The adjacency establishment process on an NBMA network is similar to that on a broadcast network. The blue part shown in Figure 5-5 highlights the differences from a broadcast network.
On an NBMA network, all routers establish adjacencies only with the DR and BDR.
The adjacency establishment process on an NBMA network is as follows:
Neighbor relationship establishment
After Router B sends a Hello packet to a Down interface of Router A, Router B's state changes to Attempt. The packet carries the DR field of 2.2.2.2 (ID of Router B) and the Neighbors Seen field of 0. A neighbor router has not been discovered, and Router B regards itself as a DR.
After Router A receives the packet, Router A's state changes to Init and Router A returns a Hello packet. The returned packet carries the DR and Neighbors Seen fields of 2.2.2.2. Router B has been discovered but its router ID is greater than that of Router A, and therefore Router A agrees that Router B is a DR.
The following procedures are not performed for DR others on an NBMA network.
Master/Slave relationship negotiation and DD packet exchange
The procedures for negotiating a master/slave relationship and exchanging DD packets on an NBMA network are the same as those on a broadcast network.
LSDB synchronization
The procedure for synchronizing LSDBs on an NBMA network is the same as that on a broadcast network.
Adjacency establishment on a point-to-point (P2P)/Point-to-multipoint (P2MP) network
The adjacency establishment process on a P2P/P2MP network is similar to that on a broadcast network. On a P2P/P2MP network, however, no DR or BDR needs to be elected and DD packets are transmitted in multicast mode.
Route Calculation
OSPF uses an LSA to describe the network topology. A Type 1 LSA describes the attributes of a link between routers. A router transforms its LSDB into a weighted, directed graph, which reflects the topology of the entire AS. All routers in the same area have the same graph. Figure 5-6 shows a weighted, directed graph.
Based on the graph, each router uses the SPF algorithm to calculate an SPT with itself as the root. The SPT shows routes to nodes in the AS. Figure 5-7 shows an SPT.
When a router's LSDB changes, the router recalculates a shortest path. Frequent SPF calculations consume a large amount of resources and affect router efficiency. Changing the interval between SPF calculations can prevent resource consumption caused by frequent LSDB changes. The default interval between SPF calculations is 5 seconds.
The route calculation process is as follows:
A router calculates intra-area routes.
The router uses an SPF algorithm to calculate shortest paths to other routers in an area. Type 1 and Type 2 LSAs accurately describe the network topology in an area. Based on the network topology described by a Type 1 LSA, the router calculates paths to other routers in the area.
If multiple equal-cost routes are produced during route calculation, the SPF algorithm retains all these routes in the LSDB.
The router calculates inter-area routes.
For the routers in an area, the network segment of the routes in an adjacent area is directly connected to the area border router (ABR). Because the shortest path to the ABR has been calculated in the preceding step, the routers can directly check a Type 3 LSA to obtain the shortest path to the network segment. The autonomous system boundary router (ASBR) can also be considered connected to the ABR. Therefore, the shortest path to the ASBR can also be calculated in this phase.
If the router performing an SPF calculation is an ABR, the router needs to check only Type 3 LSAs in the backbone area.
The router calculates AS external routes.
AS external routes can be considered to be directly connected to the ASBR. Because the shortest path to the ASBR has been calculated in the preceding phase, the router can check Type 5 LSAs to obtain the shortest paths to other ASs.