Double-Edge Embedding Based Provenance Recovery for Low-Latency Applications in Wireless Networks

A number of applications in next-generation multi-hop networks, e.g., vehicular 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 protocols may help the packets to satisfy latency-constraints, such strategies do not facilitate the destination in learning the path traveled by the packets, which in turn could be used for either learning the topology of the network or detecting security threats on the network. In addition to low-latency constraints, vehicular networks also result in variable network topology owing to the mobility of the nodes, which in turn imposes additional challenges to the destination in learning the path traveled by the packets. Thus, with potential applications to vehicular networks, we address the problem of designing provenance embedding algorithms that reduce the delays on the packets and yet assist the destination in determining the path traveled by the packets with no knowledge of 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. Using fixed-size bloom filters as tools to implement the double-edge embedding ideas, first, we derive upper bounds on the error-rates of the DE embedding techniques so that the parameters of the bloom filter can be chosen to facilitate provenance recovery within a given quality of service. Subsequently, we present experimental results on a test bed of XBee devices and Raspberry Pis to demonstrate the efficacy of the proposed techniques, and show that the DE embedding techniques offer latency benefits upto 17 percent along with remarkable reduction in error-rates in comparison with the baselines. We also present a security analysis of the proposed provenance embedding methods to asses their vulnerabilities against various attacks including impersonation threats.