# On Sharing an FIB Table in Named Data Networking
## 2 Related Works  
### Routing in Named Data Networking  
Conventional routing algorithms used in the Internet can also be applied for the NDN because the forwarding model of the NDN is a superset of the current IP network [2; 7; 8]. However, the NDN has fewer restrictions in routing. For example, while multi-source or multi-destination packets are prohibited in the Internet protocol in order to avoid looping, they are allowed in the NDN. Furthermore, while routers in the current Internet cannot identify changes that have occurred in a network without running routing protocols, NDN routers can detect network changes without running routing protocols due to the stateful forwarding, in which a router waits for the _Data_ packet after transmitting an _Interest_ packet [5]. Unlike the IP network, forwarding engines in NDN allow for multiple output faces, and thus NDN routers can rank the list of faces and alter the forwarding path when a link failure occurs. Since forwarding planes can adapt short-term changes, control planes in NDN can be more focused on long-term changes occurring in a network [7]. Therefore, new unconventional but effective routing algorithms can be applied [6; 8; 9; 10; 11; 12].  
As a routing protocol for NDN, Named-data Link State Routing (NLSR) protocol [8] updates routing information using _Interest_ and _Data_ packets and produces a list of ranked faces for each name prefix in order to support adaptive forwarding strategies. In the Coordinated Routing and Caching (CoRC) scheme [6], many off-path caching mechanisms are correlated with a hash-based routing algorithm. Because responsible routers (RRs) only have FIB tables, memory consumption can be reduced. However, every RR should perform the tunneling for a given designated set of producers, and every packet should be forwarded to the corresponding RR. Hence, the CoRC cannot provide the shortest-path delivery.  
Another hash-based routing scheme, \(\alpha\)Route [11], employs a name-based distributed hash table (DHT) and a distributed overlay-to-underlay mapping. By partitioning name prefixes based on similarity, similar names are located in the same partition. The overlay-to-underlay mapping is utilized to support near-shortest path routing. This scheme claims to provide the near-optimal routing in theory, but this claim has not yet been fully evaluated by simulations. Moreover, because this scheme treats a name prefix as a set of characters, finding the longest matching name prefix at component levels is hard to achieve.  
A Bloom Filter-based Routing (BFR) [13] has been introduced. Each content server broadcasts Content Advertisement Interest (CAI) message which contains the information of the content server with a Bloom filter. The received CAI messages are stored in PITs, and hence all nodes have CAI from all content servers in their PIT after the routing phase. Initially, the Interest is forwarded by looking up the Bloom filters stored in PIT, and then the FIB is populated when the Data is returned as the response. BFR reduces the traffic to build FIB tables by employing Bloom filters. However, the Bloom filters are only used for populating the FIB tables, and finding the longest matching prefix is not considered when looking up the CAI messages as well as no protection is provided for the delivery towards the wrong content server due to false positives. Furthermore, a router should search both FIB and CAI messages when the entry for the requested content has not been populated.