Hello Daud,
First of all, the distinction between RIB and FIB should be made more precisely.
A RIB is actually a term that is used to denote either the "classic" routing table, or more precisely, the data from which this table can be computed. A FIB is an optimized version of this routing table compiled into a form that allows, either algorithmically or physically, for faster lookups.
The RFC 1322, 'A Unified Approach to Inter-Domain Routing', says it very nicely in Section 2.1.1:
The RIB contains the
routing information that entities exchange via the inter-domain
routing protocol; the RIB is the input to the route computation. The
FIB contains the information that the entities use to forward the
inter-domain traffic; the FIB is the output of the route computation.
Also, the RFC 3222, 'Terminology for Forwaring Information Base (FIB) based Router Performance' says in Section 5.3:
Definition:
As according to the definition in Appendix B of [4]:
"The table containing the information necessary to forward IP
Datagrams, in this document, is called the Forwarding Information
Base. At minimum, this contains the interface identifier and next
hop information for each reachable destination network prefix."
Discussion:
The forwarding information base describes a database indexing
network prefixes versus router port identifiers.
A forwarding information base consists of [FIB size (5.5)] FIB
entries (5.4).
The forwarding information base is distinct from the "routing
table" (or, the Routing Information Base), which holds all routing
information received from routing peers.
The forwarding information base contains unique paths only (i.e.
does not contain secondary paths).
Also, RFC 4271, 'A Border Gateway Protocol 4 (BGP-4)' uses the term RIB to denote the parts of the BGP database, not necessarily the resultant routing table. Many similar examples could be drawn from other RFCs.
In other words, the RIB consists of working databases of different routing protocols, and optionally the basic routing table itself (this slight ambiguosity is unpleasant, I admit myself). Often, the process of routing a packet is described on a table structure - the routing table that is sorted according to the netmasks in descending order, and going from the topmost entry step by step until a match is found. This process is computationally strongly ineffective - in the worst case, routing a packet will require to perform as many ANDs/matches as how many routing table entries are present. In other words, the complexity is linear, or O(N), as we sometimes use to say. The 'N' in this case denotes the number of entries in the routing table. It is interesting, by the way, that many of my students who are well-versed in software engineering including effective data structures usually just accept this way of explaining how IP routing works, and usually do not discover that this approach is workable but hugely inefficient.
The FIB is a compilation of the routing table, or more precisely, of the RIB, that tries to reorganize data in such a manner that it is considerably faster to perform lookups. Now, in software-based routers, the FIB occupies exactly the same memory as the RIB - the (D)RAM of the router. However, the FIB is built using efficient data structures - usually using trees - so that the lookup is faster. For example, if you used a binary tree (each bit in an IPv4 address occupying one level in the tree), each lookup would require only 32 matches at worst, regardless of the number of prefixes in the routing table. Compare this to tens or hundreds of thousands of matches necessary in a classic "routing table" lookup if the table is large!
And the optimization can go even further. On high-end routers and multilayer switches, the FIB is actually downloaded into the TCAM memory. The TCAM is able to perform the lookups even faster, partially caused by the fact that the TCAM performs the necessary matching operations in parallel - on all bits of the IP address at once. The TCAM lookup is therefore faster again, as the matching operations are performed by a hardware specially tailored for these operations, and are performed in parallel.
Hence, the difference between the lookup speed in RIB and FIB is caused primarily by their internal organization. If the RIB is seen as routing protocol databases and the data within, optionally including the classic routing table, then the slowness of the RIB lookup is explicable by the mere fact that these databases are organized to the routing protocol's needs, not to the needs of efficient packet forwarding, not even mentioning the amount of data that is irrelevant to the routing process itself (think feasible distances, timers, topological detail in LSAs or LSPs, etc.). The FIB is a distillation of all this data that leaves out all the information irrelevant for packet forwarding, and organizes the prefixes so that the lookups can be performed as fast as possible.
The Fast Switching is something called a Route Cache - 'route once, switch many times'. It is actually a cache of lookups formerly performed against a routing table. Once a match was found, all remaining packets directed towards the same destination are forwarded identically. That is the reason why the Fast Switching performs per-destination load balancing - even if there are multiple ways to the same destination, for a particular destination, only one particular route has been selected and cached. All remaining packets will be sent according to the cached result, i.e. through the same route.
Regarding the traceroute experiment you have performed, I remember reading somewhere that locally-originated packets are process-switched, not fast-switched. That would probably explain the phenomenon you are seeing. I frankly do not remember if locally originated packets can be CEF-switched. Anyone to fill me in here, please?
Best regards,
Peter
