In a typical distance vector protocol, each router advertises its table of reachable destinations (vectors) and the distances to them (distance) on each of its interfaces on a regular basis (periodic updates). OSPF routers advertise the state of their directly connected links to all routers on the network (through flooding). Although OSPF uses periodic updates, long periods of time exist between them, reducing network traffic to a minimum. Each router receives these link-state advertisements (LSAs) from its neighbors and floods them out each of its other interfaces, making certain that all routers on the network receive all LSAs.

After all routers have received all advertisements, they perform a shortest path first (SPF) calculation to find a loop-free path to each destination on the network. OSPF uses neighbor relationships to reliably flood LSAs. It enforces hierarchy and restricts flooding domains in a network through areas.
Router IDs

Each router that is running OSPF on a network must have a unique identifier—the router ID. This router ID is used in combination with an LSA sequence number to detect duplicate LSAs and to prevent a router from accepting an LSA that it originated.

The router ID is chosen from among the IP addresses on a Cisco router; it is either the highest IP address from any operational interface (interface and line protocol both up), or it is the address of the lowest numbered loopback interface. The recommended practice is to use loopback interfaces or the router-id command in the router OSPF configuration mode to set the router ID because this provides more stability in the network and makes the router ID more predictable.

LSAs

LSAs are classified by type, each type serving a different purpose:

• Router Link State (type 1)— These LSAs contain information about the following:
- A router's connected (fully adjacent) neighbors
- Connected stub networks (networks on which this router has no neighbors)
- IP reachability information for connected point-to-point networks
• Network Link State (type 2)— These LSAs are generated by the designated router to advertise connectivity to a broadcast (multiaccess) network and connections to all the routers that are connected to the broadcast network.
• Summary Network Link State (type 3)— These LSAs advertise internal networks to routers in other areas (interarea routes). Each intra-area route might represent a single destination or a set of destinations aggregated into one route. Summaries are only generated by area border routers (ABRs).
• Summary ASBR Link State (type 4)— These LSAs advertise the location of an autonomous system boundary router. Routers that are trying to reach an external network use these advertisements to determine the best path to the next hop. They are generated by Autonomous System Boundary Routers (ASBRs).
• External Network Link State (type 5)— These LSAs redistribute routes from other autonomous systems, generally using a different routing protocol, into OSPF.
• External Network Link State (type 7)— These LSAs are similar to type 5 LSAs, but they represent externally reachable destinations within a not-so-stubby area (NSSA).

Figure B-1 illustrates the first five of these LSA types in a small network.

Figure B-1. Primary LSA Types in an OSPF Network

What would each router in this network originate, and why?

• Router A would generate a type 1 LSA with the following:
- A bit set indicating that it is an ASBR, because it is redistributing.
- A connection to Router D.
- A connection to 10.1.2.0/24.
• Router A would generate a type 5 LSA with a connection to 10.1.4.0/24, because it is redistributing that connected interface into OSPF.
• Router B would generate a type 1 LSA with the following:
- A connection to Router D.
- A connection to the pseudonode that is advertised in the type 2 LSA of Router C. Router B does not advertise a connection to 10.1.5.0/24 or to Router C, because this is a broadcast network with a designated router.
- A connection to 10.1.1.0/24.
- A connection to 10.1.3.0/24.
• Router C would generate a type 1 LSA with connection to the pseudonode that is advertised in its own type 2 LSA. Router C does not advertise a connection to 10.1.5.0/24 or to Router B, because this is a broadcast network with a designated router.
• Router C would generate a type 2 LSA with the following:
- A connection to Router C.
- A connection to Router B.
- A connection to 10.1.5.0/24.
• Router D would generate a type 1 LSA into area 1 with the following:
- A connection to Router A.
- A connection to Router B.
- A connection to 10.1.2.0/24.
- A connection to 10.1.3.0/24.
• Router D would generate a type 1 LSA into area 0 with a connection to Router E, and include a connection to the network between Routers D and E.
• Router D would generate a type 4 LSA into area 0, including the cost to reach Router B. This type 4 LSA is generated because Router B is setting a bit in its router LSA (type 1), indicating that it is an ASBR.
• Router D would generate a type 3 LSA including the following:
- A connection to 10.1.1.0/24.
- A connection to 10.1.2.0/24.
- A connection to 10.1.3.0/24.
- A connection to 10.1.5.0/24.
• Router D would react with the following:
- Reflood Router A's type 5 LSA into area 0.
- Not reflood Router B's type 1 LSA into area 0.
- Not reflood Router C's type 1 LSA into area 0.
- Not reflood Router C's type 2 LSA into area 0.

LSA Age

Each LSA that is flooded to the network has an age parameter (LSAge), which is set by the originating router to 0. When a router receives an LSA from a neighbor, it begins aging it out by adding 1 to the LSAge for each second it holds the LSA in its database. When the LSAge equals MaxAge, the router sets the cost to unreachable, floods the LSA, and then removes the LSA from its database. This clears any LSA from the network that is not periodically refreshed.
Because of this aging-out mechanism, OSPF routers must reflood their LSAs periodically to prevent them from being timed out. How often a router floods its LSAs is called the LSRefreshTime. The MaxAge is set to 1 hour, and the LSRefreshTime is set to 30 minutes.

Reliable Flooding of LSAs

