In a system where a transmitter transmits packets to a number of receivers, a packet may be received one or more times over the set of receivers or may be lost (not received at any of the receivers). The problem is to determine, in a scalable and computationally feasible manner, packets that have been received over the set of receivers and packets that have been lost. For such single-transmitter-multiple-receiver scenarios, this disclosure describes scalable and computationally efficient techniques to detect missing or duplicate packets based on sequence numbers. Each receiver maintains an array of bits corresponding to packets it received. A logical-OR operation across bit arrays reveals the sequence numbers of packets that are lost. A logical-AND between two bit arrays reveals duplicates between those two bit arrays. The result of a pairwise logical-OR operation on two or more bit arrays, when logically ANDed with another bit array, reveals the sequence numbers of packets that have been received in duplicate.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
N/A, "Scalable Near Realtime Loss and Duplicate Detection from Received Sequence Numbers", Technical Disclosure Commons, (December 02, 2020)