The basic scheme has a lot of redundancy. All the supporter packets carry the same hash value of a given packet. In the experiments we use six hashes per packet, hence six packets carry the same hash value. Removing this redundancy might give us a lower communication overhead and improved robustness against loss.
The core idea is to split the hash into chunks, where a quorum of any chunks is sufficient to allow the receiver to validate the information. One approach is to use Rabin's Information Dispersal Algorithm [25], which has precisely this property. Another approach is to produce a hash function with a large number of independent bits, but only look at a limited number of those bits. This can most easily be realized by a family of universal hash functions [8].
The main advantage of this scheme is that any out of the packets need to arrive, which has a higher robustness in some circumstances than receiving packet out of in the basic scheme. For example, if we use the basic scheme with -bit hashes and six hashes per packet, the communication overhead is at least bytes, and the probability that at least one out of six packets arrives is , where is the loss probability. In contrast, if we use the extended scheme with a hash of bits, chunks of bits, , and , the probability that the receiver gets more than four packets is . Clearly, the latter probability is much higher. Although both probabilities only provide an upper bound on the verification probability, it still gives an intuition on why the extended scheme provides higher robustness to packet loss.
The simulation confirmed these findings. The extended scheme outperforms the basic scheme in robustness against packet loss. Figure 10 shows a comparison of the two schemes with identical communication overhead.
Figure 10: The verification probability for the basic vs. the
extended scheme. Top line is the extended scheme. Bottom line is the basic scheme.