What's the most efficient protocol for reliable multicast?

Question

When a sender needs to multicast a relatively large volume of data (say several megabytes per second) in a reliable way over Ethernet to a modest number of receivers (say less than a dozen) on the same subnet, what is the most efficient protocol? By reliable I mean that if a packet is lost, the protocol ensures that it gets resent such that there is no data loss in any receiver. The term efficient is a lot harder to define, but let's say we want to maximize throughput and minimize network bandwidth with modest CPU usage on both ends. That's still not a clear-cut definition but it's the best I can come up with. Either a stream-oriented or a message-oriented protocol would be acceptable.

I'd appreciate real-world examples and I'll gladly accept subjective answers, i.e. what's your favorite multicast protocol, if you can explain its pros and cons.

Answer 1

BitTorrent!

No, seriously. You might want to read up on it.

UDP is useful for multicast but it doesn't provide the guarantees you're looking for - BitTorrent will require you to transmit more than one full copy from the original source, but it's still fairly efficient and provides useful guarantees, especially considering how much checksumming is done on each "chunk" of data passed along.

Answer 2

Real-world example: TIBCO Rendezvous.

Data is sent out via multicast with a sequence number. A client that detects a missing sequence number sends out a messge on the multicast group "hey, I missed packet 12345". The server re-multicasts out that data. The server has a configurable amount of data to buffer in case a client requests it.

The problem:

Imagine having a single client that drops half of his packets, and 100 healthy clients. This client sends a retransmission request for every other packet. The server begins to cause enough load on one of the healthy clients such that it starts dropping packets and requesting retransmissions. The extra load from that causes another healthy client to begin requesting retransmissions. And so on. A congestion collapse results.

Tibco provides a workaround, of cutting off a subscriber that sends too many retransmission requests. This makes it harder for a single subscriber to cause a congestion collapse.

The other workaround to limit the risk of congestion collapse is to limit the amount of data that a server is willing to retransmit.

Tibco should also provide heuristics in the client and server as to whether to multicast or unicast the retransmission request, and the retransmission itself. They don't. (For the server, you could unicast the retransmission if only one client requested it in a certain time window, for the client you could unicast the retransmission request if the server has told you - in the retransmitted packet - that you are the only one requesting retransmissions and to please unicast the requests in the future)

Fundamentally you will have to decide between how strongly you want to guarantee that clients receive data vs the risk of congestion collapse. You will have to make guesses as to where a packet was dropped and whether the retransmission is most efficiently sent unicast or multicast. If the server understands the data and can decide to not send a retransmission if there is updated data to be sent anyway (that makes the retransmission irrelevant), you are in a much better position than a framework such as Tibco RV.

Sometimes understanding the data can lead to wrong assumptions. For example, market data - it may seem at first OK to not retransmit a quote when there is an updated quote. But later, you may find that a subscriber was keeping a quote history, not just trying to keep track of the current quote. Perhaps you may have different requirements depending on the subscriber, and some clients will prefer unicast TCP vs multicast.

At some point you will need to make arbitrary decisions on the server of how much data to buffer in case of retransmissions or slow clients.

Answer 3

This is an open research question; there are commercial solutions available but which are prohibitively expensive. Good luck.

Answer 4

I think you should perhaps take a look at Stream Control Transmission Protocol as an alternative to UDP / multicasting if you really want reliable simultaneous transmission to multiple clients.

Answer 5

Following on from TIBCO, the PGM protocol is an open standard reliable multicast with many optimisations to efficiently work at very large scales with network element acceleration. PGM was developed by TIBCO and CISCO and is an optional protocol underneath TIBCO Rendezvous, the default protocol being TRDP which is very similar in design.

You can calculate theoretical efficiencies such as listed here for PGM,

http://code.google.com/p/openpgm/wiki/PgmPerformance

Unfortunately real world network elements, NICs and general computer architectures perform a lot less than the theoretical maximums.

Answer 6

http://www.jgroups.org/

Answer 7

Might I suggest UFTP. It uses a NAK based mechanism to determine which packets to retransmit and has an option for either a fixed transmission rate or congestion control using TFMCC.

Each file is sent in passes, where the first pass transmits the entire file, while subsequent passes only send retransmissions. Each client keeps track of which packets it received and which ones it missed. At particular checkpoints (and at the end of a pass), if the receiver missed any packets since the last checkpoint it will send a NAK listing the packets that were missed. This has the advantage that low-loss receivers will finish before high-loss receivers. UFTP can also be configured to drop receivers whose percentage of NAKs exceeds a certain threshold.

By limiting NAKs to only receivers that have exhibited loss it reduces the risk of congestion collapse, which is the sender getting overwhelmed by receiver feedback.

Disclosure: author of UFTP.