Steve,
There are a few reasons why a lookup through the CEF table is
faster than a lookup in the IP routing table.
A lookup in the IP routing table is done top down until a match
is found, much like how an access-list is processed. The problem,
however, is that the IP table is not in any specific order, therefore,
the worst case lookup for a route is directly proportional to how many
prefixes exist in the IP routing table.
The CEF table, on the other hand, takes a maximum of four
lookups before a match is found. CEF uses four data structures, each
with 256 children, with each child having 256 children, etc. This gives
us a maximum entry size of 2^32 (all IP address space). These
structures are divided as follows:
Root
-0.0.0.0
-1.0.0.0
-2.0.0.0
..
-255.0.0.0
Suppose we're doing a lookup on the prefix 1.2.3.4. First we
find the 1st child under the root (1.0.0.0)
Root
-1.0.0.0
--1.0.0.0
--1.1.0.0
--1.2.0.0
--...
--1.255.0.0
Under the child 1.0.0.0, we now find the 2nd child (1.2.0.0).
Next, we find the 3rd child under 1.2.0.0 (1.2.3.0), and finally the
fourth child under 1.2.3.0, (1.2.3.4). Our final lookup is now as
follows:
Root
-1.0.0.0
--1.2.0.0
---1.2.3.0
1.2.3.4
As you can see, no matter which prefix we are doing a lookup on,
we have to do a maximum of 4 lookups in order to find it, unlike the
normal IP routing table, where our worst case lookup time is
proportional to the amount of prefixes in the table.
The next reason that CEF is faster than a normal lookup is the
adjacency table. Every time a lookup is done in the IP routing table,
an addition lookup (recursive lookup) must be done to find the outgoing
interface for the next hop IP address. In the case of CEF, this lookup
is already done for you in the adjacency table. The adjacency table
provides us with the outgoing interface, and the destination layer 2
address that must be encapsulated in order to send the packet out said
interface.
Lastly, the main advantage of CEF is that the above mentioned
lookups are done *before* any traffic is sent. In the case of the other
caching mechanisms, a cached entry is not created until the first packet
in the flow is fast-switched. This follows the paradigm of route once,
switch many. CEF on the other hand is just switch many, since the
routing lookup is already performed.
HTH,
Brian McGahan, CCIE #8593
[EMAIL PROTECTED]
Internetwork Expert, Inc.
http://www.InternetworkExpert.com
Toll Free: 877-334-8987
Direct: 708-362-1418 (Outside the US and Canada)
-Original Message-
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of
Steven Aiello
Sent: Thursday, September 04, 2003 10:06 AM
To: [EMAIL PROTECTED]
Subject: ??? Cisco Express Forwarding ??? [7:74794]
Another question,
in CEF is the whole routing table held in a cache? If so what is the
diffrence between this and the routing table held in RAM? Is the cache
faster than the regular RAM in the router?
Thanks,
Steve
**Please support GroupStudy by purchasing from the GroupStudy Store:
http://shop.groupstudy.com
FAQ, list archives, and subscription info:
http://www.groupstudy.com/list/cisco.html
Message Posted at:
http://www.groupstudy.com/form/read.php?f=7i=74811t=74794
--
**Please support GroupStudy by purchasing from the GroupStudy Store:
http://shop.groupstudy.com
FAQ, list archives, and subscription info: http://www.groupstudy.com/list/cisco.html
