Packet loss recovery probability when adding redundant packets only for some pairs of original packets

Packet loss recovery probability when adding redundant packets only for some pairs of original packets

For packet loss recovery we are proposing to add to the original set of data packets some redundant packets each representing one of few selected pairs of original packets. We propose three different methods each adding the same number of redundant packets, and we measure the probabilities of successful recovery of the original packets out of a given number of elements from the mix of the original and redundant packets.

In this experiment we have 9 original packets and 18 redundant packets, which are added according to following three different methods:

- In the Torus method the original packets are considered as nodes of a graph representing a torus (each packet has a degree of four) and each of the 18 links of the graph represents a redundant packet for the two adjacent nodes (Fig. 1)

- In the Double cycle method, the original packets are sorted along a cycle and for each two neighbors there are two redundant packets built with an RS(4,2) code (see Fig. 2)

- In the Copies method each of 9 original packets is provided in three copies (Fig. 3)

Fig. 1. Each of 9 nodes represents an original packet, each link represents a redundant packet, which is the XOR product of the adjacent nodes (adjacent original packets); top nodes are connected with bottom nodes of the same column and the most right nodes are connected with the most left nodes of the same row

Fig. 2. The 9 nodes represent the original packets, the two links between pairs of nodes are two different redundant packets representing the two adjacent nodes with an RS(4,2) code (such that the original packets are restored from two redundant packets or from one redundant and one original packets)

Fig. 3. For each packet two additional copies are provided, such that in total there are 27 packets

In respect to the total set of 27 packets obtained from one of the three above methods, for various subsets with 9 to 27 packets we measure the probabilities of recovering the original nine packets. The probability as a function of the number of available packets is shown in Fig. 4 for each of three methods. The highest probability of recovery is provided when the 18 redundant packets are formed by the Torus method.

Fig. 4. Probabilities of recovery of the 9 original packets from subsets of available packets of sizes from 9 to 27