Link-State Routing Algorithm
Link-State Routing Algorithm
Link-State (LS) Routing is a routing algorithm used to find the least-cost path from a router to all other routers in a network.
The main idea is:
Every router builds a complete map of the network and independently calculates the shortest paths.
This is different from Distance Vector Routing, where routers learn information mainly from their immediate neighbors.
1. What does “Link State” mean?
A network can be represented as a graph:
- Routers → Nodes
- Networks/links between routers → Edges
- Cost of a link → Weight of an edge
The state of a link refers mainly to information such as:
- Which router is connected to which neighboring router
- The cost of that connection
For example:
A -------- B Cost = 2
The link state information can be represented as:
Router A → Router B, Cost = 2
A lower-cost link is generally preferred.
2. Main Idea of Link-State Routing
Link-state routing works in three major stages:
Stage 1: Discover neighbors and link costs
Each router finds its directly connected neighbors and determines the cost of each link.
Stage 2: Build the Link-State Database (LSDB)
Each router distributes its link information throughout the network using flooding.
As a result:
Every router obtains the same complete map of the network.
Stage 3: Run Dijkstra's Algorithm
Each router uses the complete network map and runs Dijkstra's algorithm to create a least-cost tree.
This tree is then used to create the router's forwarding table.
3. Link-State Database (LSDB)
The Link-State Database (LSDB) contains information about the state of all links in the network.
For example, consider this network:
B / \ 2 4 / \ A-------E \ / 3 5 \ / C
The LSDB contains information about all connections and their costs.
A router does not know only its own neighbors. After exchanging information, it learns about the entire network topology.
For example:
| Router | Neighbor | Cost |
|---|---|---|
| A | B | 2 |
| A | C | 3 |
| B | E | 4 |
| C | E | 5 |
Every router eventually maintains a copy of this information.
4. How is the LSDB Created?
The LSDB is created using a process called flooding.
Step 1: Each router learns about its immediate neighbors
Suppose Router A is connected to:
- Router B with cost 2
- Router C with cost 3
Router A creates information such as:
Router A: B → Cost 2 C → Cost 3
This information is called a Link-State Packet (LSP).
Step 2: The router sends its LSP to neighbors
Router A sends its LSP to all directly connected routers.
Similarly:
- Router B sends information about its neighbors.
- Router C sends information about its neighbors.
- Every other router does the same.
Step 3: Flooding spreads the information
When a router receives an LSP:
- It checks whether it already has that information.
- If the received information is new, it stores it.
- It forwards a copy to its other neighbors.
- If the information is old, it discards it.
A sequence number is used to determine whether an LSP is new or old.
This process is called flooding because the information spreads throughout the entire network.
Important Comparison
Distance Vector Routing
Each router tells its neighbors what it knows about the whole network.
Link-State Routing
Each router tells the whole network what it knows about its immediate neighbors.
This is one of the most important differences between the two algorithms.
5. Formation of the Least-Cost Tree
After every router has the complete LSDB, each router independently calculates the least-cost paths.
This is done using Dijkstra's Algorithm.
Suppose Router A is calculating the best paths to all other routers.
Initially:
Tree = {A}
Router A then finds the closest router and adds it to the tree.
Then it updates the costs of reaching the remaining routers.
This process continues until all routers are included.
6. Dijkstra's Algorithm – Basic Steps
The algorithm can be understood using three simple steps.
Step 1: Choose the router itself as the root
For example, Router A starts with:
Tree = {A}
The cost from A to itself is:
Cost(A) = 0
The initial costs to neighboring routers are obtained from the LSDB.
Step 2: Select the closest router
Among all routers not yet included in the tree:
Select the router with the smallest cost from the root.
Add that router to the tree.
Step 3: Update the costs
After adding a router, check whether using that router provides a cheaper path to other routers.
If a cheaper path is found:
Update the cost and the path.
Repeat the process until all routers are included in the tree.
7. Simple Example
Consider the following network:
2 A ------- B | | 5| |3 | | C ------- D 1
Let Router A calculate the least-cost paths.
Initial information
From A:
- A → B = 2
- A → C = 5
So initially:
| Router | Cost from A |
|---|---|
| A | 0 |
| B | 2 |
| C | 5 |
| D | ∞ |
Iteration 1: Select B
The closest router is B, with cost 2.
Tree = {A, B}
From B, Router D can be reached with cost:
A → B → D = 2 + 3 = 5
So:
| Router | Best Cost |
|---|---|
| A | 0 |
| B | 2 |
| C | 5 |
| D | 5 |
Iteration 2: Select C or D
Both have a cost of 5.
Suppose we select C.
Tree = {A, B, C}
From C:
A → C → D = 5 + 1 = 6
But D already has a path with cost 5 through B.
Therefore, the cost of D remains 5.
Final Least-Cost Paths from A
| Destination | Least-Cost Path | Cost |
|---|---|---|
| B | A → B | 2 |
| C | A → C | 5 |
| D | A → B → D | 5 |
The resulting least-cost tree is:
A / \ B C | D
Learn Dijikstra's Algorithm - refer blog
8. Creating the Forwarding Table
After creating the least-cost tree, Router A creates a forwarding table.
For example:
| Destination | Best Path | Next Hop |
|---|---|---|
| B | A → B | B |
| C | A → C | C |
| D | A → B → D | B |
The next hop is especially important because the router only needs to know:
Which neighboring router should receive the packet next?
It does not need to make the complete decision again for every hop.
9. Overall Working of Link-State Routing
The complete process can be summarized as:
1. Discover immediate neighbors ↓ 2. Determine link costs ↓ 3. Create Link-State Packets (LSPs) ↓ 4. Flood LSPs throughout the network ↓ 5. Build the Link-State Database (LSDB) ↓ 6. Every router gets a complete network map ↓ 7. Run Dijkstra's Algorithm ↓ 8. Create Least-Cost Tree ↓ 9. Create Forwarding Table ↓ 10. Forward packets using the best path
Link-State vs Distance Vector Routing
| Feature | Distance Vector | Link State |
|---|---|---|
| Information shared | Distance to destinations | Information about neighboring links |
| Network knowledge | Partial knowledge | Complete network map |
| Information exchange | With neighbors | Flooded throughout the network |
| Algorithm | Bellman-Ford concept | Dijkstra's algorithm |
| Routing calculation | Based on neighbors' vectors | Based on complete LSDB |
| Convergence | Can be slower | Generally faster |
| Complexity | Simpler | More complex |
Summary
- Link-State Routing allows every router to build a complete map of the network.
- Each router creates a Link-State Packet (LSP) containing information about its neighbors and link costs.
- LSPs are distributed using flooding.
- Every router builds the same Link-State Database (LSDB).
- Each router independently runs Dijkstra's Algorithm.
- The result is a least-cost tree.
- The least-cost tree is used to create the forwarding table.
- Each packet is forwarded through the best next hop toward its destination.
Link-state routing works by allowing every router to learn the complete network topology and independently calculate the least-cost paths using Dijkstra's algorithm.
Comments
Post a Comment