Rip - Learning Module | OneNoughtOne

Loading content...

0/228

Distance Vector Algorithm: The Mathematical Foundation of RIP

Computing Routes Without a Map

Imagine you're in a city where no one has a complete map, but everyone knows the distance to their immediate neighbors. Your goal: determine the shortest path to every destination, relying only on information from people next door. This seemingly impossible task is exactly what distance vector routing accomplishes—and it works remarkably well.

The distance vector algorithm is one of the most elegant distributed algorithms in computer science. It allows routers with only local knowledge to collectively compute globally optimal paths. Each router knows nothing beyond its direct connections, yet the network as a whole converges to correct routing decisions.

This page explores the mathematical foundations, operational mechanics, and convergence properties of the distance vector algorithm as implemented in RIP. Understanding these principles is essential for troubleshooting routing issues, predicting network behavior, and appreciating why RIP behaves the way it does.

What You Will Learn

By the end of this page, you will understand the Bellman-Ford algorithm that underpins distance vector routing, how routers compute and exchange route information, the mathematical convergence properties of the algorithm, and why certain pathological behaviors like counting-to-infinity occur.

The Bellman-Ford Foundation

Distance vector routing is the distributed implementation of the Bellman-Ford algorithm, a classic shortest-path algorithm developed independently by Richard Bellman (1958) and Lester Ford Jr. (1956). To understand RIP, we must first understand Bellman-Ford.

The Shortest Path Problem

Given a graph with weighted edges representing network links, find the minimum-cost path from each source to each destination. In networking terms:

Vertices (nodes) = Routers
Edges = Network links
Edge weights = Costs (in RIP, cost = 1 for each hop)
Shortest path = Minimum total cost path

The Bellman-Ford Equation

The algorithm is based on a fundamental recursive relationship. For any destination d and router x, the distance is:

D(x,d) = min over all neighbors y { cost(x,y) + D(y,d) }

This reads: "The distance from x to d is the minimum of: the cost to reach each neighbor y, plus that neighbor's distance to d."

Bellman-Ford Algorithm (Centralized)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# Centralized Bellman-Ford Algorithm
# This is the theoretical basis - RIP distributes this computation
 
def bellman_ford(graph, source):
    """
    Compute shortest paths from source to all vertices.
    
    Args:
        graph: Dictionary of {vertex: {neighbor: cost}}
        source: Starting vertex
    
    Returns:
        distances: Dictionary of {vertex: minimum_distance}
        predecessors: Dictionary of {vertex: next_hop_to_source}
    """
    # Initialize distances
    distances = {v: float('infinity') for v in graph}
    distances[source] = 0
    predecessors = {v: None for v in graph}
    
    # Relax edges |V| - 1 times
    num_vertices = len(graph)
    
    for iteration in range(num_vertices - 1):
        updated = False
        
        for u in graph:
            for v, weight in graph[u].items():
                # The Bellman-Ford relaxation step
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
                    predecessors[v] = u
                    updated = True
        
        # Early termination if no updates
        if not updated:
            break
    
    return distances, predecessors
 
# Example usage with simple network
#     A ---1--- B
#     |         |
#     2         1
#     |         |
#     C ---3--- D
 
network = {
    'A': {'B': 1, 'C': 2},
    'B': {'A': 1, 'D': 1},
    'C': {'A': 2, 'D': 3},
    'D': {'B': 1, 'C': 3}
}
 
distances, paths = bellman_ford(network, 'A')
print(f"Distances from A: {distances}")
# Output: Distances from A: {'A': 0, 'B': 1, 'C': 2, 'D': 2}

Why |V| - 1 Iterations?

The algorithm iterates |V| - 1 times (where |V| is the number of vertices) because the longest possible simple path visits every vertex exactly once, which contains |V| - 1 edges. After |V| - 1 iterations:

Shortest paths of length 1 are found by iteration 1
Shortest paths of length 2 are found by iteration 2
Shortest paths of length k are found by iteration k
All shortest paths (max length |V| - 1) are found by iteration |V| - 1

Complexity Analysis

Time complexity: O(|V| × |E|) — iterate over all edges for each of |V| - 1 iterations
Space complexity: O(|V|) — store distance and predecessor for each vertex

For RIP's hop count metric where all edge costs are 1, the algorithm effectively finds minimum-hop paths.

Bellman-Ford vs. Dijkstra

