Cisco Express Forwarding (CEF)

cef, fib and adjacency tables

22 April 2018   14 min read

I am currently studying to rectify my CCIE and it is at these times that I realise there is so much I have studied and learnt but forgotten. There are many cool things I come across that I think at the time are useful features that I need to remember, but unfortunately if you don’t have a real world use for them they are soon put to the back of the brain and over time forgotten. The same applies with taking for granted the way things work, be that ARP, DHCP or the process a switch or router goes through when moving traffic. I came across some of my old notes on CEF which I thought worth sharing.

Table Of Contents

Cisco Express Forwarding (CEF)

The forwarding of IP packets is done by the forwarding plane, also called the data plane. Routing protocols come under the control plane, as this relates to the communication of control traffic.

Process switching uses the routing table with the best route for every path requiring some form of route lookup. Fast switching is know as ‘route once switch many’, where the first packet to a destination IP is process switched with that entry also added to the fast-switching cache. The cache holds the destination IP, next hop info and data-link info that is needed to be added to a packet before forwarding. Future packets to same destination use this information from the cache rather than needing to be process switched.

These days CEF is enabled by default on switches for both IPv4 and IPv6. It overcomes shortcomings of fast-switching by offering high performance packet forwarding using dynamic lookup tables to switch the traffic.

With CEF the router or MLS pre-constructs the Layer 2 frame headers and egress interface information for each neighbor and keeps them ready in an adjacency table stored in its memory. A packet that is to be routed through a particular next hop will then simply use the pre-constructed Layer 2 frame header for that next hop without needing to visit the ARP or similar tables over and over again.

Locally generated or received traffic will always be process switched. The output of debugs like debug ip packet will only show the output of packet switched traffic as all transit traffic is processed by CEF. Therefore to see this you would have to disable CEF on the interface or globally. If CEF is disabled it falls back to fast switching, then finally process switching

show ip cache                                   Show the route cache (fast switching table)
show interfaces stats         Displays the switching path stats in a table, with the processor row indicating process-switched (software-switched) packets, while the router cache row includes both CEF-switched and fast-switched pkts

show ip cef ip_addr internal       Useful to see L3 packet details
show adjacency next-hop_addr detail    Useful to see L2 packet details

CEF works by creating two tables:

  • Adjacency table: Maintains the L2 forwarding information for each FIB entry eliminating the need for router to send out ARP requests. It holds adjacency entries for both IPv4 and IPv6 with these learnt from ARP and NDP Neighbor Advertisements.
  • FIB: Contains info from the routing tables and tracks the next-hop for all routes. IPv4 and IPv6 have separate FIB tables learnt from their respective routing tables. Where the adjacency table manages L2 info, the CEF table manages the L3 forwarding info.

Once the packets arrive at the router the layer 2 info is stripped off. This is normal and happens whenever a frame is accepted to a layer 3 device. Next the router looks up the destination using the CEF table, then finds corresponding adjacency table entry. Finally, the router adds the corresponding layer 2 information (found in the adjacency table) back to the packet and forwards the packet on.

CEF is implemented purely in software as part of the IOS run. Both FIB and adjacency tables are maintained in the router’s memory and lookups in these structures are done by the CPU as part of interrupt handler executed when a packet is received.

Multilayer switches and high-end routers go even further, instead of software-based FIB they use specialized circuit TCAMs to store the FIB contents and perform even faster lookups that aren’t dependent on the number of FIB entries. On these platforms the CEF structures are distributed to individual linecards if present and stored in TCAMs and forwarding ASICs.

CEF is enabled by default but can be disabled/ enabled globally or per interface.

show ip interface                                              See if CEF or other switching method is enabled
(config)# ip cef
(config-if)# no ip route-cache cef

show cef state     See if CEF is running and the different algorithms
show ip cef summary          Number of prefix entries
show adjacency summary       Number of adjacency entries

Forwarding Information Base (FIB)

The FIB is the Layer3 information but a lot more sparse than the routing table. It has the destination prefix, the next hop address and outgoing interface. Instead of carrying over the plain next hop IP from the routing table each entry in the FIB that represents a destination prefix instead contains a pointer toward the particular entry in the adjacency table that stores the appropriate rewrite information (Layer2 frame header and egress interface indication).

To view the FIB you need to look at the CEF table. It is particularly useful for looking at all the routes pointing out of a specific interface.
It only shows an exact match for the prefix and mask unless you add longer-prefixes.
The detail keyword will show you the MPLS label info, you can’t find this in routing table.
receive entry is generally created when the prefix is an IP address configured on one of the router’s interfaces.
An attached entry is created when the destination is directly attached to the router, so what’s in the directly connected network.

