# A Review on Impact of Bloom Filter on Named Data Networking: The Future
Internet Architecture

Sabuzima Nayak  Ripon Patgiri<EMAIL_ADDRESS>[ Angana Borah  National
Institute of Technology Silchar

###### Abstract

Today is the era of smart devices. Through the smart devices, people remain
connected with systems across the globe even in mobile state. Hence, the
current Internet is facing scalability issue. Therefore, leaving IP based
Internet behind due to scalability, the world is moving to the Future Internet
Architecture, called Named Data Networking (NDN). Currently, the number of
nodes connected to the Internet is in billions. And, the number of requests
sent is in millions per second. NDN handles such huge numbers by modifying the
IP architecture to meet the current requirements. NDN is scalable, produces
less traffic and congestion, provides high level security, saves bandwidth,
efficiently utilizes multiple network interfaces and have many more
functionalities. Similarly, Bloom Filter is the only good choice to deploy in
various modules of NDN to handle the huge number of packets. Bloom Filter is a
simple probabilistic data structure for the membership query. This article
presents a detailed discussion on the role of Bloom Filter in implementing
NDN. The article includes a precise discussion on Bloom Filter and the main
components of the NDN architecture, namely, packet, content store, forward
information base and pending interest table are also discussed briefly.

###### keywords:

Bloom Filter, Named Data Networking, NDN, Survey, Future Internet
Architecture, Information-Centric Network, Froward Information Base, Content
store, Pending Internet Table, 5G, IoT.

††journal: Journal of Network and Computer Applications

up#1

url]http://cs.nits.ac.in

##  1 Introduction

Named Data Networking (NDN) is the most recent emerging research area which is
known as the future Internet. It is introduced in 2010 and has become one of
the most emerging research fields. Since then, the NDN is able to influence
academician, industrialist, scientist and practitioner. IPv4 has serious
scalability issue and therefore, the NDN overtaking the IPv6 and creates a new
future possibilities. The Internet using IP address permits point-to-point
connectivity between two nodes. With the advancement of packet switching, not
only text, audio and video are also sent through the Internet. However, IP is
unable to satisfy the customer requirements due to increasing demands of the
Internet, changing nature of applications, user requirements, and huge
increment of the Internet users. Network layer of the OSI communication model
has only IP. This does not permit IP to modify existing functionality nor add
new functionality to satisfy new requirements of the users. The network today
have multiple interfaces and very mobile. IP only forward within a spanning
tree. Therefore, IP is not suitable for today’s network [62]. The new user
requirement is “what data” without knowing “where data”. These requirements
lead to the ingress of the Internet to a new era of content-centric
communication [46].

Internet with content-centric communication provide ubiquitous inter-
connectivity and a wide range of services [142]. It enables information-
intensive business (eg. banking, travelling and financial services) to use the
Internet to expand their business. Internet helps in storing data in different
geolocations, staying connected to their data around the clock, providing
their services easily to the users, and interacting with the user without
physical interaction. In addition, hardware advancement also contributed
largely to increase the inter-connectivity between the systems. With the
growth of mobile devices, the Internet is also becoming mobile. Mobile
Internet helps in inter-connectivity between every smart device with our
mobile phones. Not just text, large sized audio, video and images are also
transmitted through the Internet. Several projects are proposed for designing
content-based future Internet paradigms [95, 60, 54]. To achieve Information-
Centric Network [138, 47], the Named Data Networking (NDN) [117, 141, 4] is
proposed which has an efficient design and simple communication model. NDN is
capable of handling variable-length, location-independent names, searching and
retrieving content upon content request.

Bloom Filter is a simple set membership filtering data structure. Simplicity
of Bloom Filter makes it suitable to implement along with an application with
a negligible overhead. Its advantages far exceed its issues. Bloom Filter is
implemented in diverse network applications such as Network Traffic [116],
Network Security [52, 136, 98], Routing Algorithms [94], Web Cache [45],
Wireless Sensor Networking [125], wired/wireless networking [127]. Packet
filtering in networking had been always an issue. However, with the onset of
the Big Data era, the importance of Bloom Filter escalated. Big Data being a
problem in every domain, all domain felt a need for a simple deduplicating
data structure. Therefore, Bloom Filter emerged as a solution for Big data.
Some emerging topics implementing Bloom Filter are Internet of Things [10,
121], Cloud Computing [137, 89], and 5G [75]. Moreover, interdisciplinary
domains such as Biometrics [111, 114] and Bioinformatics [61, 92] are
preferring Bloom Filter due to the above mentioned advantages along with tiny
memory consumption. Bloom Filter is able to attract the research community;
because, it provides a faster lookup or a filter using a tiny on-chip memory.
Bloom Filter is highly adaptable and is able to enhance a system performance
significantly. For instance, BigTable claims that its performance is increased
dramatically after using Bloom Filter.

NDN consists of many components such as Content store, Forward Information
Base and Pending Interest Table. Each component has to deal with Big Data.
Therefore, NDN requires Bloom Filter to deal with its problem. Currently,
Bloom Filter is playing a vital role in NDN. Bloom Filter is an approximation
data structure to check membership with some error tolerance. It uses a tiny
amount of memory to check whether a given element is a member of a set or not.
Also, it can answer any query in $O(1)$ time complexity. Therefore, NDN is
able to use Bloom Filter in its all components to check whether a given item
is a member of a set or not. NDN is enhanced drastically by engaging Bloom
Filter. Therefore, we carried out a rigorous review to expose the impact of
Bloom Filter in NDN.

###  1.1 Motivation

Numerous surveys are available on both Bloom Filter and NDN individually. A
list of Bloom Filter survey papers are presented in Table 1 and Table
LABEL:ndn_survey representing a list of NDN survey articles. Observing those
papers it is concluded that no survey paper is published which focuses on the
role of Bloom Filter in NDN. Bloom Filter is a crucial part of NDN, and hence,
this survey is carried out to explore the state-of-the-art NDN, which fully
depends on the Bloom Filter data structure. The literature search exposes the
similar survey published by reputed publishers, for instance, IEEE. However,
this survey focuses on the significance of Bloom Filter in implementing NDN.
Bloom Filter is used to implement the Pending Interest Table (PIT), Content
Store (CS) and Foreward Information Base (FIB). Bloom Filter is able to
enhance the performance of these modules of NDN using a tiny amount of main
memory.

Table 1: List of survey papers available on Bloom Filter Authors |  Year |  Title of the paper |  Domain
---|---|---|---
Broder et al. [23] |  2004, Taylor & Francis |  Network Applications of Bloom Filters: A Survey |  Bloom Filter, Distributed Caching, P2P/Overlay Networks, Resource Routing, Packet Routing
Tarkoma et al. [127] |  2012, IEEE |  Theory and practice of bloom filters for distributed systems |  Variants of Bloom Filter, Distributed Computing
Geravand et al. [52] |  2013, Elsevier |  Bloom filter applications in network security: A state-of-the-art survey |  Bloom Filter, Network (Wireless and Wired), Network security
Sangeetha et al. [115] |  2015, IEEE |  A survey of hardware signature implementations in multi-core systems |  Hardware signature
Gupta and Batra [56] |  2017, IEEE |  A short survey on bloom filter and its variants |  Variants of Bloom Filter
Patgiri et al. [105] |  2018, CSREA Press |  Shed More Light on Bloom Filter’s Variants |  Variants of Bloom Filter
Patgiri et al. [98] |  2018, EAI |  Preventing DDoS using Bloom Filter: A Survey |  DDoS
Luo et al. [80] |  2019, IEEE |  Optimizing Bloom Filter: Challenges, Solutions, and Comparisons |  Mathematical analysis of various aspects of Bloom Filter
Patgiri et al. [101] |  2019, Hindawi |  Hunting the pertinency of bloom filter in computer networking and beyond: A survey |  Computer Network (Wireless Sensor, P2P), Security (Network, Big Data, Biometric), IoT Environment, Metadata Server
Nayak et al. [93] |  2019, IEEE |  A Review on Role of Bloom Filter on DNA Assembly |  Variants of Bloom Filter, DNA Assembly
Patgiri et al. [104] |  2019, TheSAI.org |  Role of Bloom Filter in Big Data Research: A Survey |  Data Storage
Table 2: List of survey papers available on Named Data Network Authors |  Year |  Title of the paper |  Domain
---|---|---|---
Ariefianto et al. [17] |  2017, IEEE |  Routing in NDN network: A survey and future perspectives |  Routing
Aboodi et al. [2] |  2019, IEEE |  Survey on the Incorporation of NDN/CCN in IoT |  IoT, Data naming, In-network caching, Access control and policies, Routing
Soniya and Kumar [123] |  2015, IEEE |  A survey on named data networking |  Forwarding plane, Adaptive forwarding
Zhang et al. [146] |  2016, IEEE |  A survey of mobility support in Named Data Networking |  Mobility support, Producer mobility support
Chen and Mizero [28] |  2015, CoRR |  A Survey on Security in Named Data Networking |  Security and Privacy
Bakkouchi et al. [42] |  2019, IEEE |  A hop-by-hop Congestion Control Mechanisms in NDN Networks – A Survey |  Congestion control, Hop-by-hop Congestion control
Li et al. [73] |  2019, IEEE |  Packet Forwarding in Named Data Networking Requirements and Survey of Solutions |  Data structure used in FIB, content store and PIT
Aloulou et al. [12] |  2017, IEEE |  Taxonomy and comparative study of NDN forwarding strategies |  Taxonomy of NDN Forwarding strategies
Tariq et al. [126] |  2019, IEEE |  Forwarding Strategies in NDN based Wireless Networks: A Survey |  Forwarding In Ad Hoc (wireless, mobile, vehicular), Forwarding Based on Wireless Sensor and Wireless Mesh
Feng et al. [49] |  2016, Springer |  Mobility support in Named Data Networking: a survey |  Mobility support schemes
Khelifi et al. [66] |  2019, IEEE |  Named Data Networking in Vehicular Ad hoc Networks: State-of-the-Art and Challenges |  Vanet based (Naming Schemes, Routing, Data Discovery, Forwarding And Content Dissemination, Caching Schemes, Mobility, Security And privacy solutions, Issues)
Chen et al. [27] |  2016, IEEE |  Transport Control Strategies in Named Data Networking: A Survey |  Comparisons of transport control between NDN and IP-based Internet, Recent proposals for NDN Transport control, Challenges
Rahel et al. [110] |  2017, IEEE |  Energy-efficient on caching in named data networking: A survey |  System Services, Energy Efficiency
Chatterjee et al. [26] |  2018, IEEE |  Security Issues in Named Data Networks |  Types of security attack
Kumar et al. [68] |  2019, Springer |  Security Attacks in Named Data Networking: A Review and Research Directions |  Types of security attack
Saxena et al. [117] |  2016, Elsevier |  Named data networking: a survey |  System services, Applications, Issues
Ren et al. [112] |  2016, Elsevier |  Congestion control in named data networking - a survey |  Congestion control issues, Mechanism of congestion control, Issues
Ahed et al. [7] |  2019, IEEE |  Content Delivery in Named Data Networking based Internet of Things |  IoT, IoT application, Content Forwarding In NDN-based IoT
Hussaini et al. [59] |  2018, IAES |  Producer mobility support schemes for named data networking: A survey |  Producer Mobility Support
Yovita et al. [139] |  2018, IAES |  Caching on Named Data Network: a Survey and Future Research |  Caching

###  1.2 Organization of the article

The article is organized as follows- initially, Section 3 provides a brief
tutorial on Bloom Filter to understand Section 4 which exposes various
variants of Bloom Filter developed for NDN. Again, Section 5 presents a brief
tutorial on NDN and its architecture. Also, Section 6 establishes the relation
between packet and Bloom Filter to understand the rest section. The rest
sections present a rigorous survey on NDN using Bloom Filter. Thus, the survey
begins from Section 7 which illustrates the impact of Bloom Filter on Content
Store. Furthermore, Section 8 exploits Bloom Filter in the capability of
enhancement of Pending Interest Table. Similarly, Section 9 exposes the
necessity of Bloom Filter in implementing Forward Information base. Moreover,
Section 12 emphasizes on implementation of Bloom Filter in other components of
NDN. Section 10 reviews the security requirements of NDN. Section 13 discuss
some future trends of NDN along with some techniques implementing Bloom
Filter. Section 14 discusses on effects of Bloom Filter in NDN implementation,
and also, discusses lesson learnt from the survey. Finally, the article draws
a suitable conclusion in Section 15.

##  2 Review plan

The research papers/articles are collected from leading indexing engines,
namely, IEEE Xplore, ACM Digital Library, Springer Link and ScienceDirect. We
have also searched research papers/articles from SCOPUS and Web of Science.
The query terms are {”Named Data Network”}, {”Bloom Filter”}, and {”Named Data
Network” AND ”Bloom Filter”}. We have excluded Google Scholar for this review.
This paper presents the review of query {”Named Data Network” AND ”Bloom
Filter”} performed on the indexing engines.

###  2.1 Study of NDN Trend

Figure 1: Number of publications in various publishers.

Figure 1 illustrates the number of publications published by a prominent
publisher like IEEE (ieeexplore.ieee.org), ACM (dl.acm.org), Springer
(link.springer.com), and Elsevier (sciencedirect.com). The publication of NDN
starts from 2010 while the publication of Bloom Filter starts from 1970. In
our search, we have concluded that a few papers have been published for both
the term ”named data networking” and ”Bloom filter”. However, IEEE publisher
has published 627 papers of ”named data networking”, and Springer has
published 2186 papers of ”Bloom Filters” which is the highest. Interestingly,
ACM publishes 7, IEEE publishes 21, ScienceDirect publishes 38 and Springer
publishes 29 papers for both the terms ”Named Data Networking” and ”Bloom
filter”.

Figure 2: Number of paper indexed by various indexing engines.

Nowadays, Google Scholar is the most popular search engine to discover
research papers. However, quality paper indexing is not assured in Google
Scholar. On the contrary, Scopus and Web of Science, both are popular search
and indexing engine for high quality papers. Surprisingly, Scopus and Web of
Science have indexed 41 papers and 30 papers that contain both terms ”Named
Data Networking” and ”Bloom filter”. Google Scholar indexed 685 papers in the
said terms.

Figure 3: Number of patent awarded by various organizations.

