Bloom filters and their variants are widely used as space-efficient probabilistic data structures for representing sets and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications, a common engineering solution is to set the false positive rate very small and ignore the existence of the very unlikely false positive answers. This article is devoted to close the gap between the two design concepts ofunlikelyandnot havingfalse positives. We propose a data structure called EGH filter that supports the Bloom filter operations, and besides, it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false-positive free zone of a filter. We then generalize the filter to support the listing of the elements through the use of counters rather than bits. We detail networking applications of the filter and discuss potential generalizations. We evaluate the performance of the filter in comparison with the traditional Bloom filters. We also evaluate the price in terms of memory that needs to be paid to guarantee real false positive-free operations for having a deterministic Bloom filter-like behavior. Our data structure is based on recently developed combinatorial group testing techniques.

Bloom filters and their variants are widely used as space efficient probabilistic data structures for representing set systems and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications a common engineering solution is to set the false positive rate very small, and ignore the existence of the very unlikely false positive answers. This paper is devoted to close the gap between the two design concepts of unlikely and not having false positives. We propose a data structure, called EGH filter, that supports the Bloom filter operations and besides it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false positive free zone of a filter and generalize the filter to support listing of the elements. We evaluate the performance of the filter in comparison with the traditional Bloom filters. Our data structure is based on recently developed combinatorial group testing techniques.

Internet of Things (IoT) systems produce great amount of data, but usually have insufficient resources to process them in the edge. Several time-critical IoT scenarios have emerged and created a challenge of supporting low latency applications. At the same time cloud computing became a success in delivering computing as a service at affordable price with great scalability and high reliability. We propose an intelligent resource allocation system that optimally selects the important IoT data streams to transfer to the cloud for processing. The optimization runs on utility functions computed by predictor algorithms that forecast future events with some probabilistic confidence based on a dynamically recalculated data model. We investigate ways of reducing specifically the upload bandwidth of IoT video streams and propose techniques to compute the corresponding utility functions. We built a prototype for a smart squash court and simulated multiple courts to measure the efficiency of dynamic allocation of network and cloud resources for event detection during squash games. By continuously adapting to the observed system state and maximizing the expected quality of detection within the resource constraints our system can save up to 70% of the resources compared to the naive solution.

Network-wide local unambiguous failure localization (NL-UFL) has been demonstrated as an interesting scenario of monitoring trails (m-trails). It attempts to enable every node to autonomously localize any failure event in the network in a distributed and all-optical manner by inspecting a set of m-trails traversing through the node. This paper investigates the m-trail allocation problem under the NL-UFL scenario by taking each link and node failure event into consideration. Bound analysis is performed using combinatorial group testing (CGT) theory and this is followed by the introduction of a novel heuristic on general topologies. Extensive simulation is conducted to examine the proposed heuristic in terms of the required cover length and the number of m-trails to achieve NL-UFL.

Linear error correction is widely implemented in millions of telecommunication devices to cope with unreliable or noisy communication channels. A common error in linear encoders is when some bits that are originally one in the generator matrix get erased and become zero - usually due to a soft error becoming a hard error or simply a physical impact on the device. The need to deal with this phenomenon has been recognized in the literature, although to the best of our knowledge no one has ever tried to diagnose erasure-type faults in an encoder. In this paper we focus on the situation when the linear encoder hardware unit becomes faulty and propose a novel combinatorial fault detection scheme based on group testing to diagnose its state with great efficiency in a quick manner. Furthermore we touch upon some solutions to compensate for at both the sender and the receiver side.

Network-wide local unambiguous failure localization (NL-UFL) [1] has been demonstrated as an interesting scenario of monitoring trails (m-trails). It attempts to enable every node to autonomously localize any failure event in the network in a distributed and all-optical manner by inspecting a set of m-trails traversing through the node. This paper investigates the m-trail allocation problem under the NL-UFL scenario by taking each link and node failure event into consideration. Bound analysis is performed using combinatorial group testing (CGT) theory and this is followed by the introduction of a novel heuristic on general topologies. Extensive simulation is conducted to examine the proposed heuristic in terms of the required cover length and the number of m-trails to achieve NL-UFL.