Experimental erasure resilient code
whose redundant packets are XOR packets of either two or three source packets
2006-02-24
We are assuming 9 source packets and 18 redundant packets, together forming a set of 27 packets. Redundant packets are XOR checksums of either two or three source packets. Redundant packets which are checksums of pairs of sources lead to a graph, where nodes are the source packets and the edges are the redundant packets. Redundant packets which are checksums of triplets of sources lead to a 3-hypergraph, where nodes are the source packets and the 3-subset edges are the redundant packets [aa-hypergraph]. A mix of all 18 redundant packets leads to a mixed hypergraph with 9 nodes and 18 either normal or 3-subset edges. The 3-subset edges we will call henceforth sides.
Each mixed hypergraph is characterized by the distribution of the numbers of normal edges and sides. For a specified distribution of edges and sides, various random hypergraphs can be built. A specific hypergraph sample can be rated by a probability of restoring the 9 source packets as a function of the number of received packets (out of 27 transmitted).
The recovery probability curve for a specific graph is built by testing various packet arrival sequences. Each arrival sequence results in the number of the arrived packet at which all source packets can be successfully restored and reception of no more packets is required. All these numbers for each arrival sequence determine the recovery probability curve of the hypergraph.
The diagram below represents a graph sample with 18 normal edges only (without sides):
[eps]
For various packet arrival sequences (each node and each edge in the above graph is a packet to be transmitted) the below animation demonstrates the source packets discovery process (decoding). At each frame of the animation we receive one packet (a node or an edge) and if the arrived packet contributes also to decoding of some source packets, an intermediary frame shows additionally the source packets decoded due to arrival of the just received packet:
The diagram below represents a hypergraph with 16 edges and 2 sides. The sides are visualized as gray triangles:
[eps]
The below animation shows various arrival sequences of the above mix of 9 source packets, 16 checksums of pairs and 2 checksums of triplets:
The diagram below represents a hypergraph with 9 edges and 9 sides:
[eps]
And here are few arrival sequences:
The last example represents a hypergraph with 18 sides only and with no (normal) edges:
[eps]
And here are few arrival sequences for the above graph:
For each distribution of the numbers of edges and sides (18 edges and 0 sides, 17 edges and 1 side, etc) we generated 800 random hypergraph samples. For each hypergraph sample we produced 10’000 random arrival sequences. Thus we obtained 800 recovery probability curves for each edges/sides distribution.
For 18 edges and 0 sides:
[xls]
The magenta curve represents a 3 by 3 torus graph, which is an upper bound for all considered random graphs, see also [ ch | us ]. The yellow curve is that of a random linear fountain code (the number of source packets is 10 instead of 9, but it remarkably does not matter for random linear fountain code, whose curve is always better than those of all our hypergraphs), see also [ ch | us ]. The numbers on the horizontal ax are the excess packets after arrival of the first 9 packets (after arrival of first 10 packets in case of the yellow curve).
For random hypergraphs with 17 edges and 1 side:
[xls]
Among the 800 random graphs there are samples performing a little bit better than the magenta curve of 3 by 3 torus graph (the upper bound of graphs with 18 edges and no sides).
For hypergraphs with 16 edges and 2 sides:
[xls]
With one more side and one less edge, there are more random hypergraphs exceeding the performance of the 3 by 3 torus graph.
For hypergraphs with 15 edges and 3 sides:
[xls]
The random graphs perform yet better with 3 sides. The successive charts are showing that the performance of the random hypergraphs continues to increase as the sides number increases and the number of edges decreases.
For random hypergraphs with 14 edges and 4 sides:
[xls]
The random hypergraphs with 4 sides perform better than those with 3 sides.
For 13 edges and 5 sides:
[xls]
The random graphs with 5 sides perform better (the best of them can, with 5 excess packets, recover all source packets with 90% probability of success).
For 12 edges and 6 sides:
[xls]
The trend continues and the random graphs with 6 sides perform yet better.
For 11 edges and 7 sides:
[xls]
The trend continues: the random graphs with 7 sides perform better than those with 6 sides.
For 10 edges and 8 sides:
[xls]
The random graphs with 8 sides perform better than those with 7 sides.
For 8 edges and 10 sides:
[xls]
The random graphs with 10 sides perform yet better.
For 6 edges and 12 sides:
[xls]
The random graphs with 12 sides exhibit almost the best performance (the best of the 800 random graphs can recover the source packets with a probability of almost 90% with an excess of 4 packets only; still it is more than the 3 packets required by the random linear fountain code).
For 4 edges and 14 sides:
[xls]
The random graphs with 14 sides seem to not perform better than the graphs with 12 sides.
For 2 edges and 16 sides:
[xls]
The performance is either not improved or improved only negligibly. The increase of the side number does not result anymore in visible improvements.
For no edges and 18 sides:
[xls]
With 18 sides and no edges the performance is either not increased or is even reduced.
Conclusions:
By moving the distribution of edges and sides from 18-edges graphs toward 18-sides hypergraphs, there is a noticeable improvement: the 90% probability of recovery of all source packets is obtained with 4 excess packets instead of 6. However when we reach hypergraphs with 6 edges and 12 sides, it seems that no additional performance can be obtained by a further pursuit of the side increase and edge decrease strategy.
Related links:
- Hypergraph definition from AA reference [aa-hypergraph]
- a C++ program generating random hypergraphs for specified distribution of edges and sides, and building the recovery probability curves [ cpp | txt ]
- AFPL Ghostscript – a freeware program converting the postscript files (generated by the C++ program) to PDF files [Ghostscript]
- ImageMagick – a freeware program converting the encapsulated postscript files (generated by the C++ program) to animated GIF files [ImageMagick]
- The MS word document of this web page [doc]
- Computing the packet recovery probabilities for random linear fountain codes, whose recovery probabilities depend on the number of excess packets only and do not become worse when the number of source packets increases [ ch | us ]
- Computing the curves of packet recovery probabilities (as functions of number of excess packets) for various numbers of source packets, when the redundant packets are XOR checksums of pairs of source packets and they are selected according to a K-ring graph [ ch | us ]
-
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 ]
* * *