Routing Algorithms - Distance Vector (RIP) vs Link State (OSPF)

▶

Steps

setup

Initialize Routers and Links

All four routers (R1, R2, R3, R4) are initialized with their interfaces and direct neighbors. Links between routers are set with equal cost of 1.

💡 Setting up the network topology is essential to understand how routing information will flow between routers.

Line:

initialize_routers()
initialize_links()

💡 The network topology and initial router states are the foundation for routing algorithms to operate.

fill_cells

R1 Sends Initial Distance Vector Packet to R2

Router R1 creates a Distance Vector packet containing its routing table (only itself with cost 0) and sends it to neighbor R2.

💡 This step starts the RIP algorithm by sharing initial routing info with neighbors.

Line:

packet = create_distance_vector_packet(R1)
send_packet(R1, R2, packet)

💡 Distance Vector routing relies on routers sharing their routing tables with neighbors periodically.

compare

R2 Receives Distance Vector from R1 and Updates Table

R2 receives the Distance Vector packet from R1 and updates its routing table to include R1 with cost 1 (link cost).

💡 Routers update their routing tables based on neighbors' advertised distances plus link cost.

Line:

receive_packet(R2, packet)
update_routing_table(R2, packet)

💡 Routing tables grow as routers learn about new destinations through neighbors.

fill_cells

R2 Sends Distance Vector Packet to R3

R2 sends its updated Distance Vector (now including R1 and itself) to neighbor R3.

💡 Routing info propagates hop-by-hop as each router shares its updated table.

Line:

packet = create_distance_vector_packet(R2)
send_packet(R2, R3, packet)

💡 Each router shares its best known distances with neighbors to enable network-wide convergence.

compare

R3 Receives Distance Vector from R2 and Updates Table

R3 receives the Distance Vector from R2 and updates its routing table to include R2 and R1 with costs 1 and 2 respectively.

💡 Routers add new routes or update costs if a shorter path is found.

Line:

receive_packet(R3, packet)
update_routing_table(R3, packet)

💡 Routing tables reflect cumulative costs from neighbors plus link cost.

fill_cells

R3 Sends Distance Vector Packet to R4

R3 sends its Distance Vector (including R3, R2, and R1) to neighbor R4.

💡 Routing info continues to propagate through the network.

Line:

packet = create_distance_vector_packet(R3)
send_packet(R3, R4, packet)

💡 Each router shares its best known distances to help neighbors update their tables.

compare

R4 Receives Distance Vector from R3 and Updates Table

R4 receives the Distance Vector from R3 and updates its routing table to include R3, R2, and R1 with costs 1, 2, and 3 respectively.

💡 Routers add routes with cumulative costs from neighbors plus link cost.

Line:

receive_packet(R4, packet)
update_routing_table(R4, packet)

💡 Routing tables reflect shortest known distances learned from neighbors.

fill_cells

R4 Sends Distance Vector Packet to R1

R4 sends its Distance Vector (including R4, R3, R2, and R1) to neighbor R1, completing one full cycle of RIP updates.

💡 Routing info circulates around the network to ensure all routers learn all routes.

Line:

packet = create_distance_vector_packet(R4)
send_packet(R4, R1, packet)

💡 Distance Vector routing relies on iterative sharing until tables converge.

compare

R1 Receives Distance Vector from R4 and Updates Table

R1 receives the Distance Vector from R4 and updates its routing table to include R4, R3, and R2 with costs 1, 2, and 3 respectively.

💡 Routers continuously update tables until no shorter paths are found.

Line:

receive_packet(R1, packet)
update_routing_table(R1, packet)

💡 Routing tables converge as routers learn all reachable destinations with shortest costs.

insert

OSPF: R1 Floods Link State Advertisement (LSA) to Neighbors

R1 creates a Link State Advertisement describing its directly connected links and floods it to neighbors R2 and R4.

💡 OSPF uses LSAs to share link info, not distance vectors.

Line:

lsa = create_lsa(R1)
flood_lsa(R1, [R2, R4], lsa)

💡 Link State routing floods detailed link info to all routers for global topology knowledge.

prune

