Cisco Support Community
cancel
Showing results for 
Search instead for 
Did you mean: 
Announcements

Welcome to Cisco Support Community. We would love to have your feedback.

For an introduction to the new site, click here. If you'd prefer to explore, try our test area to get started. And see here for current known issues.

New Member

RIB and FIB

Hi all,

It is stated that the time needed to access the FIB is much less than accessing the RIB.

Can some one please clarify in which physical memories are actuall RIB and FIB stored?

Also the Fast Switching is considered to perform Destination based Load Balancing. I have configured a lab using 7200 series routers in which Fast Switching is enabled by default. I configured a loopback address on every router and established two parallel links between the two routers. I then performed a traceroute (extended) using loopback addresses. However, the tracerouter alternatively used each link showing that actually the PER PACKET BASED load sharing is used.

Can someone please clarify this?

Best Regards,

Daud Parvez

4 REPLIES

RIB and FIB

What routing protocol were you running between the 7200 series routers in your lab? Also, can you paste the output of the traceroute command that you say is proving per-packet load sharing?

Cisco Employee

RIB and FIB

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

RIB and FIB

That was an excellent read.

New Member

Thanks so much for the

Thanks so much for the clarity Peter..I'm a newbie when it comes to MPLS..also can u elaborate more on the Data Plane and Control Plane lookups onece the packet reaches the ingress of the PE router?

 

Thanks,

Malcolm

2470
Views
0
Helpful
4
Replies