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 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, it sends an HTTP web page request encapsulated in an IP packet and displays the response.

IP packets are routed toward the destination on an outgoing link from your laptop to the server at each hop.

From your in-house internet router, only one link connects to ISP. But on other intermediate routers, there can be one or more next hops toward 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 dev enp0s3
default via dev enp0s3 proto dhcp metric 100
default via dev enp0s9 proto static metric 102 dev enp0s3 scope link metric 1002 dev enp0s3 proto kernel scope link src metric 100 dev enp0s3 proto kernel scope link src metric 100 dev enp0s9 proto kernel scope link src metric 102 dev enp0s8 proto kernel scope link src metric 101

If you look at any of the lines, it says what IP address (subnet/default) needs to be forwarded via which ethernet interface. The IP routes are static in the above example. But what if a node has multiple links to reach a destination, and the link chosen is down?

In this case, we must use a dynamic routing protocol such as Link State Routing Protocol. In this, the neighbor nodes inform each other about the link status from them. 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, 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 look like the following.

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

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.