The patent is an intellectual property right that preserves the copyright of
any intellectual creations. This is also important to discuss to understand
the current scenario of Bloom Filter and NDN. NDN already has 1290 patents
awarded since its inception (2010) while Bloom Filter has 2030 patents awarded
from 2010. With the increasing popularity of NDN, Bloom Filter is also
intensively experimented to deploy.

Figure 4: Popularity of Bloom Filter and Named Data Networking in Google
trends.

Current trends of Bloom Filter are higher than NDN, because, NDN has been
introduced in 2010 while Bloom Filter is introduced in 1970. The trend gap
clearly depicts that a few research community is engaged with NDN and it has
more miles to go.

##  3 Bloom Filter

Bloom Filter is a probabilistic data structure for set membership checking
[20]. Bloom Filter has a few issues and challenges [81]. The key issues of
Bloom Filter are false positive and false negative. Most of the modern Bloom
Filter does not have a false negative. However, some variants of Bloom Filter
suffer from false negative. For instance, counting Bloom Filter (CBF) [77]. On
the other hand, the Bloom Filter has many challenges to achieve, namely, high
scalability, high accuracy, high lookup performance and low memory
consumption.

###  3.1 Architecture

Figure 5: Architecture of Bloom Filter. Figure depicts insertion and query
when $k=3$. Source [93]

In Bloom Filter [20], the input items are hashed into bitmap array [130].
Unlike a conventional hash data structure, Bloom Filter uses a bitmap array
instead of object array (for instance, int, char, float etc.) and it permits
errors in lookups. The bitmap array consists of bits [130] and the input items
are hashed into these bits. Initially, bitmap array is set to zero. $m$ is the
size of the Bloom array. $m$ is a prime number, otherwise, collision
probability increases. The Bloom Filter implements multiple hash functions to
map the input item to bit locations. $k$ is the number of hash functions. The
Less number of hash functions cause more collision probability. On the
contrary, the number of hash functions trigger invoking many operations which
affect the performance adversely. This trade-off is removed by calculating the
optimal number of hash functions.

Bloom Filter returns response in $True$ or $False$. $True$ indicates the item
is present. $False$ indicates the item is absent. The $True$ response is
further classified into $True~{}positive$ and $False~{}positive$. Similarly,
$False$ response is further classified into $True~{}Negative$ and
$False~{}Negative$. Let, $\mathbb{B}$e a Bloom Filter, $\mathbb{S}$ be a set
whose elements are inserted into $\mathbb{B}$ $\kappa$ be the input item, then

  * 1.

True Positive: If $\kappa\in\mathbb{S}$, and $\kappa\in\mathbb{B}$, then the
result of $\mathbb{B}$s true positive.

  * 2.

False Positive: If $\kappa\not\in\mathbb{S}$, but $\kappa\in\mathbb{B}$, then
the result of $\mathbb{B}$s false positive.

  * 3.

True Negative: If $\kappa\not\in\mathbb{S}$, and $\kappa\not\in\mathbb{B}$,
then the result of $\mathbb{B}$s true negative.

  * 4.

False Negative: If $\kappa\in\mathbb{S}$, but $\kappa\not\in\mathbb{B}$, then
the result of $\mathbb{B}$s false negative.

###  3.2 Operations

for tree= if level=0align=centeralign=@C20mm@, , grow=east, draw, font=, edge
path= [draw, edge] (!u.parent anchor) – +(4mm,0) —- (.child anchor)edge label;
, parent anchor=east, child anchor=west, l sep=10mm  [Operations [Deletion]
[Lookup] [Insertion] ]

Figure 6: Operations of Bloom Filter

Bloom Filter supports three key operations, namely, insert, lookup, and
delete.

####  3.2.1 Insertion

Bloom Filter stores bit information about an input item in bitmap array. Any
input item is hashed into a particular slot of the bitmap array and the slot
is set to ‘1’ in insertion operation. As shown in Figure 5, input item $X$ is
hashed and three hash functions (i.e $h_{1}()$, $h_{2}()$, and $h_{3}()$)
generates three bit locations. These locations are set to 1. Similarly, the
input item $Y$ is inserted.

Any hash function can be used to insert an item in Bloom Filter, namely,
CRC32, MD5, FNV, DJB and other hash functions. The Murmur hash function is the
fastest hash algorithm among the string hash functions including FNV1, FNV1a,
CRC32, DJB, DJB2a, SuperFastHash and xxHash. The Murmur hash function has
three version Murmur, Murmur2 and Murmur3. Algorithm 1 uses Murmur hash
function to hash the input items in the Bloom Filter. The input item $Key$,
string length $length$ and seeds $S_{1},~{}S_{2},~{}and~{}S_{3}$ are passed to
Murmur hash function. The seed values are prime numbers. The Murmur hash
function returns a ten digit number. The ten digit number is hashed using $m$
where $m$ is the size of Bloom array. The performance of Bloom Filter depends
on the Murmur hash function and the number of modulus operations in Algorithm
1.

The insertion operation performance depends on the number of hash functions.
Therefore, the time complexity of insertion operation is $O(k)$ where $k$ =
number of hash functions. $k$ is constant, therefore the time complexity of
insertion operation is $O(1)$.

Algorithm 1 Insertion of an input item $Key$ into Bloom Filter $\mathbb{B}$
using three hash functions. The seed values $Seed~{}S_{1},~{}S_{2},~{}S_{3}$
are used to create different hash functions.

1:procedure Insert($\mathbb{B}[],~{}Key,~{}S_{1},~{}S_{2},~{}S_{3}$)

2: $v_{1}=\textsc{Murmur}(Key,~{}length,~{}S_{1})\%m$ $\triangleright$ $m$ is
the size of $\mathbb{B}[]$ which is a prime number.

3: $v_{2}=\textsc{Murmur}(Key,~{}length,~{}S_{2})\%m$ $\triangleright$ % is
modulus operator

4: $v_{3}=\textsc{Murmur}(Key,~{}length,~{}S_{3})\%m$

5: $\mathbb{B}[v_{1}]\leftarrow 1$ $\triangleright$ Key is hashed into Bloom
Filter array $\mathbb{B}[]$ to insert the input item $Key$

6: $\mathbb{B}[v_{2}]\leftarrow 1$

7: $\mathbb{B}[v_{3}]\leftarrow 1$

8:end procedure

####  3.2.2 Lookup

Bloom Filter is most popular for its deduplication. Both in insertion and
deletion operations first the item is searched in the Bloom Filter. Therefore,
lookup operation is the most invoked operation in Bloom Filter. As shown in
Figure 5, lookup operation is invoked for item $X$. Similar to insertion
operation, $X$ is hashed by $k$ hash functions. The bit value of the location
generated by the hash function is checked. In case all bits are 1, then $True$
is returned. In case at least one bit is 0, then $False$ is returned.

Algorithm 2 is Lookup operation invoking three Murmur hash functions. The AND-
ing operations are performed to examine whether the item $Key$ is a member of
the Bloom Filter or not, i.e.,
$\mathbb{B}[v_{1}]~{}AND~{}\mathbb{B}[v_{2}]~{}AND~{}\mathbb{B}[v_{3}]$. If
any slot contains $0$ values, then the item is not a member of the Bloom
Filter and the Bloom Filter returns negative.

Similar to insertion operation, the time complexity of lookup operation is
$O(k)\approx O(1)$.

Algorithm 2 Lookup an item $Key$ in Bloom Filter using three hash functions.

1:procedure Lookup($\mathbb{B}[],~{}Key,~{}S_{1},~{}S_{2},~{}S_{3}$)

2: $v_{1}=\textsc{Murmur}(Key,~{}length,~{}S_{1})\%m$

3: $v_{2}=\textsc{Murmur}(Key,~{}length,~{}S_{2})\%m$

4: $v_{3}=\textsc{Murmur}(Key,~{}length,~{}S_{3})\%m$

5: if $\mathbb{B}[v_{1}]~{}AND~{}\mathbb{B}[v_{2}]~{}AND~{}\mathbb{B}[v_{3}]$
then $\triangleright$ AND-ing operation is perform to check the bit values of
$\mathbb{B}[]$.

6: $\textbf{return}{}~{}True$

7: else

8: $\textbf{return}{}~{}False$

9: end if

10:end procedure

####  3.2.3 Deletion

Algorithms 3 performs deletion operation on non-counting Bloom Filter. Before
deleting an item, lookup operation is performed. If the item exists in the
Bloom Filter, then reset the bit values to $0$. The bit locations are obtained
as discussed in insertion and lookup operations. Bloom Filter may reset the
bit location to ‘0’ in case of an absent key, if the lookup operation is not
performed before the deletion operation. To elaborate, let us assume
$\mathbb{B}[v_{1}]=1$, $\mathbb{B}[v_{2}]=0$ and $\mathbb{B}[v_{3}]=1$. In
this case, the $\mathbb{B}[v_{1}]$ and $\mathbb{B}[v_{3}]$ are reset to zero
unnecessarily, albeit, the item was not actually present in the Bloom Filer.
This causes a false negative issue. Thus, the lookup operation is performed
before removal of an item from Bloom Filter. However, this process does not
ensure free from false negatives due to collision probability in deletion
operation. For instance, let us assume $\mathbb{B}[v_{1}]=1$,
$\mathbb{B}[v_{2}]=1$ and $\mathbb{B}[v_{3}]=1$, and the item was not actually
inserted into Bloom Filter. The slots are exhibiting value ‘1’ due to the
false positives. In deletion operation, the slots are reset to ‘0’ assuming
that the item was inserted into the Bloom Filter while it is not the case.
Thus, conventional Bloom Filter exhibits false negative if and only if it
supports the deletion operation. Therefore, deletion operation is not
permitted in the conventional Bloom Filter. To permit the deletion operation,
counting Bloom Filter was introduced. The time complexity of deletion
operation is similar to insertion and lookup operations, i.e., $O(1)$.

Algorithm 3 Deletion of an item $Key$ from Bloom Filter using three hash
functions.

1:procedure Delete($\mathbb{B}[],~{}Key,~{}S_{1},~{}S_{2},~{}S_{3}$)

2: $v_{1}=\textsc{Murmur}(Key,~{}length,~{}S_{1})\%m$

3: $v_{2}=\textsc{Murmur}(Key,~{}length,~{}S_{2})\%m$

4: $v_{3}=\textsc{Murmur}(Key,~{}length,~{}S_{3})\%m$

5: if $\mathbb{B}[v_{1}]~{}AND~{}\mathbb{B}[v_{2}]~{}AND~{}\mathbb{B}[v_{3}]$
then

6: $\mathbb{B}[v_{1}]\leftarrow 0$ $\triangleright$ Key is hashed into Bloom
Filter array $\mathbb{B}[]$ to reset to $0$ for the input item $Key$

7: $\mathbb{B}[v_{2}]\leftarrow 0$

8: $\mathbb{B}[v_{3}]\leftarrow 0$

9: else

10: False

11: end if

12:end procedure

###  3.3 Taxonomy of Bloom Filter

for tree= align=center, parent anchor=south, child anchor=north, font=,
edge=thick, -Stealth[], l sep+=10pt, edge path= [draw, edge] (!u.parent
anchor) – +(0,-10pt) -— (.child anchor)edge label; , if level=0 inner
xsep=0pt, tikz=[thick] (.south east) – (.south west);  [Bloom Filter [Platform
[ HDD
Flash memory/SSD
RAM Cache ]] [Implementation [Multi-dimensional
Chain
Hierarchical
Block-based
Flat] ] [Memory Allocation [Dynamic
Static] ] [Architecture [Counting
Non-counting] ] ]

Figure 7: Taxonomy of Bloom Filters

Figure 7 classifies the variants of Bloom Filters depending on the
characteristics. Bloom Filter poses different characteristics depending on the
architecture, memory allocation, implementation, and platform. For instance, a
Bloom Filter can be counting or non-counting type. The next subsequent
subsection illustrates about taxonomy depicted in Figure 7.

####  3.3.1 Architecture

Bloom Filter is classified into two key categories, particularly, counting
Bloom Filter, and non-counting Bloom Filter depending on the architecture.
Counting Bloom Filter (CBF) [77] typically count the number of input and
increment the counter upon insertion of an item. The counter is decremented
upon deletion of an item. Let, $X=3$ be the value of counter for certain
states. The $X$ value is decremented upon removal of an item, and thus, $X=2$.
Now, if the deleted item is looked up again, then Bloom Filter returns true,
since, $X>0$. Thus, the false positive become a challenge in CBF, but CBF has
a low false negative probability. Furthermore, CBF offers high scalability. On
the other hand, non-counting Bloom Filter set the bit to 1 during insertion of
an item, and set the bit to 0 during deletion of an item. Thus, there is a
false negative issue in non-counting Bloom Filter.

####  3.3.2 Memory allocation

We classify the Bloom Filter into two types depending on the memory allocation
strategy, specifically, static Bloom Filter and dynamic Bloom Filter. Static
Bloom Filter allocates memory once, and does not permit to increase the
allocated memory size. Also, static Bloom Filter does not allow to alter the
parameters of the Bloom Filter. However, another instance of static Bloom
Filter can be created on demand. Thus, static Bloom Filter meets the
requirement of scalability. On the contrary, dynamic Bloom Filter allocates
memory as per the requirement of the current situation. Dynamic Bloom Filter
grows the size over a time period and adjust automatically. However, the
dynamic Bloom Filter requires adjustment of the Bloom Filter to keep the same
rule of insertion, lookup, and deletion. These requirements make the designing
of dynamic Bloom Filter more complex compared to static Bloom Filter.

####  3.3.3 Implementation

Based on implementation, Bloom Filter is classified into five categories,
particularly, flat Bloom Filter, block-based Bloom Filter, hierarchical Bloom
Filter, chained Bloom Filter, and multidimensional Bloom Filter. Flat Bloom
Filter uses an array of bits. The bit array contains information about
membership of a large dataset. Block-based Bloom Filter creates multiple
blocks on the given bit array to reduce the collision probability. However,
this is similar to flat Bloom Filter. Notably, hierarchical Bloom Filters
create multiple Bloom Filters and forms treelike structure. Each node of the
hierarchical Bloom Filter is embedded with conventional Bloom Filter. The
hierarchical Bloom Filters greatly helpful in very large scale membership
filtering. Similarly, the chained Bloom Filter creates a chain of multiple
Bloom Filters to increase scalability, i.e., the chained Bloom Filter creates
a chain of Bloom Filters. A new Bloom Filter is linked to chained Bloom Filter
to increase the scalability. On the contrary, multidimensional Bloom Filter is
implemented using multidimensional Bloom Filter array [103]. For instance, 3D
array. Multidimensional Bloom Filter is similar to flat Bloom Filter except it
has more dimension.

