Spatial bloom filter in named data networking: A memory efficient solution

Among the possible future Internet architectures, Information Centric Networking (ICN) is the most promising one and researchers working on the Named Data Networking (NDN) project are putting efforts towards its deployment in a real scenario. To properly handle content names, the different components of an NDN network need efficient and scalable data structures. In this paper, we propose a new data structure to support the NDN forwarding procedure by replacing the current Forwarding Information Base (FIB): the Spatial Bloom Filter (SBF), a probabilistic data structure that guarantees fast lookup and efficient memory consumption. Through a set of simulations run to compare the performance of FIB and SBF, we found that the latter uses less than 5 KB of data to handle 10⁶ queried interests, with a (negligible) probability 10^-4 of false positive events. Conversely, the FIB requires up to 2.5 GB of data in disadvantageous cases, e.g. when interests are composed of a considerable number of components.