Quick Notes: Cisco Express Forwarding (CEF)

• Cisco Express Forwarding (CEF) is a packet forwarding or switching method that Cisco IOS uses. 
• It is the latest IP switching method developed in Cisco IOS, and it is the default packet forwarding method being used now.
• MPLS requires CEF.
• Packets can be forwarded through the router in three basic ways: process switching, interrupt switching, or through an application-specific integrated circuit (ASIC).
• In process switching, a special Cisco IOS process that is scheduled to run when the router receives packets is what performs the switching of packets.
• A Cisco IOS process does not perform the switching of packets in Interrupt mode. Rather, when packets arrive to the router, the interface processor interrupts the central CPU and asks it to switch the packet according to a route cache or switching table. That cache or table can be built in several ways.
• Finally, the router can program the switching table into an ASIC so that the packets can be switched in hardware. Several Cisco platforms can program the CEF table into ASICs.

Process Switching

• Process switching is the slowest of all switching methods. 
• When switching a packet through the router, a Cisco IOS process copies the packet to the CPU memory and looks up the destination IP address in the IP routing table.
• The central CPU of the router always looks at the packet; no other intelligent hardware decides how the packet is forwarded.

Fast Switching

• Fast switching is a switching method that builds an on-demand forwarding table. 
• The first packet for a destination that arrives is process switched.
• This cache is not permanent. Some timers govern the fast switching route cache, and from time to time, some entries are deleted, freeing memory. 
• As long as packets are switched for certain destinations, these destinations remain in the route cache.
• Each IP prefix entry in the route cache has an outgoing interface, next hop, and Layer 2 rewrite field.

CEF Switching

• The switching table is no longer built on demand, but it is built in advance.
• As such, each prefix in the routing table has an entry in the CEF switching table at the same time.
• When the routing table changes, the CEF switching table is updated.
• In some cases, the other switching methods might still be needed. For example, packets that have IP options - then it is process-switched.

CEF in MPLS Networks

• Labeled packets that enter the router are switched according to the label forwarding information base (LFIB) on the router. 
• IP packets that enter the router are switched according to the CEF table on the router. 
• Regardless of whether the packet is switched according to the LFIB or the CEF table, the outgoing packet can be a labeled packet or an IP packet.
• CEF is the only switching method in Cisco IOS that can label an incoming IP packet and forward it.
• CEF has two main data structures: the Forwarding Information Base (FIB) and the adjacency table. (The FIB is also referred to as just the CEF table.)

• The adjacency table is the CEF component that is responsible for the MAC or Layer 2 rewrite.
• The adjacency table holds one adjacency or Layer 2 rewrite structure per router that is connected to that multipoint interface. This adjacency can be built from information learned from Address Resolution Protocol (ARP), ATM, or Frame Relay map statements, and inverse ARP on ATM or Frame Relay.
• Interpreting the Ethernet3/3 adjacency: The first twelve characters are the MAC address of the destination next-hop interface. The next twelve characters represent the MAC address of the source interface of the packet (Ethernet3/3). The last four characters represent the well-known Ethertype value 0x0800 for IP.

• The CEF table or FIB is the CEF component that is responsible for the Layer 3 forwarding decision that is made.
• The CEF table looks similar to the IP routing table on the router. In fact, each prefix in the routing table has the same prefix in the CEF table.
• The CEF table holds essential information to make a forwarding decision, i.e. the IP prefix, the recursively evaluated next hop, and the outgoing interface.
• An important aspect of the CEF table is that recursive prefixes are immediately resolved. If, for instance, a BGP prefix is in the routing table, and it points to a BGP next hop—which is learned via an IGP—the BGP prefix is inserted into the CEF table with a next hop that is learned from recursing to the BGP next hop.

Distributed CEF (dCEF)

• Some Cisco routers use a central CPU without any form of decentralized or distributed intelligence.
• Other routers can distribute the burden of forwarding traffic through CEF by using the distributed CPUs to forward traffic without interrupting the central CPU.
• To achieve the distributed forwarding, both the CEF and adjacency table have to be distributed to these distributed CPUs.
• The redistributed intelligence can be present on Versatile Interface Processor (VIP) or line cards, depending on the router platform. They are all interconnected by means of a bus or switching fabric architecture, which can distribute the CEF and adjacency table.
• To enable distributed CEF on a router, configure the command ip cef distributed.
• If you use CEF in the Distributed mode, LFIB is also distributed.
• To achieve high rate packet forwarding, the router can use ASICs (specifically built chips) on the boards or line cards. To have the ASICs forward the packets per the routing table, the router distills the CEF table into the ASIC so that it is correctly programmed to forward the packets.

