SPF Tree

Link state is the most used routing protocol; therefore, the link state operation is essential for networking students. In this article, we are discussing the link state operation. Link State Routing protocols reduce broadcast traffic as they do not send periodic updates. It also does not send entire routing tables with each broadcast.

Link state only exchanges entire routing tables during initialization. After initialization, routing updates are only multicast when a change occurs. It also sends only the change in the update, not the entire routing table. The changes in the topology are flooded immediately and computed in parallel. If no changes occur, they do not generate any periodic updates.

The event-triggered updates improve network convergence time because on the event required, the router sends an update message right away. An event such as a new link installation or an existing link failing or removed triggers the link-state update when link-state changes occur.

The link-state protocols support VLSM, which enables routers to recognize and forward traffic to subnets within a network. The link-state updates also include the subnet mask, which allows a router to identify the exact subnet to forward traffic.

All Link State protocols build and maintain three types of tables called databases: The Adjacency database, the Link State database, and the Forwarding database. To maintain routing information, OSPF routers do the following generic link-state operation to achieve a state of convergence:

Establish Neighbor Adjacencies

All OSPF-enabled routers must establish Neighbor Adjacencies and relationships with one another. The OSPF-enabled routers must recognize each other on the network before sharing information. Adjacent routers establish this relationship using the exchange of hello packets.

OSPF enables routers to send hello packets to all OSPF enabled interfaces, as shown in the figure below. The routers build the adjacency table using these hello packets. Within hello messages packets, routers announce themselves and also identify directly connected links and the state of these links.

Exchange of LSAs

Once the adjacency relationship is completed, the routers exchange link-state advertisements (LSAs). LSAs contain the router’s state and the cost of each directly connected link. Each router floods its LSA to adjacent neighbors.

The adjacent neighbours which receive the LSA, immediately flood the LSA to other directly connected neighbours without any changes, the process is continued until all routers in the area received all routers LSA. The figure below illustrates the exchange of LSAs

Building a Link state database (LSDB)

After exchanging LSAs, each router builds a topology table or link-state database (LSDB) and places itself in the root position. This database holds all information about the network’s topology.

SPF Tree

After building a Link State database on all the routers, the routing protocol executes the SPF Algorithm (Dijkstra’s algorithm). The SPF algorithm creates the SPF tree for each router based on LSDB. The SPF tree includes each possible path to the destination with its cost. The figure below illustrates the SPF tree.

Forwarding Database

From the SPF tree, the best paths are inserted into the routing table, also known as the forwarding database, and the router makes routing decisions based on entries in the routing table.