show ip cef interface detail                                detail is optional
show ip cef vlan id detail
show ip cef prefix_ip prefix_mask longer-prefixes longer-prefixes is optional

show ip cef null0      To see all nulled routes
show ipv6 cef               To see all IPv6 FIB entries

Under next-hop rather than an address you may see the type of adjacency, such as receive, attached or drop.
Receive means all packets handled by this adjacency are to be locally received and processed by the CPU. It also means that the packets shall not be rerouted elsewhere. Simply, the packets handled by the receive adjacency are considered to be addressed to the local host. All IPs configured on a multilayer switch will be present in the CEF with a receive adjacency and a /32 bit mask to match only the exact address configured on a SVI or on a routed port. The same goes for the broadcast and network addresses of each network configured on the switch.

For example, with the SVI on a switch you can expect to see at least these receive adjacency type entries in the CEF:

  • (our own IP)
  • (the broadcast)
  • (network number)

You would also expect to see an attached entry for the actual network address:

  • (network address)

For any other entries that are not directly attached (a connected device or device on a different network) and the adjacency is available, you will have the address of the next hop and the interface to reach it.

The show ip cef command is straight to the point, is great if you just want the next hop as it won’t show all the other irrelevant information. It is also a good way to see if you are using the default route.

show ip cef
nexthop Vlan350

show ip cef
    nexthop Vlan800

Adjacency table

The adjacency table maintains layer2 or switching information linked to a particular FIB entry, avoiding the need for an ARP request for each table lookup. It contains the entire data link header that should be used to reach the next-hop (adjacent) device. This will include the MAC of L2 destination address (could be end device or next-hop), the MAC of L2 source address (outbound L3 switches interface), Ethertype and if over a sub-interface the 802.1q VLAN tag.

Two nodes in the network are considered adjacent if they can reach each other using a single hop across a link layer. For example, when a packet arrives at one of the router’s interfaces, the router strips off the data-link layer framing and passes the enclosed packet to the network layer. At the network layer, the destination address of the packet is examined. If the destination address is not an address of the router’s interface or the all hosts broadcast address, then the packet must be routed.

Just like the routing table uses the ARP table for L3 to L2 mapping, the FIB uses the adjacency table for the corresponding L2 for every next-hop entry. It keeps records for every next-router and hosts that are directly connected to the switch, so all nodes that can be reached in a single L2 hop. For example it won’t have an entry for an IP behind the firewall, but will have an entry for the firewall itself.

The adjacency table will show you what layer2 information is going to be used in rewriting a frame header.

show adjacency ip_addr detail                           detail is optional
show adjacency interface detail
show adjacency vlan id detail
show adjacency summary       See a table of entries with the adjacency count for each interface

For Ethernet adjacencies the detail keyword will show the MAC addresses. The first 6 octets (12 digits) of the long hex number is the destination MAC (next-hop) and the next 6 is the MAC of the L3 departing interface (SVI or routed port). If it is a sub-interface next have 8100 followed by the VLAN number in HEX (4 digits). Finally, will have the Ethertype of 0800 if is IPv4.

For example, if you have the following entries in the ARP table, with .1 being local and .4 being the next-hop:

  • Fa0/0 - Native vlan - 0019.e87f.38e4 - 0017.9446.b340
  • Fa0/0.2 – vlan2      - 0019.e87f.38e4 - 0017.9446.b341
show adjacency fa0/0 detail
Protocol          Interface         Address
IP                FastEthernet0/0
00179446B3400019E87F38E40800             0017-9446-B340     0019-E87F-38E4        0800

show adjacency fa0/0.2 detail
Protocol       Interface           Address
IP             FastEthernet0/0.2
00179446B3410019E87F38E481000002    0017-9446-B341     0019-E87F-38E4        8100 0002 0800 0800

The CEF adjacency table (show ip cef adjacency) shows information on the different types of adjacencies.

  • Cache adjacency: This type of entry contains the correct outbound interface and the correct MAC address for its FIB entry. The MAC is the IP addresses MAC if the destination’s subnet is directly connected to the router, or is the MAC of the router that the packet needs to be sent to if the destination’s subnet is not directly connected to the router currently processing the packet
  • Receive adjacency: This type of entry handles packets whose final destinations include the router itself. This includes packets whose IP addresses are assigned to the router itself, broadcast packets, and multicasts that have set up the router itself as one of the destinations
  • Null adjacency: Handles packets destined to a NULL interface. Packets with FIB entries pointing to NULL adjacencies will normally be dropped, but this is NOT done silently so ICMP sent to source to inform of the drop
  • Punt adjacency: Deals with packets that require special handling or cant be switched by CEF. Such packets are forwarded to the next switching layer (generally fast switching) where they can be forwarded correctly
  • Glean adjacency: This adjacency is created when the router knows that either the destination IP’s subnet is directly connected to the router itself and it does not know that destination device’s MAC address, or the router knows the IP address of the router to forward a packet to for a destination, but it does not know that router’s MAC address. Packets that trigger this entry will generate an ARP request
  • Discard adjacency: Silently discard, no ICMP. Discarded because of ACL or other policy action
  • Drop adjacency: Packets that cant be forwarded normally, so are in effect dropped rather than forwarded (for example no route)

