# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 1 Introduction  
The global IP traffic forecast provided by Cisco Systems reported that the annual run rate for global IP traffic was 1.5 Zeta bytes per year (122 EB per month) in 2017, and the global IP traffic will reach 4.8 ZB per year by 2022, which means it will increase nearly threefold over the next five years. The rapid growth of traffic has made packet forwarding in routers a bottleneck in constructing high-performance networks. An IP address is composed of a network part and a host part. The network part indicates a group of hosts included in a network while the host part indicates a specific host [1]. The network part is called a prefix and hosts connected to the same network have the same prefix. In a class-based addressing scheme, the prefix length is fixed at 8, 16, or 24 bits and routers perform an exact match operation for an IP address lookup. However, because of the excessive address wasting caused by the inflexibility of the prefix lengths under the class-based addressing scheme, a new addressing scheme called classless inter-domain routing (CIDR) has been introduced. In the CIDR scheme, arbitrary prefix lengths are allowed and routers identify the longest prefix among all matching prefixes as the best matching prefix (BMP) for an IP address lookup [2; 3; 4]. Various IP address lookup algorithms have been researched, including trie-based [2; 3], hash table-based [5] and Bloom filter-based algorithms [6; 7]. Since an access to an off-chip memory is 10-20 times slower than an access to an on-chip memory [8], reducing the number of off-chip memory accesses required for looking up an IP address is the most effective strategy [6; 7]. While the trie and the hash table are generally stored in off-chip memories due to their sizes, a Bloom filter is an efficient structure that can be stored in an on-chip memory. In building a packet forwarding engine, various hardware components, such as application- specific integrated circuits (ASIC), ternary content addressable memory (TCAM) and field-programmable gate arrays (FPGA), are used to satisfy the wire-speed packet forwarding requirement. As a flexible and programmable device, the FPGA has a matrix of configurable logic blocks connected through programmable interconnects. In particular, FPGAs have been widely used to build the prototypes of packet forwarding engines [9; 10; 11; 12; 13] and intrusion detection systems [14; 15; 16]. The contribution of this paper is as follows. We propose a vbf architecture, which is a multi-bit vector Bloom filter for the purpose of IP address lookup. The vbf is proposed to obtain lookup results by accessing only an on-chip memory. An off-chip hash table is rarely accessed when the vbf fails to provide the results. We have evaluated our proposed architecture in two steps. The construction procedures of the vbf and the hash table are implemented using C at behavior level, since the construction procedure is not necessarily performed in real-time. The performance at the behavior level has been evaluated in terms of on-chip memory requirement, off-chip memory requirement, the average number and the worst-case number of memory accesses, indeterminable rate and false port return rate. The search procedure that should be performed in real-time is implemented using Verilog with a single FPGA. The performance of the FPGA has been evaluated in terms of block-RAM (BRAM) requirement, resource utilization and throughput. The remainder of this paper is organized as follows. Section 2 briefly explains the Bloom filter and previous IP address lookup algorithms utilizing on-chip memories. Section 3 describes our proposed IP address lookup algorithm using a vectored-Bloom filter including theoretical analysis on the search failure probability of our proposed algorithm. Section 4 describes the hardware architecture implemented on an FPGA. Section 5 shows behavior simulation results comparing the performance of the proposed vbf with other structures. Section 6 shows the hardware implementation details of our proposed structure.