Producing redundant XOR packets from pairs of original packets according to a K-ring graph: computing the probabilities of packet loss recovery for various numbers of original packets [doc]

We are examining the probabilities of recovery of lost packets when using redundant XOR packets of some pairs of original packets. For a given set of original packets the choice of redundant packets leads to a graph (with the nodes representing the original packets and the edges representing the redundant packets). We are examining graphs with twice as much redundant packets (edges) as there are original packets (nodes).

The chart below represents the recovery probability curves for random graphs with 20 nodes and 40 edges. The chart represents a few graphs from total 10’000 graphs, including the graphs having the best and the worst performances within the considered set.

[xls]

All 10’000 graphs are bounded above by a K-ring graph, having a uniform degree of four for all 20 nodes:

[eps]

Each node of the considered K-ring graph is adjacent to four nodes: (1) to the next node, (2) to the node after the next, (3) to the previous node and (4) to the node before the previous.

The graph of the considered set having the worst performance:

[eps]

The graph of the considered set having the best performance:

[eps]

For each graph the probabilities of recovery for all numbers of received packets (from 20 to 60) can be summed up. Such a sum rates the performance of the graph. Distribution of 10’000 random graphs by this sum is presented in the below chart. The rightmost histogram with the performance equal to about 30 represents the K-ring graph.

[xls]

Further, the performances of K-ring graphs only were analyzed for graphs from 9 to 20 nodes (correspondingly from 18 to 40 edges). The recovery probability curves are built as functions of the number of received packets starting from the number of original packets (referred to as 100%) and finishing by the number of all packets (referred to as 300%). Comparisons of all curves are given in the below chart:

[xls]

As the number of original packets increases (M from 9 to 20), for maintaining a certain probability of recovery, the number of exceeding packets (in respect to the number of original packets) grows faster than the number of original packets does. That is a bad news. We are certainly looking for a method which is requiring a smaller relative increase of exceeding packets in respect to the relative increase of the original packets. The best case is to require no increase in exceeding packets at all, like in fountain codes [MacKay05].

Related links:

- A C program generating the graphs and computing the decoding probabilities [ cpp | txt | screenshot ]

- Comparing the recovery probabilities of a Torus graph and a K-ring graph with 9 nodes and 18 edges [ ch | us ]

- Computing the recovery probabilities for 2500 random graphs with 18 edges [ ch | us ]

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

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

* * *