This is a Tutorial excerpt from OSPF I: OSPF in Single Areas: Learning the Protocol by Howard Berkowitz. If you're not a Certification Zone Subscriber and you would like complete, unrestricted access to the rest of this and every other Tutorial, Study Quiz, Lab Scenario, and Practice Exam available at Certification Zone, become a Subscriber today!

OSPF Protocol Mechanisms

As shown in Figure 5, OSPF does not use a transport protocol like UDP or TCP, but runs directly over the data link layer. OSPF has its own mechanisms to perform any required retransmission.

Figure 5. Routing Protocol Stacks

All OSPF packets have a common OSPF header that follows the IP header. The IP header for most OSPF packets has a multicast address in the destination field and the address of the router generating the packet as the source field.

Figure 6. OSPF Common Packet Header

All OSPF packet headers have an authentication field. This field can be blank, it can contain a clear text password, or it can contain an MD5-encrypted authentication value. There are applications for each of these choices.

First, understand what is being authenticated: routing packets not routed packets. OSPF authentication protects the integrity of the routing system, but does nothing to protect user data packets. If the user traffic needs integrity protection, you will need to use an additional mechanism such as IPSec.

Cryptographic authentication protects routers against deliberate attacks on the routing system. Such attacks would generally have to be launched by someone with direct access to the media, which certainly is plausible in academic environments.

Plain text passwords still have a value, but in less hostile environments. I find them useful when combining OSPF domains that were built separately, as you may encounter in a merger or acquisition. By putting a unique password on routers that you have reconfigured for the new environment, they will ignore routing updates from routers that have not yet have been reconfigured for the new environment.

Figure 7. OSPF Packet Types

OSPF Hello Processing

Four of the five OSPF packet types contain LSAs. Hello packets (see Figure 8.) are the only exception.

Figure 8. Hello Packet

Hello processing serves several functions. Obviously, it discovers the existence of other routers on the same subnet.

Once a router is discovered, the next question is the type of relationship the local router wishes to have with it.

Neighbors describe routers that share a common medium and have agreed to form a basic relationship. In all interior routing protocols, two routers that are neighbors are connected to a common subnet (or equivalent such as an OSPF virtual link). Contrast this with routers that can reach one another, but may be separated by intermediate routers.

OSPF distinguishes between neighbors and adjacencies. At this point, assume that adjacencies are neighbors that have met additional criteria.

The following output contains the OSPF-related information relevant to each interface active in the OSPF process on Munster. The show ip ospf interfaces command is used to generate this output.

Munster>sh ip ospf int
Ethernet0/0 is up, line protocol is up
  Internet Address 192.168.10.254/24, Area 0.0.0.1
  Process ID 99, Router ID 223.254.254.251, Network Type BROADCAST, Cost: 10
  Transmit Delay is 1 sec, State DR, Priority 1
  Designated Router (ID) 223.254.254.251, Interface address 192.168.10.254
  No backup designated router on this network
  Timer intervals configured, Hello 10, Dead 40, Wait 40, Retransmit 5
    Hello due in 00:00:04
  Neighbor Count is 0, Adjacent neighbor count is 0
  Suppress hello for 0 neighbor(s)
Serial0/0 is up, line protocol is up
   OSPF not enabled on this interface
Serial0/0.1 is up, line protocol is up
   OSPF not enabled on this interface
Serial0/0.2 is up, line protocol is up
  Internet Address 10.201.32.2/24, Area 0.0.0.1
  Process ID 99, Router ID 223.254.254.251, Network Type BROADCAST, Cost: 1
  Transmit Delay is 1 sec, State DROTHER, Priority 0
  Designated Router (ID) 223.254.254.254, Interface address 10.201.32.1
  No backup designated router on this network
  Timer intervals configured, Hello 10, Dead 40, Wait 40, Retransmit 5
    Hello due in 00:00:05
  Neighbor Count is 1, Adjacent neighbor count is 1
    Adjacent with neighbor 223.254.254.254  (Designated Router)
  Suppress hello for 0 neighbor(s)
