# A New Bloom Filter Architecture
## 1 Introduction  
Currently, on the Internet, massive multimedia contents are being widely transferred, and the use of mobile applications is becoming increasingly popular. The amount of Internet traffic requiring high speed data transfer is therefore increasing exponentially. Since the Internet is based on a host-based communication infrastructure and forwards packets using IP addresses, transmission bottlenecks can easily occur if multiple users repeatedly request the same contents to a single host. In order to solve this problem, Named Data Networking (NDN) technology has been proposed as a promising future Internet architecture [1; 2; 3]. The NDN is an Internet architecture used to distribute content requests to different nodes in a network that had previously been concentrated on content sources. The NDN architecture effectively reduces network traffic by storing contents in network nodes such as routers, and repetitively providing the contents requested by different users. Content producers and content consumers in the NDN infrastructure communicate using both _Interest_ packets and _Data_ packets. When a consumer broadcasts an Interest packet for some content, the Data packet generated by the content producer can be transmitted by any router receiving the Interest and holding the Data. In other words, if an NDN router has the corresponding Data packet on the path between the producer and the consumer, the NDN router transmits the content to the consumer. In this way, the Data packet is transmitted from the network node closest to the consumer among the nodes with the content. An NDN router has three tables for packet forwarding: Content Store (CS), Pending Interest Table (PIT), and Forwarding Information Base (FIB). The CS is a cache memory for the temporary storage of Data packets [4]. The PIT is used for the transmission of the arrived Data packet by recording each forwarded Interest as well as the corresponding incoming face (port) of the Interest [5]. The FIB stores multiple output faces mapped to a name prefix in order to forward each Interest packet to itsproducer [6]. Among the many issues that need to be addressed in realizing the NDN infrastructure, wire-speed FIB lookup is one of the most essential [7; 8; 9]. FIB lookup algorithms can be categorized based on their approach: trie-based algorithms, such as name prefix trie (NPT) and priority-NPT (p-NPT) [10; 11]; hashing-based algorithms such as hashing-based NPT [9]; and Bloom filter-based algorithms such as NPT-BF, NPT-BF-chaining, and I(FIB)F [9; 12]. The motivation of this paper is to propose a high-speed FIB lookup algorithm based on a name prefix trie (NPT). Generally, a name prefix trie (NPT) is implemented with an off-chip memory because of its size [10]. Starting from the root node, the search procedure in an NPT finds the longest matching prefix, called the best matching prefix (BMP). The off-chip NPT search should then continue until a leaf node is encountered, even if matching prefixes have already been found in the search path. Hence, the NPT does not provide very good search performance. In this paper, we attempt to improve the search performance in an NPT by effectively utilizing on-chip memories because the time to access an off-chip memory is 10-12 times slower than that to access an on-chip memory [13]. Our primary goal is to use a space-efficient data structure that can be implemented with on-chip memories so that the search procedure required in the FIB lookup is completed only through on-chip memory accesses. Our secondary goal is to reduce the amount of on-chip memory access by preferentially searching the prefix with the longest level. In this paper, we propose a level-priority trie (LPT) algorithm for the FIB table lookup and a 2-phase Bloom filter architecture implementing the LPT. Bloom filters have been applied in many network algorithms to improve the search performances of routing tables because of their simplicity [14; 15; 16].