####  3.3.4 Platform

Finally, we categorize the Bloom Filter into four key categories based on
platform, namely, cache, RAM, Flash/SSD, and HDD. Cache-based Bloom Filter is
designed to improve the caching performance. However, caching can be
implemented in cache memory, and main memory. The block size of Bloom Filter
is ought to be small such that the block size should fit in cache memory. On
the other hand, the RAM-based Bloom Filters are most popular. Bloom Filters
are stored in RAM. Flash/SSD is used to increase the scalability and fault
tolerance. This type of Bloom Filter adapts lazy write policy, whereas any
update does not immediately cause write into Flash/SSD. Immediate update cause
performance issue because the update operation writes 3-8 bits per update into
Flash/SSD. Thus, Flash/SSD based Bloom Filter adapts lazy write-back policy.
Similar to Flash/SSD based Bloom Filter, the HDD is used to backup the Bloom
Filter to implement persistence Bloom Filter. If the system shuts down, then
Bloom Filter can be reconstructed from the backup which is stored in HDD.

###  3.4 Key objective

for tree= if level=0align=centeralign=@C40mm@, , grow=east, draw, font=, edge
path= [draw, edge] (!u.parent anchor) – +(4mm,0) —- (.child anchor)edge label;
, parent anchor=east, child anchor=west, l sep=10mm  [Objective [Maximize
Performance] [Increase Scalability] [Reduce False negative] [Reduce False
positive] ]

Figure 8: Key objectives of Bloom Filters

The prime objectives of developing new variants of Bloom Filter are maximize
performance, increase scalability, reduce false negative and reduce false
positive. False positive and false negative are the key issues of Bloom
Filter. Therefore, there are numerous variants of Bloom Filter to reduce both
issues. However, performance of Bloom Filter is effected while reducing those
issues. Moreover, increasing scalability is also a challenge. Because, the
applications of Bloom Filter demand large scale Bloom Filter, for instance,
deduplication. There is a trade-off between false positive and performance. A
few Bloom Filters sacrifice performance to reduce false positive. For
instance, Cuckoo Filter [44]. Also, sometime the space consumption increases
to reduce false positive.

###  3.5 Issues and Challenges

The simplicity and performance of Bloom Filter positively impact the research
community and developers. However, there are still some issues and challenges
in the Bloom Filter.

####  3.5.1 False Positive and false negative

False positive and false negative are a key issue in Bloom Filter data
structure. False positive negatively impacts the Bloom Filter. A false
positive is an overhead to Bloom Filter. It increments the procedural steps by
unnecessary searching in the application. Hence, the key challenge is to
reduce the false positive probability. The counting Bloom Filter exhibits high
false positive probability while it lowers the false negatives. Similarly, the
non-counting Bloom Filter lowers the false positive probability while it
exhibits high false negative probability provided if it allows the deletion
operation. Therefore, non-counting Bloom Filter does not support deletion
operation to prevent the false negative. On the other hand, false positive
introduces errors in duplicate key filtering. False positive filter out the
wrong elements due to collision. On the other hand, false negative also
introduces error in some applications. Therefore, it’s a grand challenge to
reduce both the false positive and false negative probability of Bloom Filter.

The false positive of Bloom Filter can be derived from $m$, $n$ and $k$ where
$m$ is the size of memory, $n$ is the number of input items and $k$ is the
number of hash functions, the probability of a particular slot is not set to
$1$ by a particular hash function is

$\left(1-\frac{1}{m}\right)$

Let us assume, $k$ hash functions are used by the Bloom Filter and the above
probability is

$\left(1-\frac{1}{m}\right)^{k}$

If $n$ elements are inserted into the Bloom Filter and the above probability
is

$\left(1-\frac{1}{m}\right)^{nk}$

The probability of that particular bit to be $1$ is

$p=1-\left(1-\frac{1}{m}\right)^{nk}\approx\left(1-e^{-\frac{kn}{m}}\right)$
(1)

From Equation (1), the required memory can be calculated by the optimal number
of hash functions.

####  3.5.2 Scalability

Scalability is also a key issue in the Bloom Filter. Conventional Bloom Filter
is non-scalable. Large number of entries causes more occurrences of false
positive. Let the set be $\mathcal{S}$nd the total number of elements in the
set be $n$. Elements are
$\varepsilon_{1},~{}\varepsilon_{2},~{}\varepsilon_{3},~{}\ldots~{}\varepsilon_{n}$.
During insertion, the element is mapped to $k$ slots of the Bloom Filter. If
the value of $n$ increases, then the number of slots set to 1 increases. This
leads to increase in the probability of false positive. Therefore, high
scalability is a prominent challenge to achieve.

####  3.5.3 Space complexity

Bloom Filter requires extra space from primary memory to hold the information
of the elements. Different kinds of Bloom Filter have different space
requirements. For example, CBF has an extra information in each slot i.e. the
counter. The counter also requires some memory. Therefore, the CBF [77]
consumes more memory than other variants. Thus, low space consumption is
another challenge to achieve. The space requirement is calculated by

$m=-\frac{n~{}lnp}{(ln2)^{2}}$

where $n$ is the number of input items and $p$ is the desired false positive
probability.

####  3.5.4 Deletion

The conventional Bloom Filter does not support deletion. Nowadays, most of the
Bloom Filters support deletion operation. However, it is a great challenge to
design an efficient deletion algorithm where false negative is also reduced.
If a Bloom Filter variant does not support deletion, then the Bloom Filter
array sets all slots to 1 over a time period. Thus, the false positive
probability leads to 100%. Therefore, an efficient deletion algorithm for the
Bloom Filter is essential. CBF implements deletion operation where deletion
does not cause a false negative. However, CBF suffers from high false positive
probability.

####  3.5.5 Hashing

Bloom Filter is a hashing data structure that uses a complex hashing technique
which is introduced to reduce the false positive probability, for example,
Murmur hashing [16], Cuckoo hashing [96], SHA-1 [41], SHA-2 [106], SHA-3 [40],
MD5, and other cryptographic hashing. However, nested use of such complex
hashing scheme introduces computational overhead. The challenge is to have an
optimal number of hash functions while maintaining the desired false positive
probability.

####  3.5.6 Dependency on number of hash functions

Bloom Filter depends on the number of hash functions to place an item in
various locations of Bloom Filter. Bloom Filter requires an optimal number of
hash functions to reduce the false positive probability and improve
performance. A large number of hash functions place an item in various places
which consumes more bits. Consequently, false positive increases. The Less
number of hash functions increases false positive. However, reduction of hash
functions improves the performance of Bloom Filter. The optimal number of hash
functions $k$ is

$k=\frac{m}{n}ln2$

where $m$ is memory size and $n$ is the number of inputs.

####  3.5.7 Dependency on input item size

Bloom Filter consumes memory based on input item sizes. Conventional Bloom
Filter does not depend on the input item size. However, fingerprint-based
Bloom Filter depends on the input item size. This is another issue in
fingerprint-based Bloom Filter.

####  3.5.8 Performance

Bloom Filter is a performance enhancer. Therefore, the performance of Bloom
Filter impacts the system. Hierarchical Bloom Filter is able to scale massive
input items, however, the performance is not satisfactory. For instance,
BloomFlash [36]. On the other hand, scaleBF is able to filter the massive
amounts of input items [99].

##  4 Variants of Bloom Filter

Subsequent years saw the development of various variants of Bloom Filters. The
main motive to develop various variants despite of good performance of the
conventional Bloom Filter is reduction of false positive and false negative
issues. In this section, various such variants are discussed in detail.
However, only those Bloom Filter variants that are used in the NDN techniques
are discussed in this article. Table LABEL:BF_table highlights the advantages
and disadvantages of the Bloom Filters.

###  4.1 Compressed Bloom Filter

Compressed Bloom Filter [88] reduces the number of broadcast bits. Moreover,
it reduces computations per lookup and false positive probability. Compressed
Bloom Filter is used as a proxy. In compressed Bloom Filter, first the Bloom
Filter is compressed and transmitted to the destination node. After receiving
the compressed Bloom Filter at the destination node, it is decompressed to the
original array. Bloom Filter is partitioned into parts and each part is
compressed separately. At destination node required parts are decompressed.
This reduces the decompression computation time. Compressed Bloom Filter
implements a less number of hash functions. Hence, requires less computation
per lookup. Compressed Bloom Filters produce less traffic. However,
compression and decompression processing are overheads. Moreover, the
processing consumes large memory at the endpoint machines.

###  4.2 Stateful Bloom Filter

Approximate Concurrent State Machines (ACSMs) [21] helps to compactly present
concurrent state machines. Concurrent state machines help to track the state
of a huge number of flows simultaneously. In Stateful Bloom Filter (SBF), a
slot consists of a cell value and a counter. The cell value saves the flow ID
and state of the flow. A state have value [1,v] or $null$. Along with false
positive and false negative, SCF returns another error called $don’t~{}know$
(DK). DK occurs when in a slot the cell value have null, but counter have
value 2 or more. This means many flows are hashed to that slot having
different states. Initially, the cell value is assigned null and counter as 0.
During an insert operation, first flow ID is hashed by $k$ hash functions to
obtain $k$ slots. In case counter=0, then cell value is as assigned by a new
value and counter is incremented. In case, the cell value is DK or equal to
flow ID, the counter is incremented. When cell value $\neq$ flow ID, increment
the counter, but cell value is assigned by DK. During modify operation, first
$k$ slots are found. In case, the cell value is DK, then ignore. When
counter=1, modify the cell value. If counter¿1, cell value is assigned to DK.
During delete operation, in case counter=1, then cell value=0. If counter is
at least 1, then the counter is decremented and cell value is unchanged.
During a query, first $k$ slots are found. All slots are checked. In case, all
cell values are DK, then return DK as a response. When at least one value is
not DK, then return that value. If the slots have different values, then the
requested flow is absent. SBF has less space complexity compared to CBF [77].
SBF is applicable for application-aware network devices. However, the
application has to tolerate some false positive response. Another issue is
that if improperly terminated flows are saved in Bloom Filter, then Bloom
Filter gives more DK returns. Moreover, if DK error is ignored, then it
increases the false negative probability. Also, over a time period, most of
the cells are filled with DK values.

###  4.3 Stable Bloom Filter

Stable Bloom Filter (Stable BF)[37] is a variant of Bloom Filter. Each element
in Stable BF is about $d$ bits and called as cell. Each cell can have maximum
value $Max$. Initially, the cell is assigned to a value 0. Stable BF uses $k$
uniform and independent hash functions. During insertion, first Stable BF is
checked whether it is a duplicate. Then, randomly $P$ cells are decremented by
1. This step makes space for insertion of new elements. Then, each element is
mapped to $k$ cells. Then, the $k$ cells are set to $Max$. The Bloom Filter is
called stable because using theorem it is proved, after many iterations the
probability that the cells becomes zero is a constant. The array becomes
stable when the number of iterations is infinite which is practically
impossible. False positive probability is
$(1-(\frac{1}{1+\frac{1}{P(1/(Z-1/m))}})^{Max})^{Z}$ where $Z$=number of cells
set to $Max$ and $m$ = array size. The processing of each element is
independent of the array size. Each element processing time is O(1). Stable BF
does not have a false negative issue.

###  4.4 Attenuated Bloom Filter

Attenuated Bloom Filter (ABF) [79] is a hierarchical Bloom Filter consists of
multiple conventional Bloom Filters. The first layer consists of the
information about the current node. The second layer consists of information
regarding nodes, which are just one hop far away. Therefore, context type
information about the nodes $(i-1)$ hops away is found in the $ith$ layer.
Saturation of the Bloom Filter is avoided by attenuating bits set that are far
away from the sources. Context aggregation is implemented by ABFs. Context
discovery using ABFs is a method of combining reactive and proactive discovery
mechanisms. Nodes exchanges Bloom Filters to collect context types information
and their distribution. When there is a query, the node will first check
locally for its existence. If it does not exist, the query is performed on
Bloom Filter. After that it is compared to local filters. If a match is found
at any layer, a query message consisting of the Bloom Filter received from the
stored filter is sent to the neighbor. In case same query is received by the
node, the query is dropped. Each node records the path of each query message.
If an exact match is found, then a Context-Available reply is sent as a
response. If no match is found, it is discarded. The rate of false positive is
identical to the conventional Bloom Filters. The performance of ABF highly
depends on the appropriate ratio of the query and advertisement rates, and a
query range of nodes.

###  4.5 Retouched Bloom Filter

Retouched Bloom Filter (RBF) [39] makes conventional Bloom Filters more
flexible. [It reduces selected false positives, but introduces false
negatives]. It implements a bit clearing process, in which it resets
individually chosen bits in the vector $v$ for 0. This removes some false
positives, but it produces false negatives. In case of randomized bit
clearing, false positives depend on the size of $U-A$ where $U$ is the
universal set and $A$ is the element set. False negatives depend on the size
of $A$. $U-A$ is much bigger than $A$, therefore resetting a bit to 0 in $v$
eliminates a large number of false positives compared to the number of false
negatives generated. In case of selective clearing, those bits are focused
which correspond to elements that trigger false positives. This is done using
various algorithms. False positives encountered are recorded in a set.
[Elements of the set are false positives that are labeled as troublesome
keys]. These are eliminated from the Bloom Filter. RBFs are applied across a
wide range of applications. The applications have to identify false positive
instances. A false negative is more damaging compared to false positives.
Hence, exchanging false negative with false positive is more damaging.

###  4.6 Invertible Bloom Filter

