Link-State Operation

Link-state is most used routing protocol, therefore the link-state operation is very important for the networking student. In this article, we are discussing the link-state operation. Link State Routing protocols reduce broadcast traffic as they do not send any periodic updates. It also not sends 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 has occurred. It is also sent 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 update.

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

The link-state protocols support VLSM, which enable 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 the table called databases: The Adjacency database, Link State database and Forwarding database. To maintain routing information, OSPF routers done the following generic link-state operation to achieve a state of convergence:

Establish Neighbor Adjacencies

All OSPF enabled routers to establish Neighbor Adjacencies and relationship with one another. The OSPF enabled routers must recognize each other on the network before they can share information. Adjacent routers make this relationship using the exchange of hello packet. The OSPF enables routers to send hello packet out to all OSPF enabled interfaces as shown in the figure below. The routers build the adjacency table using these hello packets.  Within hello messages packet routers announce themselves and also identify directly connected links and the state of these links.

Link-State Operation 3

Exchange of LSAs

Once the adjacency relationship is completed, the routers exchange link-state advertisement (LSAs). LSAs contain the state of the router and cost of each directly connected link. Each router floods their LSA to adjacent neighbours. 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

Link-State Operation

Building a Link-state database (LSDB)

After the exchange of LSAs each router builds a topology table or link-state database (LSDB) placing themselves in the root position. This database holds all the information about the topology of the network.

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 on the bases of LSDB. The SPF tree included each possible path to the destination with its cost. The figure below illustrates the SPF tree.

Link-State Operation 4

Forwarding Database

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