Serial0/1 is administratively down, line protocol is down
   OSPF not enabled on this interface
Loopback0 is up, line protocol is up
   OSPF not enabled on this interface

Be aware that neighbor and/or adjacency relationships cannot currently be formed when using secondary addressing as the basis for routing protocol communication. The reasons for such behavior go deeply into protocol design, and may not be a restriction in the future. At present, don't depend on secondaries working in OSPF, EIGRP, or ISIS. Subinterfaces, such as those used in VLANs or Frame Relay for example, are transparent to these protocols.

Modern (i.e., OSPF, ISIS, EIGRP) routers on a subnet use the hello subprotocol to become aware of one another and decide to become neighbors, as shown in Figure 9.

Figure 9. Hello Processing

The logic of hello processing, at times, reminds me of a singles bar. Router Romeo may say to Router Juliet, "Come in here often? What's your sign?" Juliet can ignore this and not become Romeo's neighbor.

Juliet can politely shake hands and become a neighbor, but tell Romeo that she is already Deeply Committed to the Designated Router, Friar Lawrence.

Once a neighbor relationship is established, one router will begin to route through its neighbor but does not necessarily have information on all that router's knowledge.

Full knowledge is shared when the additional commitment of adjacency is undertaken. Adjacent routers exchange their full databases, as well as providing routing services to one another. Authentication is the OSPF protocol equivalent of safer sex.

If Juliet already has dinner plans with Friar Lawrence, the good father is already adjacent to her, and she and Romeo will just be friends ...er... stay in the neighbor relationship. If Juliet has no router to which it is adjacent, then Romeo has a chance of success with "wanna get adjacent, baby?"

Negotiations are much simpler on point-to-point links, because there can be no third party with whom a router might already have a relationship.

Link State Advertisements

For a moment, bear with me and assume that LSAs are magically distributed. We will get into the initialization and change mechanisms by which LSAs are distributed, but it's worthwhile to understand what is in the LSAs.

In this discussion of single area OSPF, we are most concerned with type 1 (router) and type 2 (network) LSAs. See Table 6 for a full list of types supported by the Cisco IOS. Like any OSPF packet, they begin with a standard header. Following the IP header and OSPF headers is the LSA Header (see Figure 10), which identifies the kind of LSA, the router that originated the LSA, and the identity of the link to which the LSA refers (e.g., a router ID or a subnet).

Table 6. Major LSA Types

Note: LSA types in gray are relevant only in multi-area configurations.

Figure 10. Standard LSA Header

