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.

Practice

1. What is the main purpose of link state routing in OSPF?

easy

A. To encrypt data for secure transmission

B. To broadcast data packets to all devices in the network

C. To share detailed information about network connections to build a complete map

D. To assign IP addresses to devices automatically

Solution

1. Step 1: Understand link state routing basics

   Link state routing shares detailed information about each router's connections to build a full network map.

2. Step 2: Identify OSPF's role

   OSPF uses this map to find the shortest and best paths for data transmission.

3. Final Answer:

   To share detailed information about network connections to build a complete map -> Option C

4. Quick Check:

   Link state routing = detailed network map [OK]

Hint: Link state routing builds a full network map [OK]

Common Mistakes:

• Confusing link state routing with broadcasting
• Thinking OSPF assigns IP addresses
• Mixing routing with encryption functions

2. Which of the following is the correct way OSPF routers share their link state information?

easy

A. By using static routing tables updated manually

B. By broadcasting their IP addresses every 5 seconds

C. By encrypting data packets with SSL

D. By sending Link State Advertisements (LSAs) to all routers in the area

Solution

1. Step 1: Identify OSPF communication method

   OSPF routers share link state info using Link State Advertisements (LSAs) to all routers in the same area.

2. Step 2: Eliminate incorrect options

   Broadcasting IP addresses or using static tables are not how OSPF shares link states; encryption is unrelated here.

3. Final Answer:

   By sending Link State Advertisements (LSAs) to all routers in the area -> Option D

4. Quick Check:

   OSPF shares info via LSAs [OK]

Hint: OSPF uses LSAs to share link states [OK]

Common Mistakes:

• Confusing LSAs with IP broadcasts
• Thinking OSPF uses static routing
• Mixing routing info sharing with encryption

3. Consider a network running OSPF where Router A has three links with costs 10, 20, and 5. Which link will OSPF prefer to send data through?

medium

A. The link with cost 5

B. The link with cost 10

C. The link with cost 20

D. All links equally

Solution

1. Step 1: Understand OSPF cost metric

   OSPF prefers the path with the lowest cost to send data.

2. Step 2: Compare link costs

   Among costs 10, 20, and 5, the lowest is 5, so OSPF will choose that link.

3. Final Answer:

   The link with cost 5 -> Option A

4. Quick Check:

   Lowest cost link = chosen path [OK]

Hint: OSPF picks the lowest cost path [OK]

Common Mistakes:

• Choosing the highest cost link
• Assuming equal load on all links
• Ignoring cost metric in path selection

4. A network administrator notices that OSPF is not updating routes after a link failure. What is the most likely cause?

medium

A. The router has too many static routes configured

B. The router is not sending Link State Advertisements (LSAs)

C. The router is using RIP instead of OSPF

D. The router's IP address is incorrect

Solution

1. Step 1: Identify OSPF update mechanism

   OSPF updates routes by sending LSAs to inform all routers about changes.

2. Step 2: Analyze failure cause

   If routes are not updating after a link failure, it likely means LSAs are not being sent properly.

3. Final Answer:

   The router is not sending Link State Advertisements (LSAs) -> Option B

4. Quick Check:

   No LSAs = no route updates [OK]

Hint: No LSAs means no route updates [OK]

Common Mistakes:

• Blaming static routes for OSPF updates
• Confusing OSPF with RIP protocol
• Assuming IP address errors cause routing updates

5. In a large OSPF network, how does dividing the network into areas improve routing efficiency?

hard

A. By limiting the scope of link state updates to within each area

B. By allowing routers to ignore all link state information

C. By forcing all routers to maintain a full map of the entire network

D. By disabling route calculation on some routers

Solution

1. Step 1: Understand OSPF area concept

   Dividing a network into areas limits the size of link state databases each router must maintain.

2. Step 2: Explain efficiency gain

   This reduces the amount of link state updates routers process, improving speed and reducing resource use.

3. Final Answer:

   By limiting the scope of link state updates to within each area -> Option A

4. Quick Check:

   Areas limit update scope = better efficiency [OK]

Hint: Areas limit updates to improve efficiency [OK]

Common Mistakes:

• Thinking routers ignore link state info
• Assuming all routers keep full network maps
• Believing route calculation is disabled