Packet loss recovery using redundant
packets of pairs of original packets
We are assuming 9 original packets and 18 redundant packets,
each of which is an XOR of a pair of original packets. A selection of 18 pairs of
original packets leads to a graph with 9 nodes (representing the original
packets) and 18 edges (representing the redundant packets). We are considering
two graphs with 18 edges: a 
Torus graph and a K-ring
graph, both with a degree four for all vertices (see the two figures below):
|
K-ring graph:
the degree of all nodes is equal to four |
|
Torus graph: the degree of all nodes is equal to four |
For each graph we are computing the probability of recovery of the 9 original packets as a function of the number of available packets. The below chart shows the recovery probability curves for the Torus and K-ring graphs:
|
The recovery probabilities of the torus and K-ring graphs are almost identical except that the Torus graph performs slightly better; the third curve represents a randomly chosen graph with 18 edges. |
The torus graph seems to form an upper bound for all graphs with 18 edges.
Related links:
- A C program generating the graphs and computing the decoding probabilities [ cpp | txt | screenshot | eps files ]
- Excel file of the chart with the values of recovery probabilities [ xls ]
- An MS word document of this page [ doc ]
- 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 ]
* * *