IntroductionA router can learn prefixes from different sources: directly connected, static routes, or dynamic routing protocols. Each dynamic routing protocol has its own data structures to store routing information from packet exchanges, namely, OSPF/IS-IS database, EIGRP topology table, or BGP table.
Each routing protocol runs its own route selection algorithm (for example, SPF for OSPF and DUAL for EIGRP) to determine the best paths. These best paths are then candidates to be installed into the routing table, also known as the Routing Information Base or RIB. What actually gets put in the RIB depends on the administrative distance (AD) value (lower is preferred).
Ideally, the RIB would forward the IP packets but this is not always possible. For example, BGP routing table entries don't have an outgoing interface and often the next hop is not directly connected. In this case, the router has to perform a recursive lookup to resolve the exit interface. Historically, this process was done "on demand" as packets arrived (process switching/fast switching). However, this method is not very efficient and can cause high CPU utilization, even resulting in a router meltdown. To counteract these issues, Cisco Express Forwarding (CEF) was developed.
Instead of performing the whole routing process "on demand", CEF takes a proactive approach and processes the RIB information before any packets have even arrived. CEF pre-builds a forwarding table ahead of time, instead of waiting for incoming packets. This table is called the Forwarding Information Base (FIB).
Forwarding Information Base (FIB)The FIB is conceptually similar to the RIB. It maintains a mirror image of the forwarding information contained in the IP routing table. When routing or topology changes occur in the network, the IP routing table is updated, and these changes are reflected in the FIB. The FIB maintains next-hop address information based on the information in the IP routing table.
The FIB is built and ordered in a way that allows it to optimize fast retrieval of information and longest prefix match lookup.
Read more: Demystifying CEF
Router# show ip cef
Prefix Next Hop Interface
192.168.0.0/30 attached Serial2/0/0:1
10.2.61.8/24 192.168.100.1 FastEthernet1/0/0
Router# show ip cef 10.2.61.8 255.255.255.0
10.0.0.0/8, version 72, per-destination sharing
0 packets, 0 bytes
via 192.168.100.1, 0 dependencies, recursive
traffic share 1
next hop 192.168.100.1, FastEthernet1/0/0 via 192.168.100.1/32
via 192.168.101.1, 0 dependencies, recursive
traffic share 1
next hop 192.168.101.1, FastEthernet2/1/0 via 192.168.101.1/32
0 packets, 0 bytes switched through the prefix
The Adjacency TableThe FIB is only one part of the routing process, and it does not contain complete forwarding information. The full Layer 2 frame rewrite information is still needed to successfully forward the packet. This information is available in different data structures, such as the ARP table. The complete forwarding information is compiled from the RIB/FIB and Layer 2 data, and it is then be placed into the adjacency table. As with the FIB, building the adjacency table is completed before any packets are forwarded.
The adjacency table is holds, unsurprisingly, the list of all adjacencies known to the router. A router can know thousands of routes (even 500,000+) but only have a few neighbors. The complete forwarding information for these neighbors is contained in the adjacency table. That is, the outgoing interface toward the neighbor, and the complete Layer 2 frame header that can be used to send packets to that neighbor.
Router# show adjacency detail
Protocol Interface Address
IP FastEthernet1/0/0 10.2.61.8(7)
0 packets, 0 bytes
00107BC30D5C = destination MAC address
00500B32D820 = source MAC address
0800 = Ethertype of the packet
See: IP Switching Cisco Express Forwarding Guide