Goodrich and Mitzenmacher [53] proposed an invertible Bloom lookup table
(IBLT). The element of IBLT is $key-value$. IBLT is capable of tolerating some
natural errors (eg., deletion of an absent element, insertion of keys with
different values simultaneously). IBLT along with standard operations (insert,
delete and query) also supports listing operation. Listing operation lists all
$key-value$s present in IBLT. This operation sometimes returns a partial list
with an $list-incomplete$ error. IBLT consist of a lookup table. Each cell in
lookup table is a single memory word. Each cell consists of three fields,
namely, counter, keySum and valueSum. The counter counts the number of
elements hashed to its corresponding cell. keySum stores the total sum of all
the $key$s hashed to its corresponding cell. valueSum stores the total sum of
all the values hashed to its corresponding cell. Initially, all cells are
assigned the value 0. In insert operation of an element $key-value$, first
$key$ is hashed by $k$ hash functions to obtain $k$ locations. The element is
stored in $k$ locations. If the element is inserted for the first time, then
assign counter = 0, keySum=$key$ and valueSum=$value$. In case of duplicate
element, the counter is incremented and keySum = $Previous_{keySum}$\+ $key$,
valueSum = $Previous_{valueSum}$+$value$. In delete operation, the counter is
decremented and keySum = $Previous_{keySum}$\- $key$, valueSum =
$Previous_{valueSum}$-$value$. During query operation, if the counter is 0,
then return $False$. If counter is greater than 0, then return $True$. IBLT
handles natural errors by defining an extra cell field and a hash function.
IBLT uses quotienting to reduce the space complexity.

###  4.7 Mapping Bloom Filter

Mapping Bloom Filter (MBF) [74] is an improved Bloom Filter to reduce the
space complexity on on-chip memory. MBF consists of a Packet Store and an
Index Table. Index Table consists of a Bloom Filter and a Mapping Array (MA).
Initially, all bits of Bloom Filter and MA are set to 0. Packet store is
accessed using MA. MA gives the offset address of the Packet Store of $n$ bits
length. Bloom Filter is partitioned into $n$ parts. Each part maps to one bit
of MA. When an element is inserted it is hashed using $k$ hash functions. The
part to which the element is hashed, that corresponding bit in MA is set to 1
and other bits remain as 0. Same procedure as convention Bloom Filter is
followed to insert element into the Bloom Filter.

###  4.8 Complement Bloom Filter

Complement Bloom Filter [78] is a Bloom Filter variant that determines the
trueness of positive responses returned by the Bloom Filter. The Bloom Filter
variant uses two Bloom Filters. One is a conventional Bloom Filter and other
is the complement of the Bloom Filter. After construction of the Bloom Filter,
complement Bloom Filter is constructed using the Bloom Filter. During query
operation, the item is checked in both Bloom Filters. In case, both Bloom
Filters return $True$, a hash table is checked to verify the false positive.
Using two Bloom Filters and a hash table to reduce the false positive
probability is a big compromise with memory. Bloom Filter is mostly used to
handle the huge number of packets. And, many are duplicate packets. Hence, the
majority of the responses of the Bloom Filters are positive. Therefore, the
frequency of referring to the hash table increases.

###  4.9 Compression Trie-based Bloom Filter

Zhang [145] proposed Compression Trie-based Bloom Filter (CT-BF) for filtering
Interest in a content store. It is deployed on on-chip memory for faster
searching process. Moreover, the compression trie accommodates a huge number
of names in space constraint on-chip Bloom Filter. The names in NDN have
multiple segments. These segments are separated by ”/”. The separator is used
in a content store to organize the name trie. A whole name is obtained by the
conjunction of name from the root to a leaf node. Moreover, the same node
children share the same prefix. In compression trie, only the leaf nodes of
the names are inserted into the Bloom Filter. In CT-BF, false positive is
based on the depth of the trie. During insert operation, the first segment is
added to the first level and the second segment at second level. This process
is repeated till all segments are inserted. During delete operation, the last
segment is deleted (i.e., leaf node) first, then the second last segment.
Again, this process is repeated till all the segments are deleted. Another
variant of compression trie is proposed, called Adaptive Compression Trie
(ACT). It dynamically adjusts the size of Bloom Filter to increase the
filtering efficiency. When more mismatch occurs in any node in compression
trie, that space is expanded. The expansion is the process of deleting leaf
nodes and inserting its children as leaves. Longer name increases filtering
efficiency. This process consumes space, hence, shrinking operation is
performed to decrease unwanted space. In shrinking operation, the space where
very less request is made is reduced by a new node. The children of the new
node are compressed and deleted from compression trie. Construction of ACT-BF
is performed in two steps. First, CT-BF is constructed. False positive and
filter ratio of the Compression Trie is calculated based on space constraints.
Then, CT-BF is reconstructed. When mismatch crosses a threshold value ACT-BF
is constructed. This improves the filtering efficiency. When CT-BF reaches the
fifth level the false positive probability increases. Hence, the depth of CT-
BF is not increased further than fifth level.

###  4.10 Bitmap-mapping Bloom Filter

Bitmap-mapping Bloom Filter (B-MBF) [75] is a variant of MBF [74]. B-MBF is
proposed by combining bitmap and MBF. The number of slots of MA and the bitmap
is exponential. The bitmap is about $N$ dynamic memory spaces. MA value gives
the element location in the bitmap. Based on the sequence of insertion of
elements, the sequence number is assigned to the element. This sequence number
serves as the offset address. Based on the offset address, memory for the
element is assigned in off-chip memory. This memory is dynamically allocated.
The memory is allocated dynamically to reduce memory consumption. B-MBF
includes a CBF [77] to permit the delete operation, however, memory
consumption increases. Hence, the advantage gained is lost. The false positive
probability is same as MBF.

###  4.11 Sum-Up Counting Bloom Filter

Sum-Up Counting Bloom Filter (SCBF) [58, 135] is a variant of CBF [77]. It
contains a CBF with $k$ hash functions, Hash-based Lookup Table (LT) and a
Sum-up Table (ST). Each ST slot corresponds to a LT slot. The slot value is
determined by the corresponding counter in each CBF level. $k$ hash functions
of CBF maps the string to $k$ bits. Then the string is encoded. Then, the
smallest value slot is chosen from ST. Its index helps in locating the string
in LT. ST and LT reduces the false positive probability. In case CBF returns
false positive result, ST does not save the string. This results in accurate
and fast searching. ST performs mapping between CBF and LT, while LT is
responsible for query.

###  4.12 Fast Two Dimensional Filter

Fast Two Dimensional Filter (FTDF) [120, 119] is a fingerprint based Bloom
Filter. Initially, all cells of FTDF matrix are initialized to zero. Then a
quotienting technique is executed. The hash function returns a string called
fingerprint. The fingerprint is separated into two parts, namely, quotient and
remainder. The quotient is the most significant bits. And, the remainder is
the least significant bits. The Bloom Filter maps every element into a single
bit by finding the fingerprint and using quotient as row index and remainder
as column index. FTDF has low memory consumption. It is scalable. Also, it is
easy for implementation without dedicated hardware. The cell value 0 indicates
the absence of the fingerprint of the item. The cell value 1, indicates the
presence of the fingerprint with very high probability. FTDF delete operation
is very fast. For deletion, the content of the position is simply altered from
1 to 0. FTDF is more influenced by hard collision compared to soft collision.
A soft collision occurs when two or more elements have different fingerprints,
but same quotient fractions. Hard collision is when two or more elements have
the same fingerprint.

Table 3: Comparison of Bloom Filters Name |  Advantages |  Disadvantages
---|---|---
Compress- ed [88], 2002 |  $\bullet$ Reduces the number of broadcast bits $\bullet$ Bloom Filter is used as a proxy $\bullet$ Only required part of the compressed Bloom Filter is decompresses which reduces decompression computation time $\bullet$ Reduces network traffic $\bullet$ Reduces number of computations per lookup $\bullet$ Reduces false positive probability |  $\bullet$ Increases processing time due to compression and decompression processes $\bullet$ Large memory consumption at endpoint machines $\bullet$ Performance of compression process depends on the array size
Stateful [21], 2006 |  $\bullet$ State of the flow is saved in the Bloom Filter
$\bullet$ Space complexity is less compared to conventional CBF
$\bullet$ Applicable for application-aware network devices |  $\bullet$ Applicable in system that tolerate some false positive
$\bullet$ Apart from false positive and false negative another error called
$Don’t~{}know$ is present
$\bullet$ In some applications, ignoring DK error leads to an increase in
false negativity
$\bullet$ Collision in the slot leads to DK error
$\bullet$ Saving improperly terminated flows in Bloom Filter returns more DK
error
Stable [37], 2006 |  $\bullet$ With limited storage, it has less false positive probability
$\bullet$ False positive probability is dependent on the number of 0s in the
array
$\bullet$ Processing of each element is independent of array size
$\bullet$ Each element processing time is O(1) |  $\bullet$ Decrementing random cells by 1 may set the counter to 0 which leads to increase in false positive probability
$\bullet$ The array becomes stable when the number of iterations is infinite
which is practically impossible
Attenuated [79], 2006 |  $\bullet$ Context aggregation is easily implemented
$\bullet$ Content discovery can be implemented
$\bullet$ Context information about nodes are easily found |  $\bullet$ High false positive and false negative probability due to use of conventional Bloom Filters
$\bullet$ Performance highly depends on the appropriate ratio of the query and
advertisement rates, and a query range of nodes
$\bullet$ Density of network context information sources influences the
performance
Retouched [39], 2010 |  $\bullet$ Reduces false positive probability |  $\bullet$ In exchange of false positive false negatives is introduced $\bullet$ Application implementing RBF must understand the instances of false positive
Invertible [53], 2011 |  $\bullet$ Complete listing of tolerance towards some natural errors
$\bullet$ Quotienting reduces the space complexity |  $\bullet$ Number of duplicate elements are limited to a threshold value
$\bullet$ In some cases of listing operation, IBLT returns partial list, and
an error
$\bullet$ Counter overflow
Mapping (MBF) [74], 2014 |  $\bullet$ Consumes less on-chip memory
$\bullet$ Increases efficiency of Index table |  $\bullet$ Uses conventional Bloom Filter which has high false positive and false negative probability
$\bullet$ Off-chip memory is wasted
Comple- ment [78], 2015 |  $\bullet$ Determines the trueness of Bloom Filter positives
$\bullet$ Reduces false positive probability |  $\bullet$ Compromises with memory
$\bullet$ Increase in size of Bloom Filter increases the frequency of hash
table reference
$\bullet$ Time complexity increases in case of huge number of packets
Compress- ion Trie-based [145], 2017 |  $\bullet$ False positive reduces with increase in level of compression
$\bullet$ Update operation does not require extra space
$\bullet$ Cache hit ratio of content store increases |  $\bullet$ Increment in level, increases space complexity
$\bullet$ Determining the false positive from the Bloom Filter capacity is
difficult
$\bullet$ Expansion and shrinking process of ACT sometimes negatively affect
the query operation
$\bullet$ Expansion operation by ACT consumes more memory space
$\bullet$ CT-BF level cannot increment further than fifth level due to
increase in false positive probability
Bitmap-mapping [75], 2018 |  $\bullet$ Memory is dynamically allocated |  $\bullet$ False positive probability is same as MBF. Hence, no improvement
$\bullet$ Implements CBF to permit delete operation, but it increases memory
consumption
Sum-up Counting [58], 2018 |  $\bullet$ Reduces false positive probability
$\bullet$ Enhances data content matching rate
$\bullet$ Improves data content searching rate and accuracy
$\bullet$ Reduces searching time |  $\bullet$ Consists of CBF, which has higher memory consumption than conventional Bloom Filter
Fast Two Dimensional Filter [120, 119], 2019 |  $\bullet$ Scalable
$\bullet$ Easy to implement without dedicated hardware
$\bullet$ Fast delete operation
$\bullet$ Reduces false positive probability
$\bullet$ Not affected by soft collision
$\bullet$ Occupies less memory |  $\bullet$ Influenced by hard collision

##  5 Named data networking (NDN)

The NDN is conceptualized from the Information-Centric Networks (ICN) [8,
138]. Ted Nelson proposed 17 rules in his project, called Project Xanadu in
1979. These 17 rules provide the basic principles of ICN. Project Xanadu was
founded in 1960. However, it took a very long time to make Project Xanadu
visible. The Wired magazine criticized Project Xanadu and published an article
called “The Curse of Xanadu“ [133]. Wired magazine called the project as “the
longest-running vaporware story in the history of the computer industry“.
Vaporware is mostly used in computer domain which is defined as a product
(computer software or hardware) that is announced officially but not actually
manufactured or cancelled officially. In 1988, an incomplete implementation
was released. However, in 2014, a working version, called OpenXanadu, was
released. After the declaration of Project Xanadu, Stanford proposed TRIAD
project [124] in the year 1999. TRIAD is defined as Translating Relaying
Internetwork Architecture integrating Active Directories. In this project, the
name of an object is used to route to avoid DNS (Domain name system) lookups.
TRIAD concept is improved in another project called Data Oriented Network
Architecture (DONA) [67, 138] by UC Berkeley and ICSI in the year 2006. DONA
project improves TRIAD by adding security (authenticity) and persistence to
the architecture as first-class primitives. In 2009, under CCNx project PARC
released an initial open source implementation with content-centric
architecture. In 2010, NDN is proposed. NDN is defined as an instance of more
general network research direction of ICN [117].

A new era of Internet expects new things from NDN. A network layer of NDN
[142] must be scalable. A single network consists of millions of nodes and
also dynamic in nature due to the addition and removal of mobile devices.
These million nodes make millions of requests per second. Therefore, NDN needs
to be capable of providing services with less traffic and congestion. NDN [26]
have to provide high level security. The security includes origin
authentication, integrity, and capability of evaluating the importance of
routing information. In NDN, every named content is digitally signed by the
sender. This helps in storing data in cache for future use. Moreover, it helps
in saving bandwidth and efficient utilization of multiple network interfaces
[51]. NDN has to be resilient [12, 126]. It constantly maintains efficient
packet delivery performance. NDN follows one interest and fetches at most one
data packet to maintain the balanced packet flow. Moreover, NDN balances the
packet flow in every hop to prevent additional execution of congestion control
techniques in between the network path [62].

###  5.1 Why NDN architecture is called an hourglass architecture?

