Skip to content
Tutorials Center
My learning

Topics

Lesson 75 of 79 ยท How the Web Works and Real-World Projects

Project: A Network Simulator with Routing

Build a network simulator in Python: routers and links, Dijkstra routing tables, hop-by-hop packet forwarding, TTL, traceroute and link failure recovery.

Routers are the part of the Internet that is hardest to see. You can watch a packet leave your computer and arrive at a server, but the dozen decisions in between happen inside machines you do not own. A simulator makes those decisions visible. In this project you build a small network in Python: routers connected by links with delays, routing tables computed by Dijkstra's algorithm, packets forwarded one hop at a time with a time to live, a working traceroute, and a network that heals itself when a link fails. Then you break it on purpose with a routing loop and watch the TTL save the day.

The ideas come from the routing chapter: routing and forwarding, link-state routing and Dijkstra and the IPv4 header's TTL field. Here they become about 80 lines of code. Everything runs live.

The model

Our simulated network is an undirected graph. Each router is a node, each link is an edge with a cost (think of it as milliseconds of delay), and each link can be up or down. The map used throughout the lesson is this one:

flowchart LR
    A((A)) ---|"4"| B((B))
    A ---|"2"| C((C))
    B ---|"1"| C
    B ---|"5"| D((D))
    C ---|"8"| D
    C ---|"10"| E((E))
    D ---|"2"| E
    D ---|"6"| F((F))
    E ---|"3"| F

Six routers and nine links. The numbers are link costs in milliseconds. The cheapest way from A to F is not the one with the fewest hops.

The simulator has three layers, which mirror real routers:

  1. Topology: the links and whether they are up.
  2. Control plane: every router runs Dijkstra on the topology and stores a routing table mapping each destination to a next hop and a total cost. Our simulator pretends link-state flooding has already given every router the full map, as OSPF does. That keeps the focus on routing itself.
  3. Data plane: a packet carries a destination and a TTL. At each router it is checked, its TTL is reduced, the table is consulted and the packet is sent to the next hop. The router never knows the complete path; it only knows the next hop. That is hop-by-hop forwarding.

Step 1: Dijkstra, step by step

Dijkstra's algorithm finds the cheapest path from one router to all others. It repeatedly settles the not-yet-settled router with the smallest known cost, then offers its neighbors a path through it. Python's heapq is a priority queue that always gives back the cheapest entry. An entry may be stale (a longer path to a router that was already settled), so the loop skips routers already in best.

The function below also remembers each router's parent, the router before it on its shortest path. Following parents backwards from a destination reconstructs the whole path, and the second router on that path is the next hop that goes into the routing table.

Python Step 1: Dijkstra on the map

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The settle order is 0, 2, 3, 8, 10, 13: costs only grow, which is why the algorithm is correct as long as no link has a negative cost. Notice that A reaches everything through C, even D, E and F, because the cheap detour A-C-B (3 ms) beats the direct A-B link (4 ms). The route to F uses five hops where a shorter-looking A-C-E-F uses only three, yet the five-hop route costs 13 ms against 15. The shortest path in cost is not the one with the fewest hops. Seen from D, the next hops are different: each router has its own view of the same map.

Step 2: routing tables, forwarding and traceroute

Now the whole simulator. A Network stores the links and the tables. converge() runs Dijkstra from every router and stores {destination: (next_hop, cost)}. send() is the data plane. At each router, in this order:

  1. If this router is the destination, the packet is delivered.
  2. Decrease the TTL. If it reaches zero, the packet is dropped (a real router would also send an ICMP "time exceeded" message back to the source, see ICMP).
  3. Look up the destination in the table. No entry means "no route to host".
  4. Check that the link to the next hop is up. Otherwise drop the packet.
  5. Move to the next hop and add the link's cost to the delay.

The returned Result lists every router the packet visited. That list is what makes a traceroute easy to build: send the same packet with TTL 1, then 2, then 3, and so on, and note where it expires. The router that expires the packet is the one at that distance. This is exactly the trick that the real traceroute command uses.

Python Step 2: send packets and run a traceroute

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The traceroute reveals the path even though no router knew it as a whole: A only knew "send it to C", C only knew "send it to B", and so on. The table at the end gives the delay for every pair of routers. It is symmetric here because links have the same cost in both directions; on the real Internet routes in the two directions often differ.

