RIBs and FIBs (aka IP routing table and CEF table)

Every now and then, I’m asked about the difference between Routing Information Base (RIB), also known as IP Routing Table and Forwarding Information Base (FIB), also known as CEF table or IP forwarding table.

We’ve discussed this topic during the Enterprise MPLS Packet Pushers Podcast, so you might want to listen to that one first before going into details.

Let’s start with an overview picture (which does tell you more than the next thousand words I’ll write):

A router has numerous ways of learning the best paths toward individual IP prefixes: they might be directly connected, configured as static routes or learned through dynamic routing protocols.

Each dynamic routing protocol (including RIP) has its own set of internal data structures, known as OSPF/IS-IS database, EIGRP topology table or BGP table. The routing protocol updates its data structures based on routing protocol updates exchanged with its neighbors, eventually collecting all the relevant information. Throughout this article we’ll work with 10.0.1.1/32 learned through OSPF and 10.0.11.11/32 learned through BGP, so let’s inspect the relevant OSPF/BGP data structures.

RR#show ip bgp | begin Network
   Network          Next Hop            Metric LocPrf Weight Path
r>i10.0.1.1/32      10.0.1.1                 0    100      0 i
r>i10.0.1.2/32      10.0.1.2                 0    100      0 i
*>i10.0.11.11/32    10.0.1.1                 0    100      0 i

RR#show ip ospf database router 10.0.1.1

            OSPF Router with ID (10.0.1.5) (Process ID 1)

                Router Link States (Area 0)

  LS age: 1612
  Options: (No TOS-capability, DC)
  LS Type: Router Links
  Link State ID: 10.0.1.1
  Advertising Router: 10.0.1.1
  LS Seq Number: 80000003
  Checksum: 0xC764
  Length: 60
  Number of Links: 3

    Link connected to: a Stub Network
     (Link ID) Network/subnet number: 10.0.1.1
     (Link Data) Network Mask: 255.255.255.255
      Number of MTID metrics: 0
       TOS 0 Metrics: 1

    Link connected to: another Router (point-to-point)
     (Link ID) Neighboring Router ID: 10.0.1.6
     (Link Data) Router Interface address: 10.0.7.9
      Number of MTID metrics: 0
       TOS 0 Metrics: 64

    Link connected to: a Stub Network
     (Link ID) Network/subnet number: 10.0.7.8
     (Link Data) Network Mask: 255.255.255.252
      Number of MTID metrics: 0
       TOS 0 Metrics: 64

Each routing protocol runs its own route selection algorithm (SPF algorithm in case of OSPF or IS-IS or pretty complex set of rules in case of BGP), deriving a set of IP prefixes reachable through that routing protocol and IP next hops that should be used to reach them. You can view the results of these route selection algorithms with protocol-specific show commands (for example, show ip bgp prefix for BGP and show ip ospf rib prefix for OSPF).