R2 Receives LSA from R1 and Floods to R3

R2 receives LSA from R1, updates its link state database, and floods the LSA to neighbor R3 to propagate topology info.

💡 OSPF routers flood LSAs to all neighbors except the one they received it from.

Line:

receive_lsa(R2, lsa)
flood_lsa(R2, [R3], lsa)

💡 Flooding ensures all routers learn the complete network topology.

prune

R3 Receives LSA from R2 and Floods to R4

R3 receives LSA from R2, updates its link state database, and floods the LSA to neighbor R4.

💡 Flooding continues until all routers have the LSA.

Line:

receive_lsa(R3, lsa)
flood_lsa(R3, [R4], lsa)

💡 Each router helps propagate complete topology info to all others.

prune

R4 Receives LSA from R3 and Floods to R1

R4 receives LSA from R3, updates its link state database, and floods the LSA to neighbor R1, completing the flooding cycle.

💡 Flooding ensures all routers have the same topology info for shortest path calculation.

Line:

receive_lsa(R4, lsa)
flood_lsa(R4, [R1], lsa)

💡 Flooding is a controlled broadcast to all routers except the sender.

reconstruct

Routers Compute Shortest Paths Using Dijkstra's Algorithm

Each router uses the collected LSAs to build a complete network graph and runs Dijkstra's algorithm to compute shortest paths to all other routers.

💡 OSPF routers calculate shortest paths locally after flooding completes.

Line:

graph = build_graph_from_lsdb()
for router in routers:
    router.routing_table = dijkstra(graph, router.id)

💡 Link State routing separates topology discovery from path computation.

reconstruct

Final Routing Tables Established

The routing tables at each router now reflect shortest paths to all other routers computed by both RIP and OSPF algorithms.

💡 This final state shows the outcome of both routing algorithms for comparison.

Line:

print_routing_tables()

💡 Distance Vector converged routing tables and Link State computed shortest paths are visible side-by-side.

def initialize_routers():
    # STEP 1: Setup routers and links
    pass

def create_distance_vector_packet(router):
    # STEP 2,4,6,8: Create RIP packet with routing table
    pass

def send_packet(src, dst, packet):
    # STEP 2,4,6,8: Send packet from src to dst
    pass

def receive_packet(router, packet):
    # STEP 3,5,7,9: Receive RIP packet and update table
    pass

def create_lsa(router):
    # STEP 10: Create LSA describing router's links
    pass

def flood_lsa(src, neighbors, lsa):
    # STEP 10-13: Flood LSA to neighbors
    pass

def receive_lsa(router, lsa):
    # STEP 11-13: Receive LSA and update LSDB
    pass

def build_graph_from_lsdb():
    # STEP 14: Build network graph from LSDB
    pass

def dijkstra(graph, start):
    # STEP 14: Compute shortest paths
    pass

def print_routing_tables():
    # STEP 15: Output final routing tables
    pass

📊

Routing Algorithms - Distance Vector (RIP) vs Link State (OSPF) - Watch the Algorithm Execute, Step by Step

Watching the packet flow and routing table updates live reveals the fundamental differences between RIP and OSPF, making it easier to grasp their mechanisms than reading theory alone.

Network topology initialized with 4 routers and equal cost links.

Hop: 0

R1

R2

R3

R4

R1 sent initial Distance Vector packet to R2.

Hop: 1

R1

R2

R3

R4

📦Packet

↗ fromR1

↘ toR2

📄 payloadDistance Vector: {R1:0}

🔌 protocolRIP

🚩 flags

src→R1:520

dst→R2:520

data→Distance Vector: {R1:0}

Distance Vector: R1→R2 (costs={R1:0})

R2 updated routing table to include R1 at cost 1.

Hop: 1

R1

R2

R3

R4

src→R1:520

dst→R2:520

data→Distance Vector: {R1:0}

Distance Vector: R1→R2 (costs={R1:0})

R2 updated routing table with R1: cost 1

R2 sent updated Distance Vector packet to R3.

Hop: 2

R1

R2

R3

R4

📦Packet

↗ fromR2

↘ toR3

