Choice of the MDS FEC block size

By the choice of an MDS code, the reception of the sufficient number of any type of transmitted packets, precisely said exactly the same number as there were media packets in the original data, is the only condition for the successful decoding of all original media packets.

One parameter of streaming is M, the number of media packets in the block, another parameter we must rely on for computing the transmission block size is the desired decoding failure probability at the receiver.

If we have 20 media packets in each transmission and 20% losses in the network, the mean number of received packets is 16. If we add 5 redundant packets and transmit for each 20 media packets a block of 25 packets the mean number of successfully received packets will be 20, which is the number needed for the recovery of the original media. However the probability of receiving 19 packets or 18 packets (which makes the decoding impossible) is quite high. Therefore for small values of M, which is the limiting factor of the short round-trip time of the two-way real-time media, we must send much more redundant packets in the block than is necessary to receive mean M packets on the receiver side. Thus the mean of received packets should be much higher than M and the probability of receiving less than M packets must be maintained very low, i.e. .

The probability of having n losses (erasures) in a block of N packets with a random loss probability p is computed by binomial distribution:

where

and

The probability of having and more losses (i.e. less than M survived packets), is computed as follows:

The below figure shows a binomial distribution for a block of 20 packets () and the random loss probability of 30% (). The probability of having the mean of losses, i.e. 6 lost packets, is the highest.

The probabilities of having 9, 10, 11 … 20 packet losses are marked on the histograms of the above chart in red. The sum of these probabilities is the probability of having more than 8 packet losses or the probability of receiving less than 12 survived packets. Below is the same chart but in the logarithmic scale.

If the number of media packets carried by a block is 12 and the number of all packets in the transmission block is 20, i.e. we use RS(20,12), then the probability of the failure of decoding at the receiver is .

The below table contains the value of the binomial distribution of this example. Critical loss numbers are marked in red. The decoding failure probability of the RS(20,12) code sums up to about 11.3%

Number of lost packets	The probability
0	0.000797923
1	0.006839337
2	0.027845873
3	0.071603672
4	0.130420974
5	0.178863051
6	0.191638983
7	0.164261985
8	0.11439674
9	0.065369566
10	0.030817081
11	0.012006655
12	0.003859282
13	0.001017833
14	0.000218107
15	3.73898E-05
16	5.00756E-06
17	5.04964E-07
18	3.60688E-08
19	1.62717E-09
20	3.48678E-11
Media Packets	Decoding Failure probability
12 (more than 8 lost packets are critical)	0.113331463

If the application sustains the decoding failure probability of 11.3%, it can then maintain for its 12 media packets the size of the transmission block at 20 packets. But if the probability of the decoding failure of 11.3% is too high, then the application needs to transmit in the carrier block more than 20 packets (for the same number of 12 media packets).

Let have another example, where M, the number of media packets, is equal to 5 and the desired probability of decoding failure is 1%. The probability of random loss is still 30%. The below plot shows four Binomial distributions for four carrier blocks of the lengths of correspondingly 9, 11, 13 and 15 packets.

For each of four binomial distributions, the probabilities of receiving of insufficient number of packets, i.e. only 4, 3, 2, 1 or 0 successfully received packets, we marked in yellow. The decoding is not possible in all these cases due to missing number of packets and the decoding failure probability, for each distribution, is the sum of these probabilities.

The two charts below show (in the linear and logarithmic scales) the decoding failure probability of the FEC blocks of four different sizes: 9, 11, 13 and 15 packets in length (each of these blocks carries the same number of 5 media packets).

According to the charts, if we desire to have the decoding probability below 1% we must transmit the media in blocks of 13 packets and if we wish to reduce the decoding probability below 0.1% it will be sufficient to increase the FEC block size to 15 packets.

Thus for computing the carrier block’s minimally needed length for a satisfactory communication, it is sufficient to steadily increase the carrier block length until the desired decoding error rate (DER) is met. Fast binomial distribution algorithm, especially fast algorithm for computing a value of the binomial distribution when the value at the neighboring position is already computed, and simple search optimizations quickly find the minimally required length of the FEC block at which the decoding failure probability is below or equal the permitted limit DER.

The needed length of the FEC block as a function from the random loss probability p has integer values. We, however, desire to have smoothly interpolated values, which do not jump from one integer value to another at slightest changes of p. The best fitting is obtained by a logarithmic interpolation between the following three values (under the same loss rate p).

- the decoding failure probability at N, which is below DER

- the permitted limit DER

- the decoding failure probability at , which is higher the value of DER

We find thus the precise value laying between two integers and N, and corresponding “exactly” to the failure probability of DER. The below approximation of the decoding failure probability (as a function from N) is highly coarse, but it points to the right interpolation function (i.e. logarithmic).

= decoding failure probability at

= decoding failure probability at N

The minimal number of packets in the transmission block (an integer) needed for keeping the decoding failure probability below DER is plotted on the below chart (the thick dark blue curve). The interpolated function is plotted on the same chart (the thin blue curve).

,

Comparison of several functions for media packets from 1 to 10 with the function, derived from the Shannon capacity, is presented in the below chart (). Higher is the number of media packets in the block (i.e. longer is the buffering time) closer the transmission will approach to the Shannon conditions.

Therefore, concluding this section: for a real-time streaming application ARON must be computed using a function which takes into account the maximal number of media packets in the FEC block and the maximally permitted DER (as it’s been presented above, see the first equation below). Assumption of the Shannon capacity (second equation below) is permitted for very long buffers, file transfers, on-line but one-way video, etc.

	(1) Based on function assuming the decoding failure probability and an MDS encoder
	(2) Assuming Shannon capacity (file transfers)

Obviously, for a given routing patter, the ARON value computed according the first equation above will be much higher the ARON value computed, according the second equation. The choice of the equation must be based on the type of the media.

We are now equipped with a technique for measuring the friendliness of a network routing toward the efforts of a streaming application in protecting its media against losses. Within a number of suggested network routings, the best is the one, whose ARON is the smallest.