AP Computer Science Principles · Unit 4 lecture · Part 3 of 11 · 9 min

4.1 Packets, routing and scalabilityMessages travel in pieces

Mr. Thompkins
Here's something that sounds like it couldn't possibly work. Your message is chopped into little pieces, the pieces are sent separately, they take different roads, some show up late, some get lost, and somehow the other side still reads it perfectly. Let's see how.

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?
Metadata is data about data, from Unit 2. A photo's metadata might be the date, the camera and the location. A packet's metadata is its destination address, its source address and its place in the order. It describes the chunk; it isn't the chunk.
Part of a packetWho uses itWhat for
Destination addressEvery router on the wayTo pick the next hop toward the receiver
Source addressThe receiverTo know where to send a reply
Packet number (and total)The receiverTo put the pieces back in order and notice gaps
Chunk of dataThe receiving programOne small piece of the message itself
What a packet carries, and who reads each part. Routers need the destination. The receiver needs the numbers.

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.

MEET AT NOON1: MEE2: T A3: T N4: OONrouted separately, different paths3: T N1: MEE4: OON2: lostarrived: 3, 1, 4. Number 2 never cameTCP: ask for 2 again, then sortUDP: hand over 3, 1, 4 as they are
One short message as four packets. They arrive as 3, 1, 4, and packet 2 is lost. The packet numbers let the receiver notice the gap and rebuild the order.

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?
n bits can represent 2ⁿ different values, from Unit 2. 8 bits give 2⁸ = 256 values. That matters for addresses: every device needs a different one, so the number of bits in an address limits how many devices can have one.

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.

Pause and think
A 1,500,000-byte file is sent in packets that each carry 1,000 bytes of data. How many packets is that, and what happens to the download if just one of them is lost and the protocol in use resends lost packets?
I thought about it. Show me
1,500,000 ÷ 1,000 = 1,500 packets. If one is lost, only that one packet is sent again. The other 1,499 don't need to be resent, which is one big reason messages are split up.
Trace the code: which packets are missing?
A receiver got packets numbered 4, 1, 6, 2, 3 of a 6-packet message. The pseudocode below checks each number from 1 to 6. What does it display, and why does the order in which the packets arrived not matter to the answer?
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}
  1. line 3-9 look at every packet number that arrived
  2. line 14 check the numbers 1 to 6, one at a time
output › 5
  1. 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.
  2. num = 2, 3 and 4: each one is in the list, so isMissing returns false each time.
  3. 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.
  4. num = 6: found, so nothing is displayed. The REPEAT loop has now run 6 times and stops.
  5. 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
  1. isMissing returns true only if the FOR EACH loop finishes without finding num.
  2. Go through num = 1, 2, 3, 4, 5, 6 and ask: is it in [4, 1, 6, 2, 3]?
  3. Only one number from 1 to 6 is not in the list.
Check yourself
A video file is sent across the internet as 800 packets. Which statement is true?
  1. AAll 800 packets must follow the same path, so they arrive in order.
  2. BRouters choose the whole path before the first packet leaves.
  3. CThe packets may take different paths and arrive out of order, and metadata helps the receiver reassemble them.
  4. 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.