20.16 Building a Packet Routing Simulation
Design a simulation that routes packets through a network of routers and links.
20.16 Building a Packet Routing Simulation
Problem
Design a simulation that routes packets through a network of routers and links. The simulator should model topology, forwarding decisions, link costs, queues, packet delivery, and packet loss.
Packet routing appears in computer networks, distributed systems, data centers, sensor networks, peer-to-peer systems, and game networking. A simulator lets you test routing policies without deploying them to real infrastructure.
Given this topology:
A --1-- B --1-- C
| |
4 2
| |
D --1-- E
A packet from A to C should normally take:
A -> B -> C
because the total cost is:
1 + 1 = 2
The simulator should answer questions such as:
Which route does a packet take?
What happens when a link fails?
Where do queues grow?
How many packets are dropped?
How does routing change when costs change?
The core algorithmic problem is shortest-path forwarding. The engineering problem is modeling time, queues, events, and failure behavior clearly enough to make the simulation useful.
Solution
Represent the network as a weighted graph. Compute forwarding tables using shortest paths. Represent packet movement as discrete events. At each simulation step, routers forward packets according to their next-hop table.
Start with graph representation:
from collections import defaultdict, deque
import heapq
import itertools
import math
class Network:
def __init__(self):
self.links = defaultdict(dict)
def add_link(self, left, right, cost=1, capacity=1):
self.links[left][right] = {
"cost": cost,
"capacity": capacity,
"up": True,
}
self.links[right][left] = {
"cost": cost,
"capacity": capacity,
"up": True,
}
def neighbors(self, node):
for neighbor, link in self.links[node].items():
if link["up"]:
yield neighbor, link
This models an undirected network with link costs, capacities, and failure state.
Computing Shortest Paths
Each router needs a next hop for each destination.
For one source router, run Dijkstra and record predecessors.
def dijkstra(network, source):
distances = defaultdict(lambda: math.inf)
previous = {}
distances[source] = 0
heap = [(0, source)]
while heap:
current_distance, node = heapq.heappop(heap)
if current_distance != distances[node]:
continue
for neighbor, link in network.neighbors(node):
candidate = current_distance + link["cost"]
if candidate < distances[neighbor]:
distances[neighbor] = candidate
previous[neighbor] = node
heapq.heappush(heap, (candidate, neighbor))
return distances, previous
Convert shortest-path predecessors into next hops.
def next_hop_to(previous, source, destination):
if source == destination:
return destination
if destination not in previous:
return None
node = destination
while previous[node] != source:
node = previous[node]
if node not in previous:
return None
return node
Build a forwarding table for one router:
def forwarding_table_for(network, source):
distances, previous = dijkstra(network, source)
table = {}
for destination, distance in distances.items():
if destination == source:
continue
hop = next_hop_to(previous, source, destination)
if hop is not None:
table[destination] = {
"next_hop": hop,
"cost": distance,
}
return table
Build tables for every router:
def build_forwarding_tables(network):
return {
router: forwarding_table_for(network, router)
for router in network.links
}
The forwarding table turns global shortest-path computation into local routing decisions.
Packet Model
A packet needs an identifier, source, destination, current location, and route history.
from dataclasses import dataclass, field
@dataclass
class Packet:
id: str
source: str
destination: str
current: str
created_at: int
path: list = field(default_factory=list)
delivered_at: int | None = None
dropped: bool = False
Create a packet:
def make_packet(packet_id, source, destination, time):
return Packet(
id=packet_id,
source=source,
destination=destination,
current=source,
created_at=time,
path=[source],
)
The path is useful for debugging and reporting.
Router Queues
Each router has a queue of packets waiting to be forwarded.
class RouterState:
def __init__(self, queue_limit=100):
self.queue = deque()
self.queue_limit = queue_limit
self.dropped = 0
def enqueue(self, packet):
if len(self.queue) >= self.queue_limit:
packet.dropped = True
self.dropped += 1
return False
self.queue.append(packet)
return True
The queue limit lets the simulator model congestion and packet loss.
Simulation State
The simulator owns the network, forwarding tables, router queues, and metrics.
class RoutingSimulation:
def __init__(self, network, queue_limit=100):
self.network = network
self.tables = build_forwarding_tables(network)
self.routers = {
node: RouterState(queue_limit)
for node in network.links
}
self.time = 0
self.delivered = []
self.dropped = []
self.packet_counter = itertools.count()
def inject(self, source, destination):
packet_id = f"p{next(self.packet_counter)}"
packet = make_packet(
packet_id,
source,
destination,
self.time,
)
accepted = self.routers[source].enqueue(packet)
if not accepted:
self.dropped.append(packet)
return packet
Injecting a packet places it into the source router queue.
Forwarding One Step
At each time step, each router forwards a limited number of packets. This models finite link capacity.
class RoutingSimulation(RoutingSimulation):
def step(self):
outgoing = []
for router_id, router_state in self.routers.items():
if not router_state.queue:
continue
packet = router_state.queue.popleft()
if packet.destination == router_id:
packet.delivered_at = self.time
self.delivered.append(packet)
continue
table = self.tables.get(router_id, {})
entry = table.get(packet.destination)
if entry is None:
packet.dropped = True
self.dropped.append(packet)
continue
next_hop = entry["next_hop"]
outgoing.append((next_hop, packet))
for next_hop, packet in outgoing:
packet.current = next_hop
packet.path.append(next_hop)
accepted = self.routers[next_hop].enqueue(packet)
if not accepted:
self.dropped.append(packet)
self.time += 1
This version allows each router to forward at most one packet per tick. Link capacity is present in the network model, but not yet enforced per link. That is a useful next extension.
Running the Simulation
Create a topology:
network = Network()
network.add_link("A", "B", cost=1)
network.add_link("B", "C", cost=1)
network.add_link("A", "D", cost=4)
network.add_link("D", "E", cost=1)
network.add_link("E", "B", cost=2)
sim = RoutingSimulation(network)
packet = sim.inject("A", "C")
while not packet.delivered_at and not packet.dropped:
sim.step()
print(packet.path)
print(packet.delivered_at)
Expected path:
['A', 'B', 'C']
The packet reaches C through the least-cost route.
Link Failures
A routing simulation becomes more useful when topology changes.
class Network(Network):
def set_link_state(self, left, right, up):
self.links[left][right]["up"] = up
self.links[right][left]["up"] = up
When a link changes, recompute forwarding tables.
class RoutingSimulation(RoutingSimulation):
def fail_link(self, left, right):
self.network.set_link_state(left, right, False)
self.tables = build_forwarding_tables(self.network)
def restore_link(self, left, right):
self.network.set_link_state(left, right, True)
self.tables = build_forwarding_tables(self.network)
Example:
sim.fail_link("A", "B")
Now packets from A to C should route through:
A -> D -> E -> B -> C
if that path remains available.
Routing Loops
A routing loop occurs when packets circulate instead of reaching the destination.
Example:
A forwards to B
B forwards to A
With consistent shortest-path tables computed from the same topology, loops should not occur. But loops can appear when routers have stale or inconsistent tables.
Add a time-to-live field.
@dataclass
class Packet:
id: str
source: str
destination: str
current: str
created_at: int
ttl: int = 32
path: list = field(default_factory=list)
delivered_at: int | None = None
dropped: bool = False
During forwarding:
packet.ttl -= 1
if packet.ttl <= 0:
packet.dropped = True
self.dropped.append(packet)
continue
TTL prevents infinite circulation. It also gives the simulator a way to detect routing instability.
Modeling Link Capacity
The earlier step method limits each router to one outgoing packet per tick. Real links have capacities. A router may send one packet over link A-B and one packet over link A-D in the same tick, but not unlimited packets over the same link.
Track per-link usage in each tick.
def link_key(left, right):
return tuple(sorted((left, right)))
During a step:
usage = defaultdict(int)
Before forwarding over a link:
key = link_key(router_id, next_hop)
capacity = self.network.links[router_id][next_hop]["capacity"]
if usage[key] >= capacity:
router_state.queue.appendleft(packet)
continue
usage[key] += 1
outgoing.append((next_hop, packet))
This models contention. Packets that cannot use a saturated link wait in the router queue.
Event-Driven Simulation
A step-based simulation is simple. Every tick, it checks all routers. This is fine for small networks.
For larger simulations, use an event queue.
Events:
packet_arrives(router, packet)
link_fails(left, right)
link_recovers(left, right)
inject_packet(source, destination)
Priority queue by time:
class EventQueue:
def __init__(self):
self.heap = []
self.counter = itertools.count()
def push(self, time, event):
heapq.heappush(
self.heap,
(time, next(self.counter), event),
)
def pop(self):
if not self.heap:
return None
return heapq.heappop(self.heap)
Event-driven simulation skips idle time and can model variable link latency more naturally.
Metrics
A routing simulator should produce metrics, not only packet paths.
Track:
| Metric | Meaning |
|---|---|
| delivered_count | Packets that reached destination |
| dropped_count | Packets lost due to queue overflow, no route, or TTL |
| average_latency | Delivery time minus creation time |
| max_queue_size | Congestion indicator |
| per_router_drops | Where loss occurs |
| per_link_usage | Which links are hot |
| path_stretch | Actual path cost divided by shortest possible cost |
| reroute_count | Number of packets affected by topology changes |
Example latency calculation:
def average_latency(packets):
latencies = [
packet.delivered_at - packet.created_at
for packet in packets
if packet.delivered_at is not None
]
if not latencies:
return None
return sum(latencies) / len(latencies)
Metrics make simulation results comparable across routing policies.
Testing
Test shortest route selection.
def test_packet_uses_shortest_path():
network = Network()
network.add_link("A", "B", cost=1)
network.add_link("B", "C", cost=1)
network.add_link("A", "C", cost=5)
sim = RoutingSimulation(network)
packet = sim.inject("A", "C")
while packet.delivered_at is None and not packet.dropped:
sim.step()
assert packet.path == ["A", "B", "C"]
Test no route:
def test_packet_drops_when_no_route():
network = Network()
network.add_link("A", "B", cost=1)
network.add_link("C", "D", cost=1)
sim = RoutingSimulation(network)
packet = sim.inject("A", "D")
sim.step()
assert packet.dropped is True
Test failure rerouting:
def test_link_failure_changes_route():
network = Network()
network.add_link("A", "B", cost=1)
network.add_link("B", "C", cost=1)
network.add_link("A", "D", cost=2)
network.add_link("D", "C", cost=2)
sim = RoutingSimulation(network)
sim.fail_link("A", "B")
packet = sim.inject("A", "C")
while packet.delivered_at is None and not packet.dropped:
sim.step()
assert packet.path == ["A", "D", "C"]
Small deterministic networks make routing behavior visible and testable.
Common Bugs
The most common simulation bug is mixing routing computation and packet movement too tightly. Keep topology, forwarding tables, packet state, and simulation time separate.
Another common bug is failing to recompute forwarding tables after link failures or cost changes.
Shortest-path forwarding can produce no route when the graph is disconnected. Handle that as packet drop or delivery failure, not as a crash.
Step-based simulations can accidentally allow packets to move multiple hops in one tick. Use an outgoing buffer so movement from this tick becomes visible after all routers have acted.
Queue overflow must mark packets as dropped. Silent loss makes metrics impossible to trust.
Routing-loop tests require TTL. Without TTL, bad policies can hang the simulation.
Link capacity is often modeled globally instead of per link. Capacity should apply to a specific link and time interval.
Recipe
Build the simulator in layers.
Start with a weighted graph. Compute forwarding tables with Dijkstra. Represent packets with source, destination, current router, path, and timestamps. Give each router a queue. Advance the simulation in ticks, forwarding packets through next-hop tables. Add link failures and table recomputation. Add TTL to detect loops. Add link capacity to model congestion. Move to event-driven simulation when idle ticks become expensive. Track delivery, drops, latency, queue sizes, and link utilization.
The main lesson is that routing simulation combines graph algorithms with discrete-event modeling. Shortest paths decide where packets should go, but queues, capacities, failures, and time determine what actually happens.