The answer lies with the hourglass architecture of Internet protocol (IP). The
layered architecture of IP appears as an hourglass. The architecture of the
Internet has seven layers (specifically, application, presentation, session,
transport, network, data-link, and physical layer). The protocols implemented
in every layer are represented in Figure 9 (left), and it takes a shape of an
hourglass based on a number of protocols. Top and bottom layers have many
protocols. Middle layer contains IP protocol, transport layer contains two
protocols and network layer contains one protocol. Some modification is
performed to the IP hourglass architecture to support NDN. As shown in Figure
9, the two new layers, i.e., the security and strategy are added to NDN
architecture. And, the waist layer is named data/content chunk.

Figure 9: The main building blocks of NDN [Source [143]].

NDN mainly consist of three components, namely, Content Store (CS), Pending
Interest Table (PIT) and Forwarding Base Table (FIB). Short elaboration on
various components of the NDN is provided in their respective sections. In
Table 4, various features, among CS, PIT and FIB are compared.

Table 4: Comparison of various features among CS, PIT and FIB. In data structure feature, widely used technique is mentioned. N/A: not applicable Feature |  CS |  PIT |  FIB
---|---|---|---
Frequency of read operation |  High |  High |  High
Frequency of write operation |  High |  High |  Low
Size of data structure |  Different and based on edge and routers |  Different and based on edge and routers |  Same
Algorithm |  Cache Replacement policy |  Timeout operation |  Forwarding Strategy
Matching algorithm |  $\bullet$ Interest packet: All Sub-Name Matching
$\bullet$ Data packet: Exact Name Matching |  $\bullet$ Interest packet: Exact Name Matching
$\bullet$ Data packet: All Name Prefix Matching |  $\bullet$Interest packet: Longest Name Prefix Matching
$\bullet$ Data packet: N/A
Data structure |  Skip List |  Bloom Filter |  Trie
Issue |  Fast name lookup |  High memory access frequency |  Memory consumption

##  6 Packet

NDN communication starts when a node (called a consumer) requests for data by
sending packet called Interest packet. Interest packet contains the name
(called content name) to identify the requested data. Figure 10 shows the
architecture of forwarding an Interest packet. Content name helps to retrieve
content using name and it is independent of the network. First, the content
name of the Interest is checked in CS to retrieve data from the cache. CS is a
memory buffer that stores the Data packet. More functionalities of CS are
elaborated in section 7. PIT saves the interest name and the interface from
which the interest is received. PIT stores unresolved interest. PIT is
discussed in detail in section 8. Interest packet is dispatched to next node
after referring FIB. The FIB is a data structure maintained by the router. It
stores the list of neighboring nodes and other information. More discussion on
FIB is provided in section 9. A node sends a Data packet when the node
receives the Interest packet containing the requested data. The sender is
called producer. A Data packet contains the name, content (i.e., the requested
data) and signature (producer’s key). Data packet follows the Interest packet
path in reverse to reach the consumer. The packet does not contain any IP
address, the routers forward the packet based on the content name. Figure 11
shows the transmission of Interest and Data packet. The dotted box in Figure
11 is a router. A router contains three data structures, namely, CS, FIB and
PIT. Table LABEL:packet_table illustrates the advantages and disadvantages of
the techniques discussed in this section.

Figure 10: Packet Architecture [Source [143]]. Figure 11: Data forwarding and
receiving process of NDN [Source [143]].

###  6.1 Bloom Filter in Packet

Mun et al. [91, 90] proposed a new packet called a summary packet. A summary
packet contains a Bloom Filter to represent the summary of the cache present
in a node. It helps in increasing the cache efficiency in routers. The Bloom
Filter is exchanged with neighboring nodes using summary packet. The summary
helps in taking decision regarding caching. The nodes also maintain a new data
structure called Summary Store. Summary store saves summary packets. When a
node receives a Data packet, it checks with cache summaries of neighbor nodes.
If the data exists with neighbor nodes, then the data is not saved in the
cache. In case the node receives an Interest packet the summary is checked
with Bloom Filter. If Bloom Filter returns $True$, then it is searched in its
cache. If cache also returns true, then requested Data packet is sent to the
consumer. When the face of matching summary and incoming Interest packet are
different, the Interest packet is forwarded to face of a matching summary.
However, if both faces of matching summary and incoming Interest packet are
same, then it is a case of false positive. In case of no matching summary or
false positive, the Interest packet is sent to the next node after referring
FIB. In case Data packet is received by a node, first Bloom Filter is
searched. If present, the data is ignored. If absent, it is cached in CS and
updates its own summary. Summary store in a node maintains $f+1$ Bloom
Filters. One Bloom Filter for each face of NDN router. So, $f$ faces require
$f$ Bloom Filters. Another Bloom Filter for its own cache. Thus, increase in
number of faces increases number of Bloom Filters. Eventually, increases space
complexity. Query with Bloom Filters are performed sequentially, leading to a
high query time complexity. The proposed method uses SBF [21] to reduce space
and time. SBF supports association queries. Association query recognizes the
set to which an element belongs.

A technique called Network Coding (NC)[22] deploys Bloom Filter in Interest
and Data packets. Bloom Filter stores the IDs of the consumer. When a consumer
sends an Interest packet its ID is stored in the Bloom Filter. As the packet
gets transmitted towards the producer of the requested data, Bloom Filter is
modified based on some rules. After receiving the Interest packet, the Bloom
Filter helps to decide (a) aggregates the Interest packet with other Interests
stored in PIT, (b) utilizes the Data packets saved in CS, and (c) insert as a
new entry into PIT and send to the neighbor node. When the intersection
between Bloom Filter of received Interest and existing same content name
Interest, is empty, then both Interests are merged. In case the intersection
is not empty, then producer receives both Interests. When a Data packet is
transmitted, the Bloom Filter of the Interest packet is stored in the Data
packet. A node after receiving Data packet, consumes the Interest whose Bloom
Filter has a subset of the consumer IDs stored in the Bloom Filter of the Data
packet. When the Data packet reaches a node its name is removed from the Bloom
Filter. It prevents re-transmission to same consumer. Bloom Filter is also
stored in PIT and CS.

Watano et al. [132] proposed a re-route algorithm for Interest forwarding
based on the degree of similarity of cached contents among each neighboring
content routers (CR). Bloom Filter helps in selecting an alternate adequate
route with similar contents when original route is lost. This helps to
maintain the cache hit ratio. CR cannot forward an Interest, if it cannot
reach the next CR hop caused by link disconnection or inoperative state of the
next CR hop. This degrades the performance and increases network traffic. The
method is based on the similarity of the Bloom Filters among chosen candidate
CRs. Each CR consist of a CS, PIT, FIB and a Bloom Filter corresponding to the
faces connecting to the CR. CRs can exchange their Bloom Filter value via
Interest/Data Packet communications. Similarity is calculated between the
initial next CR hop according to its entry in the FIB and the candidate CR.
$EXOR$ of the values of the Bloom Filters are considered. Similarity rate is
based on the sum of bits calculated as 1. More number of 1s indicates lesser
similarity. Since this method uses conventional Bloom Filter, it has a high
false positive and false negative probability. The cache hit ratio of this
method is much better than the conventional. Although, when the link down time
is less, it does not perform very well. Because initially differences in
similarities of Bloom Filters is not reflected, hence, appropriate alternate
next CR hop cannot be determined.

###  6.2 Content Discovery

Bloom Filter-based Routing (BFR) [83, 14] is a content discovery technique. It
is content oriented, and fully distributed. In this technique, origin server
uses Bloom Filter to advertise its content objects. Moreover, it is robust to
topology changes. BFR has three phases, namely, representation, advertisement
and content retrieval, and FIB population. In the first phase, origin servers
construct a Bloom Filter to represent their content objects. Initially, all
slots of the Bloom Filter are assigned 0. Then, content object name and name
prefixes are mapped to the Bloom Filter. In the second phase, the Bloom Filter
is sent to advertise the content objects. A new Interest packet is proposed,
called the Content Advertisement Interest (CAI). CAI packet consists of
content advertisement Bloom Filter. CAI packets are forwarded to all
neighbors. CAI is broadcasted till all nodes receives the packet.

COntent-driven Bloom filter based Routing Algorithm (COBRA) [128, 14] is a
content-driven, fully distributed, and Bloom Filter based intra-domain routing
algorithm. It maintains routing information without extensive signaling
between nodes. Each interface has its own Stable BF [37]. When a Data packet
is received, it is transmitted to the consumer. Then, the whole name and
prefixes are hashed and inserted into the Stable BF. The information on Stable
BF is used to rank the interface during each query. When a new Interest is
received, the whole name is searched in Stable BFs. The searching process
terminates when all interfaces are ranked or new prefix is obtained after
removing the last component of the received name. After completion of the
search process, all interfaces are assigned to a routing cost. Then, the
Interest is forwarded with lowest routing cost. In COBRA, stale information
leads to incorrect forwarding. Therefore, Stable BF is updated. Moreover,
COBRA deploys an ad-hoc retransmission handling technique to remove stale
information. Moreover, the number of used interfaces are incremented as per
the requirement. During a retransmission request, Interest is sent both
towards the probed before interface and interfaces just after in the global
rank. Then, finally the requested whole name is removed from Stable BF. In
case of failed link detection, Stable BF associated with the interface is
reset. And, the new alternative path is identified. In case of link recovery,
directly connected nodes set the Stable BF slots to 1 that are associated with
the interface. Then, the recovered link is used as a primary or an additional
path.

Pull-based BFR [84] algorithm was proposed to advertise only on-demand content
objects. This algorithm saves bandwidth, other network nodes requires less
memory to save content advertisement information and scalable compared to
push-based BFR [83]. The algorithm follows two phases (i) obtaining demanded
content object and (ii) advertisement. When a consumer sends an Interest. If
there is no FIB entry for the content name or no Bloom Filter has content
advertisement, then the Interest is not forwarded and kept as pending. The
consumer request the server to pull content advertisement information for the
demanded content. Moreover, the consumer constructs a Bloom Filter containing
the content file name and name prefixes. It also constructs a Content
Advertisement Request (CAR) message containing the Bloom Filter. Again, when
another consumer sends the same Interest it creates another CAR message. When
a router receives both the CAR messages, it unites both CAR messages. This new
CAR message is forwarded in a different face. This algorithm is also followed
by other routers to create CAR messages. Nodes use sequence numbers in CAR
messages to maintain their construction sequence. This process is a Bloom
Filter based strategy to inform the server about the demanded content names.
All nodes use Bloom Filter of same size and same hash functions for the
efficient union of Bloom Filters. Maximum capacity Bloom Filter is not united
because all slots of Bloom Filters have value 1. In such case, for any content
matching, the Bloom Filter returns a false positive response. Due to false
positive response the server advertise the content which is not in demand.
Increase in forwarding rate of routing messages increases content
advertisement overhead. Similarly, increasing content advertisement refreshes
rate increases communication overhead. Memory consumption is less compared to
push-based BFR.

###  6.3 Wireless NDN

BlooGo (BLOOm filter based GOssip algorithm) [15] is a gossip algorithm that
transmits the packets using minimum number of transmissions. A gossip
algorithm transmits data in a robust manner within a disruptive network.
BlooGo uses Bloom Filter to quickly find the neighbor node. In BlooGo, when a
node receives the Interest packet, it compares its local Bloom Filter and the
Bloom Filter present in the packet. The comparison is performed by
$NBF_{node}~{}AND~{}NBF_{packet}~{}XOR~{}NBF_{node}$. NBF contains the list of
the nodes within the transmission range of the sender node. $AND$ operation
finds the bits common between them. $XOR$ finds the neighbor nodes that the
current node can forward the packet in a single transmission. In case Bloom
Filter returns a false positive response, then the node may not transmit the
packet to its neighbor nodes. When a node is not the producer of the Interest
packet, then the node only forward the packet to its neighbor nodes.
Breadcrumb technique is implemented to send Data packet back to consumer node.
In this technique, the node that received the Interest packet saves the packet
id. Data packet has the same id as Interest packet. Advantages of BlooGo are
it is completely decentralized, lightweight and uses shortest path to deliver
packets. It is easy to hardwire because basic arithmetic operations are
performed on Bloom Filter. Moreover, BlooGo is easy to deploy as nodes do not
require any knowledge about the network or unique identifier. BlooGo uses
conventional Bloom Filter which does not permit deletion. Hence, for every
packet new Bloom Filter is constructed. Moreover, dynamic nature of the
network causes errors because Bloom Filter is unable to delete failed nodes.

###  6.4 Software Defined Network (SDN)

A forwarding technique called (NDN-SF) [63, 64, 65] implements Bloom Filter to
improve the efficiency of content delivery in SDN. NDN-SF hypothetically
partition the network into areas. Each area consists of a single SDN
controller, multiple NDN nodes and multiple switches. SDN controller centrally
manages the NDN network. SDN controller uses OpenFlow protocol [69] to
communicate with the switches. Name lookup is enhanced by using CBF based
table [77], namely, FIB-Bloom, PIT-Bloom and CS-Bloom. Implementation of Bloom
Filter improves prefix searching. During routing step, S-FIB table is
constructed/updated. It helps to forward Interest messages to the neighboring
node. The controller calculates the most recent path to all available data
names in the network. Then, controller broadcast its S-FIB to all switches in
the network. During forwarding step, upon receiving an Interest it is searched
in CS-Bloom. If present, Data packet is forwarded to requesting interface
after referring to CS-Bloom. If absent, the Interest is searched in S-PIT. If
absent, then again, it is searched in FIB-Bloom. If present, it is forwarded
to the requesting interface after referring to S-FIB. If absent, the Interest
is sent to controller to search in other network areas. NDN-SF uses many
tables/data structures which leads to increase in memory consumption.