Load Balancing in CEF

• CEF allows for load balancing or load sharing of traffic among multiple outgoing links. 
• CEF needs multiple outgoing links as next hops in the routing table to perform load balancing. 
• The command maximum-paths specifies how many paths or next hops are allowed per prefix in the routing table.
• Two main load balancing schemes: per-packet or per-destination.
• The per-packet load balancing scheme sends packets in round-robin on the outgoing links.
• The default CEF load balancing scheme is per-destination. 
• The per-destination load balancing is actually done by hashing the destination and source IP address.
• The per-destination load balancing is the default load sharing method for CEF because the per-packet load sharing scheme can send consecutive packets of the same flow (this means the same source/destination IP address pair) across different paths and hence might lead to a reordering problem of the IP packets at the destination. This can lead to problems for traffic such as VoIP because a performance hit or quality degradation can occur if the packets arrive out of sequence, as packets might be considered lost. In addition, it adds jitter.
• Per-packet load sharing, however, gives a perfect load sharing distribution on the outgoing paths, whereas the per-destination load sharing is only a statistical method of distributing flows per pairs of (source IP address, destination IP address).
• Cisco IOS can load-balance in CEF by hashing the source and destination IP address and pointing the result of that hash to a load sharing table. This table holds 16 hash buckets. Each of the 16 hash buckets points to one adjacency, and multiple buckets can point to the same adjacency.
• Sixteen hash buckets exist. These hash buckets distribute the load of traffic among all possible outgoing paths in the best possible way. For example, in the case of two outgoing paths, eight hash buckets are assigned to each outgoing path. In the case of three outgoing paths, five hash buckets are assigned to each outgoing path, and one hash bucket is unassigned. In short, if 16 is not divisible by the number of paths, the remainder hash buckets are not used and are disabled.

Unequal Cost Load Balancing

• Possible - In that case, the 16 hash buckets are not evenly distributed among all possible paths.
• EIGRP variance allows unequal cost load balancing because it enables routes to be installed in the routing table that are not the best.
• The traffic share counters represent how traffic is distributed between the paths.
• For example, for two unequal cost EIGRP paths with metrics 16640 and 5120, the traffic share count is almost the same ratio 120:37 (inversely proportional to the path's metric).
• Based on the traffic share count, CEF assigns 12 buckets to the faster path and 4 buckets to the slower path (12:4 is very close to 120:37).
• A perfect distribution of the hash buckets according to the metric is not always possible. The distribution will always be approximate.
• See: Understanding Unequal-Cost Load-Balancing

Labeling IP Packets by CEF

• A stack of at least one label is imposed on the IP packet on the ingress LSR at the edge of the MPLS network.
• The CEF table shows the imposed label stack for each prefix.
• The labels are top label to bottom label when read from left to right.

• An LSR can add labels to an already labeled packet, but the LSR performs that function according to the LFIB and not the CEF table. CEF labels only IP packets.
• Recursion can also be used to assign the label to a prefix.
• For example, when the recursion of the BGP prefix 10.99.1.1/32 to the IGP prefix 10.200.254.4 (the BGP next hop) is done, the label 23 is inherited from the IGP prefix and shows up in the CEF table as the imposed label for the BGP prefix 10.99.1.1/32.
• This is an extremely important feature of MPLS. All the packets that are flowing along the same LSP (in this case, all the packets that are destined for prefixes with the same BGP next hop) are imposed with the same label.

Load Balancing Labeled Packets

• If the MPLS payload is an IPv4 or IPv6 packet, Cisco IOS uses the CEF hashing algorithm to determine the outgoing interface (per-destination load balancing).
• The load balancing is done only between labeled paths. This means that if an IP (unlabeled) and a labeled path have the same cost, only the labeled path is used to forward the packets.
• The algorithm for load balancing the MPLS packets is as follows:
• If the MPLS payload is an IPv4 packet, the load balancing is done by hashing the source and destination IP address of the IPv4 header.
• If the MPLS payload is an IPv6 packet, the load balancing is done by hashing the source and destination IP address of the IPv6 header.
• If the MPLS payload is not an IPv4 or IPv6 packet, the load balancing is done by looking at the value of the bottom label.

References

MPLS Fundamentals