The header also contains information that can be used to tell which is the most recent copy of an LSA. This is not a true timestamp, but it effectively serves that purpose without requiring strict time-of-day synchronization. Three fields -- sequence number, age, and checksum -- are involved in the process of selecting the update that is most recent with respect to the advertising router. The actual algorithm used is complex and beyond the scope of this discussion (there really isn't any way for you to affect it at the router configuration level). See [RFC2328] for the specification of the algorithm, and see [Perlman] for a discussion of the complex "lollipop" algorithm used for sequence numbers.

Because link state protocols can tell which is the most recent information about a link, they avoid a great deal of the loop formation potential found in early distance vector protocols such as RIP and IGRP. Having this age information prevents problems in situations where information that is more recent arrives through a fast path, while out-of-date information arrives afterward because it went through a slow path.

Think of the type 1 and type 2 LSAs as trees. The type 1 has the router ID as its root, with branches identifying all the networks to which the router connects. The type 2 has the network as the root, and branches that identify all routers that connect to the network.

You can display the link state database at various levels of detail. show ip ospf database, an example of which is shown in Table 7 (type 1 and 2 LSAs only), gives basic information only.

Table 7. Summary-Level LSDB Display

     OSPF Router with ID (223.254.254.251) (Process ID 99)
             Router Link States (Area 0.0.0.1)
                                                          Link
Link ID         ADV Router      Age   Seq#       Checksum count
223.254.254.242 223.254.254.242 399   0x80000003 0xC735   2
223.254.254.251 223.254.254.251 1115  0x80000007 0x55AB   2
223.254.254.254 223.254.254.254 261   0x80000017 0xD5A5   21
             Net Link States (Area 0.0.0.1)
Link ID         ADV Router      Age   Seq#       Checksum
10.201.32.1     223.254.254.254 466   0x80000002 0xC1EE
10.201.192.1    223.254.254.254 398   0x80000001 0x5EBB

You can get information that is more detailed by adding a keyword to the command, as in show ip ospf database router (Table 8) or show ip ospf database network (Table 9).

Table 8. Detailed Router Entries in a LSDB

    Router Link States (Area 0.0.0.1)
  LS age: 529
  Options: (No TOS-capability, DC)
  LS Type: Router Links
  Link State ID: 223.254.254.242
  Advertising Router: 223.254.254.242
  LS Seq Number: 80000003
  Checksum: 0xC735
  Length: 48
   Number of Links: 2
    Link connected to: a Stub Network
     (Link ID) Network/subnet number: 10.19.32.0
     (Link Data) Network Mask: 255.255.255.0
      Number of TOS metrics: 0
       TOS 0 Metrics: 10
    Link connected to: a Transit Network
     (Link ID) Designated Router address: 10.201.192.1
     (Link Data) Router Interface address: 10.201.192.2
      Number of TOS metrics: 0
       TOS 0 Metrics: 781

Table 9. Detailed Network Entries in an LSDB

LS age: 1245
  Options: (No TOS-capability, DC)
  LS Type: Router Links
  Link State ID: 223.254.254.251
  Advertising Router: 223.254.254.251
  LS Seq Number: 80000007
  Checksum: 0x55AB
  Length: 48
   Number of Links: 2
    Link connected to: a Transit Network
     (Link ID) Designated Router address: 10.201.32.1
     (Link Data) Router Interface address: 10.201.32.2
      Number of TOS metrics: 0
       TOS 0 Metrics: 1
    Link connected to: a Stub Network
     (Link ID) Network/subnet number: 192.168.10.0
     (Link Data) Network Mask: 255.255.255.0
      Number of TOS metrics: 0
       TOS 0 Metrics: 10
Routing Bit Set on this LSA
  LS age: 613
  Options: (No TOS-capability, DC)
  LS Type: Network Links
  Link State ID: 10.201.192.1 (address of Designated Router)
  Advertising Router: 223.254.254.254
  LS Seq Number: 80000001
  Checksum: 0x5EBB
  Length: 32
  Network Mask: /24
        Attached Router: 223.254.254.254
        Attached Router: 223.254.254.242

You must allow LSAs to propagate everywhere in an area. If you use switches to control multicast traffic with IGMP snooping or CGMP, you must ensure that these do not inadvertently block routing updates. I've always been surprised to see how often the question is asked, "How can I make OSPF go through a firewall?" This doesn't make a great deal of sense, since the scope of OSPF announcements is limited to a single link. Firewalls go between links.

Designated Routers

The first thing to realize about a designated router is that it isn't a router. It's a property of an interface of a router. (See Figure 11.) A router with four interfaces could be a designated router on two of them, a backup designated router on another, and recognize another physical router as the designated router for the medium associated with its fourth interface.

Figure 11. Designated Routers

"Medium" is the key to understanding the idea of the designated router. In OSPF domains, each multiaccess network has a designated router. It may or may not have a backup designated router. The combination of designated and backup designated router is represented by the well-known multicast group AllDRouters (224.0.0.6).

The DR is the "traffic cop" to the medium, and is a means of reducing traffic involved in updates. Rather than having every router connected to the shared medium establish an adjacency with every other, thus having N routers sending updates to (N-1) routers, conceptually a router sends an update to the DR. The DR evaluates the update, and, if the update is significant, multicasts to all other routers on the medium. Rather than (N-1) updates, there are two.

Actually, the update is sent to the multicast group of DR and BDR, but as long as the DR operates properly, the BDR remains silent.

Becoming a DR or BDR

When a router begins to send out hellos, it listens for other hellos. If a DR or BDR is already established for the medium, the new router accepts the incumbents. When there is neither a BDR nor DR, an election is held first for BDR. If there is only one router in the election (i.e., one router initializes before any of the others), it will become BDR, and then promote itself to DR.

If more than one router is active and none of them are claiming to be DR or BDR, they hold an election for BDR. (See Figure 12.) Two factors affect the result of the election. First, the OSPF router priority value is advertised in the hello. Second, if there are multiple routers with the same priority, the router with the higher router ID is elected.

Figure 12. DR/BDR Election

In practice, on LAN-style broadcast media, priority is far less important in DR selection than the order in which routers initialize. With such media, the only real reason even to try to affect selection is that there is a significant difference in processing power among routers and you want to encourage the router with the most processing power to become DR. Being DR or BDR does increase processing load.

There is no reason to have a DR on a point-to-point medium, because there is only one router to receive updates. Having a DR mechanism does nothing to reduce traffic.

NBMA media, however, are a special case for DR management.

DR and BDR Response to Failures

Several failure recovery mechanisms are involved with DRs and BDRs. The BDR hears updates being sent to the DR and starts a timer. If the DR does not respond before the BDR timer expires, the BDR will send out the update that the DR should have sent. Under these circumstances, however, the BDR does not take over as DR.

The BDR does replace the DR, however, when the BDR does not receive a hello packet from the DR within the interval specified by the dead timer, which is 40 seconds by default. When the dead timer expires, all neighbor relationships are cancelled.

When the dead timer expires, the current BDR will promote itself and a new election will be held for BDR. If the originally failing DR or BDR comes back to life, it will not replace the current DR or BDR unless the current device dies. Once a BDR and DR have been elected, they will not be replaced by a router with a higher OSPF priority. In ISIS, the higher priority router will replace the DR.

Database Initialization

Once routers decide that they should be neighbors -- that they can route through one another -- they next need to decide if they should, in addition, become adjacent to the new neighbor. This is straightforward on point-to-point media, but, on multiaccess, a new router will only form an adjacency with the DR and BDR. Of course, an active DR must exist before this can happen.

The next step after adjacency formation is for the two routers to share information in their databases until they agree that the databases contain an identical set of links. The links can be of a different age, but the link identifiers must be identical. Since both routers may be receiving updates while they exchange database information, the process often takes more than one iteration.

RFC 2328 states that adjacencies should be created with a neighbor when any of the following conditions is true:

• The underlying network type is point-to-point.
• The underlying network type is point-to-multipoint.
• The underlying network type is virtual link.
• The router itself is the Designated Router.
• The router itself is the Backup Designated Router.
• The neighboring router is the Designated Router.
• The neighboring router is the Backup Designated Router.

So, the new router will form an adjacency and exchange databases with one or more routers, one per connected medium.

Before the exchange begins, each pair of routers needs to decide which one will be master and which one will be slave for the purposes of the exchange. These roles have nothing to do with designated router status, and are defined primarily by internal timing and state information internal to the protocol. Selection of the master and slave takes place in the ExStart state of the interface state machine. Once these roles are set, the pair of router interfaces enters the Exchange state and goes through the initial synchronization of databases. I say "initial" synchronization because, after the routers are up and running, they will use other means to stay synchronized with respect to changes.

Initial synchronization starts when the master sends the slave a set of database description (DD) packets that contain summaries of the LSAs in the master's database. Don't confuse these summaries with the type 3 LSA, which contains summarized inter-area information. Indeed, during database initialization, the summaries sent in DD packets will include summaries of type 3 LSAs if any exist.

Once the slave receives this information, it asks itself:

• "Is my information on this link more recent or, in any way, better than that sent to me by the master?"

• "Is this a destination that I already know about, but the master has a lower-cost or otherwise preferable path to it?"

• "After I learn what destinations the master knows about, what do I know about destinations that the master doesn't, and should tell it about?" Remember that the slave might have direct connections to media the master does not, or the slave might have received information about distant links through one of its other interfaces.

The slave acknowledges information for which the master's information is authoritative, but, for things where it has better information than the master, the slave sends that information to the master. During the initialization process, both the master and slave might be receiving new information from other sources, so more than one exchange may be needed before they agree on all information.

Eventually, no new information is exchanged, all information sent has been acknowledged, and the interface transitions from the Exchange to the Full state. The routers explicitly signal one another that they consider themselves synchronized by no longer sending the M (more data) bit in their DD packets.

Once in the Full state, the router now goes through the routing computation and sends the resulting best OSPF routes to the main routing table installation task -- the task that produces the table you display with show ip route. While you can display the OSPF database, there is no command to display the OSPF-only routing table, which is a temporary data structure.

The show ip ospf neighbor command is your friend for determining the state of initialization. See Table 10.

Table 10. Representative Neighbor Display after Initialization

Munster>sh ip ospf nei
Neighbor ID     Pri  State    Dead Time  Address      Interface
223.254.254.254   1  FULL/DR  00:00:32   10.201.32.1  Serial0/0.2

The "2-Way" state refers to routers that are neighbors but are not currently adjacent to one another. This state is common on multi-access networks between routers that are neither the DR nor BDR.

Propagating Topology Changes

Once the router has synchronized and is up and running, it will learn about changes in the topology and will inform other routers. There are two basic mechanisms for doing so: updating and flooding.

Updating is done on a single medium, between the router detecting the change and the DR/BDR. Flooding is the process of routers sending the changes to other routers on different media.

In either case, when a router receives an update, it does not directly install it in its database but goes through a series of steps to decide if it should install it, or if it should take other actions:

• "Is this link in my topological database?" If not, add it to the database and schedule flooding.

• "Is the information about this link newer than the information currently in my database?" If so, replace my current information and schedule flooding.

• "Does the age of this update exactly equal the age of the information in my database?" If so, update timers in the database.

• "If the link in the update is older than the one in my database, do not change my database." Send an update back to the originator of the just-received update, containing the newer information in the receiving router's database.

Under normal conditions, when a router detects a change, it sends the information to the DR and BDR. See Table 11.

Table 11. Normal Flooding

OSPF updates are actually sent to a multicast address that includes both the DR and BDR. When the BDR hears an update sent to the DR, it starts a timer. If the DR does not respond before the BDR's timer expires, the BDR will assume that the DR is dead and will promote itself to DR.

Independent of the decision of the BDR to promote itself is the decision of the BDR to send an apparently missed routing packet.

There really is more than one failure mode to consider:

• (Moy, 1998, p. 106) "If the DR fails, so does database synchronization over the broadcast subnet. OSPF deals with this problem by electing a BDR for the broadcast subnet. All routers synchronize with both the DR and BDR, and the BDR acts as a hot standby in case the DR fails." See Table 12.

• (Moy, 1998, p. 107) " ...if the BDR does not see the Link State Update from the DR within the LSA retransmission interval (typically 5 seconds), it will step in and flood the LSA back onto the Ethernet in order to keep the database synchronization going."

Table 12. Flooding with DR Failure

So, if active updating is going on, the BDR will act to keep that process working before a DR is elected.

The absence of a DR, especially when the subnet is otherwise idle, will be detected by missing hellos by the dead timer.

Once a router, designated or not, receives a confirmed update on one of its interfaces, it floods the information out its other non-stub interfaces (i.e., interfaces that know another router is listening on the same medium). See Figure 13. The flooded information is in the form of LSAs, contained in LS Update packets.

Figure 13. Flooding

In Figure 13, as soon as routers on the shared medium hear a confirmed update, they flood a copy of the update onto the networks connected to their other interfaces. Whether or not a router is DR on the local medium makes no difference with respect to flooding. If the router has other interfaces in the same area, it will flood over them.

LS Updates caused by flooding must be acknowledged, just as are LSAs in updates multicast by the DR. Acknowledgements can explicitly use LS Ack packets or be implicit: one router implicitly acknowledges by sending the same LSA it received back to the source. Implicit acknowledgements are efficient because multiple LSAs can be batched in the same packet, reducing packet header processing and bandwidth.

Improving Update Efficiency

Batched LSAs can include both new information and implicit acknowledgements. OSPF will normally delay sending an LSA so that it improves the chance of being able to batch several delays.

Another timer-based efficiency mechanism tries to reduce the processing load of flapping routes. While the mechanism is considerably simpler than that used with BGP, OSPF does have a configurable holddown timer. Once an update for a given LSA is received, the holddown timer is started, and, until it expires, no additional updates will be accepted for the same LSA.

You can also control the amount of time the router delays before starting a new routing table computation. The longer the delay, the more likely it is that more than one update will be received before the recomputation. The processing load will thus be amortized over multiple updates. To control these timers, use the timers spf spf-delay spf-holdtime command.

Dealing with Old LSAs

While OSPF does not routinely re-announce LSAs in the manner in which RIP and IGRP periodically rebroadcast their routing tables, the protocol does have a "sanity checking" mechanism for purging obsolete information from topological databases. LSAs are aged both in transmission and while they reside in an LSDB. When an LSA reaches the ripe old age of 30 minutes, all but the originating router reflood the LSA, with its age artificially set to MaxAge, equal to 60 minutes.

If any router still has an active instance of the LSA, it will follow the rules of flooding, and respond with its more recent instance (i.e., an instance younger than 60 minutes). Routers along the path where the aged-out LSA was propagated hear the updated information and refresh their LSDBs.

In Cisco's original OSPF implementations, a single age timer was kept per LSDB. All LSAs in the LSDB expired at the same 30-minute interval, which, in large areas, could impose a major burst of processing load. A new feature called LSA group pacing allows each LSA to have an individual timer. These timers expire at different times, thus spreading out the update load. The more LSAs you have, the more group pacing will help.

Nothing, however, is free. An advantage of all LSAs expiring at once was that the router could maximize the number of LSAs batched into each update. The compromise reached by the group pacing feature is either to send one update every 30 minutes, or to send individual updates for every expiring LSA. LSAs are grouped, and the groups are expired together and reflooded. The interval between group expiration, when LSA group pacing is enabled, is 4 minutes.

To change the default value, use the timers lsa-group-pacing seconds command. Values between 10 and 1800 seconds can be set. Again, this timer value will be slightly randomized to avoid inappropriate synchronization.

Stub Networks and Host Routes

OSPF has the capability of advertising routes to single hosts (i.e., /32 prefixes with a 255.255.255.255 subnet mask). The usual purpose of such routes is to handle a host directly connected to the router.

Stub networks (see Figure 14) can have one or more routers connected to the same medium, but there can be no routing across the medium between the routers. Most commonly, there is only one router present on a stub network, or, if there are multiple routers, they all act as default gateways to hosts on the same medium.

Figure 14. Stub Network

OSPF simplifies its internal data structures by treating stub networks, even if they contain multiple hosts, as host routes. The stub network will appear normally in the routing table, but you will not find a network LSA for it in the LSDB. Not being able to find the network LSA does not mean you have a problem.

[IE-OSPF1-WP1-F04]
[2001-09-07-01]

This is a Tutorial excerpt from OSPF I: OSPF in Single Areas: Learning the Protocol by Howard Berkowitz. If you're not a Certification Zone Subscriber and you would like complete, unrestricted access to the rest of this and every other Tutorial, Study Quiz, Lab Scenario, and Practice Exam available at Certification Zone, become a Subscriber today!