Unlike Dijkstra's algorithm (used by OSPF), Bellman-Ford doesn't require global network knowledge. Each iteration uses only local information. This property makes it naturally distributable—each router runs its own copy with information from neighbors. The trade-off: Bellman-Ford is slower (O(VE) vs O(E + V log V)) but doesn't require complete topology.

Distributed Bellman-Ford in RIP

The genius of distance vector routing is transforming the centralized Bellman-Ford algorithm into a distributed protocol. Instead of one computer computing all paths, every router participates in a collective computation.

The Transformation

In the centralized algorithm:

A single processor knows the entire graph
Iterations happen synchronously
Completion is deterministic after |V| - 1 iterations

In RIP's distributed version:

Each router knows only its neighbors
Iterations happen asynchronously (via periodic updates)
Convergence depends on update propagation

How the Distribution Works

Converting Mermaid diagram...

The Distance Vector

The term "distance vector" comes from what routers exchange:

Distance: The metric (hop count) to each destination
Vector: A list of (destination, distance) pairs

Each router maintains a distance vector containing its best-known distance to every destination. Periodically, routers send their distance vectors to neighbors. Upon receiving a neighbor's vector, the router performs the Bellman-Ford calculation for each destination:

For each destination D in neighbor's vector:
    new_distance = cost_to_neighbor + neighbor's_distance_to_D
    if new_distance < my_distance_to_D:
        update my route: via neighbor, distance = new_distance

Key Insight: Information Propagation Speed

In RIP, information about a new route propagates one hop per update interval:

Update interval: 30 seconds
5-hop destination: 5 × 30 = 150 seconds to propagate
15-hop network: Up to 7.5 minutes for full convergence

This is why RIP converges slowly—each "iteration" of the distributed algorithm takes 30 seconds.

RIP Distance Vector Processing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Pseudo-code for RIP update processing
# This runs on each router independently
 
class RIPRouter:
    def __init__(self, router_id, interfaces):
        self.id = router_id
        self.interfaces = interfaces  # {neighbor: cost}
        
        # Distance vector: {destination: (distance, next_hop)}
        self.routing_table = {}
        
        # Initialize with directly connected networks
        for network in self.directly_connected_networks():
            self.routing_table[network] = (1, 'direct')
    
    def process_update(self, neighbor, received_vector):
        """
        Process a distance vector received from a neighbor.
        This is the core Bellman-Ford step, distributed.
        """
        link_cost = self.interfaces[neighbor]  # Usually 1 for RIP
        
        for destination, distance in received_vector.items():
            # Bellman-Ford: D(me, dest) = min(current, cost(me,neighbor) + D(neighbor,dest))
            new_distance = link_cost + distance
            
            # RIP maximum: 16 means unreachable
            if new_distance > 15:
                new_distance = 16
            
            if destination not in self.routing_table:
                # New destination learned
                if new_distance < 16:
                    self.routing_table[destination] = (new_distance, neighbor)
                    print(f"Learned {destination}: {new_distance} hops via {neighbor}")
            
            elif new_distance < self.routing_table[destination][0]:
                # Better path found
                old_distance = self.routing_table[destination][0]
                self.routing_table[destination] = (new_distance, neighbor)
                print(f"Improved {destination}: {old_distance} -> {new_distance} via {neighbor}")
            
            elif self.routing_table[destination][1] == neighbor:
                # Update from current next-hop (could be worse)
                self.routing_table[destination] = (new_distance, neighbor)
                if new_distance >= 16:
                    print(f"Lost route to {destination} via {neighbor}")
    
    def generate_update(self):
        """Generate distance vector to send to neighbors."""
        return {dest: dist for dest, (dist, _) in self.routing_table.items()}

The Synchronization Assumption

RIP assumes asynchronous updates eventually propagate everywhere, but timing variations can cause temporary routing inconsistencies. If Router A updates before receiving Router B's update, routes may temporarily diverge. This asynchrony is why loop prevention mechanisms like split horizon are essential.

Route Selection Logic

When a RIP router receives updates from multiple neighbors, it must decide which route to install in the routing table. This decision process is deceptively simple but has subtle implications.

The Basic Rule: Lowest Metric Wins

RIP's route selection is straightforward:

Compare metrics (hop counts) of all known paths
Select the path with the lowest metric
If metrics are equal, keep existing route (stability preference)
Metrics ≥ 16 mean unreachable

The Decision Table

