Link-State Operation

Link-state is most used routing protocol, therfore 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 exchange entire routing tables during initialization. After initialization routing updates are only multicast when a change has occurred. It is also send 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 link-state update. When link-state changes occurs, the

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 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 establish Neighbor Adjacencies and relationship with one another. The OSPF enabled routers must recognize each other on the network before they can share information with each others. Adjacent routers make this relationship using the exchange of hello packet. The OSPF enable routers sends 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.

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 flood their LSA to adjacent neighbors. The adjacent neighbors which receive the LSA, immediately flood the LSA to other directly connected neighbors without any changes, the process is continoues 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 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 execute the SPF Algorithm (Dijikstras algorithm) The SPF algorithm creates the SPF tree for each router on the bases of LSDB. The SPF tree included the 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 forwarding database and the router made routing decisions on the bases of entries in the routing table.