RR#show ip bgp 10.0.11.11
BGP routing table entry for 10.0.11.11/32, version 6
Paths: (1 available, best #1, table default)
  Not advertised to any peer
  Local
    10.0.1.1 (metric 66) from 10.0.1.1 (10.0.1.1)
      Origin IGP, metric 0, localpref 100, valid, internal, best
RR#show ip ospf rib 10.0.1.1

            OSPF Router with ID (10.0.1.5) (Process ID 1)

OSPF local RIB
Codes: * - Best, > - Installed in global RIB

*>  10.0.1.1/32, Intra, cost 66, area 0
     SPF Instance 2, age 00:48:15
     Flags: RIB, HiPrio
      via 10.0.2.1, FastEthernet0/0, flags: RIB
       LSA: 1/10.0.1.1/10.0.1.1

Both BGP and OSPF associate IP next hops with IP prefixes, but BGP simply uses the value of the next-hop attribute attached to the BGP route, whereas OSPF computes the IP address of the next-hop OSPF router with the SPF algorithm.

The results of intra-routing-protocol route selection are inserted in the IP routing table (RIB) based on administrative distance (and there are interesting consequences if two routing protocols have the same AD). Most routing protocols don’t complain when their routes are not used in the IP routing table; BGP has a special show command that can display RIB failures. In our scenario, the 10.0.1.1/32 prefix is received via OSPF and BGP and the OSPF route wins as OSPF has lower AD than internal BGP route.

RR#show ip bgp rib-failure
Network      Next Hop    RIB-failure            RIB-NH Matches
10.0.1.1/32  10.0.1.1    Higher admin distance  n/a
10.0.1.2/32  10.0.1.2    Higher admin distance  n/a

Ideally, we would use RIB to forward IP packets, but we can’t as some entries in it (static routes and BGP routes) could have next hops that are not directly connected.

Compare an IBGP route in the IP routing table (RIB) with an OSPF route:

RR#show ip route 10.0.11.11
Routing entry for 10.0.11.11/32
  Known via "bgp 65000", distance 200, metric 0, type internal
  Last update from 10.0.1.1 00:00:55 ago
  Routing Descriptor Blocks:
  * 10.0.1.1, from 10.0.1.1, 00:00:55 ago
      Route metric is 0, traffic share count is 1
      AS Hops 0
      MPLS label: none

RR#show ip route 10.0.1.1
Routing entry for 10.0.1.1/32
  Known via "ospf 1", distance 110, metric 66, type intra area
  Last update from 10.0.2.1 on FastEthernet0/0, 00:33:47 ago
  Routing Descriptor Blocks:
  * 10.0.2.1, from 10.0.1.1, 00:33:47 ago, via FastEthernet0/0
      Route metric is 66, traffic share count is 1

OSPF route has an outgoing interface; it’s computed by the SPF algorithm and transferred in the IP routing table. BGP route has no outgoing interface and its next hop is not directly connected; the router has to perform recursive lookups to find the outgoing interface (recursive lookups are also used to implement EBGP load balancing with loopback interfaces).

Early IOS releases performed a recursive lookup on the first packet sent to a new destination (process switching) and cached the result for subsequent packets (fast switching). Fast switching worked well in early Internet (with few global IP prefixes), but as the Internet grew and address-spraying DoS attacks became common, core routers frequently experienced cache trashing. Large number of packets were being process switched, resulting in very high CPU utilization and occasional router meltdown. It was time to move from cache-assisted forwarding to deterministic forwarding.

Forwarding Information Base (FIB) and Cisco Express Forwarding (CEF) switching were introduced to make layer-3 switching deterministic. When IP routes are copied from RIB to FIB, their next hops are resolved, outgoing interfaces are computed and multiple entries are created when the next-hop resolution results in multiple paths to the same destination.

For example, when the BGP route from the previous printout is inserted into FIB, its next-hop is changed to point to the actual next-hop router. The information about the recursive next-hop is retained, as it allows the router to update the FIB (CEF table) without rescanning and recomputing the whole RIB if the path toward the BGP next-hop changes.

RR#show ip cef 10.0.11.11 detail
10.0.11.11/32, epoch 0, flags rib only nolabel, rib defined all labels
  recursive via 10.0.1.1
    nexthop 10.0.2.1 FastEthernet0/0 label 19

Fully-evaluated FIB (CEF table) can then be used directly for layer-3 switching.

10 comments:

  1. excellent post, but sometimes I wish Cisco would give you a way to walk the RIB and not just the FIB. Picking routes and creating separate RIBs, (AKA Juniper does this -- not sure about the RIB though). This could be useful in some MPLS VPN scenarios and such.. just a rant :) (not really my idea, but it's cool)

    ReplyDelete
  2. Superb!! My Guru. Ivan :D

    ReplyDelete
  3. In the second to last paragraph you say "When IP routes are copied from RIB to FIB...and multiple entries are created when the next-hop resolution results in multiple paths to the same destination. I have a C6513 dual-homed to a single AS. When I do "sh ip bgp 4.2.2.2" I see two Paths. When I do "sh ip cef 4.2.2.2 detail" or "sh ip route 4.2.2.2" I see only one Path which seems normal.
    If the FIB had multiple Paths/next-hops/interfaces for a single prefix - wouldn't that require process switching and defeat the purpose?

    Oh and Thank You very much for sharing all of this great information!

    ReplyDelete
  4. Ivan Pepelnjak13 August, 2011 08:59

    Next-hop of a BGP or static route could be reachable by more than one IGP path (several equal-cost OSPF/EIGRP paths to the same destination). In that case, you'd see one BGP or static route entry in the RIB and multiple entries in FIB (at least that's what you'd have seen before CEF switching rewrite, not sure what the latest IOS releases would show).

    ReplyDelete
  5. Got it. Thank you Sir.

    ReplyDelete
  6. "The routing protocol updates its data structures based on routing protocol updates exchanged with its neighbors" doesn't make sense for me, a routing protocol doesn't have neighbors. would you explain this a little more ?

    ReplyDelete
    Replies
    1. Then please explain to me what the "show ip ospf neighbor" command displays?

      Delete
  7. Great post that actually explains why that secondary table is even needed.

    ReplyDelete
  8. Ivan, I love you. OK, not truly, but I want to express great appreciation. I am cutting my teeth on early routers and I asked "how does a router know what interface to use when it resolves next hop?" I learned about recursive lookups, why we have FIB(CEF) now, and I'm more prepared when I move into dynamic routing protocols.

    ReplyDelete
  9. Is it possible to calculate the FIB's from RIB's by just chossing the path with lower administrative distance. or there are other parameters/metrics that are considered while a path is moved from RIB to FIB ?
    In such a case do the vendors make their algorithm available like how they select a router from RIB to FIB ?

    ReplyDelete

You don't have to log in to post a comment, but please do provide your real name/URL. Anonymous comments might get deleted.

Ivan Pepelnjak, CCIE#1354, is the chief technology advisor for NIL Data Communications. He has been designing and implementing large-scale data communications networks as well as teaching and writing books about advanced technologies since 1990. See his full profile, contact him or follow @ioshints on Twitter.