What is Link State Routing Protocol?


Before delving into the protocol’s details, it’s necessary to understand how packets are routed through a computer network. When it comes to computer networks, their primary objective is to enable communication among computing devices. The devices may be connected directly or via one or more intermediary devices, such as routers or switches.

What is link state routing
What is a link-state routing?

For example, when you browse a website on the internet e.g www.cspsprotocol.com.  Your laptop first does a DNS lookup to get the hosting server IP address. After getting the IP, sends an HTTP web page request in an IP packet, and displays the response.

At each hop from your laptop to the server, IP packets are routed towards the destination on an outgoing link.

From your in-house internet router, there is only one link that connects to ISP.  But on further intermediate routers, there can be one or more next hops towards the destination.

A Routing protocol decides what link to choose for the next hop.  Link State Routing Protocol is one of the routing protocols.

What is Routing Protocol?

In a computer network,  each node maintains a routing table. When it receives a packet,  a lookup is made in the routing table and the outgoing link for the next hop is selected.

You can check a routing table on Linux with the command ip route.

# ip route
default via 192.168.1.1 dev enp0s3
default via 192.168.1.1 dev enp0s3 proto dhcp metric 100
default via 192.168.1.1 dev enp0s9 proto static metric 102
169.254.0.0/16 dev enp0s3 scope link metric 1002
192.168.1.0/24 dev enp0s3 proto kernel scope link src 192.168.1.181 metric 100
192.168.1.0/24 dev enp0s3 proto kernel scope link src 192.168.1.6 metric 100
192.168.1.0/24 dev enp0s9 proto kernel scope link src 192.168.1.182 metric 102
192.168.56.0/24 dev enp0s8 proto kernel scope link src 192.168.56.102 metric 101

If you look at any of the lines, it says what IP address (subnet/default) needs to be forward via which ethernet interface.  All IP routes are static in the example. But what if you have multiple links towards the same destination and the chosen link is down.

In this case, we need to use a dynamic routing protocol such as Link State Routing Protocol.  In this protocol, the neighbor nodes inform each other about the link status. That results to have updated routing tables after a new update.

What is Link State Routing Protocol?

It belongs to the family of Dynamic routing protocols. Mainly the network routers implement it.  This is based on open standards so that each routing device can support it. Each router in the network exchanges links state messages to the neighboring routers either on startup/attach or whenever network topology changes.

With the information received, the router updates/creates a link-state database and applies the Dijkstra algorithm, shortest path first, and updates the routing table.

Link State Routing Protocol Network
Link State Routing Protocol Network with link cost and routers

Link States Packets – Example flow of message exchanges among routers.

R3–>R2 : [ R2-5, R4-7],  R3–>R4 : [ R2-5, R4-7], R4–>R3 : [ R1-4, R3-7], R2–>R3 : [ R1-8, R3-5]
R2–>R1 : [ R1-8, R3-5], R4–>R1 : [ R1-4, R3-7], R4–>R1 : [ R1-4, R3-7], R1–>R2 : [ R1-4, R3-7]
R1–>R4 : [ R8-4, R4-4] 

After updating the database on R1 and Applying the Dijkstra algorithm the routing tables will be following

RouteCostVia
Route to R311R4
Route to R313R2
Route to R44NA
Route to R28NA

We can see that if R1 receives a packet to the server, it will send it via R4.  The above metrics will again change if the network updates the link status of cost.