Link State Routing Algorithm: Working, Steps & Examples
Overview
Think about how Google Maps finds a route. It does not ask every nearby driver to pass their own route table to the next driver. Instead, it maintains a full map of all roads, knows the cost (time or distance) of every road segment, and computes the best path for each traveler on its own copy of that map.
The link state routing algorithm does almost exactly this, but for routers. Every router in the network builds a complete, identical map of the whole network, and then each router independently runs a shortest path calculation on that map to build its own routing table. In this article, we will understand what the link state routing algorithm is, how it works phase by phase, how Dijkstra's algorithm fits in, and which real protocols use it.
What is a Link State Routing Algorithm?
Before learning about the Link State Routing Algorithm, let us briefly discuss the term Routing.
Routing is a process of establishing the routes that data packets must follow to reach the destination. In this process, a routing table is created, which contains the information regarding routes that data packets follow. Now, various routing algorithms are there which are used to decide the best optimal route that the incoming data packet must be transmitted.
The best or optimal path is the path from the source to the destination router, having the least connection cost. For example, refer to the routers shown in the image below.
If a packet needs to be transmitted from Router-1 to Router-2, then it can follow two paths.
- Directly from Router-1 to Router-2, the cost of this traveling is 6.
- It can also go from Router-1 to Router-2, via path: Router-1 --> Router-3 --> Router-2. The cost of this traveling is (2 + 3) = 5.
So, the data packet will be sent from the second path i.e. Router-1 --> Router-3 --> Router-2.
The Link State Routing Algorithm is an interior protocol used by every router to share information or knowledge about the rest of the routers on the network. The link state routing algorithm is distributed by which every router computes its routing table.
With the knowledge of the network topology, a router can make its routing table. Now, for developing the routing table, a router uses a shortest path computation algorithm like Dijkstra's algorithm along with the knowledge of the topology. The routing table created by each router is exchanged with the rest of the routers present in the network, which helps in faster and more reliable delivery of data.
A router does not send its entire routing table with the rest of the routers in the inter-network. It only sends the information of its neighbors. A router broadcasts this information and contains information about all of its directly connected routers and the connection cost.
Now, the process of transferring the information about a router's neighbors is termed flooding. A router transfers the information to all the inter-network routers except its neighbors. Every router that receives the information sends the information copies to all its neighbors. In this way, all the routers of the inter-connected network have the same copy of the information.
This information exchange only occurs when there is a change in the information. Hence, the link state routing algorithm is effective. Refer to the image below for the basic overview of the router and updation done by the link state routing algorithm.
Note: Dynamic routers use the link state routing algorithm and maintain a database of the entire topology. The database is updated once there is a change in the connection.
Important Points Related to the Link State Routing Algorithm
- The link state routing algorithm exchanges information only when there is a change in the connection.
- It requires large memory as it maintains a routing database.
- It requires the computation of the shortest path, which is an overhead for the CPU.
- The information of each router needs to be transmitted all over the network.
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreKey Building Blocks of Link State Routing
Four components work together in the link state algorithm:
- Link State Packet (LSP) / Link State Advertisement (LSA): A small packet a router creates to describe its directly connected links and their costs. In OSPF terminology, this record is called a Link State Advertisement, or LSA.
- Link State Database (LSDB): The collection of all LSPs received from every router. Once flooding completes, every router in an area holds an identical copy of this database, which together forms the full topology map.
- Shortest Path First (SPF) algorithm: The calculation run on the LSDB. In practice this is Dijkstra's algorithm, which computes the lowest cost path from the local router to every destination
- Routing table: The final output. It stores the best next hop and interface for each destination, and it is what the router uses to forward packets.
An important subtlety: the LSA is data, not a route. The routing table is the result of running the SPF algorithm over the LSDB. A link can be present in the database while still not appearing in the routing table, for example if no path to it exists or a better route from another source wins.
Link State Routing Protocols
A routing protocol is a routing algorithm that provides the best path from the source to the destination.
In the link state routing protocol, a router transmits its IP address, MAC address, and signature to its neighboring routers. Now, using the information (i.e. IP address, MAC address, and signature), the neighboring routers create a record by combining the IP address and the MAC. This information helps the router to transmit the data packet through the optimal path. It also tells a router about the various possible paths.
Let us discuss the various protocols that use the link state routing protocol.
OSPF or Open Shortest Path First is a routing protocol that uses the link state routing algorithm to exchange information (about neighboring routers, cost of the route, etc.) among the inter-network routers.
The OLSR or Optimized Link State Routing Protocol is an optimized link state routing protocol that is used in mobile ad hoc networks and wireless ad hoc networks. The OLSR sends a hello message to identify the connected neighboring routers and the connection cost. Along with the hello message, it also uses the Topology Control messages.
Phases of the Link State Routing Algorithm
The algorithm runs in two phases:
Phase 1: Reliable Flooding
In this phase, information about every router's neighbors is gathered and shared across the whole network.
Initial state: Each router learns about its directly connected neighbors. This happens through hello packets, small messages routers exchange to discover who is on the other end of each link, and to measure the cost of each connection.
Final state: Each router knows the complete network graph. This happens through flooding. When a router creates an LSP describing its links, it sends the LSP to all its neighbors (except the one it came from). Each neighbor that receives it stores a copy and forwards it onward. This way, the LSP reaches every router, and eventually every router holds the same LSDB. Flooding is reliable: in OSPF, every LSA is acknowledged, and unacknowledged ones are retransmitted. (RFC 2328)
The exchange happens only when something changes. Once the network is stable, routers do not keep broadcasting the same information. A router sends a new LSP only when a link goes up or down, a new neighbor appears, or a link cost changes.
Phase 2: Route Calculation
In this phase, every router independently runs Dijkstra's algorithm on its copy of the LSDB, with itself as the root, and computes the shortest (lowest cost) path to every other router. The result is a shortest path tree, which becomes the routing table.
Every time the LSDB changes, the router recalculates its shortest paths and updates the routing table. This is why link state protocols are known for fast convergence: they detect changes quickly and recompute routes in a consistent, loop free way.
Dijkstra's Algorithm: A Worked Example
Let us compute the shortest paths for a small network of four routers: A, B, C, and D. The links and their costs are:
- A to B: cost 2
- A to C: cost 5
- B to C: cost 1
- B to D: cost 4
- C to D: cost 2
We want the shortest paths from A to every other router.
Step 1: Initialize distances. A = 0, B = infinite, C = infinite, D = infinite.
Step 2: From A, relax its neighbors. B becomes 2, C becomes 5. So A = 0, B = 2, C = 5, D = infinite.
Step 3: Pick the closest unvisited router, B (distance 2). From B, relax its neighbors. C becomes 2 + 1 = 3, which is better than 5, so C = 3. D becomes 2 + 4 = 6, so D = 6.
Step 4: Pick the next closest, C (distance 3). From C, relax D. D becomes 3 + 2 = 5, which is better than 6, so D = 5.
Step 5: Pick D (distance 5). Done.
Final distances from A:
| Router | Shortest distance from A | Best path |
|---|---|---|
| A | 0 | A itself |
| B | 2 | A to B |
| C | 3 | A to B to C |
| D | 5 | A to B to C to D |
Notice that the direct path A to C costs 5, but the two hop path A to B to C costs only 3. Dijkstra's algorithm correctly prefers the longer hop count because it minimizes total cost, not hop count. That is exactly what routers care about: the cheapest path, not the shortest path in number of links. (Wikipedia)
Link State vs Distance Vector: Comparison Table
Both algorithm families produce routing tables, but they do it very differently.
| Feature | Link State Routing | Distance Vector Routing |
|---|---|---|
| What is shared | Only local link information (LSP/LSA) | Entire routing table with neighbors |
| Knowledge of the network | Every router knows the complete topology | Each router knows only its neighbors' information |
| Algorithm used | Dijkstra's algorithm (SPF) | Bellman-Ford algorithm |
| Convergence | Fast | Slower, prone to the count to infinity problem |
| Memory and CPU usage | Higher (stores full topology, computes SPF) | Lower |
| Scalability | Good for large networks, with areas | Limited in large networks |
| Example protocols | OSPF, IS-IS | RIP (Routing Information Protocol) |
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreIn general, link state protocols scale better to large networks and converge faster, at the cost of more memory and CPU on each router. Distance vector protocols are simpler and lighter, but they converge more slowly and can suffer from the classic count to infinity problem when links fail. For a detailed look at the other side, read the Distance Vector Routing Algorithm article.
Real Protocols That Use Link State Routing
The link state algorithm is not just a textbook idea. It powers routing in real networks around the world.
OSPF (Open Shortest Path First): The most widely used link state routing protocol in large enterprise networks. OSPF gathers link state information, builds a topology map, and computes a shortest path tree for each route using Dijkstra's algorithm. It converges on a new loop free structure within seconds after a link failure, and it supports equal cost multipath so traffic can be balanced across multiple equally good routes. OSPF version 2 is defined in RFC 2328, and the IPv6 version, OSPFv3, in RFC 5340.
OSPF also introduces areas to keep the topology manageable. All areas must connect to the backbone area, area 0. Routers inside one area share a full link state database for that area, while area border routers summarize routes between areas. This hierarchy is what lets OSPF scale to thousands of routers. (RFC 2328)
IS-IS (Intermediate System to Intermediate System): Another link state protocol, and the one more commonly found in large service provider networks. It predates OSPF and works directly at layer 2, which makes it easier to extend for new network layer protocols.
OLSR (Optimized Link State Routing): A link state protocol optimized for mobile ad hoc networks and wireless ad hoc networks, where nodes move and links appear and disappear frequently. It uses hello messages to discover neighbors and topology control messages to spread link information.
Where Link State Fits in the Bigger Picture
Link state protocols like OSPF are interior gateway protocols (IGPs): they route within a single organization or autonomous system. Routing between autonomous systems on the internet uses a different protocol, BGP. So in a real network, OSPF often handles routing inside a campus or data center, while BGP handles routing between networks. Both run at the network layer of the OSI model.
Advantages of the Link State Routing Algorithm
- Fast convergence. When a link fails or appears, routers learn about it quickly and recompute routes consistently, avoiding loops and long outages. (Wikipedia)
- Complete topology knowledge. Every router has a full map of the network, so it can make globally good decisions rather than guessing from neighbor rumors.
- No count to infinity problem. Unlike distance vector routing, link state routing does not suffer from slow, looping convergence on failure.
- Scalable. With areas (as in OSPF) and hierarchical design, link state routing scales to very large networks. (RFC 2328)
- Efficient updates. Routers exchange information only when the topology changes, not periodic full table dumps, which saves bandwidth.
- Flexible metrics. Costs can represent distance, throughput, latency, or reliability, giving administrators control over path selection.
- Equal cost multipath. Multiple best paths can be used simultaneously for load balancing.
Turn Learning into Career Growth
Disadvantages of the Link State Routing Algorithm
- Higher memory usage. Every router must store the complete link state database for its area.
- Higher CPU usage. Running Dijkstra's algorithm on every topology change costs processing power, especially on large networks.
- More complex to configure and tune. Concepts like areas, costs, and designated routers require more expertise than a simple distance vector setup.
- Flooding overhead during instability. If links flap (go up and down repeatedly), the resulting LSA floods and SPF recalculations can temporarily consume significant bandwidth and CPU.
- Initial sync cost. When two routers first become neighbors, they must synchronize their entire databases, which takes time and bandwidth.
Conclusion
The link state routing algorithm lets every router build a complete, identical map of the network and then compute its own best paths using Dijkstra's algorithm.
- It works in two phases: reliable flooding, where routers share their local link information, and route calculation, where each router computes shortest paths over the shared database.
- It shares only local connectivity, not full routing tables, which makes updates efficient and event driven.
- It converges fast and avoids the count to infinity problem, at the cost of higher memory and CPU.
- Real protocols like OSPF and IS-IS run the internet's largest networks on exactly this idea.
Once you understand the link state algorithm, the behavior of OSPF in real networks stops being magic: it is just a room full of routers agreeing on one map, each computing its own fastest route. For the complementary approach, see the Distance Vector Routing Algorithm, and to see how routing fits into the wider network stack, visit the Computer Network Tutorial.
FAQs
1. What is the link state routing algorithm?
It is a routing algorithm in which every router builds a complete map of the network topology by flooding information about its directly connected links, then independently computes the lowest cost path to every destination using Dijkstra's algorithm.
2. What are the two phases of the link state routing algorithm?
The two phases are reliable flooding, where routers discover neighbors and spread link state packets so everyone ends up with the same database, and route calculation, where each router runs Dijkstra's algorithm on that database to build its routing table.
3. What is the difference between link state and distance vector routing?
Link state routers share only local link information and each builds a complete topology map, then computes paths with Dijkstra's algorithm. Distance vector routers share their full routing tables with neighbors and compute paths with the Bellman-Ford algorithm. Link state converges faster and scales better, but uses more memory and CPU.
4. Which algorithm is used in link state routing?
Dijkstra's algorithm, also called the Shortest Path First (SPF) algorithm. It finds the lowest total cost path from the local router to every other router in the network.
5. What is a link state advertisement (LSA)?
An LSA is a record a router creates to describe its directly connected links and their costs. The set of all LSAs forms the link state database. In OSPF, LSAs are flooded reliably and acknowledged by neighbors.
6. What is flooding in link state routing?
Flooding is the process of forwarding a router's link state information to the entire network. Each router sends the LSP to all its neighbors except the one it received it from, until every router has a copy. This ensures all routers share an identical topology database.
7. Which protocols use the link state algorithm?
The main ones are OSPF (widely used in enterprise networks) and IS-IS (common in service provider networks). OLSR is a link state protocol designed for mobile ad hoc networks
8. Why is link state routing faster to converge than distance vector?
Because every router has the complete topology map, a change is flooded immediately and each router recomputes a consistent, loop free shortest path tree locally. Distance vector protocols rely on routers gradually informing each other, which can take many rounds and can loop (count to infinity).
9. What are the disadvantages of link state routing?
It needs more memory to store the full link state database, more CPU to run SPF after every change, and more configuration expertise. Flooding and recalculation can also spike during unstable periods when links flap.
