Writing a reliable, totally-ordered multicast system in Python

Question

I have to write a reliable, totally-ordered multicast system from scratch in Python. I can't use any external libraries. I'm allowed to use a central sequencer.

There seems to be two immediate approaches:

1. write an efficient system, attaching a unique id to each multicasted message, having the sequencer multicast sequence numbers for the message id's it receives, and sending back and forth ACK's and NACK's.
2. write an inefficient flooding system, where each multicaster simply re-sends each message it receives once (unless it was sent by that particular multicaster.)

I'm allowed to use the second option, and am inclined to do so.

I'm currently multicasting UDP messages (which seems to be the only option,) but that means that some messages might get lost. That means I have to be able to uniquely identify each sent UDP message, so that it can be re-sent according to #2. Should I really generate unique numbers (e.g. using the sender address and a counter) and pack them into each and every UDP message sent? How would I go about doing that? And how do I receive a single UDP message in Python, and not a stream of data (i.e. socket.recv)?

Answer 1

The flooding approach can cause a bad situation to get worse. If messages are dropped due to high network load, having every node resend every message will only make the situation worse.

The best approach to take depends on the nature of the data you are sending. For example:

1. Multimedia data: no retries, a dropped packet is a dropped frame, which won't matter when the next frame gets there anyway.
2. Fixed period data: Recipient node keeps a timer that is reset each time an update is received. If the time expires, it requests the missing update from the master node. Retries can be unicast to the requesting node.

If neither of these situations applies (every packet has to be received by every node, and the packet timing is unpredictable, so recipients can't detect missed packets on their own), then your options include:

1. Explicit ACK from every node for each packet. Sender retries (unicast) any packet that is not ACKed.
2. TCP-based grid approach, where each node is manually repeats received packets to neighbor nodes, relying on TCP mechanisms to ensure delivery.

You could possibly rely on recipients noticing a missed packet upon reception of one with a later sequence number, but this requires the sender to keep the packet around until at least one additional packet has been sent. Requiring positive ACKs is more reliable (and provable).