Detecting missing messages

Before you can deal with a problem, you have to spot it. Error detection is therefore an important part of programming.

Error detection

At the end of the previous step you were asked how you could determine whether a pixel had been lost, and what you could do about it.

There are countless possible options, but some that you may have considered are:

• Counting pixels received and making assumptions about how many should have been received
• Identifying gaps in the image that has been received
• Filling in empty pixels with the colour of the pixels surrounding it

The answers to these questions are techniques for error detection and correction.

Many of the approaches to detecting errors in unreliable communication are hampered by the fact that you may not even know when a message was not received or never sent. Due to this, you may have to make assumptions and best guesses. This is another reason why many real-world applications use a mix of reliable and unreliable communication.

You will now implement a simple algorithm to detect whether a message has been lost. By simulating data loss, you can investigate ways of improving error detection.

Missing pixels

For the moment, assume that the pixels are received in the order in which they are sent. Therefore, if a pixel is received out of sequence, we can assume that a message has been lost.

This simple error detection algorithm will work like this:

1. Receive a pixel.
2. Store the position of the pixel received.
3. Receive a new pixel.
4. Ask whether the position of the new pixel is more than 1 greater in x or y than the last pixel.
5. If so, a pixel has been lost.

Change your get_pixel_data function to implement this algorithm:

1. At the top of your program, create two new variables to hold the number of lost pixels and the last pixel that was updated.

   lost_pixels = 0
   last_pixel_updated = (-1, -1)
   

2. Output how many pixels have been lost to the image viewer.

   viewer.text = lost_pixels
   

3. Check to see whether the pixel received is out of sequence. Compare the position of the pixel received to the position of the last one received, and update the last_pixel_updated variable.

    if (pos[0] - last_pixel_updated[0] > 1) or (pos[1] - last_pixel_updated[1] > 1):
    lost_pixels += 1
    viewer.text = lost_pixels
   
    last_pixel_updated = pos
   

4. Run your program again. You will see that a count of lost pixels has appeared at the top of the image viewer.

It could be that, like mine, your lost pixel count is showing as zero! This could be because no pixels were lost, and is particularly likely if you are running your sending and receiving programs on the same computer.

Simulating lost packets

To test and ensure that your error detection is working, you can simulate losing pixels by randomly choosing not to send some of them.

1. Import the randint function, which you can use to generate random numbers to use in deciding whether to send a packet.

   from random import randint
   

2. To understand how well the error detection is working, you should keep a count of the pixels “lost”.

   pixels_lost = 0
   

3. Use randint to decide randomly whether to send a pixel or not.

    if randint(0,9) > 0:
    udp_client.sendto(data, ("127.0.0.1", 20001))
    else:
    pixels_lost += 1
   

   The function randint(0,9) will return a random number between 0 and 9. The condition randint(0,10) > 0 will return True and send the pixel if the random number returned by randint is 1 or higher. Therefore, anytime a 0 is returned by randint a pixel won’t be sent, so you should expect to lose about 10% of all the pixels. You can change the error rate by modifying this formula.

4. Print the number of pixels “lost” when the complete image has been sent.

   print(pixels_lost)
   

5. Run your two programs and compare the number of pixels you simulated as being lost and the number you detected as being lost. In my example, I lost 1,322 pixels, but detected only 1,162 being lost.

Improving the error detection

The algorithm I created to detect errors is finding about 88% of all errors. That’s quite good, but it could be better.

Try changing the error detection algorithm in the receiving program to improve the detection rate, you can also edit the sending program to send more information to help you.

Here are some pointers to get you started improving the existing error detection algorithm:

1. When more than one pixel in sequence is lost, only one is counted. For example, if three pixels between the positions (0,1) and (0,3) were lost, the count is only incremented by one.
2. When pixels are received out of order, subsequent pixels will be detected as lost even though they may later be received. For example, if four pixels were received in the order (0,4) (0,6) (0,5), (0,7), pixels (0,5) and (0,7) would be marked as lost because they didn’t arrive in order.

Share your new programs in the comments section using a Pastebin link. Remember that you can ask for help if you need it!