# On Sharing an FIB Table in Named Data Networking
## 3 Proposed Work
### Sharing Connectivity Information  
Figure 2 illustrates the proposed scheme, where \(r_{i}\) (for \(i=1,...,7\)) represents a router in the network. It is assumed that nodes \(r_{3},r_{6},\) and \(r_{7}\), which are directly connected to other networks, receive prefix announcements from content publishers. As shown in the figure, they build an FIB table and create a summary of the FIB table in the form of a Bloom filter, named a summary Bloom filter (S-BF). The S-BF is constructed by programming every name prefix in the FIB table one by one. After building the S-BF, the router propagates its connectivity information to its neighboring nodes by flooding  
Figure 1: An example of two Bloom filter union, where the size of the Bloom filters, the number of hash indices, and the used hash functions are identical.  
the S-BF. Hence, a set of name prefixes programmed in the S-BF is shared in the network instead of actual name prefixes and the link state information. Because transmitting the S-BF consumes much less bandwidth than transmitting actual name prefixes, the traffic for propagating the connectivity information is greatly reduced.  
Each node builds a forwarding Bloom filter (F-BF) by combining the received S-BFs. Figure 3 shows an example of building F-BFs using the received S-BFs in \(r_{4}\) in Figure 2. A node has \(n\) F-BFs, where \(n\) is the number of faces, and the F-BF which dedicated for face \(i\) is denoted as F-BF[i]. The F-BFs are constructed by bitwise-ORing the received S-BFs, as described in Figure 1. If we assume that all links have the same delay and \(r_{3}\), \(r_{6}\), and \(r_{7}\) send the S-BF at the same point, the S-BF from \(r_{3}\) arrives first through face 1. The F-BF[1] for face 1 is formed by bitwise-ORing the S-BF from \(r_{3}\) and existing F-BF[1]. Later, the S-BF from \(r_{7}\) also arrives through face 1 and combines into F-BF[1]. As a result, S-BF from \(r_{3}\) and \(r_{7}\) are bitwise-ORed to form the F-BF[1] for face 1. The S-BF from \(r_{6}\) arrives first through face 2, and forms the F-BF[2] in face 2. Even though the same S-BFs may arrive later through other faces, the proposed work builds F-BFs only using the S-BFs arrived first to forward packets through the shortest path.  
The detailed procedure when a router receives an S-BF is shown in Algorithm 1. Initially, a node initializes all F-BFs corresponding to each face. If a node receives a new S-BF, the face combines the received S-BF with the F-BF, as shown in Figure 3; the S-BF is then forwarded to faces other than the incoming face. If a node receives a duplicate S-BF through different faces, it means that multiple paths to the publisher are available. The proposed work builds an F-BF using the firstly received S-BFs; however, the time difference between multiple S-BFs can be used to rank the faces. Since the proposed scheme works in a fully decentralized way, each node terminates the sharing the connectivity information right after flooding the S-BF, and this is repeated whenever a new S-BF arrives. When the process for propagating the connectivity information has been completed, FIB tables are only stored at edge nodes, which are connected to the outside of a network. Internal nodes only have an F-BF at each face. It is not possible for a node to know whether the connectivity information spreads to all other nodes in the network; however, the packet forwarding is possible even in the middle of the procedure sharing the connectivity information.  
Figure 2: An example of the proposed scheme. The nodes connected to other networks, \(r_{3}\), \(r_{6}\), and \(r_{7}\), only have the FIB table and the connectivity information is carried in S-BF.