Experimental hypergraph based erasure
resilient code with checksum packets of either two or three source packets
2006-03-07
EG
Table of contents:
III..... Second
experiment – searching the best K-ring hypergraph with 9 nodes 9 edges and 9
sides
IV..... Third
experiment – searching the best K-ring hypergraph with 9 nodes 18 sides and no
edges
VI..... Fifth
experiment – searching the best distribution of the number of edges and sides
VII.... Sixth
experiment – searching the best K-ring hypergraph with 18 nodes 36 sides and no
edges
VIII... Conclusion
or further work
I.
Introduction
We are experimenting with a packet erasure resilient systematic code, where the redundant packets are checksums of either of pairs or of triplets of source packets. The performance of a specific coding method is evaluated by the curve of the probability of decoding of all source packets as a function of the number of available excess packets (in respect to the number of source packets). In all our examples the transmitter has twice as much redundant packets as there are source packets, thus the excess of received packets can vary from 0 to 200%. The coding method (i.e. the choice of the redundant packets at the sender) can be regarded as a hypergraph [hypergraph], whose vertices are the source packets and the redundant packets are either usual edges (connecting two vertices) or hyperedges [hyperedge] connecting three vertices. Hyperedges connecting three vertices will be called henceforth sides. The term node will be used here as a synonym for vertex.
II.
First
experiment: searching the best distribution of the numbers of edges and sides
for hypergraphs with 9 vertices
We are analyzing hypergraphs with 9 vertices (i.e. 9 source packets) and 18 edges or sides (i.e. 18 redundant packets). We are considering 19 possible distributions of numbers of edges and sides in hypergraphs: from graphs with 18 edges and no sides to hypergraphs with no edge and 18 sides. For each hypergraph type we consider 2’000 random samples and we test each sample with 10’000 random arrival sequences (in order to build the curves of decoding probability). For each hypergraph type we keep the probability curve of the best sample only (see the below chart). Curves are indexed by the number of edges in the hypergraph. The graph with 18 edges (E=18) and therefore with no side has the worst performance.
[xls]
The scalar value of the hypergraph’s performance is computed as the sum of the probabilities of decoding for all numbers of excess packets from 0 to 18. The performances of the best hypergraph samples for all numbers of sides (from 0 to 18 and the number of edges correspondingly from 18 down to 0) are plotted in the below chart. The performance visibly improves as the number of sides in the hypergraph increases and the number of edges decreases. The best performance of 16.9138 is observed at the hypergraph with 16 sides and 2 edges.
[xls]
For all considered random hypergraphs with zero, one and two sides below are shown the diagrams of their corresponding best samples.
|
Best sample of the considered random graphs with no side |
Best sample of the considered random hypergraphs with one side |
Best sample of the considered random hypergraphs with two sides |
For each type of hypergraph we observed that the best performance is exhibited by the samples having the regular degree of edges and hyperedges. Let the weighted degree of the vertex be its degree of edges divided by 2 plus its degree of sides divided by 3. The average of weighted degrees is 2 for all considered hypergraphs. Let the graph’s variance of the weighted degrees be the sum (for each vertex) of absolute deviations of all weighted degrees from their average. In the below chart we can see that for each hypergraph type almost always the graph’s variance of the weighted degrees decreases (the black curves) as the sample’s performance increases (the red curves).
[xls]
- C++ program generating for each distribution of sides and edges random samples of hypergraphs and building their curves of decoding probability [ cpp | txt | out ]
- Definition of hypergraph from MathWorld [hypergraph]
- Definition of hyperedge from MathWorld [hyperedge]
III.
Second
experiment: searching the best half/half K-ring hypergraph with 9 nodes, 9
edges and 9 sides
Since the best samples of hypergraphs have a tendency of having regular degrees of vertices, we build K-ring hypergraphs with 9 nodes, 9 edges and 9 sides. In our example the 9 edges and the 9 vertices form a ring. The sides and nodes are indexed (from 1 to 9). Each side is connected to the node of the same index and two non-equal shift values (from 1 to 8) determine the two other nodes being connected by the side. Here is an example of such a half/half K-ring hypergraph with an equal number of sides and edges:
[eps]
The valid combinations of the two shift values form 56 K-ring hypergraphs (they are not unique and are repeating). With 40’000 packets’ random arrival sequences we computed the performances of each of the half/half K-ring hypergraphs. These performances are plotted on a 3D histogram shown in the two figures below (there are two views of the same histogram):
[xls]
The best performance of 16.99485 is obtained with the half/half K-ring with the two shift values of 5 and 2. This performance beats the best performance of 16.9138 from previous section (i.e. the performance of the best sample from 2000 random hypergraphs with 16 sides and 2 edges).
- C++ program generating the samples of half/half K-ring hypergraphs with 9 nodes 9, edges and 9 sides, and computing their scalar performance values [ cpp | txt | out ]
IV.
Third
experiment: searching the best all-sides K-ring hypergraph with 9 nodes, 18
sides and no edges
All-sides K-ring hypergraphs containing 18 sides and no edges are built assuming that there are two equally sized subsets of sides. The sides in each subset and the nodes are indexed (from 1 to 9). Each side of the first subset is connected to the node of the same index, to the next node and a shift value (from 2 to 8) determines the third node. Each side of the second subset is connected to the node of the same index and two non-equal shift values (from 1 to 8) determine the two other nodes being connected by the side. The combinations of these three shift values lead to 189 all-sides K-ring hypergraphs. Here is an example of such all-sides K-ring hypergraph:
[eps]
The performances of the considered all-sides K-ring hypergraphs are computed by passing each one through 20’000 random arrival sequences (of the packets). These performances are plotted in the below chart in ascending order. The best performance value of 16.96035 is below the performance of the best half/half K-ring hypergraph (16.99485) presented in the previous section.
[xls]
- C++ program generating the samples of all-sides K-ring hypergraphs with 9 nodes, and computing their scalar performance ratings [ cpp | txt | out ]
V.
Fourth
experiment: searching the best half/half K-ring hypergraph with the number of
vertices from 9 to 18
Since for all considered hypergraphs with 9 vertices, the half/half K-ring hypergraph so far is the best, we then search the best half/half K-ring hypergraphs also for larger number of vertices (from 9 to 18).
For each node number we consider all possible samples (determined by two shift values) and we chose the half/half K-ring hypergraph exhibiting the best performance. The decoding probability curves of the best half/half K-ring hypergraph samples (for the number of vertices from 9 to 18) are plotted in the below chart. The number of excess packets is given as a percentage in respect to the number of source packets.
[xls]
The bad news is that the need of excess packets for meeting a certain probability of decoding increases faster than the number of source packets does. With the random linear fountain codes, as the number of source packets increases, the number of needed excess packets does not grow at all, [ ch | us ]. Compared with the K-ring graphs with only edges and no sides [ ch | us ], as the number of source packets increases, the need of excess packets now grows however a little bit slower.
The performance of the best half/half K-ring hypergraph with 18 edges is of 30.725250.
- C++ program, which for the different numbers of vertices (from 9 to 18) searches the best sample within all corresponding half/half K-ring hypergraphs and saves their decoding probability curves [ cpp | txt | out ]
- Random linear fountain codes [ ch | us ]
- Decoding probability curves for K-ring graphs with only edges (no sides) with the numbers of vertices from 9 to 20 [ ch | us ]
VI.
Fifth
experiment: searching the best distribution of the number of edges and sides for
hypergraphs with 18 vertices using random graph samples
Here we are searching the best distribution of the numbers of edges and sides in hypergraph with 18 vertices. For each of possible 19 distributions we generate 2’000 random samples and each sample is tested with 10’000 random arrival sequences. The best sample of each distribution is kept as a reference. The below chart shows that the best performance is exhibited by the distribution containing only sides and no edges (E=0). The worst performance is exhibited by the distribution with only edges (E=36) and no sides.
Below is the 3D view of the same chart:
[xls]
Performances of the best samples of each distribution of edges and sides show that the hypergraph with 18 vertices becomes visibly better as the number of sides in the hypergraph increases and the number of edges decreases:
[xls]
The best hypergraph with sides only (36 sides) and no edges has a performance of 31.6616, which is better than the performance of the best half/half K-ring hypergraph with 18 nodes, computed in the previous section (30.725250).
We are comparing this so far best sample (with 18 nodes) with the best half/half K-ring hypergraph with 9 nodes:
[xls]
Although the performance of the 18-vertices hyper graph is slightly improved it cannot beat the performance of the 9-vertices half/half K-ring hypergraph. Still bad…
- C++ program generating the random samples of hypergraphs with 18 vertices and building their curves of decoding probability [ cpp | txt | out ]
VII. Sixth experiment:
searching the best all-sides K-ring hypergraph with 18 nodes, 36 sides and no
edges
Since the previous section has shown that for hypergraphs with 18 nodes the best performance is exhibited by the hypergraphs with only sides and no edges, here we produce all all-sides K-ring hypergraphs with 18 nodes. Among 2’160 considered graphs (sorted in the below chart in the ascending order of their performances) the best hypergraph has a performance of 32.526, which beats the performance of the best random graph (31.6616) found in the previous section.
[xls]
The curve of the now best all-sides K-ring hypergraph with 18 nodes is again compared with the best half/half K-ring hypergraph with 9 nodes:
[xls]
Although the obtained 18-nodes all-sides hypergraph has the best performance compared to all previously considered 18-nodes examples, the 9 node version however still remains the best one in the relative scale, which is a bad news.
- C++ program generating the samples of the all-sides K-ring hypergraphs with 18 nodes, and computing their scalar performance ratings [ cpp | txt | out ]
VIII. Conclusion or further
work
We would like to find a hypergraph with 18 nodes, if not with the constant number of excess packets as in the case of the random fountain code [ ch | us ], but at least with a relatively smaller fraction of excess packets compared with the half/half K-ring hypergraph with 9 nodes.
IX.
Related
links
- Definition of hypergraph from MathWorld [hypergraph]
- Definition of hyperedge from MathWorld [hyperedge]
- The MS word document of this web page [doc]
- Computing the packet recovery probabilities for 9 source packets and 18 redundant packets corresponding to hypergraphs with edges and sides (i.e. 3-hyperedges) [ ch | us ]
- 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 ]
* * *