BGP and inter-domain routing in Computer Networks - Time & Space Complexity

Time Complexity: BGP and inter-domain routing

O(n * m)

Understanding Time Complexity

When studying BGP and inter-domain routing, it is important to understand how the time to process routing updates grows as the network size increases.

We want to know how the routing decisions and message exchanges scale when more networks connect.

Scenario Under Consideration

Analyze the time complexity of the following simplified BGP update processing.

for each received_update in updates:
    for each route in routing_table:
        if route conflicts with received_update:
            update route
    add new routes from received_update

This code processes each BGP update by checking existing routes and updating or adding routes accordingly.

Identify Repeating Operations

Look at the loops and repeated checks in the code.

• Primary operation: The inner loop that checks each route in the routing table for conflicts.
• How many times: For each update received, it loops through all routes in the routing table.

How Execution Grows With Input

As the number of updates and routes grows, the work increases.

Input Size (n)	Approx. Operations
10 updates, 10 routes	About 100 checks
100 updates, 100 routes	About 10,000 checks
1000 updates, 1000 routes	About 1,000,000 checks

Pattern observation: The number of operations grows quickly as both updates and routes increase, roughly multiplying together.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to process updates grows proportionally to the number of updates times the number of routes.

Common Mistake

[X] Wrong: "Processing each update takes the same fixed time regardless of routing table size."

[OK] Correct: Each update must be checked against many routes, so more routes mean more work and longer processing time.

Interview Connect

Understanding how routing update processing scales helps you explain network performance and design choices clearly in discussions or interviews.

Self-Check

What if the routing table used a data structure that allows faster lookups? How would the time complexity change?