Table 5: Comparison of Techniques used to improve Packet delivery in NDN Paper |  Advantages |  Disadvantages
---|---|---
BlooGo [15], 2012 |  $\bullet$ Completely decentralized
$\bullet$ Appropriate for an application that does not know the producer
$\bullet$ Easy to hardware because basic arithmetic operations are performed
on Bloom Filter
$\bullet$ Lightweight
$\bullet$ Easy to deploy as nodes do not require any knowledge regarding the
network or unique identifier
$\bullet$ Packets delivered using shortest path |  $\bullet$ In case of false positive response the node does not transmit the packet to the neighbor node
$\bullet$ Implements Conventional Bloom Filter which gives more false positive
$\bullet$ Every new packet contains the newly constructed Bloom Filter
$\bullet$ Dynamic nature of the network causes error because Bloom Filter is
unable to delete failed nodes
COBRA [128], 2014 |  $\bullet$ Fully distributed
$\bullet$ Content oriented
$\bullet$ Maintains routing information without extensive signaling between
nodes
$\bullet$ No requirement for any update message exchanges between the nodes |  $\bullet$ Increase in number of the interface increases number of Stable BF which increases memory usage
$\bullet$ Stale information leads to incorrect forwarding
NDN-SF [63, 64, 65], 2017 |  $\bullet$ Helps in acquiring a global view of the network that enable better control
$\bullet$ Implements a non-flooding data publication mechanism to reduce
network overloading
$\bullet$ Non-flooding data publication mechanism also helps the controller to
monitor prefixes in real time
$\bullet$ Implementation of Bloom Filter improves prefix searching
$\bullet$ Reduces bandwidth usage and delay |  $\bullet$ Implements many tables/data structure that increases memory consumption
$\bullet$ Forwarding to other network requires searching in many data
structures
$\bullet$ CBF is used in three tables, but it consumes more memory compared to
conventional Bloom Filter
BFR [83], 2017 |  $\bullet$ Fully distributed
$\bullet$ Content oriented
$\bullet$ Robust to topology change
$\bullet$ Does not store topology information
$\bullet$ Resilient to link failure
$\bullet$ Delay is less
$\bullet$ Takes less congested route |  $\bullet$ An Interest reaches a wrong origin server due to the false positive response
$\bullet$ Transmit CAI through multiple paths to reach the origin server,
which increases traffic congestion
$\bullet$ Takes longer route
$\bullet$ Efficiency less compared to Pull-based BFR
$\bullet$ Total communication overhead depends on the content universe size
$\bullet$ Increasing content advertisement refresh rate increases
communication overhead
$\bullet$ Memory space increases with the increase in content universe
Mun et al. [91, 90], 2017 |  $\bullet$ Increases cache hit
$\bullet$ Helps to cope with link failure, dynamic network topology, and
congestion in some links
$\bullet$ Change in the request pattern does not affect content diversity |  $\bullet$ Query with Bloom Filters are performed sequentially, which increases time complexity
$\bullet$ $f+1$ Bloom Filters are maintained by Summary store, where $f$ =
number of faces of NDN router and one for own cache.
Watano et al. [132], 2018 |  $\bullet$ Cache hit ratio higher than conventional method
$\bullet$ Essential when there is an unwanted loss of connection
$\bullet$ Space efficient |  $\bullet$ Cache hit ratio unsatisfactory for early link down times
$\bullet$ Uses conventional Bloom Filter, therefore has a high false positive
and false negative probability.
Network Coding (NC) [22], 2018 |  $\bullet$ Delivers scalable video
$\bullet$ Packet delivery rate is based on the popularity of the content
$\bullet$ Maximises average video quality
$\bullet$ Bloom Filter supports deploying of network coding in NDN
$\bullet$ Decision of Bloom Filter helps in deciding the packet movement among the data structure of NDN |  $\bullet$ Choosing the network coding coefficients randomly leads to decrease in video quality
$\bullet$ Implementing conventional Bloom Filter which gives a high false
positive probability.
Pull-based BFR [84], 2019 |  $\bullet$ Advertise only on-demand content objects
$\bullet$ Bandwidth is saved
$\bullet$ Other network nodes require less memory to save content
advertisement information
$\bullet$ Scalable
$\bullet$ Memory consumption is less compared to push-based BFR |  $\bullet$ Server is unable to know the demanded content objects in priori
$\bullet$ Union of maximum capacity Bloom Filter gives very high false
positive response
$\bullet$ Due to false positive response the server advertise the content
which is not in demand
$\bullet$ Increase in forwarding rate of routing messages increases content
advertisement overhead
$\bullet$ Increasing content advertisement refresh rate increases
communication overhead

##  7 Content store

After the NDN router receives an Interest packet, first CS searches for a
matching data [76]. CS is the buffer memory of the router. It caches data to
serve future requests. CS consist of index and packet buffer. Index stores the
data name. Packet buffer is the cache. CS size is small. Also, CS is of
different size as it is based on the size of the edges and the router. CS
follows All Sub-Name Matching (ASNM) name matching algorithm. This algorithm
searches for any data having the initial name as the requested Interest.
After, the Interest packet is forwarded to the corresponding interfaces based
on decisions made by PIT. CS decides whether to cache the data. In case of
Data packet, Exact Name Matching (ENM) algorithm is followed for name
matching. ENM matches the Interest name exactly with the CS entry. If a name
mismatch between the data and the Data packet occurs, then data is cached. CS
has a high read and write operation frequency. Absence of CS in router does
not hinder the routing operations. However, CS is included to store popular
Interests. For example, CS greatly helps in live streaming [48]. CS requires
an efficient cache replacement policy. Widely, skip list data structure is
adopted for CS. Linked list in the skip list helps in maintaining the order of
data storage. Hence, skip list itself helps in replacement policy. However,
the time complexity of query operation in skip list is more. Therefore, Bloom
Filter is a better option because the time complexity of all operations of
Bloom Filter is $O(1)$. In this section, various technique implementing Bloom
Filter in CS is discussed. Table LABEL:CS_table is listing the advantages and
disadvantages of the techniques.

Dai et al. [35] proposed a technique based on Bloom Filter to store the
popularity of content. This technique is deployed in CS to increase the cache
hit ratio and reduce the upstream traffic. It uses multiple Bloom Filters
where each Bloom Filter is dedicated to a particular range of popularity.
Suppose content popularity ranges from 1 to $p$ and $t$ is a content
popularity such that $1<t<p$. The first Bloom filter ($BloomFilter_{1}$)
stores content popularity ranging from 1 to $t$. Second Bloom Filter
($BloomFilter_{2}$) from popularity ranging from $t+1$ to $2t$ and so on.
While inserting a new element, the content is searched in all Bloom Filters.
If the content is new, then its content popularity is 1 and it is stored in
$BloomFilter_{1}$. Every time an existing content arrives its popularity is
increased by 1. When a content has popularity $t+1$, then that content is
inserted to $BloomFilter_{2}$. During the query, the content is searched in
very Bloom Filters. If at least one Bloom Filter returns $True$, then the
content is present. Otherwise, the content is absent.

Bloom Filter based Request Node Collaboration (BRCC) [58] uses a variant of
CBF called sum-up counting Bloom Filter (SCBF). It helps BRCC to optimize the
cache performance. BRCC consists of SCBF and caching information table (CIT).
During updating, the neighbor nodes exchange their cached data content.
Updated caching information is saved in CIT. Collaborative caching helps in
reducing data content redundancy. It also improves the data content diversity
and hit rate. BRCC does not improve Internet packet’s caching, but only
improves the data packet’s caching. In the improved data packet format,
Caching Index (CI) is caching flag. This is initially set to 0. When CI is 1,
it means the data content is cached in the data packet. The caching age (CA)
records the lifespan of Data packets. Caching Remain Age (CRA) saves remaining
lifespan of the Data packet. When a new data packet arrives, it replaces the
existing packet with CRA value 0, when the CS caching capacity reaches its
limit. If there are no available packets with CRA value 0, the one with lowest
CRA value is replaced. And, if there are multiple packets that can be
replaced, Least Recently Used (LRU) is used for replacement. NDN router uses
SCBF to search the CIT when it performs caching. Collaboration caching helps
in reducing data content duplication and makes it more diverse. Therefore, it
has a high cache hit ratio. Moreover, First Hop Hit Ratio (FHHR) is enhanced.
Because, frequently requested data are stored in the cache for a long time in
the NDN router near the consumer. The increment in caching capacity enhances
the hit ratio of interest packet’s requests and reduces the average hop count.
BRCC also has a low Average Route Delay.

Fetching the Nearest Replica (FNR) [24] is a technique to deploy content
delivery network (CDN)-like [30] enhancement in NDN. It fetches data from the
nearest replica without checking whether it is the best path from producer to
consumer. It determines the popularity of the data using Zipf distribution
[3]. Based on the request popularity, the technique partition the CS into two
parts, namely, Top-N Subset and Heavy-Tailed Subset. Top-N Subset is a subset
of size $N$ determined by using the Zipf law. Majority request is satisfied by
Top-N Subset. It implements Bloom Filter to reduce the storage and
transmission overhead. Heavy-Tailed Subset is a very big size subset that
satisfies very less data requests. FNR deploys a Track Server (TS) for each
Internet service provider. TS is responsible for the collection and
synchronization of replica information. TS merges Top-N Subset of all routers
to construct the replica list. Hence, the replica list has all the Bloom
Filters. TS is updated periodically. In case of update in Top-N Subset, router
notifies TS to retrieve latest Bloom Filter. Then, TS updates its replica
list. And, synchronizes with every consumer. In case the router does not
update its Bloom Filter for a long period, then TS does the updating. FNR is
scalable and lightweight. Using Bloom Filter reduces announcement traffic.
However, FNR uses conventional Bloom Filter which gives a high false positive
probability. FNR maintains multiple Bloom Filters, and also, stores many data
structures which increases memory consumption. Also, FNR deploys a centralized
model which may lead to a single point of failure.

Controller-Based Caching and Forwarding Scheme (CCFS) [11] is a technique that
uses a cooperative caching to improve the forwarding decision. The technique
partitions the network into domains. Each domain is controlled by node called
a controller. Other nodes in the domain are regular router. The controller
makes the forwarding decisions based on the popularity of the content. The
controller has a data structure called Cache Information Base (CIB) to store
summary of the content along with its neighbor’s summary. Each entry of CIB
stores the interface ID of the node, type of the neighbor node and a Stable BF
[37] associated with the interface. Stable BF stores the summary of the node.
It helps to check for the summary with less time complexity. CCFS follows
cache admission based on content popularity. When the content is highly
popular it is stored in the CS. In case the outcoming interface is towards a
regular router, then content name is hashed and stored in the Stable BF
associated with the interface. Each controller periodically sends Stable BF to
one hop neighbor Controllers. Stable BF is sent using a specific Interest
packet, and at a low frequency. When a controller receives new Stable BF, then
Stable BF of corresponding CIB entry is replaced.

Scalable Content Routing for Content-Aware Networking (SCAN) [71, 72] is a
scalable routing scheme to implement content aware networking. In SCAN, a
content router (C-router) saves the contents in its attached storage modules.
It also guarantees efficient content delivery and retrieval. C-routers adopts
Bloom Filter to increase scalability. Bloom Filter compresses the stored
content information in a C-router. Each C-router maintains one Bloom Filter
for each interface in a Content Router Table (CRT). It first performs an IP
routing when it gets a request. Then, it performs scanning in case it can be
afforded. For scanning, first the Local Content Table (LCT) is searched. If
present, the C-router responds by notifying its existence to host. If absent,
Bloom Filter is searched for every outgoing interface. The requested Content
ID (CID) is searched in the Bloom Filter of a particular interface. If there
are matched interfaces, the scanning request is generated and sent to matched
interfaces. For scanning, periodically C-routers exchange CRTs. For example,
let $C_{1}$ and $C_{2}$ be two C-routers exchanging CRTs. $C_{1}$ merges Bloom
Filters of all interfaces except the interface connected to $C_{2}$. $C_{1}$
then sends the merged Bloom Filter to $C_{2}$. $C_{2}$ inserts the received
information into Bloom Filter of the interface connected to $C_{1}$.
Similarly, $C_{2}$ forward its own CRT to $C_{1}$. For reducing the false
positive probability, C-router decays all the bits set to 1 of a Bloom Filter
probabilistically before exchanging CRT. Therefore, scanning is performed
based on a threshold. When the number of matched bits is greater than the
threshold, then scanning is performed. Traffic is lowered due to use of cached
contents. It does an efficient load balancing. SCAN guarantees reachability of
content, regardless of scanning results.

CCNxTomcat[108] is the first practical CCN-enabled web server. It is based on
open source $ApacheTomcat$ and the $CCNxlibrary$. It supports CCN-based web
applications. CCNxTomcat contains a novel cache called CCNCache. CCNCache is a
cache for the Servlet Response. It performs name-lookup for content with high
efficiency. For CCNCache, CBF [77] is used to check the presence of content
packet in the cache. This reduces the number of memory accesses per query.
CCNCache implements a composite data structure consisting of hash table, skip
list and multiple CBFs. Long CCN names are split into two shorter parts to
improve lookup efficiency. The first part contains the Servlet name. The
second part contains parameters and values. These parts are stored in hash
tables and trie. When there is a huge number of CCN requests, multiple skips
lists are constructed to increase the query process. CCNcache performs
accurate prefix matching mechanism on all CBFs. When a request is received by
CCNcache, it determines the prefix length. Then CBF is searched to identify
whether it is present in the hash table. If present, then CCNcache query the
hash table to find the address of the trie tree root node. CCNcache retrieves
the requested parameters and values from trie tree. Using these parameters and
values skip list is searched. Then CCNcache returns the packet content.
CCNxTomcat directly interacts with CCN routers to reduce the cost of HTTP/CCN
protocol conversion during development and run-time phases. CCNCache performs
faster lookup, although, it occupies additional memory due to multiple CBFs.
However, the lookup performance degrades when the number of a name component
increases.