📄 payloadDistance Vector: {R2:0, R1:1}

🔌 protocolRIP

🚩 flags

src→R2:520

dst→R3:520

data→Distance Vector: {R2:0, R1:1}

Distance Vector: R1→R2 (costs={R1:0})

R2 updated routing table with R1: cost 1

Distance Vector: R2→R3 (costs={R2:0, R1:1})

R3 updated routing table with routes to R2 and R1.

Hop: 2

R1

R2

R3

R4

src→R2:520

dst→R3:520

data→Distance Vector: {R2:0, R1:1}

R2 updated routing table with R1: cost 1

Distance Vector: R2→R3 (costs={R2:0, R1:1})

R3 updated routing table with R2: cost 1, R1: cost 2

R3 sent updated Distance Vector packet to R4.

Hop: 3

R1

R2

R3

R4

📦Packet

↗ fromR3

↘ toR4

📄 payloadDistance Vector: {R3:0, R2:1, R1:2}

🔌 protocolRIP

🚩 flags

src→R3:520

dst→R4:520

data→Distance Vector: {R3:0, R2:1, R1:2}

Distance Vector: R2→R3 (costs={R2:0, R1:1})

R3 updated routing table with R2: cost 1, R1: cost 2

Distance Vector: R3→R4 (costs={R3:0, R2:1, R1:2})

R4 updated routing table with routes to R3, R2, and R1.

Hop: 3

R1

R2

R3

R4

src→R3:520

dst→R4:520

data→Distance Vector: {R3:0, R2:1, R1:2}

R3 updated routing table with R2: cost 1, R1: cost 2

Distance Vector: R3→R4 (costs={R3:0, R2:1, R1:2})

R4 updated routing table with R3: cost 1, R2: cost 2, R1: cost 3

R4 sent updated Distance Vector packet to R1.

Hop: 4

R1

R2

R3

R4

📦Packet

↗ fromR4

↘ toR1

📄 payloadDistance Vector: {R4:0, R3:1, R2:2, R1:3}

🔌 protocolRIP

🚩 flags

src→R4:520

dst→R1:520

data→Distance Vector: {R4:0, R3:1, R2:2, R1:3}

Distance Vector: R3→R4 (costs={R3:0, R2:1, R1:2})

R4 updated routing table with R3: cost 1, R2: cost 2, R1: cost 3

Distance Vector: R4→R1 (costs={R4:0, R3:1, R2:2, R1:3})

R1 updated routing table with routes to R4, R3, and R2.

Hop: 4

R1

R2

R3

R4

src→R4:520

dst→R1:520

data→Distance Vector: {R4:0, R3:1, R2:2, R1:3}

R4 updated routing table with R3: cost 1, R2: cost 2, R1: cost 3

Distance Vector: R4→R1 (costs={R4:0, R3:1, R2:2, R1:3})

R1 updated routing table with R4: cost 1, R3: cost 2, R2: cost 3

R1 flooded LSA packets to neighbors R2 and R4.

Hop: 5

R1

R2

R3

R4

📦Packet

↗ fromR1

↘ toR2

📄 payloadLSA: links={R1-R2:1, R1-R4:1}

🔌 protocolOSPF

🚩 flags

src→R1:89

dst→R2:89

data→LSA: links={R1-R2:1, R1-R4:1}

R1 flooded LSA to R2: links={R1-R2:1, R1-R4:1}

R1 flooded LSA to R4: links={R1-R2:1, R1-R4:1}

R2 flooded LSA from R1 to R3.

Hop: 6

R1

R2

R3

R4

📦Packet

↗ fromR2

↘ toR3

📄 payloadLSA: links={R1-R2:1, R1-R4:1}

🔌 protocolOSPF

🚩 flags

src→R2:89

dst→R3:89

data→LSA: links={R1-R2:1, R1-R4:1}

R1 flooded LSA to R2: links={R1-R2:1, R1-R4:1}

R2 flooded LSA to R3: links={R1-R2:1, R1-R4:1}

R3 flooded LSA from R2 to R4.

Hop: 7

R1

R2

R3

R4

📦Packet

