AP® Computer Science Principles · Big Idea 4 · Topic 4.1

Paths and Routing Between Two Devices

Routing is the process of moving a packet from device to device, each router choosing the best next hop, until the packet reaches its destination. No single device knows the whole path in advance.

The internet is a mesh of directly connected devices, not a single wire from you to anywhere. A message gets broken into packets, and each packet hops from one connected device to the next, like a letter passed hand to hand through a crowd rather than carried by one runner. No device needs to know the full route. Each one only needs to know a good next step.

That next step comes from a routing table, a list each router keeps that maps destination addresses to the neighboring device it should forward toward next. When a packet arrives, the router checks the destination address, looks up the best-known next hop, and sends it on. The next router does the same, and so on, until the packet lands at its destination. Because conditions change constantly, link traffic, congestion, outages, routers update these tables, so the next hop chosen for a packet can differ from one moment to the next.

This is why routing is decided packet by packet instead of once per transfer. Ten packets from the same file can take ten different paths and still all arrive, maybe out of order, to be reassembled at the receiver. This per-packet, adaptive routing is also what gives the network fault tolerance: if one router in the middle goes offline, its neighbors notice their routes through it no longer work, update their tables, and reroute packets through other connected devices. That resilience connects directly to why the internet as a whole keeps functioning even when individual pieces fail.

Key terms

Packet
A small chunk of a larger message, sent with addressing information so it can be routed independently.
Routing table
A list a router keeps that maps destinations to the best next device to forward a packet toward.
Next hop
The one directly connected device a router sends a packet to next, not the final destination.
Fault tolerance
A network's ability to keep delivering packets even when some devices or links fail.

Watch it explained

  1. How it worksHow does routing find a path from sender to receiver through directly connected devices?
  2. How it worksHow does a router use its routing table to pick the very next device to forward a packet to?
  3. Worked exampleTrace a path from sender to receiver through a six node network offering three possible routes.
  4. Common mistakeWhy isn't the route between two computers decided in advance and then kept?
  5. Going furtherWhat happens to routing when one of the devices in the middle suddenly goes offline?

Check yourself

Your turn1 of 2
A network offers 15 possible routes from sender to receiver. A routing table update removes 2 of them from consideration due to a link failure. How many possible routes remain?

End of topic.