Glean adjacency is one of the most common ones which means the ARP entry doesn’t exist so the L3 forwarding engine cant forward the packet in hardware because of missing L2 next-hop address. The packet is sent to L3 engine so it can generate an ARP request and receive a reply. Discard, Drop, Noroute and Null adjacencies are obvious.
The weird one is Punt adjacency which indicates that the router cannot CEF-switch the packet toward the destination due to a feature being used that is not yet supported by CEF. Therefore, the packet is punted to the L3 engine for further processing. Some conditions that cause a CEF punt are:

  • The FIB table is full
  • ICMP redirect is involved
  • The encapsulation type isn’t supported
  • An ACL with the log option is triggered
  • Packets are tunneled requiring compression or encryption
  • A NAT operation must be performed
  • The IP time to live (TTL) has expired
  • MTU is exceeded so needs fragmenting
show ip cef adjacency discard or drop or glean or noroute or  null or punt              Inspect the adjacency types
show ip cef prefix

CEF load balancing

If the routing protocol is offering several different interfaces to the CEF process and two have an equal route prefix and metric, it is down to CEF switching to do the Load Balancing for them. CEF supports two modes of load sharing:

Per-packet: Packets destined to a destination network are distributed across multiple paths in a packet-by-packet fashion.
Per-destination (per-flow): Takes the source and destination IP and optionally other data to produce a hash value that identifies the particular path to carry the packet. In effect, for a particular source/destination pair, all packets flow through a single path. Other particular source/destination address combinations toward the same destination network can produce a different hash.

The per-destination load-sharing mode is the default and in general, it is preferred because it avoids packet reordering within a single conversation. It is technically achieved by placing a so-called loadshare table between the FIB and the adjacency table. This loadshare table contains up to 16 pointers to entries in the adjacency table, so if two equal-cost paths to the same destination, eight loadshare entries will point to one next-hop adjacency entry while another eight loadshare entries will point to another next-hop adjacency entry.

Can change the load-sharing method on a per-interface basis, but the availability of this command might be limited depending on the hardware capabilities of the device (often hardware-based multilayer switches don’t while software-based ISR routers do).

(config)# ip load-share per-destination or per-packet

When using per-flow load-sharing algorithm, CEF polarization could occur where certain links are not utilized at all because of the layered network topology and the same hashing algorithm on each router. After load-sharing on first router the next router down would use the same hash to load-share, meaning all the same traffic leaving this router will use the same outbound link.

To avoid this situation Cisco introduced unique-ID/universal-ID. The CEF universal algorithm (the default in current Cisco IOS versions), adds a 32-bit router-specific value to the hash function (universal ID, is a randomly generated value) that ensures that the same source/destination pair hash is a different value on different routers along the path. There are multiple variations of the CEF load-sharing algorithm, with the default being universal per-destination.

Original algorithm: The original unseeded implementation prone to CEF polarization
Universal algorithm: An improved algorithm using the Universal ID to avoid the CEF polarization
Tunnel algorithm: An improvement on the Universal algorithm especially suitable to environments where tunnels are extensively deployed, possibly resulting in a relatively small number of outer source/destination pairs. Avoids the CEF polarization
L4 port algorithm: Based on Universal while also taking L4 source/destination ports into account. Avoids the CEF polarization

show cef state                                                        Will show the load sharing method and algorithm used
(config)# ip cef load-sharing algorithm original or universal or tunnel or include-ports

One really useful part of CEF is that it can be used to predict the exact route from a specific source to destination ip:

show ip cef exact-route src_ip dst_ip
show ip cef dst internal    If multiple paths will show the paths used and the hash value

and finally…. packet rewrite

When the switch finds a valid entry in its FIB and adjacency tables, one step remains before the packet is forwarded, the packet headers must be adjusted:

  • L2 destination address: Changed to next-hop devices MAC
  • L2 source address: Changed to outbound L3 switches interface
  • L3 IP TTL: Decremented by 1
  • L3 IP checksum: Recalculated to include changes to the IP header
  • L3 frame checksum: Recalculated to include changes to L2/L3 headers

IPv6 headers do not contain a checksum so that stage is skipped.