↗ fromR3

↘ toR4

📄 payloadLSA: links={R1-R2:1, R1-R4:1}

🔌 protocolOSPF

🚩 flags

src→R3:89

dst→R4:89

data→LSA: links={R1-R2:1, R1-R4:1}

R1 flooded LSA to R2: links={R1-R2:1, R1-R4:1}

R2 flooded LSA to R3: links={R1-R2:1, R1-R4:1}

R3 flooded LSA to R4: links={R1-R2:1, R1-R4:1}

R4 flooded LSA from R3 to R1.

Hop: 8

R1

R2

R3

R4

📦Packet

↗ fromR4

↘ toR1

📄 payloadLSA: links={R1-R2:1, R1-R4:1}

🔌 protocolOSPF

🚩 flags

src→R4:89

dst→R1:89

data→LSA: links={R1-R2:1, R1-R4:1}

R2 flooded LSA to R3: links={R1-R2:1, R1-R4:1}

R3 flooded LSA to R4: links={R1-R2:1, R1-R4:1}

R4 flooded LSA to R1: links={R1-R2:1, R1-R4:1}

Routers updated routing tables with shortest paths from link state database.

Hop: 9

R1

R2

R3

R4

All routers computed shortest paths using Dijkstra's algorithm.

Final routing tables show shortest paths computed by RIP and OSPF.

Hop: 15

R1 RIP: {R1:0,R2:3,R3:2,R4:1} OSPF: {R1:0,R2:1,R3:2,R4:1}

R2 RIP: {R2:0,R1:1,R3:1,R4:2} OSPF: {R2:0,R1:1,R3:1,R4:2}

R3 RIP: {R3:0,R2:1,R4:1,R1:2} OSPF: {R3:0,R2:1,R4:1,R1:2}

R4 RIP: {R4:0,R3:1,R1:1,R2:2} OSPF: {R4:0,R3:1,R1:1,R2:2}

All routers computed shortest paths using Dijkstra's algorithm.

Final routing tables established for RIP and OSPF.

Key Takeaways

✓ Distance Vector routing propagates routing tables hop-by-hop, which can lead to slower convergence and count-to-infinity problems.

Watching the stepwise packet exchanges reveals how routing info slowly spreads and updates, which is hard to grasp from code alone.

✓ Link State routing floods detailed link info to all routers, enabling each to compute shortest paths independently using Dijkstra's algorithm.

Seeing LSAs flood and local computation clarifies how OSPF achieves faster and more reliable convergence.

✓ The visualization shows how routing tables differ after RIP and OSPF converge, highlighting OSPF's more accurate shortest path results.

Comparing final tables side-by-side helps concretely understand the practical differences between the algorithms.

Practice

1. Trace the sequence of server state changes when a client sends a PATCH request to update a user's email address. Which of the following best describes what happens step-by-step?

easy

A. The server modifies only the specified email field without affecting other user data.

B. The server replaces the entire user resource with the new email data.

C. The server creates a new user resource with the updated email.

D. The server deletes the old email and then inserts the new email as a separate resource.

Solution

1. Step 1: Understand PATCH semantics

   PATCH is used for partial updates, modifying only specified fields.

2. Step 2: Differentiate from PUT

   PUT replaces the entire resource, while PATCH updates parts.

3. Step 3: Analyze options

   The server modifies only the specified email field without affecting other user data correctly states partial modification; others describe full replacement or resource creation/deletion.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   PATCH modifies only the targeted fields without affecting the rest.

Hint: PATCH = partial update, PUT = full replace

Common Mistakes:

• Confusing PATCH with PUT and thinking it replaces the whole resource
• Assuming PATCH creates new resources
• Believing PATCH deletes and reinserts fields

2. In which OSI layer would you most likely implement encryption to secure data before transmission?

easy

A. Presentation Layer

B. Transport Layer

C. Application Layer

D. Network Layer

Solution

1. Step 1: Understand the role of the Presentation Layer

   The Presentation Layer is responsible for data translation, encryption, and compression before passing data to the Session Layer.

