How does the software version of CEF (Cisco`s technology for speeding up packet switching) implement algorithm to search prefixes in FIB (Forwarding Information Base)?
Does it use a hash table or tree-based search algorithm, or what does it use?
Network Engineering Stack Exchange is a question and answer site for network engineers. It only takes a minute to sign up.Sign up to join this community
CEF uses a trie:
Cisco Express Forwarding
Cisco Express Forwarding, also uses a 256 way data structure to store forwarding and MAC header rewrite information, but it does not use a tree. Cisco Express Forwarding uses a trie, which means the actual information being searched for is not in the data structure; instead, the data is stored in a separate data structure, and the trie simply points to it.
This separation of the reachability information (in the Cisco Express Forwarding table) and the forwarding information (in the adjacency table), provides a number of benefits:
- The adjacency table can be built separately from the Cisco Express Forwarding table, allowing both to build without process switching any packets.
- The MAC header rewrite used to forward a packet is not stored in cache entries, so changes in a MAC header rewrite string do not require invalidation of cache entries.
- You can point directly to the forwarding information, rather than to the recursed next hop, in order to resolve recursive routes.
Essentially, all cache aging is eliminated, and the cache is pre-built based on the information contained in the routing table and ARP cache. There is no need to process switch any packet to build a cache entry. Other Entries in the Adjacency Table
The adjacency table can contain entries other than MAC header rewrite strings and outbound interface information. Some of the various types of entries that can be placed in the adjacency table include:
- cache—A MAC header rewrite string and outbound interface used to reach a particular adjacent host or router.
- receive—Packets destined to this IP address should be received by the router. This includes broadcast addresses and addresses configured on the router itself.
- drop—Packets destined to this IP address should be dropped. This could be used for traffic denied by an access list, or routed to a NULL interface.
- punt—Cisco Express Forwarding cannot switch this packet; pass it to the next best switching method (generally fast switching) for processing.
- glean—The next hop is directly attached, but there are no MAC header rewrite strings currently available.