RIP Route Selection Scenarios
Current Route	Received Update	Action	Rationale
None (new destination)	Metric < 16	Install route	First path to destination
None (new destination)	Metric = 16	Ignore	Unreachable isn't useful
Metric 5 via R2	Metric 3 via R3	Replace with R3	Better path found
Metric 3 via R2	Metric 5 via R3	Keep R2	Current path still best
Metric 3 via R2	Metric 3 via R3	Keep R2	Equal metrics, prefer stability
Metric 3 via R2	Metric 4 via R2	Update to 4 via R2	Same next-hop, trust update
Metric 3 via R2	Metric 16 via R2	Mark unreachable via R2	Next-hop reports failure
Metric 3 via R2	Metric 16 via R3	Keep R2	Unreachable via R3 is irrelevant

Critical Rule: Next-Hop Authority

One crucial aspect of RIP is that updates from the current next-hop are always accepted, even if they report a worse metric:

If update.source == current_route.next_hop:
    ALWAYS update the metric (could be worse or better)
Else:
    Only update if new metric is BETTER than current

Why? Because the next-hop router is the authoritative source for its own path. If Router R2 tells you destination D is now 5 hops away (was 3), R2 knows something you don't—perhaps a downstream link failed. Ignoring this update would create routing inconsistencies.

Equal-Cost Multipath (ECMP)

When multiple paths have identical metrics, RIP can install all of them for load balancing:

Destination: 10.1.1.0/24
  via 192.168.1.1 (Router R2), metric 3
  via 192.168.2.1 (Router R3), metric 3

Traffic to 10.1.1.0/24 is distributed across both paths

ECMP behavior varies by implementation:

Some routers alternate packets (round-robin)
Others hash based on flow (source/destination IPs)
Maximum ECMP paths is typically configurable (often 4 default)

Administrative Distance in Practice

When a router runs multiple routing protocols, routes are first compared by administrative distance (protocol trustworthiness), then by metric. RIP's default administrative distance is 120, higher than OSPF (110) or EIGRP (90 internal). This means if OSPF and RIP both know a route, OSPF wins regardless of metrics.

Convergence Properties

Convergence is the process by which all routers in a network reach a consistent, accurate view of the topology. Understanding RIP's convergence properties is essential for predicting network behavior.

What "Converged" Means

A network is converged when:

All routers have routes to all reachable destinations
All routes reflect the current topology
No routing loops exist
Further updates cause no changes

Convergence Scenarios

Good News Travels Fast

•New network appears — Propagates at 1 hop per update interval
•Better path found — Immediately replaces worse paths
•Metric improvements — Quickly adopted network-wide
•Convergence time — (diameter × update_interval)
•Example — 5-hop network: 5 × 30s = 150 seconds max

Bad News Travels Slowly

•Network disappears — Must time out (180 seconds default)
•Path degrades — May cause counting-to-infinity
•Metric increases — Can create temporary loops
•Convergence time — Up to (16 × update_interval)
•Example — Count to infinity: up to 16 × 30s = 8 minutes

Mathematical Analysis of Convergence

For a stable network with n routers and diameter d (maximum hop count between any two routers):

Best case (adding routes):

Information propagates one hop per update
Convergence time: d × 30 seconds
All routes optimal after propagation completes

Worst case (removing routes without triggered updates):

Route must time out: 180 seconds (6 missed updates)
Plus garbage collection: 120 seconds
Total: up to 300 seconds (5 minutes) per router

Pathological case (counting to infinity):

Metric increments from current value to 16
Each increment takes one update interval
Maximum: (16 - current_metric) × 30 seconds
Plus timeouts once infinity reached

Convergence Time Analysis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# Theoretical convergence time calculations for RIP
 
def calculate_good_news_convergence(diameter, update_interval=30):
    """
    Calculate time for good news (new routes, better paths) to propagate.
    
    Good news travels at 1 hop per update interval.
    """
    return diameter * update_interval
 
def calculate_bad_news_convergence_with_poison(current_metric, update_interval=30):
    """
    Calculate time for bad news with triggered update and poison reverse.
    
    Route is poisoned immediately, propagates like good news.
    """
    return 15 * update_interval  # Still must reach 16, but starts immediately
 
def calculate_bad_news_convergence_without_mechanisms(current_metric, update_interval=30):
    """
    Calculate worst-case time for bad news without loop prevention.
    
    Counting to infinity scenario.
    """
    increments_needed = 16 - current_metric
    return increments_needed * update_interval
 