Table 6: Comparison of Techniques used in Content store Paper |  Advantages |  Disadvantages
---|---|---
SCAN [71, 72], 2011 |  $\bullet$ Efficient content delivery
$\bullet$ Efficient content reachability
$\bullet$ Bloom Filter increases scalability
$\bullet$ Efficient load balancing
$\bullet$ Cached contents reduces traffic |  $\bullet$ Maintains one Bloom Filter for each interface which increases memory consumption
$\bullet$ Due to use of conventional Bloom Filter, false positive and false
negative probability is higher
Dai et al. [35], 2014 |  $\bullet$ Stores the content popularity
$\bullet$ Improves cache hit ratio to reduce upstream traffic |  $\bullet$ Implements multiple Bloom Filters which increases memory consumption
$\bullet$ A content present in higher Bloom Filter also presents in the lower
Bloom Filter. Multiple presence of content is wastage of memory
$\bullet$ Exact content popularity of a content cannot be determined from
Bloom Filter
CCNx- mcat [108], 2014 |  $\bullet$ First Practical Web Server supporting both HTTP and CCNx
$\bullet$ Seamlessly integrates with existing web server kernel and created
CCN-enabled web server
$\bullet$ Outperforms conventional methods in terms of throughput
$\bullet$ No additional cost of HTTP/CCN conversions
$\bullet$ CCNCache performs a very fast look-up |  $\bullet$ CCNCache occupies additonal memory
$\bullet$ CCNCache implements CBF which has a higher memory consumption than
conventional bloom filters
$\bullet$ Look-up performance degrades when number of name components
increases
CCFS [11], 2015 |  $\bullet$ Improves in-network caching
$\bullet$ Stable BF reduces the false positive probability
$\bullet$ Stable BF reduces time complexity of searching for summary
$\bullet$ Reduces communication load
$\bullet$ Reduces bandwidth usage |  $\bullet$ Have high server workload
$\bullet$ Each interface has an Stable BF, multiple Stable BFs increase space
complexity
$\bullet$ Monitoring using the controller may lead to single-point of failure
$\bullet$ No backup technique in case of failure of the controller
FNR [24], 2016 |  $\bullet$ Provides content delivery network (CDN)-like enhancement in NDN
$\bullet$ implements Bloom Filter to reduce storage and transmission overhead
$\bullet$ Bloom Filter reduces announcement traffic
$\bullet$ Local hashing table prevents repeated data location
$\bullet$ Scalable
$\bullet$ Lightweight |  $\bullet$ Implements conventional Bloom Filter, hence have high false positive
$\bullet$ Maintains multiple Bloom Filters occupies more memory
$\bullet$ Deploys a centralised model which may lead to a single point of
failure
$\bullet$ CS stores many data structures, increasing memory overhead
$\bullet$ CS saves one pointer to each content of Top-N Subset
BRCC [58], 2018 |  $\bullet$ Reduces data content redundancy
$\bullet$ Increases data content hit rate, diversity and searching rate and
accuracy
$\bullet$ High cache hit ratio
$\bullet$ High First Hop Hit Ratio
$\bullet$ Low Average Route Delay
$\bullet$ Enhances data content matching rate
$\bullet$ Decreases searching time |  $\bullet$ Employs SCBF, which has a higher memory consumption
$\bullet$ Does not improve Interest packet

##  8 Pending Interest Table

Pending Interest Table (PIT) [32] is an intermediate router that stores
unresolved interest. When a consumer sends an Interest packet, PIT saves the
interest name and the interface from which the interest is received. Interest
packet is forwarded to nodes till it reaches the producer node. Then a
producer sends the Data packet, which follows the path in reverse order to
reach the consumer. When the Data packet reaches PIT, it searches for the
interface from which the Interest is received. If present, the name is deleted
from PIT. Then, the Data packet is forwarded to a consumer. The speed of
incoming Interest packet is very high, hence, a large sized data structure is
required to store the packets without overflow. The frequency of read and
write operation is high. Moreover, all the operations (insert, search, delete)
need to be highly efficient to coup with high packet incoming speed. Moreover,
different application follows a different mechanism to send its packets. This
influence the size and processing speed of PIT. PIT follows an ENM algorithm
for matching the content name of the Interest packet. ENM matches the Interest
name exactly with the PIT entry. In case of Data packet All Name Prefix
Matching (ANPM) algorithm is followed for matching the content name. ANPM
algorithm searches for any pending Interest having names similar to prefix of
Data name. ANPM helps to achieve Data multicast. PIT deletes entries after a
timeout to avoid saturation of the data structure. Timeout also helps against
simple flooding attacks [87]. Each entry is associated with a timer to
determine the timeout. PIT plays an important role in NDN communication [32].
Some important advantages are

  * 1.

Content concentration: It enables only content concentration in NDN
communication. PIT routes the packets (Interest and Data) without including
source or destination address.

  * 2.

Security: Lack of source or destination address makes the attacks difficult.

  * 3.

Deduplication: Duplicate data are ignored.

  * 4.

No Looping: Unique data are stored in the PIT. Hence, the packets does not
loop.

  * 5.

Multipath routing: No looping happens. Hence, Interest packets can send
through multiple interfaces.

  * 6.

Supports Data packet multicast: If same Interests are requested by multiple
consumers, then PIT forwards the Data packet to all the consumers

  * 7.

Detects Data packet loss: PIT waits for the data time out, if the Data packet
not received it identifies as data loss.

In the rest of the section, the various techniques that implement Bloom Filter
to enhance PIT which are elaborated. Table 7 illustrate the advantages and
disadvantages of those techniques.

MaPIT [74, 73] is a technique to achieve an advanced PIT. It implements an
improved Bloom Filter called Mapping Bloom Filter (MBF). MaPIT consist of
Index Table and CBF. Index Table is constructed on on-chip memory. CBF is
constructed in off-chip memory. Packet Store saves the packet information.
When an Interest packet arrives, first CS is searched. If absent, Index Table
is searched. If also absent from Index Table, then it is stored in the FIB.
Its footprint is saved in Bloom Filter and CBF. The packet information is
stored in Packet Store using values obtained from MA. In case the Interest
exists or Bloom Filter gives a false positive response, then Packet Store is
updated and forwarded to FIB. When a Data packet arrives, Index Table’s Bloom
Filter is searched. If present, then Packet Store is searched. If the data is
absent in Packet Store, then data are blocked and the footprint is deleted
from the CBF. If data is present, then it is forwarded using the faces saved
in Packet Store. Also, the record and footprint are deleted from Packet Store
and CBF respectively. Finally, CBF and Bloom Filter are synchronized. MaPIT
consumes less on-chip memory. Moreover, it is easy to deploy on faster memory
chip. In addition, using MBF reduces the false positive probability. However,
its performance is average.

Fast Two Dimensional Filter Pending Interest Table (FTDF-PIT) [120, 119] is a
novel PIT implementation which ensures high performance. The PIT employs a
variant of FTDF, wherein every FTDF slot consists of a bit vector. The number
of bits is equal to the number of faces in the NDN node. The bit vector saves
the face number. When an Interest packet is received, first the CS is
examined. If there is a match in the CS, the NDN node will return the Data
packet. After that, it is mapped to FTDF-PIT. First, hash value appearing in
the Interest packet is calculated. Next, quotienting technique is executed.
This is performed to retrieve the row and column number. Lastly, inside the
FTDF-PIT on the specific position, the corresponding bit in the bit vector is
set to 1. This reflects the requested interface. Data packet coming from any
interface is cached in CS. Then, content name is hashed to get FTDF-PIT slot
position. Data Packet is forwarded to all the interfaces whose bit positions
are set to 1. After the requested Data packet is satisfied, the bits in the
bit-vector is reset to 0. FTDF-PIT has low false positive probability due to
hard collision. Hard collision is solved by using a collision resistant hash
function. It also has low construction time because it utilizes one hash
function. FTDF-PIT has an efficient memory, hence it is able to store all
flooded packets (due to DDoS attack) without consuming large memory. The time
complexity of insert and query operation is O(1).

Yu and Pao [140] proposes a Hardware Accelerator which is a hardware
implementation of PIT for NDN. This design incorporates an off-chip linear
chained Hash Table (HT) and an on-chip Bloom Filter. It also contains a name
ID table (nidT). nidT stores all distinct name IDs (nid) in the PIT. If
content name is found in nidT, then FIB is not referred. This reduces the FIB
workload. This technique adopted a software and hardware co-design approach.
Hardware accelerator makes the PIT lookup and management independent of
software. In the proposed design, on-chip DRAM is used to implement Bloom
Filter for the lookup table and external SRAM is used to store the full lookup
table. Bloom Filter helps in faster lookup. During lookup, the hardware first
query the Bloom Filter. If absent, then it is a PIT-miss. If present, hardware
traverses the list of keys mapped to the corresponding bucket. If the input
key is present, hardware returns a PIT-hit and deletes the data. If the data
structure becomes empty after the deletion, then the Bloom Filter is set to 0.
In a Lookup Interest (LI) command, if the key is present, the hardware returns
a PIT-hit and the address of the data. If the key is absent, it is inserted in
the data structure. The first empty slot is allocated for insertion. Insert
and delete operations on nidT and PIT are similar to LD/LI commands. Lower PIT
population increases the packet processing rate. The technique improves
throughput. A major issue is the requirement of per-packet update in the
lookup table.

Table 7: Comparison of techniques used to improve PIT in NDN Paper |  Advantages |  Disadvantages
---|---|---
MaPIT [74], 2014 |  $\bullet$ Reduces on-chip memory consumption
$\bullet$ Easy to deploy on faster memory chip
$\bullet$ Reduces false positive probability |  $\bullet$ Average performance
$\bullet$ MBF uses conventional Bloom Filter which has high false positive and
false negative issues
Hardware Accelerator [140], 2016 |  $\bullet$ Gives an efficient PIT lookup
$\bullet$ Bloom Filter reduces lookup time
$\bullet$ Reduces FIB workload
$\bullet$ Makes the PIT lookup and management independent of software
$\bullet$ Improves throughput |  $\bullet$ Requirement of per-packet update in the lookup table
$\bullet$ Saturated PIT takes more packet processing time
$\bullet$ Conventional Bloom Filter increases the false positive probability
FTDF-PIT [120, 119], 2019 |  $\bullet$ Low memory requirements
$\bullet$ Low false positive probability
$\bullet$ Quick and efficient deletion
$\bullet$ Low building time
$\bullet$ Time complexity of insertion, query and retrieving interface number
in O(1)
$\bullet$ Space and cost-efficient PIT
$\bullet$ Provides high security against DDoS attacks
$\bullet$ PIT memory independent of length of content name |  $\bullet$ FTDF is influenced by hard collision

##  9 Forward Information Base

Forward Information Base (FIB) [117] is a data structure present in a router
that stores next hop and other related information of every reachable node.
The FIB is referred to forward the Interest packet to the next node. After
searching PIT, if the Interest is absent, then the Interest packet is
forwarded to FIB. FIB follows Longest Name Prefix Matching (LNPM) for name
matching. LNPM searches for longest prefix matching of IP of Interest with the
FIB entry. LNPM helps in acquiring most accurate forwarding information. If a
matching FIB entry is present, then the Interest packet is sent to the next
hop. And, a new entry in PIT is inserted. Sometimes the Interest packet is
broadcast to all outgoing interfaces or decision is taken based on the
forwarding policy. The frequency of read operations is high, but performs very
less write operations. In case of Data packets FIB does not have any role. FIB
contains duplicate entry for the same content. In this section, Bloom Filter
based FIB techniques is precisely explained. Table 8 presents the advantages
and disadvantages of the techniques.

So et al. [122] proposed a simple technique for NDN software forwarding lookup
engine using hash table. A chained hash table is implemented. The hash table
has linked list to save collision entries. To avoid unnecessary chain
searching for absent data, every hash bucket has a Bloom Filter. When an
element is hashed to a bucket, first Bloom Filter is searched. If present,
then that data is not stored in the hash table. If absent, then that data is
stored in hash table after creating a new link in the linked list. However,
this technique implements conventional Bloom Filter that has many issues.
Moreover, data cannot be deleted from hash table. Because that data cannot be
deleted from the Bloom Filter. Sorted linked list is implemented to improve
data searching efficiency.

Bloom Filter-Aided haSh Table (BFAST) [34, 33] data structure is proposed for
faster FIB indexing. BFAST uses hash table and Bloom Filters. CBF [77]
balances hash table load. Implementing Bloom Filter reduces search time. BFAST
consist of a CBF, a hash table and $k$ auxiliary CBFs. Each slot is associated
with a hash table slot to store the elements. Each hash function has an
auxiliary CBF (aCBF). In case of collision, chaining is used in the hash
table. During insertion, first the element is hashed by $k$ hash functions to
obtain $k$ locations of CBF. The element is inserted into CBF. Then, minimum
value $min$ among the $k$ location counters is found. The element is inserted
into the hash table slot attached to $min$ CBF slot. The aCBF is considered
whose $min$ location is returned by the hash function. The location to store
the element in aCBF is obtained by performing a modulus operation on its
corresponding hash value. During query operations, first CBF is searched. If
absent, then element is also absent from hash table. Hence, returns false as a
response. If present, then all aCBFs are searched. Rank-Indexed hashing is
implemented to reduce memory consumption because the hash table uses lots of
pointers. In this technique, the hash table with chaining have multiple
buckets in each slot. The elements are stored in an address-contiguous array.
Each element is stored in a different array. Only the first element is stored
in a single array called First Item Array (FIA). While searching in the hash
table $Rank$ operator is used to obtain the location dynamically. Moreover,
this operation is possible to execute using hardware instruction which reduces
the time complexity of the operation. In this technique each entry of FIB
consist of the FIB entity entry, interface ID, signature (content name), and a
pointer to the next index entry. This technique is efficient for insertion,
deletion and searching in the FIB. But, have very huge space complexity
because of using many data structures.

Bloom-Filter assisted Binary Search (BBS) algorithm [57] improves the
efficiency of name lookup. It ensures the correct path searching without
additional backtrack costs and less memory consumption. At each branching
point a Bloom Filter is deployed to detect the presence of a prefix. Instead
of storing virtual name prefixes in hash table, they are stored in Bloom
Filters. It reduces memory consumption. BBS adds Bloom Filter to each hash
table. BBS checks the presence of prefix by performing three lookups. In the
first lookup, if a content is absent in a Bloom Filter, then BBS searches in
its right subtree. Second lookup, if content is absent in both Bloom Filter
and hash table, then BBS searches in the left subtree. Third lookup, if
content is absent in Bloom Filter but present in the hash table. BBS perform
two more lookups in Bloom Filter to reduce memory consumption. However, the
time complexity increases. When a new name prefix is inserted into the FIB, it
is stored in its corresponding hash table. Then, BBS inserts the name prefix
into the specified Bloom Filters. Bloom Filter size is dynamic. It changes
with the total number of current length-component name prefixes.

MaFIB [73] is a technique that uses MBF [74] to enhanced FIB. MaFIB consists
of an off-chip and an on-chip memory. On-chip memory is high-speed memory and
uses multiple MBFs. Whereas, off-chip memory is low-speed memory and stores
multiple CBFs which correspond to on-chip MBFs. Packet store is a static
storage used to store packet forwarding information. Each MBF corresponds to
one length name prefix which helps in quick query operation. A lookup
operation in the packet store is performed using the MA value in MBF. MaFIB
supports deletion operation taking the help of timely synchronization between
the MBF and CBF. MaFIB has a false positive probability equal to the sum of
the MBFs used, and it is lower compared to conventional FIB. The operations on
the MaFIB have constant time. MaFIB also has a low on-chip memory consumption.

