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).

Answer 2

The approach you take is going to depend very much on the nature of the data that you're sending, the scale of your network and the quantity of data you're sending. In particular it is going to depend on the number of targets each of your nodes is connected to.

If you're expecting this to scale to a large number of targets for each node and a large quantity of data then you may well find that the overhead of adding an ACK/NAK to every packet is sufficient to adversely limit your throughput, particularly when you add retransmissions into the mix.

As Frank Szczerba has said multimedia data has the benefit of being able to recover from lost packets. If you have any control over the data that you're sending you should try to design the payloads so that you minimise the susceptibility to dropped packets.

If the data that you're sending cannot tolerate dropped packets and you're trying to scale to high utilisation of your network then perhaps udp is not the best protocol to use. Implementing a series of tcp proxies (where each node retransmits, unicast, to all other connected nodes - similar to your flooding idea) would be a more reliable mechanism.

With all of that said, have you considered using true multicast for this application?

---

Just saw the "homework" tag... these suggestions might not be appropriate for a homework problem.