A network that never fails needs no routing protocol. The interesting behaviour is what happens when a link dies.

When a link goes down, two things happen in order:

  1. Before the routers react, their tables are still stale. A packet that follows the old table runs into the dead link and is dropped at the router next to it. This is a black hole, and it lasts until the failure has been noticed and flooded through the network. Real protocols take milliseconds to seconds for that, and engineers work hard to shrink the interval.
  2. After reconvergence, every router has recomputed its table with the failed link removed, and traffic flows along the second-best path.

The script cuts links one at a time, so you can see all of these effects: a detour with a higher delay, a detour through a different neighbour, and finally a destination that has become unreachable (no route at all, in both directions).

The last scenario creates a routing loop by hand. Two routers disagree: A believes the way to F is through C, while C believes it is through A. A packet bounces between them forever, or it would, if it did not carry a TTL. When the TTL runs out, the packet is dropped, so one bad entry cannot flood the links with immortal packets. That is the original reason for the TTL field.

Python Step 3: cut links, reconverge and create a loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study how the delay changes: 13 ms normally, 14 ms after D-E fails and traffic detours through D-F, and 15 ms after D-F also fails and traffic goes A-C-E-F. Each failure costs a little more delay but delivers the packet as long as any path exists. Only when F loses all its links does the sender receive nothing.

Real networks add more difficulty than the simulator shows. Routers learn about failures by exchanging messages, so their views temporarily disagree and transient loops can form during convergence. Protocols reduce the problem with techniques like split horizon in distance-vector routing and fast detection of dead links. Inter-domain routing with BGP is policy-driven, not purely cost-driven, and can take minutes to settle.

Ideas to extend it

  • Equal-cost multipath (ECMP). When two next hops have the same cost, keep both and pick one per flow with a hash of the addresses, as real routers do for load balancing.
  • Queues and bandwidth. Give each link a rate and a finite queue, simulate many packets over time, and watch congestion drop packets when a queue is full.
  • Link-state flooding. Instead of giving every router the full map, make routers exchange link-state messages, and measure how many rounds until all tables agree.
  • Distance-vector mode. Replace Dijkstra with the Bellman-Ford exchange from the distance-vector lesson and reproduce count-to-infinity.
  • Prefixes. Attach address prefixes to routers and look up destinations with longest-prefix match instead of exact names.
  • A scheduler. Process events (packet arrivals, link failures at time t) from a priority queue, so the simulation runs over time rather than in one function call.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a router's table store for each destination?

    Routers forward hop by hop. They need only the next hop; each following router makes its own decision with its own table.
  2. 2. In the simulator, why is the route A to F five hops long although a three-hop path (A, C, E, F) exists?

    Dijkstra minimizes the sum of link costs. The long path uses cheap links (2 + 1 + 5 + 2 + 3), while the short path uses the expensive C-E link (2 + 10 + 3).
  3. 3. How does traceroute discover the routers on a path?

    A router that decrements the TTL to zero drops the packet and reports back with an ICMP time-exceeded message, which reveals its address. Increasing the TTL step by step uncovers one hop at a time.
  4. 4. A link fails and the routers have not yet recomputed their tables. What happens to a packet that was routed over that link?

    Forwarding follows the table, and the table is stale. After the failure is noticed and the tables are recomputed, traffic takes the next-best path.
  5. 5. What stops a packet from circulating forever in a routing loop?

    The TTL bounds the lifetime of every packet in hops. A loop wastes some bandwidth, but it cannot grow without limit.

Summary

  • A simulator needs a topology (routers, links with costs, up/down state), a control plane that fills routing tables, and a data plane that forwards packets hop by hop.
  • Dijkstra settles routers in order of increasing cost and records parents; the first hop on each shortest path becomes the table entry.
  • Forwarding checks delivery, decrements the TTL, looks up the next hop and verifies the link. Drops have clear reasons: TTL expired, no route, link down.
  • Traceroute is a loop over increasing TTL values that records where each packet expires.
  • After a failure, stale tables cause a black hole until reconvergence; after it, traffic takes the next-best path, or fails if the destination is cut off.
  • The TTL limits the damage of routing loops, which is why every IP packet carries one.

Time to test what you have learned: practice addressing and routing exercises.