Lee et al. [70] proposes two efficient forwarding engines to perform quick
name lookups. It implements a Bloom Filter and a hashing-based Name Prefix
Trie (NPT). The first algorithm accesses the trie node for every positive
result of the Bloom Filter. Second algorithm called Name Prefix Trie with
Bloom Filter (NPT-BF) queries the Bloom Filter to determine the longest
matching length. Trie nodes are processed from the longest possible length. In
case no match is found, trie nodes are tracked back. Bloom Filter is stored
on-chip and NPT is stored in an off-chip hash table. Every node in an NPT is
stored in a hash table (HT). For each Interest packet, hash index is obtained
from the content name. The hash index is compared with the hash entry of HT.
When a matching entry is found, the search continues. Searching continues till
there is no matching entry, or search equals to the input length. The output
face of the current matching entry is stored. Query operation is performed on
Bloom Filter before accessing HT. It eliminates unwanted HT accesses. In NPT-
BF, content name is used to query the Bloom Filter. If present, then HT is
accessed. HT gives the output face. Searching continues till Bloom Filter
returns false or matching entry is found. When Bloom Filter returns false, HT
searches for matching entries. Backtracking is performed until a matching
entry is found in the HT. NPT-BF-Chaining increases Bloom Filter size to
reduce the false positive probability. The average number of node accesses
during implementation of NPT-BF algorithm is higher than that of NPT-BF-
Chaining. Moreover, using non-chip Bloom Filter reduces access to an off-chip
hash table.

Table 8: Comparison of techniques used to improve FIB in NDN Paper |  Advantages |  Disadvantages
---|---|---
So et al. [122], 2012 |  $\bullet$ Hash table reduces data collision
$\bullet$ Bloom Filter reduces chain searching
$\bullet$ Sorted linked list reduces searching time |  $\bullet$ Data is not deleted from the hash table because the data deletion is not permitted in the Bloom Filter
Lee et al [70], 2016 |  $\bullet$ Non-chip Bloom Filter reduces access to off-chip hash table
$\bullet$ Average number of node access is low in NPT-BF-Chaining algorithm
$\bullet$ Enables fast look-up |  $\bullet$ Conventional Bloom Filter increases false positivity probability
BFAST [34], 2017 |  $\bullet$ Increases parallelism
$\bullet$ First-Rank-Indexed reduces memory consumption
$\bullet$ Have high-throughput and low latency Longest Prefix Match forwarding
performance with big FIB entries
$\bullet$ Supports incremental update
$\bullet$ Bloom Filter reduces searching time |  $\bullet$ Implementing lots of data structure, increases space complexity
$\bullet$ Many Bloom Filters leads to higher overall false positive and false
negative probability
$\bullet$ In a CBF, counter overflow may occur
$\bullet$ Size of CBF is four times more than conventional Bloom Filter
BBS [57], 2017 |  $\bullet$ No backtrack cost
$\bullet$ Storing virtual name prefixes in Bloom Filters reduces memory
consumption
$\bullet$ Efficient with longer prefix and large database
$\bullet$ Bloom Filter size is dynamic and changes with the total number of current length-component name prefixes |  $\bullet$ Perform two more lookups in Bloom Filter which increases time complexity
$\bullet$ Time complexity of BBS is less compared to Binary search of hash
table
MaFIB [73], 2017 |  $\bullet$ Low on-chip memory consumption
$\bullet$ Lower false positive probability compared to conventional FIB
$\bullet$ Operations are in constant time |  $\bullet$ MBF has high false positive and false-negative probability
$\bullet$ CBF for off-chip memory occupies high memory

##  10 Security

Table 9: Comparison of techniques in Security of NDN Paper |  Advantages |  Disadvantages
---|---|---
Massawe et al. [85], 2013 |  $\bullet$ Provides high security and content privacy
$\bullet$ Scalable
$\bullet$ Reduces false positive probability by deploying multiple Bloom Filters |  $\bullet$ Deploying multiple Bloom Filters occupies more memory
Chen et al. [29], 2014 |  $\bullet$ Protects access to NDN data contents
$\bullet$ Prevents unauthorized consumers to access encrypted data contents
$\bullet$ Reduces bandwidth
$\bullet$ Prevent download by unauthorized consumers and attempt to decrypt the video |  $\bullet$ Maintaining multiple Bloom Filters (one for each site) increases memory consumption
$\bullet$ Implements conventional Bloom Filter
$\bullet$ No attempt made to reduce the false positive probability
Guo et al. [55], 2016 |  $\bullet$ Efficient against address spoofing
$\bullet$ Occupies less memory
$\bullet$ One hash function in Bloom Filter reduces time complexity
$\bullet$ Reduces false-locality pollution |  $\bullet$ Saving the path information makes the Internet structure exposed to an attacker
$\bullet$ Storing path information leads to processing and network overhead
$\bullet$ Increases router overhead
$\bullet$ Not efficient against address-based attack
CPPM-DAM [147], 2018 |  $\bullet$ Provides security against cache privacy snooping
$\bullet$ Determines legitimate users
$\bullet$ Permutation indicator helps in determining the difference between the packet with high probability |  $\bullet$ Permutation indicator is an overhead for new content
$\bullet$ Increase in attack increases the round trip time
$\bullet$ Less number of hash functions leads to the possibility of guessing
the permutation by attackers
$\bullet$ Small matrix size increases the false positive probability
$\bullet$ Implements conventional Bloom Filter
$\bullet$ Permutations are saved because same packet has same permutation
Wu et al. [134], 2019 |  $\bullet$ Improves user identity filtering mechanism
$\bullet$ Improves user logout mechanism
$\bullet$ Reduces total delay
$\bullet$ Improves security of the entire system |  $\bullet$ Implements CBF, which has a higher memory consumption
$\bullet$ High false positive probability

NDN architecture is designed to provide some basic security. Every Data packet
has a cryptographically signed producer key [26]. The signature is present a
message and name, or payload. Data packet contains the key to verify the
signature. First, consumer verifies the signature, then accept the packet.
Intermediate router can verify the signature. But it is not compulsory because
the verification increases processing overhead. Content signature helps in
providing three basic securities, namely, Data integrity, Origin
authentication, and Correctness [26].

  1. 1.

Data integrity: Valid signature ensures intact content.

  2. 2.

Origin authentication: Signature is verified using the producer’s public key,
hence, any node can verify the content signature.

  3. 3.

Correctness: Due to signature the content is tied to payload. This helps to
securely identify whether the content of Data packet is same as the requested
data.

NDN architecture also solves some basic DoS and DDoS attacks [38]. DoS is
denial of service and DDoS is the distributed denial of service. The data
packet is sent after receiving a request. And, Interests requesting same Data
are merged into a single packet. In addition, timeout record and the number of
PIT entries help to analyze and detect attack behaviors. However, NDN is
vulnerable to many other issues such as [26, 38]:

  * 1.

Privacy: The hierarchically structured name of an Interest packet makes the
content vulnerable. This is name privacy. Neighbors uses timing information to
get each others content accesses from cache. This is called cache privacy.
This information helps to determine the cache hits. The content of the Data
packet is not encrypted, hence, they are vulnerable. This is content privacy.
The signature leads to identification of the producer and its organization.
This information leads to violation of producer’s privacy. This is called
signature privacy.

  * 2.

Trust: The public key provided to determine the signature may not be trusted.
This leads to trust issues in NDN.

  * 3.

Interest flooding: The attacker sends a large number of Interest packets to a
specific producer. It flooded the PIT which makes PIT unable to identify the
legitimate Interest packets. The data request are of three types, namely,
static contents, non-existent contents and dynamically-generated content. Each
type gives a different effect. In static contents, the content exists in
cache. So, the Interest packets are not forwarded. In case of non-existent
contents, the router removes invalid request. However, it occupies PIT memory
till timeout. If content is dynamically-generated, then all Interest packets
are forwarded to the producer. It wastes the bandwidth and occupies router’s
PIT.

  * 4.

Content/cache poisoning: The attacker sends corrupted data. And, CS caches the
corrupted data. When an Interest packet is sent, CS forward the corrupted data
in Data packet.

In the rest of the section, Bloom Filter based NDN techniques to solve some
security issues are discussed. Table 9 illustrates the advantages and
disadvantages of the security techniques.

Massawe et al. [85] proposed Scalable and Privacy Preserving Routing Protocol
in NDN (SP-NDN) to provide high security and content privacy. The technique is
based on Bloom Filter. Each Interest packet has a name and a secret key shared
between the consumer and producer. Both packet name and secret key are
considered as an element and inserted into the Bloom Filter. During the query,
the packet name and secret key are checked with the Bloom Filter. If the
packet matches, it is forwarded. Otherwise, the packet is dropped. The
technique uses multiple Bloom Filters to reduce the false positive
probability. Guo et al. [55] proposed an anti-pollution algorithm against the
false-locality pollution. It is based on Bloom Filter. The technique permits
the backbone router and traces the path in its CS. Each cached content is
associated with a counter and PathTracker. The counter counts the number of
times a particular content is hit, since, the last examination against
pollution. PathTracker is a data structure to trace the number of unique paths
travelled by the Interest messages corresponding to each content. When an
Interest packet is received, the cache is searched. The corresponding counter
is incremented by 1. And, PathTracker stores the travelled path information.
When a cache content reaches a threshold value, then the content is either a
popular content or a victim of an attack. Saving the path information makes
the Internet structure exposed to an attacker. To prevent this, in case of a
cache miss the path information is deleted. Moreover, storing path information
also leads to processing and network overhead. The technique implemented the
PathTracker using probabilistic counting with stochastic averaging and Bloom
Filter. The Bloom Filter uses only one hash function. The content name is
hashed by the hash function, then the slot is set to 1. The technique is
resilient against address spoofing. However, it’s not efficient in case of
address-based approach.

Wu et al. [134] proposed an access control algorithm to provide an effective
security solution for Smart Homes. The access control algorithm uses Cipher
Block Chaining (CBC) symmetric encryption algorithm, Identity Based Encryption
(IBE), Proxy Re-encryption (PR) and CBF [77]. This algorithm effectively
utilizes the cache. Cache is used to process user requests for data to cancel
user privileges, improve user logout, and reduce delays. In a smart home, the
home administrator is called a home manager that performs functions to grant
user privileges. The access control algorithm has four stages. First stage,
initialization uses CBC and IBE. Second stage is a user application permission
stage. It requires the user signs the Interest packet using a private key and
send to the home manager. After successful authentication, the home manager
stores user information in the user registry. Transform key is generated using
PR and is sent to the user along with registration confirmation Data packet. A
third stage is user access data stage. The algorithm permits the users to
access data in two ways, namely, caching and not caching. The intermediate
routers do not cache the data or it caches the data. The data keys are
converted to cipher text which is required by authorized users. Fourth stage,
user logout stage occurs in two situations. One is active cancellation and the
other is passive cancellation. In passive cancellation, the home manager
delete users from the registry based on time. The deleted users are broadcast
to the intermediate routers. The intermediate router updates the CBFs. CBFs
are also used to filter ineffective Interest. This algorithm improves both
user identity filtering and user logout mechanism.

Chen et al. [29] proposed an access control mechanism based on Bloom Filter.
The mechanism implements Bloom Filter to pre-filter Interest from consumers to
avoid unauthorized access. In this technique, for each site a Bloom Filter is
constructed to identify the authorized users. Each site constructs a Bloom
Filter using digests of all public keys present in active user tables. Then,
the Bloom Filter is sent to routers. Bloom Filter is piggybacked with Data
packet to the routers. The router uses Bloom Filter to pre-filter Interests
from users not in the active user tables. Continuously, the users get added to
the network. Hence, Bloom Filter is periodically sent to the router for the
update. In case of mobile users, a virtual subscription is given to the user.
When a new user moves to a different network and sends an Interest, if it is
rejected, then the Interest is a resend. This Interest triggers update of
Bloom Filter in producer site. The method is using conventional Bloom Filters.
Moreover, it is not using any technique to reduce the false positive
probability.

Cache privacy protection mechanism (CPPM-DAM) [147] is a Bloom Filter based
security mechanism. It determines legitimate users and prevents cache privacy
snooping. Bloom Filter has $k$ independent hash functions and $D$
$k$-dimensional matrices, where $D$ refers to the number of classes for
content popularity. And, each $k$-dimensional matrix stores the elements
belong to the corresponding class. From $n!$ permutation of hash functions,
$n$ number of hash functions are randomly chosen. This permutation indicator
is included in the Interest packet by adding as a new string field to the
content name of the packet. However, the same packet should have the same
permutation. After receiving an Interest packet, the content name and the
permutation indicator are extracted from the packet. Using the permutation
indicator the name is mapped to $n$ addresses. Based on the addresses the
matrix cell is verified whether the addresses are 1. If all are 1, then the
content is present in CS. Then the data is sent to the consumer. If any one
cell is 0, then the content is new and the addresses are set to 1. Permutation
indicator helps in determining the difference between the packet with high
probability. However, permutation indicator is an overhead in case of new
content. Increase in attack increases the round trip time. Moreover, less
number of hash functions leads to the possibility of guessing the permutation
by attackers. Matrix size depends on the popularity. The less number of hash
functions leads to the possibility of guessing the permutation by attackers.

##  11 Simulator

Currently, the only and most popular simulator for NDN is ndnSIM. It is an
open source NS-3 based simulator. In this section, the available three ndnSIM
versions are discussed. In addition, Table 10 highlights the advantages and
disadvantages of Bloom Filter based ndnSIM. Table 10 illustrates some features
and URL of the Bloom Filter based ndnSIM.

ndnSIM [5] is an open source NS-3 based simulator. The first version of ndnSIM
was proposed in the year 2012. It represents the NDN network in a modular
fashion. It has an independent protocol stack. It is possible to install the
stack on a simulated network node. It includes various helper classes and
traffic generator applications. This helps ndnSIM to provide a simplified
simulation scenario. ndnSIM provides maximum extensibility and flexibility by