Project: a reliable link

Receive a route as packets out of order, reject the damaged one, and drive it.

A12.10Networks and the webA level35 min

The radio drops, delays and damages messages, just as a real network does. In this project the Base station sends the robot a route to drive, split into packets. They arrive out of order, and one is damaged on the way. Your robot must do what the transport layer of TCP/IP does for every web page you load: check each packet, ask for a damaged one again, put them back in order, and only then act on the whole message.

What the project uses

The packet format

Each packet is text:

<number>/<total>:<command>*<checksum>

For example 1/3:forward 30*45. The checksum is the one from A12.4: add the character codes of everything before the *, take the result modulo 256, and write it as two uppercase hexadecimal digits.

How a single bit is caught

In transit, one bit of packet 2 flips. The character 2 is code 50, 00110010; flip the bit worth 4 and it becomes 00110110, which is 54, the character 6. The command right 20 now reads right 60, which would drive the robot off course. The sum of the codes has gone up by 4, so the checksum no longer matches:

def checksum(text):
    total = 0
    for ch in text:
        total = total + ord(ch)
    return format(total % 256, "02X")

sent = "2/3:right 20"
received = "2/3:right 60"
print(format(ord("2"), "08b"), "->", format(ord("6"), "08b"))
print("checksum sent:", checksum(sent), " checksum of what arrived:", checksum(received))

# the weakness: swapping two characters leaves the sum unchanged
print("swapped:", checksum("2/3:right 02"))

Run this in the simulator

A simple sum catches any single-bit error, but not two characters swapped, or two errors that cancel out. Real protocols use stronger checks: TCP uses a 16-bit checksum over its segments, and Ethernet and Wi-Fi frames end with a 32-bit cyclic redundancy check (CRC). The receiver's side of the protocol is the same whatever the check: if it fails, throw the packet away and get it again.

Designing the program

Split the job into two parts, the way the layers split a network:

1. Receive: listen until every packet of the message is held and good. For each packet that arrives, split off the checksum at the *, then the header at the :, then the number and total at the /. Recalculate the checksum. If it matches, store the command under its number and send ACK <number>. If not, discard it and send NAK <number>, which makes the Base send it again.
2. Act: only when every packet is held, go through the numbers 1 to the total in order and drive each command.

In OCR-style pseudocode, the receive part is:

good = {}
total = 0
while total == 0 OR good.length < total
    for each message received
        body, check = split message at the last "*"
        header, command = split body at the first ":"
        number, count = split header at "/"
        if checksum(body) == check then
            good[number] = command
            total = count
            send("ACK " + number)
        else
            send("NAK " + number)
        endif
    next message
endwhile

Why acknowledge good packets as well? Without an ACK, the sender cannot tell a packet that arrived from one that was lost altogether. A real sender starts a timer for every packet and sends it again if no ACK arrives in time; that covers lost packets as well as damaged ones.

Task: a reliable link

The robot starts facing forward. The Base sends a route of three packets in the format above, one every half second, out of order. One packet arrives damaged. When the Base hears NAK <number>, it sends that packet again.

1. Receive: check messages() every 0.1 s. For each packet, recalculate its checksum. If it matches, store the command under the packet's number and send ACK <number>. If it does not, print packet <number> corrupt and send NAK <number>. Keep going until you hold a good copy of every packet, as many as the total in the header says.
2. Act: for each number from 1 to the total, in order, print run: <command>, then drive it at speed 50. A command is a direction (forward, backward, left or right, where left and right slide sideways) and a whole number of centimetres.
3. Send DONE.

Do not drive until every packet is held, and read the route from the packets rather than typing it. If you act on the damaged packet, you will end up in the red zone.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def checksum(text):
    total = 0
    for ch in text:
        total = total + ord(ch)
    return format(total % 256, "02X")

wait(3)
for sender, text in messages():
    print(text)

Challenges

1. Count how many packets you received in total, including the damaged one, and print the fraction that were good.
2. Ignore a duplicate: if a good packet you already hold arrives again, acknowledge it but do not store it twice. Why must you still send the ACK?
3. Replace the checksum with one that notices two characters being swapped, for example by multiplying each code by its position before adding. Test it with the swapped example in the cell.