2. Step 2: Why not other layers?

   Application Layer handles user interface and application services, Transport Layer manages end-to-end communication and reliability, Network Layer handles routing and addressing but not encryption.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Encryption is a Presentation Layer function [OK]

Hint: Encryption and data formatting happen at the Presentation Layer [OK]

Common Mistakes:

• Assuming encryption is done at the Application Layer
• Confusing Transport Layer's reliability with security
• Thinking Network Layer handles encryption

3. Why is it generally discouraged to use POST for operations that are intended to be idempotent, such as updating a user profile repeatedly with the same data?

medium

A. Because POST requests are cached by default, leading to stale data issues.

B. Because POST always deletes the resource before updating it.

C. Because POST cannot carry a request body, limiting update capabilities.

D. Because POST is not idempotent, repeated identical requests may cause unintended side effects.

Solution

1. Step 1: Recall idempotency definition

   An idempotent method produces the same result no matter how many times it is repeated.

2. Step 2: Analyze POST properties

   POST is not idempotent; repeated identical POSTs can create multiple resources or side effects.

3. Step 3: Evaluate options

   Because POST is not idempotent, repeated identical requests may cause unintended side effects correctly identifies the non-idempotent nature of POST. Others are factually incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   POST is not idempotent, so using it for idempotent operations risks unintended consequences.

Hint: POST ≠ idempotent; PUT and DELETE are idempotent

Common Mistakes:

• Thinking POST is cached by default (it is not)
• Believing POST cannot carry a body (it can)
• Assuming POST deletes resources before updating

4. Which of the following statements about WebSockets is INCORRECT?

medium

A. WebSocket communication is inherently secure and does not require additional encryption layers

B. WebSocket connections start as HTTP requests and then upgrade to a persistent full-duplex socket

C. WebSocket reduces latency by avoiding HTTP request-response overhead after connection establishment

D. WebSocket supports bidirectional communication allowing both client and server to send messages independently

Solution

1. Step 1: Review WebSocket handshake

   WebSocket connections begin as HTTP requests and upgrade to a persistent socket (WebSocket connections start as HTTP requests and then upgrade to a persistent full-duplex socket is correct).

2. Step 2: Consider security aspects

   WebSocket itself is a protocol and does not guarantee encryption; secure WebSocket (wss://) uses TLS for encryption. So, WebSocket communication is not inherently secure (WebSocket communication is inherently secure and does not require additional encryption layers is incorrect).

3. Step 3: Analyze latency and communication

   WebSocket reduces latency by avoiding repeated HTTP overhead (WebSocket reduces latency by avoiding HTTP request-response overhead after connection establishment correct) and supports bidirectional communication (WebSocket supports bidirectional communication allowing both client and server to send messages independently correct).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   WebSocket requires TLS (wss://) for secure communication; it is not secure by default

Hint: WebSocket = HTTP upgrade + optional TLS for security

Common Mistakes:

• Assuming WebSocket is always encrypted
• Confusing WebSocket handshake with normal HTTP
• Believing WebSocket is unidirectional

5. If a company wants to improve both security and performance for a public-facing web application, which combined deployment of firewall, proxy, and reverse proxy is most effective?

hard

A. Deploy a proxy server between backend servers and clients without a firewall

B. Use only a reverse proxy to handle all security filtering and caching

C. Rely solely on a firewall to filter traffic and improve performance

D. Deploy a firewall at the network edge, a forward proxy for client requests, and a reverse proxy in front of backend servers

Solution

1. Step 1: Firewall role

   Firewall at network edge filters unauthorized traffic, providing security.

2. Step 2: Forward proxy role

   Forward proxy manages client requests, can enforce policies and cache content.

3. Step 3: Reverse proxy role

   Reverse proxy protects backend servers, performs load balancing, SSL termination, and caching.

4. Step 4: Evaluate other options

   Only reverse proxy (B) or only firewall (C) miss layered defense and performance optimization; no firewall (A) reduces security.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Combined deployment leverages strengths of all components [OK]

Hint: Layered defense: firewall + proxies for security and performance.

Common Mistakes:

• Assuming one component can handle all roles
• Ignoring the need for firewall in security