What is Link State Routing Protocol?


Before getting into the details, let’s understand how packet routing works in computer networks.  The primary goal of a computer network is to enable computing devices to communicate with each other.  The devices may be connected directly or may be via one or more intermediate devices such as routers.

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 IP address, sends an HTPP request in an IP packet, and displays the response on explorer.

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

 

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

From your internet router, there is only one link that connects to ISP.  But on other 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 computer network better to say IP routing protocol.  Each node in the network maintains a routing table. When it receives a packet a lookup is made in the routing table and the outgoing link 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 take any of the lines, it says what IP address (subnet/default) needs to forward from which ethernet interface.  All are static. But what if you have two links towards the same destination and the chosen link is down.  There we need to use a Dynamic routing protocol e.g Link State Routing Protocol, where the neighbor nodes inform each other about the link status. That results to have updated routing tables.

What is Link State Routing Protocol?

Belong to the family of Dynamic routing protocols. Mainly the network routers implement it.  This is based on open standards, to each routing device supports 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

Route Cost Via
Route to R3 11 R4
Route to R3 13 R2
Route to R4 4 NA
Route to R2 8 NA

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.