4.1 Packets, routing and scalabilityMessages travel in pieces

Information is passed through the internet as a data stream, and the stream is broken into chunks. Each chunk is wrapped in a packet. A packet holds a chunk of data plus metadata: extra information used to route the packet from its origin to its destination and to reassemble the data when it gets there.
?Wait, what's metadata again?
| Part of a packet | Who uses it | What for |
|---|---|---|
| Destination address | Every router on the way | To pick the next hop toward the receiver |
| Source address | The receiver | To know where to send a reply |
| Packet number (and total) | The receiver | To put the pieces back in order and notice gaps |
| Chunk of data | The receiving program | One small piece of the message itself |
Because routing is dynamic, each packet is routed on its own. A router reads the destination address and forwards the packet toward it, choosing among its connections based on what's working and what's busy right now. So the packets of one message can travel different paths, arrive at different times and arrive out of order. Some may not arrive at all. That's normal, not an error, and the metadata is there so the receiver can cope.
Why chop messages up at all? Small packets share the network fairly: your big download doesn't block everyone else's messages, because packets from many senders take turns on each link. And if one packet is lost, only that small piece needs to be sent again, not the whole file.
The same design is what makes the internet scalable. Scalability is the capacity of a system to change in size and scale to meet new demands. A new network joins by connecting to existing ones and following the same rules, with no central switchboard to rebuild. That's how a project that linked a few research computers grew to billions of devices.
?Wait, how many different values can n bits represent?
Beyond the course, as a bonus: the original internet addresses (IPv4) are 32 bits, which allows 2³² = 4,294,967,296 addresses. That sounded like plenty in the 1980s and ran short as phones arrived. The newer IPv6 uses 128-bit addresses, so the internet could keep scaling.
I thought about it. Show me
1PROCEDURE isMissing(received, num)2{3 FOR EACH p IN received14 {15 IF (p = num)16 {17 RETURN(false)18 }19 }110 RETURN(true)11}12arrived ← [4, 1, 6, 2, 3]13num ← 114REPEAT 6 TIMES215{16 IF (isMissing(arrived, num))17 {18 DISPLAY(num)19 }20 num ← num + 121}
- line 3-9 look at every packet number that arrived
- line 14 check the numbers 1 to 6, one at a time
- num starts at 1. isMissing(arrived, 1) loops over 4, 1, ... and finds p = 1, so it returns false. Nothing is displayed.
Why?
RETURN ends the procedure immediately, the moment a match is found. - num = 2, 3 and 4: each one is in the list, so isMissing returns false each time.
- num = 5: the FOR EACH loop checks 4, 1, 6, 2, 3 and never finds 5. The loop ends and the procedure reaches RETURN(true). DISPLAY(5) runs.
- num = 6: found, so nothing is displayed. The REPEAT loop has now run 6 times and stops.
- The order doesn't matter because isMissing checks every element of the list. Any order of the same numbers gives the same answer.
Why?
This is the job TCP does for real: use the packet numbers to spot the gap and ask for that packet again.
Answer: It displays 5. isMissing scans the whole list, so the arrival order does not change the result.
Stuck? Get a hint
- isMissing returns true only if the FOR EACH loop finishes without finding num.
- Go through num = 1, 2, 3, 4, 5, 6 and ask: is it in [4, 1, 6, 2, 3]?
- Only one number from 1 to 6 is not in the list.
- AAll 800 packets must follow the same path, so they arrive in order.
- BRouters choose the whole path before the first packet leaves.
- CThe packets may take different paths and arrive out of order, and metadata helps the receiver reassemble them.
- DEach packet carries a full copy of the file in case the others are lost.
Show the answer
C. Each packet is routed on its own, so packets can take different paths and arrive in any order, and some can be lost. The second choice is the subtle trap: on the internet, routing is dynamic, decided router by router as packets travel.
- Data is sent as packets: a chunk of data plus metadata (destination, source, packet number).
- Packets can take different paths and arrive in order, out of order, or not at all.
- The receiver uses the metadata to reassemble the message.
- Scalability: the internet can grow to meet new demand by adding networks and devices that follow the same rules.