# On Sharing an FIB Table in Named Data Networking
## 1 Introduction  
Distributing multimedia contents has become the main usage of the Internet and accounts for the majority of the Internet traffic today [1]. The current infrastructure based on a host-to-host communication model, however, is inefficient for distributing contents, since contents should be repeatedly transferred from content sources to multiple users. To overcome this inefficiency, content-oriented networking technologies have been introduced and Named Data Networking (NDN) [2] is a promising candidate as a future Internet architecture. Unlike the current Internet, NDN decouples the contents from their locations, and hence contents can be provided by any nodes which have the requested contents [2; 3; 4].  
To support the content-oriented service, the NDN defines two types of packets, _Interest_ and _Data_, to request and deliver contents, respectively. Packets are forwarded in an NDN router using three types of tables: Content Store (CS), Pending Interest Table (PIT), and Forwarding Information Base (FIB). The CS caches the contents so that any router which has the requested contents can transmit the requested content immediately. The PIT records the forwarded path of an Interest for _Data_ to be forwarded backwards. The FIB is similar to a routing table which stores the information of content sources. _Interest_ packets are forwarded by looking up FIBs [2; 3; 5].  
An FIB should have the output face information for any contents in the network while the variety of contents is enormous. Furthermore, the lengths of content names are not fixed and theoretically unbounded, unlike the Internet protocol (IP) address. Even though content names can be aggregated,it would be larger than the total number of domain names [6]. The size of an FIB table is expected to be excessively larger than an IP forwarding table, and consequently the traffic caused in building an FIB table can also be significant. Efficient routing and forwarding algorithms are essential for the successful realization of the NDN [3].  
This paper has two primary aims: (1) to reduce the traffic associated with building an FIB table; and (2) to reduce the memory requirement for storing an FIB table. To reduce the traffic for building an FIB table at each router, this paper proposes a new efficient method to share the connectivity information of an NDN network. In other words, rather than advertising each name prefix, we propose to share the summary of a set of name prefixes by using a Bloom filter. We also propose to forward _Interest_ packets based on querying the Bloom filters which are stored instead of FIB tables at each router, and hence the memory consumption is reduced.  
More specifically, the contributions of this paper are as follows:  
* We propose a novel method which combines the routing of network connectivity and the building of a forwarding engine using Bloom filters, while previous works focus on either the routing or the forwarding using Bloom filters. Since the Bloom filters used in the routing phase are also used for forwarding, the construction of forwarding engines is simplified to the union of Bloom filters.
* We also provide a method to reduce the impact of false positives, which is inevitable when using Bloom filters.
* Large scale simulations were conducted using four real topologies which have up to 279 nodes. One thousand consumers and producers were randomly allocated on the network topologies, equivalent to a network with up to 2279 nodes.
* The performance evaluation shows that the proposed scheme significantly reduces the network traffic for routing and the memory consumption for storing name prefixes in a forwarding engine.  
The remaining part of this paper proceeds as follows. Section 2 briefly introduces related works. Our proposed FIB sharing algorithm is described in Section 3. The performance evaluation result is shown in Section 4. Section 5 concludes the paper.