OSPF, Part 3

Continuing on with our discussion of LSDB synchronization, we’ve seen that in the case of point-to-point links, the two OSPF neighbors always proceed to “Full” state. On multi-access media such as an Ethernet LAN or a Frame Relay WAN, however, things are more complicated. Let’s look at an Ethernet LAN as an example.

A typical topology is that several routers are connected by a switch. Assuming that the switch ports connected to the routers lie within a common VLAN, the routers are within a common broadcast domain (an IP subnet). If every router on the subnet directly compares its LSDB to that of each of its neighbors on that subnet, the number of comparisons is governed by the “full mesh” equation:

  • c = n * (n – 1) / 2

Where:

  • c = The number of comparisons
  • n = The number of routers on the subnet

If we crank through the numbers, we obtain:

  • n = 2: c = 1 (two routers on a point-to-point link)
  • n = 3: c = 3
  • n = 4: c = 6
  • n = 5; c = 10
  • n = 6: c = 15
  • n = 10: c = 45
  • n = 20: c = 190

If there are two routers on the subnet, only one comparison is required to ensure LSDB synchronization. In the case of five routers on the subnet (n = 5), ten comparisons are required. If the number of routers on the subnet doubles to ten (n = 10), the number of comparisons increases to 45. Doubling it again (n = 20) results in 190 comparisons. Thus, as the number of routers doubles, the number of comparisons approximately quadruples, which is what computer scientists would call “O(n2)” (order n-squared), an exponential increase.

Also, once “Full” state is achieved, maintaining it will require that any router that detects a change to its LSDB will send an update to each of the other routers on the subnet, each of which will inform every other router on the subnet, etc. When many routers are involved, the large number of LSUs and LSAcks will consume excessive link bandwidth and router CPU cycles.

To solve this scalability problem, once the neighbors have reached “Two-Way”, multi-access media can elect a Designated Router (DR). The DR’s job is to maintain synchronization of the LSDBs for all routers within a subnet.

To elect the DR, the routers compare their DR election priorities, which are contained within the Hello packets. The DR priority is set per interface (or subinterface), and ranges from zero to 255, with a default value of 1. High priority wins, and the tie-breaker is highest OSPF router ID. The first runner-up is elected Backup DR (BDR). If the DR ever becomes unavailable, the BDR is promoted to DR, and a new BDR is elected.

Once the DR and BDR for the subnet have been elected, all other routers in the subnet will synchronize their LSDBs (go to “Full” state) with the DR. This has the effect of synchronizing all LSDBs on the subnet. The equation controlling the number of comparison is now:

  • c = n – 1

Where:

  • c = The number of comparisons
  • n = The number of routers on the subnet

The number of comparisons now increases linearly with the number of routers on the subnet, and if we crank through the numbers we obtain:

  • n = 2: c = 1 (two routers on a point-to-point link)
  • n = 3: c = 2
  • n = 4: c = 3
  • n = 5; c = 4
  • n = 6: c = 5
  • n = 10: c = 9
  • n = 20: c = 19

Key point: Because all routers on the subnet directly synchronize with the DR, they become synchronized with each other without having to directly compare their LSDBs.

Whenever a change to the topology occurs, the router detecting the change will inform the DR, which will inform the other routers on the subnet. In this manner, LSDB synchronization is maintained between the routers within the subnet. Those routers will then flood the LSA to other subnets to which they are attached.

Next time, we’ll examine multi-area OSPF, a technique for enhancing scalability.

Author: Al Friebe

In this article

Join the Conversation