The CEF Forwarding Process

Optimum switching tree
The CEF Forwarding Process
At last we come to CEF. CEF maintains two separate but related tables: the forwarding table and the
adjacency table. The forwarding table contains routing information, and the adjacency table contains
layer 2 next-hop addressing. CEF uses a trie instead of a tree. No, that’s not a misprint. A trie
is a pointer used with a data structure, where the data structure does not actually contain the data.
The separation in the data structure means that the lookup process can be recursive, allowing
different routes to be selected for successive packets, thus enabling per-packet load sharing.
Also, if information in a cache changes because the lookup is performed individually each time,
the most up-to-date information is always used.
The CEF forwarding process is illustrated in Figure 18.12. This simple diagram illustrates
that the lookup is much swifter because the 256-way data structure is the most efficient of all
lookup methods, and is directly associated with the adjacency table.
The result of CEF forwarding is a much higher throughput. True, a lot of this increased speed is
due to proprietary architecture inside the switch or router, including the increased use of ASICs and
specialized buses and memory arrangements. But it’s also true that packets no longer need to be forwarded
across internal buses to the busy route processor, which is where most of the router latency
is introduced. And there are other benefits to CEF, such as the ability to support packet-by-packet
load sharing, which cannot be achieved using cached entries as in fast or optimum switching.