CCIE OCG: OSPF (Chapter 9), Part I

• OSPF is a link-state routing protocol.
• "Link state" refers to the fact that the topology includes information about each data link and their current operational state.
• All topological data comprises the link-state database (LSDB).
• Each router applies the Dijkstra algorithm to the database to calculate the current best routes to each subnet.

OSPF Database Exchange

• Five different messages to establish adjacencies and exchange routing information.
• The LSA exchange process is the same in single and multi-area designs.

OSPF Router IDs

• A unique 32-bit identifier.
• Chosen in the following sequence:

1. Use the configured router ID (router-id <rid>).
2. Use the highest non-shutdown loopback interface IP address that is not reserved by another OSPF process.
3. Use any other highest non-shutdown interface IP address that is not allocated by another OSPF process.

• Valid interfaces do not have to be matched by a network statement.
• The down/down state is sufficient.
• OSPF does not have to advertise to reach the RID subnet.
• The RID does not have to be reachable per the IP routing table.
• The RID can change if the OSPF process is restarted or the RID is manually configured.
• If the RID changes, the routers in the same area will have to perform a new SPF calculation.

Becoming Neighbors, Exchanging Databases, and Becoming Adjacent

• Five different message types are encapsulated inside IP packets, using IP protocol 89.
• Hello: Used to discover neighbors, bring a neighbor relationship to a 2-Way state, and monitor a neighbor's continuous liveliness.
• Database Description (DD or DBD): Used to exchange LSA headers during the initial topology change.
• Link-State Request (LSR): A packet that identifies one or more LSAs about which the sending router would like the neighbor to supply full details about.
• Link-State Update (LSU): A packet that contains fully detailed LSAs, sent in response to an LSR message or in the event of a topological change.
• Link-State Acknowledgement (LSAck): Sent to confirm the receipt of an LSU message.

• The LSAs themselves are not OSPF messages.
• An LSA is a data structure, held inside a router's LSDB and exchanged inside LSU messages.
• An OSPF router keeps a state machine for each neighbor (show ip ospf neighbor).
• These neighbor states change as the neighbors progress through their messaging.

OSPF Neighbor States

• OSPF routers go through a series of adjacency states.
• Some of these states are transitory, and some are stable states.
• Neighbor states, not adjacency states.
• Routers can temporarily consider each other in different states, but ultimately both routers must arrive at the same state.

• Down: The initial state for a neighbor. Implies that the router already knows about its neighbor's IP address.
• Attempt: Valid only in NBMA networks. A neighbor is immediately placed into the this state and contacted by Hello packets. If no reply within the Dead interval, go back to Down state.
• Init: If a valid Hello packet has been received but the list of seen routers in this Hello packet does not contain the receiving router's RID.
• 2-Way: If a valid Hello packet has been received and the list of seen routers in this Hello packet includes the receiving router's RID. Confirms bidirectional visibility, and is a stable state between routers that do not intend to become fully adjacent.
• ExStart: The purpose is to establish the Master/Slave relationship. The routers exchange empty DBD packets to compare their RIDs, determine the Master/Slave roles, and agree on a common starting sequence number used to acknowledge subsequent DBD packets.
• Exchange: DBD packets are exchanged. Each router builds a list of LSAs to be subsequently downloaded from the other router.
• Loading: After the neighbor has advertised the complete list of LSAs and downloads the LSAs.
• Full: All required LSAs have been downloaded, so all missing or outdated LSAs have been acquired. The state is stable and neighbors are fully adjacent.

Becoming Neighbors: The Hello Process

• Hello messages perform four major functions:

1. Discover other OSPF routers on common subnets.
2. Check for agreement on selected configuration parameters.
3. Verify bidirectional visibility between routers.
4. Monitor the health of the neighbors to react if the neighbor fails.

• Listen for multicast Hellos messages sent to 224.0.0.5 (All OSPF Routers).
• Hellos are sourced from the router's primary IP address on the interface.
• Routers will advertise secondary IP addresses but never send Hellos or form neighborships using secondary IP addresses.
• OSPF neighbors will become fully adjacent if one or both of the neighbors are using unnumbered interfaces for the connection between them.

