RIB - Routing Information Base
Built in the control plane.
The routing
information base, or RIB, is the base processed together by a routing
device and compiled in the route table. This process is handled by
the device CPU in the control plane. The RIB leverages and computes
information from various sources, mainly tables from routing
processes, EIGRP (topologies) and OSPF (databases) for example. The
RIB also processes information statically defined route information.
The RIB gathers all
relevant information from all available sources and starts to make
decisions on which routes to use. Routing decisions are based on the
well known rules of the various routing processes, as well as the
administrative distances of those processes.
The most common way
to view the RIB is to issue a "show ip route" command.
RIB Failure
Instance where a
route process (BGP) cannot create routes in the RIB.
FIB - Forwarding Information Base
Original “process switching” relies on the router/switch CPU to process each packet routed through the device. The CPU can quickly become a bottleneck.
CEF is the successor
to “fast switching”. Fast switching is a process by which a
router/switch would cache initial route lookups, so that subsequent
flows do not have to perform route lookups. Only the initial route
lookup hit the CPU. All other packet switching is done in hardware.
Fast switching is enabled by the command ip route-cache
on a per interface basis. (Fun fact, Netflow is a mechanism that builds and sends a table based on the old route-cache process.)
CEF switching
expands on this concept by “pre-processing” all routes contained
in the RIB against the Layer 2 adjacency table, preventing the need
for route lookups. This results in the FIB and is built in parallel
with the RIB. In essence, Layer 3 routing is performed with direct
Layer 2 forwarding, thanks to the pre-poulation of the FIB with the
adjacency table.
The Adjacency table
maintains Layer 2 next-hop addresses for all FIB entries. Nodes are
considered to be adjacent if they can be reached over a shared,
connected IP network.
CEF Polarization
CEF polarization is
a phenomenon in which equal cost paths are present, but due to the
ECMP hashing process, some links are more saturated than others. The
default ECMP hashing operation is to hash Source and Destination IP
address. “Full” hashing includes Layer 4 values in the hash. The
hashing process itself is an XOR operation, explained in more detail
below.
Modern IOS
implements a unique-ID/universal-ID concept to help avoid CEF
polarization. The universal algorithm creates a 32-bit randomly
generated value at device bootup, the universal ID. This value is
then used to “seed” the normal ECMP hash function, ensuring the
same hash pair is always different throughout the network.
The CEF hashing
process can be modified under the ip cef load-sharing algorithm
command structure.
RouterA(config)#ip cef load-sharing algorithm ?
include-ports Algorithm that includes layer 4 ports
original Original algorithm
tunnel Algorithm for use in tunnel only environments
universal Algorithm for use in most environments
By default, CEF load
balances on a per flow vs per packet basis. This can be seen by
entering the following command on a prefix contained in the FIB, show
ip cef <prefix> internal.
RouterA#show ip cef
10.0.0.8/30 internal
10.0.0.8/30, epoch 0, RIB[O],
refcount 5, per-destination sharing
sources: RIB
feature space:
IPRM: 0x00058000
ifnums:
FastEthernet0/0(2): 10.0.0.2
GigabitEthernet1/0(3): 10.0.0.6
path 674C726C, path list 68E4D93C, share 1/1, type attached
nexthop, for IPv4
nexthop 10.0.0.2 FastEthernet0/0, adjacency IP adj out of
FastEthernet0/0, addr 10.0.0.2 674C5D00
path 674C72DC, path list 68E4D93C, share 1/1, type attached
nexthop, for IPv4
nexthop 10.0.0.6 GigabitEthernet1/0, adjacency IP adj out of
GigabitEthernet1/0, addr 10.0.0.6 674C5B80
output chain:
loadinfo 674E2984, per-session, 2 choices, flags 0083, 5 locks
flags: Per-session, for-rx-IPv4, 2buckets
2 hash buckets
< 0 > IP adj out of FastEthernet0/0, addr 10.0.0.2
674C5D00
< 1 > IP adj out of GigabitEthernet1/0, addr 10.0.0.6
674C5B80
Subblocks:
None
To change this per
flow behavior, use ip load-sharing [per-packet | per-destination].
Unlike per-destination method, per-packet load-sharing uses a round
robin method, without regard to IP addressing, to evenly distribute
network traffic over ECMP links. Of note, per-packet load-sharing
does have the potential to introduce issues, such as out of order
packets, in a traffic flow.
XOR Hashing
The XOR function is used by CEF (and port-channels) to determine
which interface to send a flow in an ECMP environment and
per-destination load-sharing is configured. The XOR function is well
suited for this as it lends to a more uniform result. When evaluating
two values (source and destination IP address in this case), the bits
of each value are compared. If the two bits are equal, then a 0
results. If the bits are different, a 1.
XOR Table
a | b | a XOR b---+---+--------0 | 0 | 00 | 1 | 11 | 0 | 11 | 1 | 0
Example XOR hash of two IP addresses, SRC 192.168.1.10, DST 8.8.8.8
SRC:
11000000 . 10101000 . 00000001 . 00001010
DST:
00001000 . 00001000 . 00001000 . 00001000
----------------------------------------------
XOR:
11001000 . 10100000 . 00001001 . 00000010
