# On Sharing an FIB Table in Named Data Networking
## 2 Related Works
### Forwarding in Named Data Networking  
As in the IP network, content names in NDN are hierarchical and aggregatable for scalability. In forwarding an _Interest_ packet, therefore, the face with the longest matching name prefix should be identified. Since finding the face of the longest matching name prefix in wire-speed is a challenging research issue, various lookup algorithms and data structures have been introduced. These algorithms can be categorized into three groups: (a) trie-based [14; 15]; (b) hashing-based [6; 16]; and (c) Bloom filter-based [14; 17; 18; 19].  
NameFilter [19] lookup structure consists of two stages: the first stage for ascertaining the longest matching length and the second stage for finding the corresponding face. Both stages are based on multiple Bloom filters. Each of the Bloom filters in the first stage is dedicated to a specific length storing name prefixes in that specific length. The second stage consists of Bloom filters for each face. When looking up, both stages are queried sequentially: the longest matching length is found in the first stage, and then the output face is determined by querying the Bloom filter of the matching length in the second stage. NameFilter is a memory-efficient lookup architecture, but it requires a number of memory instances to support the parallel query and may return false faces because of false positives of the Bloom filters.  
A Name Lookup engine with Adaptive Prefix Bloom filter (NLAPB) [18] is a hybrid lookup structure of Bloom filters and name prefix tries. In this hybrid data structure, a name prefix is divided into two parts: B-prefix and T-suffix. Bloom filters are built for the valid lengths of B-prefixes while tries are created for T-suffixes. The length of B-prefixes is adaptively chosen based on popularity. NLAPB reduces the memory consumption compared to the name prefix trie and the false return rate as opposed to Bloom filter-based structure [20].  
Name prefix trie with a Bloom filter (NPT-BF) and NPT-BF-Chaining [14] have the same architecture which contains two parts: an on-chip Bloom filter and an off-chip name prefix trie. The Bloom filter is employed to filter out unnecessary accesses to the name prefix trie. Usually, the access time to off-chip memory takes much longer than to on-chip memory, and thus reducing the number of off-chip memory is crucial for enhancing the lookup performance. The lookup procedure of NPT-BF is as follows. The Bloom filter programmed by every node in the trie is queried first and then the trie is accessed only if the query result is positive. To find the longest matching prefix, this process is continued while increasing the number of name components. To further reduce the off-chip memory accesses, NPT-BF-Chaining continues to query the Bloom filter while increasing the number of name components to find the best matching length (BML). After finding the BML, the corresponding node on BML is accessed. If the input matches with the node, then the output face is returned immediately. Otherwise, back-tracking to upper levels should be performed until the matching node is found. These algorithms guarantee to return the right face and when the on-chip Bloom filter is sufficiently large, the lookup can be done with only one off-chip memory access on average.