• Perform the following parameter check based on the received Hellos:

1. Must pass the authentication process (if configured).
2. Must be in the same primary subnet, including the same subnet mask.
3. Must be in the same OSPF area.
4. Must be of the same area type.
5. Must not have duplicate RIDs.
6. OSPF Hello and Dead timers must match.

• If any of these items do not match, the routers do not form a neighborship.
• The OSPF process ID does not have to match.
• The MTU must be equal for the DBD packets to be successfully processed.
• The MTU mismatch would negatively affect the database synchronization process in the ExStart and Exchange process.
• Each Hello contains a list of neighbors from whom the sending router received valid and acceptable Hellos.
• The Hello contains RIDs of routers whose Hellos were seen and accepted by the router originating this Hello.
• If a router finds its own RID in the list of seen routers in a Hello received from a neighbor, it can be sure that they can hear each other.
• Heartbeat: The neighbors send Hellos every hello interval. If a Hello is not received within the dead interval, the router has failed.
• Hello interval: 10 seconds for broadcast and point-to-point, 30 seconds for nonbroadcast and point-to-multipoint.
• Dead interval: 4 x Hello interval.

R1# debug ip ospf hello
OSPF hello events debugging is on
Jan 12 06:41:20.940: OSPF: Mismatched hello parameters from 10.1.111.4
Jan 12 06:41:20.940: OSPF: Dead R 40 C 120, Hello R 10 C 30 Mask R 255.255.255.0 C
255.255.255.0

C = Configured, R = Received

Transmitting LSA Headers to Neighbors

• After Hellos and parameter checks, neighbors do not immediately send LSAs.
• First, each router creates and sends Database Description (DD or DBD) packets, which contain the headers of each LSA.
• Essentially, the DBD is an index list of all the LSAs each router knows about (including revisions).
• Next, a router requests a new copy of only those LSAs it does not have or which are less recent.
• DD messages have an OSPF-defined simple error recovery process: each DD packet has a sequence number assigned, the receiver acknowledges a received DD packet by sending a DD packet with the identical sequence number to the sender.

Database Description Exchange: Master/Slave Relationship

• In ExStart, the routers determine the master and slave roles.
• Only the master is allowed to send DD packets on its own accord and to set and increase their sequence numbers.
• A slave is allowed to send a DD packet only as a response to a master's DD, and must use the same sequence number.
• In effect, a slave is polled by the master and only responds to it.
• DD packet contains three flags:

1. Master (MS) flag: Set in all DD packets sent by the master, and cleared in all packets sent by the slave.
2. More (M) flag: Set when a router intends to send an additional DD packet after this one.
3. Init (I) flag: Indicates the initial DD packet that starts the exchange. Subsequent DD packets, either from master or slave, have the I flag cleared.

• During the DD packet exchange, one router might need to send many DD packets while the other might only require a single DD packet.
• Two rules to sending DD packets:

1. Each DD packet sent from the master must be replied to by the slave (i.e. the number of DD packets sent from master to slave must match the number of DD packets sent from slave to master).
2. A slave can send a DD packet only as a response to receiving a master's DD packet.

• If a router has no more LSA headers to advertise but its peer requires it to send more DD packets, the router will simply send empty DD packets.
• If the slave has more DD packets to send, the master must continue polling the slave, even if it has no more LSAs to advertise itself.
• The slave sets the M flag in its DD packet sent in response to the master's DD packet.
• A master will stop sending DD packets to a slave when it has no more LSA headers to advertise, and the slave's last received DD packet has the M flag cleared.
• In the beginning of ExStart, both routers consider themselves to be the master, and send an empty DD packet, containing a randomly chosen sequence number, and MS (Master), M (More), and I (Init) flags set to 1.
• After receiving the neighbor's DD packet, the router with the lower RID will change its role to slave, and it will respond with a DD packet with the MS and I flags cleared and the sequence number set to the sequence number of the master's DD packet.
• The routers move into the Exchange state.
• The master will then a DD packet with the sequence incremented by 1, and the slave will respond with the same sequence number, optinally advertising its own LSA headers.
• The exchange continues in the same fashion, until both routers have advertised all known LSA headers.
• The master will stop sending DD packets when it has advertised all LSA headers itself and the last DD response from the slave has the M flag cleared.

