Multicast ECC/FEC
A typical use-case for broadcast/multicast is when we need to transmit the same data (e.g. a file) to multiple receivers simultaneously. The use of multicast/broadcast means that multiple devices may benefit from a single transmission increasing the efficiency of the system. However, a challenge in such systems is how to efficiently deal with packet loss. In the following we will show how using an erasure correcting code/Forward Erasure correction (ECC/FEC) can lead to significant bandwidth savings over a traditional retransmission based system.
“But how much can we actually save?”
Here are some stats to illustrate the savings
To compare different overheads of ECC protocols, we have simulated packet transfers in a simple multicast setting.
We have assumed that the packet losses experienced by the receivers are independent.
Each packet loss is seen as a biased coin-flip, and a block of packets is thus a series of these coin-flips. Formally, we say that the packet loss is Bernoulli distributed, and the block packet loss is binomially distributed.
We have written the Block ECC protocols on the form x+y, where x is the number of source packets and y is the number of repair packets (those which contribute to the overhead) and the sum of them is the size of the block, so e.g. 6+2 is ECC with six source packets and 2 repair packets while 8+0 is the uncoded case.
Here are two plots with packet loss probabilities 10% and 1% respectively:
Packet loss 10%:
Packet loss 1%:
For 10% packet loss, Block ECC is better in terms of retransmissions right out of the gate, and keeps the number of retransmissions lower for increasing numbers of receivers. For 1% we see that for more than 4 receivers, ECC overtakes the uncoded variant in terms of retransmissions (and thus has lower overhead). In these examples, the added overhead accounts for 12.5%, 25% and 37.5%.
But what about the distribution?
“This is just the mean transmissions for each protocol. How much does the data vary around the mean?”. An excellent question. To answer this we have created a distribution plot - for a fixed amount of receivers, G = 1000, and 10% packet loss- of the number of attempted retransmissions vs the probability of all receivers having received the packets.
In the plot, you can see that all of the probability of successful transfer for the uncoded variant is spread across 3, 4 and 5 transmissions. The probability is maximized at 4 transmissions, while almost all the probability lies at 3 transmissions for 5+3 and 6+2 with 7+1 having maximum probability at 3 transmissions but still around 20% probability for 4 transmissions.
Can we do even better?
As a matter of fact, we can. Block ECC repairs packet losses with a fixed rate, so to be able to repair, one must choose a repair rate that matches the peak packet drop probability. Our library, OTAcast, utilizes rateless codes, which do not require a fixed amount of redundancy to repair packet losses.
A simple model of a rateless code will perform like this:
Packet loss 1% (Blue) vs 10% (Yellow):
With the same packet-loss percentages for OTAcast we get:
Packet loss 10%:
Packet loss 1%:
So given certain parameters, OTAcast outperforms the Block ECC as shown above, and performs almost optimally in terms of reliability and transmissions required for all users to receive a packet.
Every ECC/FEC algorithm requires computations to be performed during decoding. Using OTAcast it is possible to “tune” the decoding complexity which is captured in the EO (Extra Overhead) value. Lower EO means higher computational complexity but less decoding attempts, whereas higher EO is the opposite.
Technical Conclusion
ECC can be very useful in a multicast setting. Especially if the connections are lossy. It can save a lot of transmission time at the cost of more computations with each packet.
OTAcast shows very good results compared to performance from the traditional block codes.
Practical Applications
As shown, solutions like OTAcast have significant advantages in multicast settings, but what sort of networks and use cases are lacking such solutions, or might have a less efficient coding solution which is leaving performance and therefore customer satisfaction on the table?
Good examples of this is FOTA and OTA updates - any networks with wireless devices which may need regular security and firmware updates will benefit from an efficient multicast solution like OTAcast. Hundreds, or thousands of devices can be updated efficiently without the need for local device access. As an example see some of our previous posts about using OTAcast for providing OTA updates over GEO and LEO satellite networks.
Does it matter how these devices are connected?
Not at all, OTAcast can work over satellite connections to update devices on remote drilling rigs, or to seafaring vessels requiring map updates, or in industrial IoT settings over proprietary WiFi or 5G networks
But don’t just take our word for it! You can try out the above simulations yourself in the following Google Colab notebook.
If you were already considering using ECC/FEC for multicasting, or our simulations have helped you realise that you really need to consider ECC/FEC for today’s wirelessly connected world you should check out OTAcast below.