def calculate_timeout_convergence(timeout=180, garbage_collection=120):
    """
    Calculate time for route to fully expire.
    """
    return timeout + garbage_collection
 
# Example calculations
print("5-hop network, good news convergence:", 
      calculate_good_news_convergence(5), "seconds")
 
print("Route with metric 3 counting to infinity:",
      calculate_bad_news_convergence_without_mechanisms(3), "seconds")
 
print("Route timing out naturally:",
      calculate_timeout_convergence(), "seconds")
 
# Output:
# 5-hop network, good news convergence: 150 seconds
# Route with metric 3 counting to infinity: 390 seconds
# Route timing out naturally: 300 seconds

The Convergence Gap

During convergence, the network is in an inconsistent state. Packets may be dropped (no route), loop (conflicting routes), or take suboptimal paths (stale routes). For business-critical networks, this convergence delay is RIP's most significant limitation.

The Count-to-Infinity Problem

The most infamous pathological behavior of distance vector protocols is the counting-to-infinity problem. This occurs when routers perpetuate false route information in a loop, incrementing metrics until they reach infinity (16 in RIP).

Anatomy of Count-to-Infinity

Consider this simple topology:

Count-to-Infinity Scenario
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Initial topology: R1 -- R2 -- R3 -- Network X
# 
# R3 is directly connected to Network X (metric 1)
# R2 learns: Network X is 2 hops (via R3)
# R1 learns: Network X is 3 hops (via R2)
 
# Now the link R3--NetworkX fails!
 
# Step 1: R3 marks Network X as metric 16 (unreachable via direct link)
# BUT before R3's update reaches R2...
 
# Step 2: R2 sends its regular update to R3:
#         "I can reach Network X in 2 hops!"
 
# Step 3: R3 thinks: "Great! R2 knows another path!"
#         R3 updates: Network X = 2 + 1 = 3 hops via R2
 
# Step 4: R2 receives R3's update: "Network X is 3 hops via R3??"
#         R2 updates: Network X = 3 + 1 = 4 hops via R3
 
# Step 5: R3 receives R2's update: "Network X is 4 hops via R2??"
#         R3 updates: Network X = 4 + 1 = 5 hops via R2
 
# ... continues until metric reaches 16 ...
 
# Timeline of R2's routing table:
# T+0:   Network X, 2 hops via R3 (correct at this moment)
# T+30s: Network X, 4 hops via R3 (believing R3's update)
# T+60s: Network X, 6 hops via R3
# T+90s: Network X, 8 hops via R3
# T+120s: Network X, 10 hops via R3  
# T+150s: Network X, 12 hops via R3
# T+180s: Network X, 14 hops via R3
# T+210s: Network X, 16 hops via R3 (finally unreachable!)
 
# Total convergence time: 7 update intervals = 210 seconds = 3.5 minutes
# During this time: Packets to Network X LOOP between R2 and R3!

Why Does This Happen?

The fundamental issue is that R3 believes R2's outdated information. R2's advertisement is based on its old route through R3, but R3 doesn't realize this. The false route information bounces back and forth, each router incrementing the metric based on the other's (wrong) information.

The Routing Loop

During counting-to-infinity, packets follow a routing loop:

Packet arrives at R2 destined for Network X
R2's table says: "Network X via R3"
R2 forwards packet to R3
R3's table says: "Network X via R2" (the phantom route!)
R3 forwards packet back to R2
Loop continues until packet's TTL expires

Packets caught in this loop are:

Delayed (looping consumes time)
Eventually dropped (TTL expires)
Wasting bandwidth (same packet traverses links multiple times)

Count-to-Infinity: Step-by-Step Analysis
Event	R2's Route to X	R3's Route to X	Packets to X
Initial stable state	2 via R3 ✓	1 direct ✓	Delivered correctly
R3-X link fails	2 via R3 (stale)	∞ (knows link down)	Loop between R2-R3
R2 sends update to R3	2 via R3	3 via R2 (wrong!)	Loop continues
R3 sends update to R2	4 via R3 (wrong!)	3 via R2	Loop continues
After 6 more iterations	14 via R3	15 via R2	Loop continues
Metrics hit 16	16 (unreachable)	16 (unreachable)	Dropped immediately

The Real Cost of Counting-to-Infinity

A single link failure can cause minutes of routing loops affecting all traffic to the failed destination. In a production environment, this means service outages, timeouts, and degraded user experience. This behavior is RIP's most serious operational limitation.

Loop Prevention Mechanisms

