Content

| 5.2 |  | Cisco Express Forwarding |
| 5.2.4 |  | CEF forwarding information base |

The forwarding information base (FIB) table consists of a four-level hierarchical tree. The four levels are derived from the fact that IPv4 uses a 32-bit address. Each level of the hierarchy is based on 8 of the possible 32 bits. CEF relies on a longest-match forwarding algorithm, meaning that the tree is searched in descending order until the “longest match", or greatest number of bits, is matched. The FIB tree is represented hierarchically, with the least-specific address at the top of the tree and the most-specific address at the bottom. Each leaf is based on an 8-bit boundary, with more-specific entries in descending order. This tree (commonly known as a 256-way radix tree) provides a highly efficient mechanism for rapid lookups. This ensures that minimal latency is incurred during the lookup process. It also provides for a highly scalable architecture in that IPv4 addressing can be completely accounted for with a minimal trade-off of performance versus table efficiency. Each leaf offers a pointer to the appropriate next hop entry in the adjacency table.

The CPU of the MSFC2 builds the FIB table from the IP routing table. The appropriate IP routing protocols first resolve the IP routing table, at which point the CEF process is invoked and the corresponding FIB and adjacency tables are constructed. The FIB table is maintained separately from the routing table. The routing table contains additional information that is important for the purposes of routing protocols, but not for the actual forwarding of packets. The routing protocol that created the route cannot be determined by the FIB. The FIB and adjacency tables are optimized to provide only the information that is necessary for a forwarding decision to be made, and nothing more. It is also important to note that recursive routes are resolved when the FIB table is built. This removes what has classically been a CPU-intensive event in non-CEF implementations.

If the FIB table becomes full, subsequent entries are compared to the existing entries, and the more-specific entries are maintained at the expense of less-specific entries. This method is necessary to ensure that proper forwarding is maintained. For example, the less-specific route of 1.2.0.0 is not specific enough to ensure proper routing to 1.2.1.0. In order to view the contents of the FIB table, use the command show ip cef detail from the MSFC2.

The second table used by CEF is the adjacency table. The adjacency table is discussed in next section.