Cisco Express Forwarding – CEF Load Balancing

When designing, configuring, or troubleshooting networks with redundant paths, it’s important to understand the role Cisco Express Forwarding (CEF) plays in forwarding packets.  Routing protocols are certainly important, but all too often engineers take CEF for granted in its default configuration without understanding the details of CEF Load Balancing.


In reality, CEF “load balancing” is really “load sharing”.  It’s fairly common for people to use these terms interchangeably because it simplifies conversation, but don’t expect interface counters to reflect equal utilization.


Cisco routers perform equal cost, per-destination load balancing by default, while EIGRP also has the unique ability to load balance unequal cost paths using the variance command.  Optionally, you can do per-packet load balancing with the interface command ip load sharing per-packet on each interface forwarding traffic, but the practice is discouraged in most production networks.  This round-robin packet level load-balancing can lead to out of order packets, ultimately causing performance problems that will be difficult to diagnose.  (Remember – VoIP packets are dropped by the destination if received out of order.)  How does this per-destination load balancing really work and how can it be tuned?  To understand this load balancing process, let’s first take a look at a couple of the components that make up CEF.

The routing table, also known as the RIB (Routing Information Base), is populated with the results of routing protocol calculations.  Whether it be a link-state, distance vector, or hybrid routing protocol, the “best path” to a destination will be in the routing table along with quite a bit of important information related to each of the calculated paths.  If you have multiple equal-cost best paths, the best 4 will be shown by default.  You can allow up to 32 using the maximum-paths command in most new IOS versions, but your mileage may vary with different hardware and software.  This next-hop information in the RIB is passed on to the FIB (Forwarding Information Base), or forwarding table. (Note: BGP only displays a single best-path in the RIB, by default.)  This forwarding table is where CEF load balancing happens.


Why have a FIB and a RIB?  The RIB shows what the routing protocols have calculated to be the next-hop.  The FIB indicates where the router is actually sending packets.  For example, Policy Based Routing (PBR) can override the routing table, so the FIB (show ip cef) would more accurately provide the next hop.


R1#show ip route 4.4.4.4
Routing entry for 4.4.4.4/32
 Known via "eigrp 100", distance 90, metric 158720, type internal
 Redistributing via eigrp 100
 Last update from 192.168.0.2 on FastEthernet0/0, 01:37:00 ago
 Routing Descriptor Blocks:
 * 192.168.1.2, from 192.168.1.2, 01:37:00 ago, via FastEthernet0/1
 Route metric is 158720, traffic share count is 1
 Total delay is 5200 microseconds, minimum bandwidth is 100000 Kbit
 Reliability 255/255, minimum MTU 1500 bytes
 Loading 1/255, Hops 2
 192.168.0.2, from 192.168.0.2, 01:37:00 ago, via FastEthernet0/0
 Route metric is 158720, traffic share count is 1
 Total delay is 5200 microseconds, minimum bandwidth is 100000 Kbit
 Reliability 255/255, minimum MTU 1500 bytes
 Loading 1/255, Hops 2
R1#

The FIB is unique to CEF in the sense that process switching and fast-switching don’t use it.  CEF’s forwarding table is prepopulated with the next-hop IP, and egress interface information is found in the adjacency table.  Unlike the routing table, the forwarding table only contains the destination prefix and the next hop.  Even if PBR is altering routes, the CEF tables will reflect the true paths.  CEF uses the adjacency table to obtain the layer 2 header information for it’s adjacent next-hop neighbor.  This adjacency table is not precalculated – it’s built as the router learns about it’s neighbors, through ARP for example.  Once the neighbor adjacency is learned, all future packets sent to that neighbor/adjacency will use the layer 2 header information stored in that table; it doesn’t look up next-hop data in the ARP cache and create a new layer 2 header for each new session.

R1#show ip cef 4.4.4.4
4.4.4.4/32
 nexthop 192.168.0.2 FastEthernet0/0
 nexthop 192.168.1.2 FastEthernet0/1
R1#
R1#show adjacency
Protocol Interface Address
IP FastEthernet0/0 192.168.0.2(14)
IP FastEthernet0/1 192.168.1.2(14)
R1#

By default, CEF uses per-destination load balancing.  This is already the default, but the command syntax is ip load sharing per-destination.  The “per-destination” term is a little misleading because it’s load balanced based on source-destination (hash value) address pairing, not just destination.  In other words, packets for a given source-destination host pair will always take the same path, even if multiple equal cost paths are available. Traffic streams destined for different pairs may take a different path.  Regardless of actual function, this is referred to as “per-destination load balancing”.


Most routers use software based forwarding, regardless of the forwarding method chosen.  CEF improves performance by using CPU interrupts to switch traffic, rather than a more resource intensive process level switching.  High end routers and almost all modern switches offload this processing to dedicated chips, called ASICs .  This hardware based forwarding is extremely fast, yet consumes no CPU resources in packet forwarding.


This is where things get interesting.  CEF can use multiple algorithms to distribute traffic across all the egress interfaces.  The default algorithm is called the Universal algorithm and each router uses a random (determined at boot up) 32 bit value as part of the hash to randomize connections across available interfaces.  This works well for most situations and balances large amounts of traffic pretty evenly, but there are times you may want to change this.

You have the option of selecting from several CEF load balancing algorithms using the global command, ip cef load-sharing algorithm.

  • Universal (default)
  • Original
  • Include-Ports (12.4.11T or later IOS required)
  • Tunnel

Cisco still offers the aptly named Original algorithm, which uses a small 4 bit hash value… the exact same value on every router.  This led to a problem called CEF Polarization, so it’s fallen out of favor and really shouldn’t be used.

The Include-Ports algorithm is probably the second most useful option, behind Universal.  If you have a small number of devices communicating with each other, you may not get a very even distribution of traffic across multiple paths.  Using the default Universal algorithm, two SIP gateways communicating between their loopback IP addresses would never use multiple network paths, since the source and destination hash would always yield the same CEF path for every connection.  To resolve this, we need to add layer 4 ports to the mix.  Since the destination port will typically be fixed for each service, ip cef load-sharing algorithm include-ports source would likely be the best choice in our example.  Because source TCP ports are more random, producing a different hash value for each connection, the resulting CEF path selection will also be more random.

This brings us to the Tunnel algorithm.  GRE tunnels (as well as other tunnel types) carry multiple traffic streams, all hidden from routers through encapsulation; the source and destination will always be the tunnel endpoints.  The Tunnel algorithm is tuned to more fairly balance connections on links consisting of a small number of source-destination pairs.

With multiple ways of getting to the same destination, how can you tell which path a particular packet will take?  The simplest way is to use the command show ip cef exact-route command.  Using this command, you can test real or hypothetical addresses against the CEF table to see which path will be taken.


dCEF is feature on larger routers and switches that provides a FIB table on each physical line card.  This allows the ASICS on the line cards to achieve extremely high packet forwarding rates without impacting the CPU on the data plane.


As a final note, you may notice when running this command that the results never change unless you change an input, such as the source or destination address.  This means that two given endpoints will always follow the exact same path through a network when using CEF.

 

One thought on “Cisco Express Forwarding – CEF Load Balancing

  1. Ali I.

    I wonder if CEF load-sharing universal (and/or Layer 4 source port) algorithm is similar to the load-sharing algorithm used by EtherChannels. EtherChannels perform an exclusive OR on the source/destination port along with the layer 3 info which yields a more balanced approach to load sharing.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload the CAPTCHA.