Distance vector protocols have developed several mechanisms to mitigate (though not eliminate) the count-to-infinity problem. RIP implements most of these.

1. Maximum Metric (Infinity Definition)

By defining 16 as infinity, RIP bounds the worst-case convergence time. Without this limit, counting could continue indefinitely. The trade-off: networks with diameter > 15 hops cannot use RIP.

2. Split Horizon

Split Horizon Rule
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Split Horizon: Never advertise a route back to its source
 
# Without split horizon:
# R2 learned route to X via R3
# R2 sends update to R3: "I can reach X in 2 hops"
# R3 believes R2 has alternate path -> COUNT TO INFINITY
 
# With split horizon:
# R2 learned route to X via R3
# R2 sends update to ALL neighbors EXCEPT R3: "X is 2 hops"
# R2 sends update to R3: (route to X OMITTED)
# R3 cannot be misled by its own route information
 
def generate_update_with_split_horizon(routing_table, target_neighbor):
    """
    Generate update for a specific neighbor, applying split horizon.
    """
    update = {}
    
    for destination, (metric, next_hop) in routing_table.items():
        # Split horizon: skip routes learned from this neighbor
        if next_hop != target_neighbor:
            update[destination] = metric
        else:
            # Route learned from this neighbor - OMIT from update
            pass  
    
    return update
 
# Example:
# R2's routing table:
#   Network X: metric 2, next_hop = R3
#   Network Y: metric 1, next_hop = R1
 
# Update to R3 (split horizon applied):
#   Network Y: metric 1  (X omitted - learned from R3)
 
# Update to R1 (split horizon applied):
#   Network X: metric 2  (Y omitted - learned from R1)

3. Poison Reverse

Poison reverse is a stronger form of split horizon. Instead of omitting routes, the router advertises them with metric 16 (unreachable):

R2 learned route to X via R3
R2 sends to R3: "Network X, metric 16" (poisoned!)

R3 thinks: "R2 says X is unreachable. If my direct link fails, 
            I definitely cannot go through R2."

Poison reverse is more reliable than simple split horizon because it explicitly tells the neighbor "don't use me for this route" rather than being silent.

4. Triggered Updates

When a route changes (especially becomes unreachable), don't wait for the 30-second periodic timer—send an immediate update:

R3 detects link to X has failed:
  1. Immediately (within 1-5 seconds) send triggered update
  2. Update contains: "Network X, metric 16"
  3. Neighbors learn of failure in seconds, not 30 seconds

Triggered updates dramatically reduce convergence time for failures.

5. Hold-Down Timer

After a route becomes unreachable, ignore any updates about it for a hold-down period (typically 180 seconds):

R3 tells R2: "X is unreachable"
R2 starts hold-down timer for X (180 seconds)

During hold-down:
  - R2 ignores updates about X from anyone
  - This prevents R2 from accepting stale information
  - After 180s, R2 will accept new routes to X

Hold-down prevents the "rebound" where stale information from other routers resurrects a dead route.

Loop Prevention Mechanism Comparison
Mechanism	How It Works	Effectiveness	Trade-off
Split Horizon	Don't advertise route to its source	Prevents simple 2-node loops	Can't prevent 3+ node loops
Poison Reverse	Advertise route as unreachable to source	Stronger than split horizon	Increases update size
Triggered Updates	Send immediate update on change	Faster convergence	Potential update storm
Hold-Down	Ignore updates for failed routes	Prevents stale route acceptance	Delays learning new paths
Maximum Metric	Define infinity (16)	Bounds convergence time	Limits network diameter

Defense in Depth

These mechanisms work best together. Split horizon prevents simple loops, poison reverse adds explicit denial, triggered updates speed propagation, and hold-down prevents race conditions. No single mechanism is perfect, but combined they significantly improve RIP's stability.

Practical Convergence Example

Let's walk through a complete convergence scenario with all mechanisms active, demonstrating how RIP actually behaves in practice.

Complete Convergence Scenario
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Network Topology:
#
#     NetA       NetB       NetC       NetD
#       |          |          |          |
#      R1 -------- R2 ------- R3 ------- R4
#              Link L1    Link L2    Link L3
#
# All links are working, network is converged
 
