Link state routing (OSPF) in Computer Networks - Step-by-Step Execution

Concept Flow - Link state routing (OSPF)

Router starts

↓

Discover neighbors

↓

Exchange Link State Advertisements (LSAs)

↓

Build Link State Database

↓

Run Shortest Path First (SPF) Algorithm

↓

Calculate best paths

↓

Update routing table

↓

Forward packets using updated routes

↓

Repeat periodically or on change

OSPF routers discover neighbors, share link states, build a network map, calculate shortest paths, and update routing tables continuously.

Execution Sample

Computer Networks

Router A:
1. Discover neighbors
2. Exchange LSAs
3. Build database
4. Run SPF
5. Update routes

Shows the step-by-step process a router follows in OSPF to find best paths.

Analysis Table

Step	Action	Details	Result
1	Discover neighbors	Router sends hello packets	Neighbors found: Router B, Router C
2	Exchange LSAs	Routers share link info	Link State Database updated with all links
3	Build Link State Database	Collect all LSAs	Complete network topology map
4	Run SPF Algorithm	Calculate shortest paths	Best paths to all routers determined
5	Update routing table	Install best paths	Routing table ready for forwarding
6	Forward packets	Use routing table	Packets sent via shortest paths
7	Repeat	On topology change or timer	Routing tables stay current

💡 Process repeats continuously to adapt to network changes

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Neighbors	None	Router B, Router C	Router B, Router C	Router B, Router C	Router B, Router C	Router B, Router C	Router B, Router C
Link State Database	Empty	Empty	Contains LSAs from all routers	Complete topology map	Complete topology map	Complete topology map	Complete topology map
Routing Table	Empty	Empty	Empty	Empty	Best paths installed	Best paths installed	Best paths installed

Key Insights - 3 Insights

Why does the router send hello packets first?

Hello packets help the router discover neighbors before exchanging detailed link information, as shown in step 1 of the execution_table.

What is the purpose of the Link State Database?

It stores all LSAs from routers to build a complete network map, enabling the SPF algorithm to find shortest paths (steps 2 and 3).

Why does OSPF repeat the process periodically?

To detect and adapt to network changes, ensuring routing tables stay accurate, as explained in step 7.

Visual Quiz - 3 Questions

Look at the execution_table, after which step does the router have a complete network map?

A After Step 3

B After Step 2

C After Step 4

D After Step 5

💡 Hint

Check the 'Result' column for Step 3 in the execution_table.

According to variable_tracker, what is the state of the Routing Table after Step 4?

A Best paths installed

B Empty

C Partially filled

D Unknown

💡 Hint

Look at the Routing Table row under 'After Step 4' in variable_tracker.

If a new router joins the network, which step will trigger the routing table update?

A Step 1 - Discover neighbors

B Step 3 - Build Link State Database

C Step 5 - Update routing table

D Step 6 - Forward packets

💡 Hint

Refer to the execution_table where routing table updates happen after SPF calculation.

Concept Snapshot

Link State Routing (OSPF):
- Routers discover neighbors via hello packets.
- Exchange Link State Advertisements (LSAs) to share network info.
- Build a Link State Database representing full topology.
- Run Shortest Path First (SPF) algorithm to find best routes.
- Update routing tables and forward packets accordingly.
- Repeat process to adapt to network changes.

Full Transcript

Link state routing in OSPF works by routers first discovering their neighbors using hello packets. Then, they exchange Link State Advertisements (LSAs) to share information about their connected links. All LSAs are collected into a Link State Database, which represents the entire network topology. Using this database, routers run the Shortest Path First (SPF) algorithm to calculate the best paths to all destinations. These best paths are installed into the routing table, which is then used to forward packets efficiently. This process repeats periodically or when network changes occur to keep routing information up to date.