Requesting, Getting, and Acknowledging LSAs

• After the DD packets, the router needs to request a full copy of each LSA that is missing from its own LSDB.
• To know whether a neighbor has a more recent copy of a particular LSA, a router looks at the sequence number of the LSA in its LSDB and compares it to the sequence number of that same LSA learned from the DD packet.
• Each LSA's sequence number is incremented every time the LSA changes or is reoriginated.
• For example, R1 sent R2 an LSA header for the type 1 LSA that describes R1 itself, with sequence number 0x80000004. If R2’s database already held that LSA, but with a sequence number of 0x80000003, R2 would know that it needs to ask R1 to send the latest copy (sequence number 0x80000004) of that LSA.
• LSA sequence numbers start with 0x80000001; increase through 0xFFFFFFFF, 0x00000000, and 0x00000001, and finish at 0x7FFFFFFF.
• Routers use Link-State Request (LSR) packets to request one or more LSAs from a neighbor.
• The neighboring router replies with Link-State Update (LSU) packets, which hold one or more full LSAs.
• The LSR/LSA process uses a reliable protocol with two acknowledgement options: 1) send back the same LSU to the sender, and 2) send back an LSAck, which contains a list of acknowledged LSA headers.
• At the end of the process, the neighbors have exchanged their LSDBs, and the LSDBs are identical.

Designated Routers on LANs

• OSPF uses a DR (and a backup DR, or BDR) on a multiaccess network. 
• The LSA flooding occurs through the DR, reducing the unncessary exchange of redundant LSAs.
• The presence of a DR/BDR allows the routers to synchronize only to a DR and BDR, alleviating the need of synchronizing to each other, possibly flooding the same set of LSAs multiple times.
• In reality, DRs have a different crucial and the only truly irreplaceable function: They create a Type 2 LSA that represents the multiaccess network segment.
• Only routers in the Full state are allowed to exchange LSAs.
• On a multiaccess network, every router is in the Full state only with the DR and BDR.
• The DR and BDR are also in the Full state with each other.
• The DR and BDR send LSUs to the multicast IP address 224.0.0.5, All OSPF Routers group.
• Other OSPF routers will acknowledge the receipt of the LSU by sending an unicast LSAck back to the originating router.
• All other non-DR/BDR send updates to the multicast IP address 224.0.0.6, the All OSPF DR Routers group that contains only the DR and BDR.
• Both the DR and BDR will store the updated LSA from the LSU in their LSDB.
• The DR then floods the new LSU to all OSPF routers (224.0.0.5).
• Other routers on the segment including the BDR, except the original router, will acknowledge the DR's LSU with a unicast LSAck sent to the DR.
• A router that is neither a DR or BDR is called a DROther.
• Routers that are DROthers do not become fully adjacent; they stop at the 2-WAY state.
• The 2-WAY simply means that the Hello parameters match and bidirectional visibility check worked, but the neighbors do not synchronize their LSDBs directly with each other.
• Neighbors: Two routers that share a common data link and that exchange Hello messages, and the Hellos must match for certain parameters.
• Adjacent (fully adjacent): Two neighbors that have completed the process of fully exchanging DD and LSU packets directly between each other.
• DROthers still end up with an identical copy of the LSDB by exchanging them with the DR.

DR Election on LANs

