Bloom Filter Based Low-Latency Provenance Embedding Schemes in Wireless Networks

A number of applications in next-generation multi-hop networks impose low-latency requirements on data transmission thereby necessitating the underlying relays to introduce negligible delay when forwarding the packets. While traditional relaying techniques such as amplify-and-forward may help the packets to satisfy latency-constraints, such strategies do not facilitate the destination in determining security threats, if any, during the packet's journey. Inspired by the problem of relaying packets that have low-latency constraints, we revisit the design of provenance embedding algorithms to reduce delays on the packets and yet assist the destination in determining the provenance with no knowledge on the network topology. We propose a new class of provenance embedding techniques, referred to as double-edge (DE) embedding techniques, wherein a subset of the relay nodes in the path strategically skip the provenance embedding process to reduce the delays on the packets. Under the framework of DE embedding techniques, we propose a deterministic skipping strategy among the nodes such that the destination can recover the provenance of every packet. Using fixed-size bloom filters as tools to implement the double-edge embedding ideas, we propose upper bounds on the error-rates of the DE embedding technique as a function of the number of nodes in the network, number of hops, bloom filter size, and the number of hash functions used by each node. Subsequently, we demonstrate the efficacy of the DE embedding technique on a testbed of Digi XBee devices, and show that it outperforms competitive baselines both in terms of latency as well as error-rates.