Adjacencies formula

If the router interface is configured with OSPF, the router must determine if another OSPF neighbor is on the link. To do this, the router forwards a Hello packet containing its router ID to all OSPF-enabled interfaces as multicast. The Open Shortest Path First process uses the router ID to recognize every router individually in the OSPF area.

A router ID is an IP address assigned to identify a specific router among OSPF links. When a neighboring router configured with Open Shortest Path First receives a Hello packet containing a router ID that is not listed with the receiving router, it attempts to establish an adjacency with the initiating router.

For example, as shown in figure-1 above, when OSPF is enabled on Rouer1, the enabled Fast Ethernet 0/1 interface transitions from the Downstate to the Init state and starts sending Hello packets to all OSPF-enabled interfaces to discover OSPF neighbors with whom to develop adjacencies.

The Router2 receives the Hello packet from Router1 and adds the Router1 ID to its neighbor list. Then, Router2 sends a Hello packet to Router1. The packet contains the Router2 Router ID, including the Router1 ID in its neighbors’ list on the same interface.

When Router1 receives the Hello packet and adds the Router2 Router ID to its OSPF neighbors list, Router1 also notices its Router ID in the Hello packet’s list of neighbors. When Router1 receives a Hello packet with its Router ID listed in the neighbor’s list, it transitions from the Init state to the Two-Way state.

The action in a Two-Way state depends on the type of interconnection between the adjacent routers. If the two adjacent neighbors are connected over a point-to-point link, they instantly transition from the Two-Way state to the database synchronization stage. A DR and BDR must be elected if the routers are interconnected over a general Ethernet network.

Note: Hello packets are repeatedly exchanged to maintain router information.

DR and BDR Election

A DR and BDR election occurs because Router1 and Router2 are connected over an Ethernet network. The figure below illustrates the election between Router1 and Router2.

Router2 becomes the DR because of the highest router ID (192.168.10.2), and Router1 becomes the BDR because of the second-highest router ID (192.168.10.1). This process only takes place on multi-access networks such as Ethernet LANs.

DR and BDR election is necessary because multi-access networks can create two challenges for OSPF about the flooding of LSAs:

• Creation of multiple adjacencies – The routers on Ethernet networks interconnect to many Open Shortest Path First routers over a common link. So, creating adjacencies with every router is not important and wanted. The interconnection to many routers leads to an unnecessary number of LSAs exchanged between routers on the same network.
• Extensive flooding of LSAs – Link-state routers flood their LSAs when OSPF is initialized, or when there is a modification in the topology. This flooding can become very excessive.

Adjacencies formula

The formula for understanding the problem with multiple adjacencies is following:

n(n – 1) / 2

n is the number of the router in the OSPF topology. For example, if there are 4 routers in the topology, as shown in Figure 3, and all routers are attached to the same multi-access network, there are n (n– 1) / 2 adjacencies in the topology. Without a mechanism to reduce the number of adjacencies, collectively, these routers would form 6 adjacencies:

4 (4 – 1) / 2 = 6

This does not seem like too much, but as routers are added to the network, the number of adjacencies increases dramatically, as shown in the calculation below.

10 routers = 10(10-1) = 45 adjacencies

20 routers = 20(20-1) = 190 Adjacencies

50 routers = 50(50-1) = 1225 Adjacencies

100 routers = 100(100-1) = 4950 Adjacencies

To understand the problem of extensive flooding of LSAs, if DR and BDR are not available in the network When changing occurs in the network or during initializing. Each router sends LSA and also required acknowledgements are sent for every LSA received.

If every router in a multi-access network had to flood and acknowledge all received LSAs to all other routers on that same multi-access network, the network traffic would become quite confusing. Suppose there are 50 routers on the network without DR and BDR. Each router will send 1225 LSAs and receive 1225 Acknowledgments, which is very extensive.

The solution to managing the number of adjacencies and the flooding of LSAs on a multi-access network is the DR and BDR. OSPF elects a DR on multi-access networks as the collection and distribution point for LSAs sent and received. A BDR is also elected for the same purpose in case the DR fails. All other routers turn into brothers. A DROTHER is a router that is not a DR or the BDR.

Database Synchronization Stage

After the Two-Way state, routers transit to database synchronization stage. As the Hello packet used to launch neighbour adjacencies, the other four types of Open Shortest Path First packets has used in the process of exchanging and synchronizing LSDBs.

In the database synchronization stage, the first state is ExStart state, in this state a master and slave relationship created between each router and its adjacent DR and BDR. The router with the higher router ID acts as the master for the Exchange state. In Figure-4 below, Router2 becomes the master.

In the Exchange state, the master and slave routers exchange one or more DBD packets. A DBD packet also includes information about the LSA entry header in the router’s LSDB.

The entries can be about a network or a link, and each LSA entry header also includes information about the type of link state, the advertising router address, the cost of the link, and the sequence number. The sequence number determines the newness of the received link state information.

In Figure-5, Router2 sends a DBD packet to Router1, and Router1 receives the DBD packet and does the following actions:

• It acknowledges the receipt of the DBD packet using the LSAck packet.
• Sends DBD packets to Router2.
• Router2 acknowledges Router1.

Router1 compares the received information with the information it has in its LSDB. If the DBD packet has a more current link-state entry, the router transitions to the Loading state. For example, in Figure 6, Router1 sends an LSR about network 192.168.20.0 to Router2 and Router2 reply with the complete information about 192.168.20.0 in an LSU packet.

On reception of LSU, Router1 sends an LSAck. Router1 then adds the new link-state entries into its LSDB. When all LSRs are fulfilled for a particular router, the adjacent routers are considered synchronized and in a full state.

If the neighboring routers continue receiving Hello packets, the network in the transmitted LSAs will stay in the topology database. After the topological databases get synchronized, Link-state updates are sent only to neighbors when:

• A change is apparent
• Every 30 minutes