Packet loss recovery using redundant packets of pairs of original packets

EG

2006-02-17

For the recovery of packet losses we are experimenting with redundant packets added for some pairs of original packets. We assume 9 original packets and 18 redundant packets (27 packets in total). A selection of the pairs of original packets forming the redundant packets, leads to a graph with 9 nodes (representing the original packets) and 18 edges (representing the redundant packets). For each graph (i.e. for each particular selection of 18 redundant packets) we compute the probability of recovery of the 9 original packets as a function of the number of available packets. For recovery probability computation at each number of available packets hundreds of thousands subsets of packets of identical sizes are considered.

In total 2500 random graphs are considered, and the probability curve is built for each of them. For a reference, the recovery probability curves of 2500 random graphs are compared with that of a torus graph:

Torus graph: the top nodes are connected with the bottom nodes of the same column; the most right nodes are connected with the most left nodes of the same row; the degree of all nodes is equal to four

For a second reference, the probability of recovery is computed for a method where each original packet is provided in three copies:

Copies: each of 9 original packet is provided in three copies forming in total a set of 27 packets

The chart below presents the 2500 recovery probability curves for all considered random graphs together with two curves of the Torus graph and Copies method:

The recovery probabilities of all considered random graphs with 9 nodes and 18 edges are bounded from the top by the recovery probabilities of the torus graph; the detached group of curves with lower probabilities are the graphs containing one or more isolated nodes, with degree of zero

If the torus method is the upper bound for the recovery probabilities, then for small sets of packets, such as with 9 original packets, adding redundant packets for selected pairs does not lead to satisfactory probabilities of recovery in respect to the number of packets to be received compared to the number of packets to be recovered.

Related links and subjects:

- a C program generating the random graphs and computing for them the decoding probabilities [ cpp | txt ]

- An explanation on how the available packets of a graph are tested for their recoverability [ diagrams ]

- Excel file of the chart with the values of recovery probabilities [ xls ]

- An MS word document of this page [ doc ]

- For each graph, the recovery probabilities as a function from the number of available packets can be summed up into a single value for all numbers of available packets; bigger is the resulting sum better is the performance of the graph; distribution of 2500 graphs by the values of these sums is provided in an excel chart [ xls ]

- Computing the recovery probabilities for a double cycle graph [ ch | us ]

- Computing the recovery probabilities for a torus graph [ ch | us ]

* * *