Distance vector routing (RIP) in Computer Networks - Time & Space Complexity

Time Complexity: Distance vector routing (RIP)

O(n^2)

Understanding Time Complexity

When studying Distance Vector Routing, it is important to understand how the routing updates scale as the network grows.

We want to know how the time to update routing tables changes when more routers join the network.

Scenario Under Consideration

Analyze the time complexity of the routing update process in RIP.

for each router in network:
    for each neighbor of router:
        send routing table to neighbor
    for each entry in routing table:
        update distance if better path found
    wait for next update interval
    

This code shows how each router sends its routing table to neighbors and updates its own table based on received information.

Identify Repeating Operations

Look at what repeats during the routing update process.

• Primary operation: Each router sends its routing table to all neighbors and updates its table entries.
• How many times: For each router, this happens once per update interval, and involves checking all neighbors and all routing entries.

How Execution Grows With Input

As the number of routers (n) increases, each router has more neighbors and more routing entries to process.

Input Size (n)	Approx. Operations
10	About 10 routers x neighbors x 10 entries
100	About 100 routers x neighbors x 100 entries
1000	About 1000 routers x neighbors x 1000 entries

Pattern observation: The work grows roughly with the square of the number of routers because each router processes information about many others.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to update routing tables grows roughly with the square of the number of routers in the network.

Common Mistake

[X] Wrong: "The update time grows linearly with the number of routers because each router only sends updates once."

[OK] Correct: Each router must process routing information about many others, so the total work grows faster than just the number of routers.

Interview Connect

Understanding how routing protocols scale helps you think clearly about network performance and design, a useful skill in many technical roles.

Self-Check

"What if routers only sent updates when their routing tables changed? How would that affect the time complexity?"