• The election occurs after the routers have become neighbors, but before they send DD packets and reach the ExStart neighbor state.
• If the DR has not been elected (a DR of 0.0.0.0 in the Hello message), the router waits before attempting to elect a DR.
• The wait period is called the OSPF wait time, which is set to the same value as the Dead timer.
• If the received Hellos already list the DR's RID, the router does not have to wait before beginning the election process.
• A router with its OSPF priority set to 1-255 inclusive is eligible to become a DR or BDR. 
• If the priority is set to 0, the router is ignored in DR/BDR elections.
• Each router performs the elections locally, but the algorithm makes sure that all routers ultimately arrive at the same conclusion.
• During the wait interval, each router collects the priorities and RIDs of other neighbors on the segment. The routers do not assert themselves as the DR or BDR during this phase.
• If, during the wait interval, a Hello packet arrives from a neighbor that claims itself as the DR or BDR, the router immediately proceeds to the DR/BDR election process. Otherwise, the full wait time on the interface needs to expire.
• The election is performed only for those roles that are not yet claimed in neighbor Hellos.
• The router with the highest priority becomes the DR, and the router with the second-highest priority becomes the BDR.
• If there are routers with the same priority, the higher RID is used to break the tie.
• After the election has completed, if a new router arrives on an existing router improves its priority, it cannot preempt and take over the existing DR (or BDR).
• When a DR is elected and the DR fails, the BDR becomes the DR, and a new election is held for a new BDR.
• If two routers arrive at different DR/BDR elections (perhaps due to STP convergence), they enter the election phase again.

Designated Routers on WANs and OSPF Network Types

• Routers can be configured to use, or not to use, a DR and a couple of other key behaviors, based on the OSPF network type.
• The OSPF network type determines the following:

1. Whether the router tries to elect a DR.
2. Whether the router uses unicast (the neighbor command) or multicast to find neighbors.
3. Whether two or more neighbors should be allowed on the same subnet.

• The OSPF network type is set with the ip ospf network <type> under the interface.
• The table lists the network types and their exact keywords for the command.

Caveats Regarding OSPF Network Type over NBMA Networks

• Make sure that the default Hello/Dead timers do not cause the Hello parameter check to fail.
• Ensure that all routers in the same NBMA network use an OSPF network type that either uses a DR or does not.
• If a DR is used, the DR and BDR must have a PVC to every other router in the subnet. Routers that do not have a PVC to every other router must not be permitted to become a DR/BDR.
• The neighbor command on a single router is sufficient to bring up the OSPF adjacency with the configured neighbor. For clarity and stability, it is better to configure the neighbor command on both routers.

Example of OSPF Network Types and NBMA

• With partial meshes, the DR/BDR election should be influenced by configuring the routers' priorities and RIDs so that the hub of a hub-and-spoke design becomes the DR.
• The priority specified in the neighbor command is never used in DR/BDR elections.
• If there are multiple neighbor statemets and at least one of them has a non-zero value, the router will first send Hello packets only to those neighbors.
• Only after the DR/BDR elections have completed between these routers, the router will start sending Hello packets to all remaining neighbors.
• This optimization increases the chances that the DR and BDR roles will be taken up by appropriate routers, and prevents routers from competing in DR/BDR elections with neighbors that are not entitled to these roles.
• The priorities specified in the neighbor commands do not need to match the real priorities of these neighbors, but if they differ, the router can engage in DR/BDR elections with neighbors not entitled to become a DR/BDR.
• In any case, the real priorities, as seen in the Hello packes, will be used to complete the DR/BDR elections.
• If all neighbor statements omit the priority setting, this optimization is not used, and all neighbors are contacted immediately.

SPF Calculation

• After a router has new or different information in its LSDB, it uses the Dijkstra SPF algorithm to examine the LSAs in the LSDB and derive the new tree of shortest paths to available networks.
• SPF on a router constructs least-cost paths from this router to all possible destinations, summing the costs for each outgoing interface along the path and picking the path with the lowest total cost.
• Found destinations and their least-cost paths are placed into the routing table.

Steady-State Operation

• Even after the network has stabilized and the LSDBs are synchronized, the routers perform the following operations:

1. Send Hellos, based on per-interface Hello intervals.
2. Expect to receive Hellos from neighbors within the Dead interval on each interface; if not, the neighbor is considered to have failed.
3. Reflood self-originated LSAs (incrementing the Sequence Number by 1) based on the LSRefresh interval (default 30 minutes) even if no change has occurred.
4. Expect to have its LSAs refreshed within each LSA's MaxAge timer (default 60 minutes).