When a router receives an LSA or the status of one of its directly connected links changes, it marks the database entry and builds a list of neighbors to which this entry needs to be flooded. As the router builds a packet to send (which can contain more than one LSA), it does the following:

• Chooses database entries marked for sending and places them in the packet
• Notes in the database neighbors to which the LSA has been advertised

As acknowledgments are received, neighbors are removed from the waiting for acknowledgment list that is associated with the LSA. Every so often, the router checks this list of outstanding acknowledgments to see if some neighbors have not responded; it resends the LSA to those that have not. This interval is configurable on a per-interface basis using the ip ospf retransmit-interval command on a Cisco router.

Building Adjacencies

Because adjacencies are vital to the reliable flooding of these LSAs, you should examine how an adjacency is built and discuss some special cases. Figure B-2 shows two routers connected to the same network.

Figure B-2. Building Adjacencies

When Routers A and B are first attached to the common serial link, they begin sending Hello packets on this network. Next, the routers begin receiving each other's Hello packets. When A and B receive each other's Hellos, they place their new neighbors in an init state, as illustrated in Figure B-3.

Figure B-3. Init State

After placing a new neighbor in an init state, a router begins including the router ID of that neighbor in its Hellos. After a router has received a Hello from a neighbor with its router ID enclosed, the router places the neighbor in a two-way state. This two-way state ensures two-way communication between the routers before exchanging database information. Routers do not enter the two-way state if the link type, Hello time, wait time, or dead time do not match.

After determining that an adjacency should be built (routers remain in a two-way state under some circumstances—see the next section, "Adjacencies on Multiaccess Networks"), the routers begin to negotiate the exchange of their OSPF databases. If a new router on the network were to wait until normal flooding occurred to obtain a complete database, it could take a half an hour to do so. During that time, the router would not be able to reach all areas in the network and could cause routing loops.

This stage is called exstart; a master and slave are chosen to synchronize the database exchange based on the router IDs of the two routers. The master controls the exchange of the database descriptors (DBDs) between the routers, as illustrated in Figure B-4.

Figure B-4. Exstart

After the routers have negotiated which one will control the DBD exchange, they begin exchanging DBDs, as illustrated in Figure B-5.

Figure B-5. Exchange

These DBDs do not really contain link-state information. They just describe each router's database. Each DBD contains a list of LSAs and LSA sequence numbers, by which each LSA in a router's database can be uniquely identified. After all the DBDs have been exchanged, each router compares the list of LSAs received through the DBDs against its local database, and requests the set of LSAs required to synchronize its databases.

After the two routers have finished requesting the LSAs required to synchronize their databases, they move their neighbor adjacency into the full state.
Adjacencies on Multiaccess Networks

It is not efficient for every router on a multiaccess (broadcast or nonbroadcast multiaccess [NBMA]) network to build full adjacencies with every other router on that network, so OSPF uses the concepts of designated routers (DRs) and backup designated routers (BDRs) to reduce the number of adjacencies built and consequently reduce the number of LSAs flooded throughout the area for the common network. Each router on the network builds a full adjacency with the DR and BDR and leaves all other neighbors on that network in the two-way state. The DR is responsible for advertising a link to the network and for flooding LSAs to other routers on the link.

The DR and BDR are elected based on the router priority (configured on a per-interface basis on a Cisco router with ip ospf priority) and the router ID.
Assuming that all three of these routers were connected to the same Ethernet segment, as shown in Figure B-6, at the same time (unlikely, but possible if you tried hard enough), each would see each other's Hellos, progress to the two-way state, and begin electing a BDR and a DR for this link.

Figure B-6. A Multiaccess Network

To better understand what transpires, look at this scenario from the perspective of Router A.

Router A will receive three Hellos, one each from Routers B, C, and D. Because B's priority is set to 0 (which means Router B cannot become the DR or the BDR), it keeps its neighbor state with Routers A, C, and D at two-way.

The Hello from Router C indicates that it has a priority of 80 and an ID of 10.1.1.5. The Hello from Router D indicates that it has a priority of 100 and an ID of 10.1.1.10.

Router A first compares the priorities of the other routers with its own; Router D's matches, but Router C's is lower. Because Router C has a lower priority, it is removed from the possibilities.

Because Router D's matches, the router ID is used to determine the BDR, (The BDR is always elected first.) Router A's router ID is higher than router D s, so Router A is chosen as the BDR.

Now Router A determines that the link has no DR, so it promotes the BDR to the position of DR and then elects a new BDR. Router A promotes itself to DR and examines each of its other neighbors in the two-way state to see which should become the BDR. Once again, Router B is not considered because its priority is 0. Router A compares the Hellos from the remaining two neighbors and discovers that Router C has a lower priority than D. Therefore, the new BDR is Router D.
The order in which this occurs is of some importance because the process must be repeatable when the DR is lost. The BDR is promoted, and a new BDR is elected.

Because getting all of these routers to connect to the link at the same moment is too difficult, you need to examine how an OSPF router deals with a new link when a DR and a BDR already exist. Assume that Routers B, C, and D are attached to this Ethernet and have been running for some time. What happens when A is attached?

Without Router A, Router D is the DR, and Router C is the BDR. When Router A is first attached, it sees Router D's Hellos asserting that it is the DR, and it does not attempt to re-elect a new one (even though it would be chosen if a new election were to occur). This prevents unecessary DR election by allowing the router connected to the link the longest become, and stay, the DR.