# Initial Routing Tables (all correct):
# =======================================
# R1: NetA=1(direct), NetB=2(R2), NetC=3(R2), NetD=4(R2)
# R2: NetA=2(R1), NetB=1(direct), NetC=2(R3), NetD=3(R3)
# R3: NetA=3(R2), NetB=2(R2), NetC=1(direct), NetD=2(R4)
# R4: NetA=4(R3), NetB=3(R3), NetC=2(R3), NetD=1(direct)
 
# EVENT: Link L2 (R2-R3) fails at T=0
# ======================================
 
# T+0: R2 and R3 detect link failure
#   R2 marks: Routes via R3 unreachable (NetC=16, NetD=16)
#   R3 marks: Routes via R2 unreachable (NetA=16, NetB=16)
 
# T+1s: Triggered updates sent (random delay 1-5s to prevent collision)
#   R2 -> R1: "NetC=16, NetD=16" (poison)
#   R3 -> R4: "NetA=16, NetB=16" (poison)
 
# T+2s: R1 and R4 process updates
#   R1: NetC=16 (was 3), NetD=16 (was 4) - now unreachable via R2
#   R4: NetA=16 (was 4), NetB=16 (was 3) - now unreachable via R3
#   Both routers start hold-down timers for these routes
 
# T+30s: Next periodic update cycle
#   R2 -> R1: Still shows NetC=16, NetD=16
#   R3 -> R4: Still shows NetA=16, NetB=16
#   
#   Split horizon in effect:
#   R1 -> R2: (NetA=1) - NetB,C,D omitted, learned from R2
#   R4 -> R3: (NetD=1) - NetA,B,C omitted, learned from R3
 
# T+180s: Hold-down expires
#   All routers can now accept new routes to NetA,B,C,D
#   But there are no alternate paths - routes remain unreachable
 
# FINAL STATE: Network partitioned
#   R1, R2 can reach: NetA, NetB only
#   R3, R4 can reach: NetC, NetD only
#   Routes between partitions show metric 16
 
# Convergence complete at T+180s (hold-down) + triggered update delay
# No counting-to-infinity occurred!

Analysis: Why This Worked Well

This scenario demonstrates RIP working correctly with all loop prevention mechanisms:

Immediate detection: R2 and R3 detected the link failure instantly when the interface went down
Triggered updates: Failure information propagated within seconds, not 30 seconds
Poison reverse: Explicit "unreachable" messages prevented any misunderstanding
Split horizon: Routers didn't advertise routes back to their sources
Hold-down: R1 and R4 refused to accept stale information for 180 seconds

Convergence Timeline Summary
Time	Event	Network State
T+0	Link failure detected	R2, R3 know immediately; others have stale routes
T+1-5s	Triggered updates propagate	All routers know about failure
T+30s	First periodic update	Poison information reinforced
T+180s	Hold-down expires	Network fully converged, stable

RIP Can Work Well

When properly configured with all loop prevention mechanisms active, RIP converges reasonably well for small networks. The 180-second total convergence time (dominated by hold-down) is acceptable for many applications. Problems arise in larger networks or when mechanisms are disabled.

Summary: The Distance Vector Algorithm

We've explored the mathematical and operational foundations of the distance vector algorithm as implemented in RIP. Let's consolidate the key insights:

Key Takeaways

•Bellman-Ford is the foundation — The distance vector algorithm is a distributed implementation of Bellman-Ford, where each router computes shortest paths using only neighbor information.
•Distance vectors are exchanged — Routers share their complete routing tables (destination, distance pairs) with direct neighbors every 30 seconds.
•Route selection is metric-based — Lowest hop count wins, with equal metrics favoring stability and updates from current next-hop always trusted.
•Good news converges quickly — New routes and improved paths propagate at one hop per update interval (diameter × 30 seconds).
•Bad news can cause loops — Failed routes can trigger counting-to-infinity, where routers incrementally increase metrics while traffic loops.
•Loop prevention is essential — Split horizon, poison reverse, triggered updates, and hold-down timers work together to minimize loop duration.
•Real convergence is complex — With all mechanisms, convergence takes about 180 seconds (hold-down dominated); without them, minutes of instability.

What's Next

Now that we understand how RIP computes routes, we'll examine its hop count metric in detail. Why was hop count chosen? What are its mathematical properties? How does the 15-hop limit affect network design? The next page explores RIP's metric system and its implications.

Page Complete

You now understand the theoretical and practical aspects of the distance vector algorithm. You can trace how routes propagate, predict convergence times, identify when counting-to-infinity occurs, and explain how loop prevention mechanisms work together. Next, we'll dive deep into RIP's hop count metric system.