Writing a robust, fully ordered multicast system in Python

Question

I need to write a reliable, fully ordered multicast system from scratch in Python. I can not use external libraries. I am allowed to use a central sequencer.

There seem to be two immediate approaches:

• write an efficient system by attaching a unique identifier to each multicast message, having the sequence numbers of the multicast sequence for the message identifier that it receives, and sends back and forth ACK and NACK.
• write an inefficient flooding system where each multicast just re-sends every message it receives once (unless it was sent by that particular multicast.)

I am allowed to use the second option, and I tend to do it.

I currently have multicast UDP messages (which seems to be the only option), but that means some messages may get lost. This means that I should be able to uniquely identify each sent UDP message so that it can be forwarded in accordance with No. 2. Do I really need to generate unique numbers (for example, using the sender address and the counter) and pack them in every UDP message sent? How can I do it? And how do I get one UDP message in Python and not a data stream (i.e. socket.recv )?

Answer 1

An approach to flooding can worsen the situation. If messages are discarded due to high network load, each repetition of each node, each message will only worsen the situation.

The best approach to selection depends on the nature of the data being sent. For instance:

• Multimedia data: no retries, a falling packet is a dropped frame, which does not matter when the next frame gets there.
• Fixed period data: The receiver node stores a reset timer each time an update is received. If time runs out, it requests the missing update from the node wizard. Retries can be unicast for the requesting node.

If none of these situations apply (each packet must be received by each node, and the packet time is unpredictable, so the recipients cannot independently detect the missing packets), then your options include:

• Explicit ACK from each node for each package. The sender repeats (unicast) any packet that is not ACKed.
• An approach to TCP-based networks, where each node manually repeats the received packets to neighboring nodes, relying on TCP mechanisms to ensure delivery.

Perhaps you can rely on recipients who notice a missed packet when receiving a number with a later sequence number, but this requires the sender to maintain the packet until at least one additional packet is sent. The requirement of positive ACKs is more reliable (and provable).

Answer 2

The approach you use will depend on the nature of the data being sent, the size of your network and the amount of data being sent. In particular, it will depend on the number of goals to which each of your nodes is connected.

If you expect this to scale for a large number of purposes for each node and a large amount of data, then you may well find that the overhead of adding ACK / NAK for each packet is sufficient to adversely limit your throughput, especially when you add repeated transfers to the mix.

According to Frank Shtserba, multimedia data has the advantage of recovering from lost packets. If you have any control over the data that you send, you should try to create a payload to minimize exposure to dropped packets.

If the data you send cannot carry dropped packets and you are trying to scale them to a high degree of utilization of your network, then perhaps udp is not the best protocol to use. Implementing a tcp proxy series (where each node retransmits, unicast, to all other related nodes - like your idea of ​​flooding) would be a more reliable mechanism.

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

---

Just saw the tag "homework" ... these suggestions may not be acceptable for problems with homework.