# On Sharing an FIB Table in Named Data Networking
## 3 Proposed Work
### Packet Forwarding Procedure  
In the proposed scheme, _Interest_ packets are forwarded according to the query result of F-BFs instead of searching through an FIB table. When an _Interest_ packet arrives at a node, the node looks up every F-BF stored at each face of the node. To support the longest name prefix matching in our proposed scheme, the querying to an F-BF is serially performed while decreasing the number of name components, starting from the entire name of the _Interest_ packet. The detailed F-BF querying procedure is shown in Algorithm 2. Even though the querying to a Bloom filter is time-efficient, querying multiple F-BFs can be time-consuming, particularly when a node has many faces. To reduce the querying time, multiple F-BFs are merged into one functional Bloom filter [19; 26], as shown in Figure 4. Each column of the functional Bloom filter represents an F-BF from each face. Cells designated by hash indexes in querying are bitwise-ANDed to obtain a result vector. Set bits in the result vector represent positive faces. In Figure 4, cells located by hash indexes 1, 4, and 8 are examined, and the F-BF stored in the \(n\)th face produces a positive result. Hence, by merging all of the F-BFs into one functional Bloom filter, the querying is performed only once for each _Interest_ packet. Bloom filters never produce false negatives, and thus the proposed scheme guarantees that _Interest_ packets are always forwarded towards content sources. However, due to false positives of Bloom filters, the query results of F-BFs can be false. When the F-BFs produce positives in multiple faces, if the _Interest_ is forwarded to only one of the matching faces, it might be forwarded to the false path, and packets may be lost or detoured. To secure the packet delivery, it is possible to forward packets to all matching faces; however, this wastes network bandwidth. To avoid such inefficiency, we propose using an auxiliary FIB table. The proposed scheme initially forwards _Interest_ packets to all of the positive faces. When an _Interest_ packet has been forwarded to multiple faces and the corresponding _Data_ packet arrives at one of the faces, an entry is added to the auxiliary FIB table with the face of the first arrived _Data_ packet. The auxiliary FIB table is only used when an F-BF produces positives in multiple faces. In such a case, the auxiliary FIB table is searched as well, and the _Interest_ packet is forwarded accordingly. The detailed procedure for the _Interest_ packet forwarding is shown in Algorithm 3. Figure 3: An example of building an F-BF. 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]. Whenever a new S-BF arrives, the F-BF of the incoming face is updated by bitwise-ORing the incoming S-BF and the existing F-BF. The false positive rate of each F-BF differs since the number of programmed elements is different. The false positive rate for each face is \(f_{f}=\left(1-(1-\frac{1}{m})^{ksn_{s}}\right)^{k}\), where \(s\) is the number of combined S-BFs in a face and \(n_{s}\) is the number of name prefixes in an S-BF. Since it is difficult to estimate the number of S-BFs to be combined at every node, it is not possible to derive the exact formula for the entire topology. However, the false positive rate of the proposed work is lower than \(f_{f}\leq\left(1-(1-\frac{1}{m})^{kn_{t}}\right)^{k}\), where \(n_{t}\) is the total number of name prefixes. Figure 5, which is adopted from [5], shows the packet handling procedure of the proposed scheme. The _Interest_ packet handling procedure is illustrated in the upper part of Figure 5. The proposed scheme differs from the conventional one in several ways as follows. The F-BFs are first queried to identify matching faces. The auxiliary FIB is only looked up when the F-BF query produces positives in multiple faces.