How can router forward so fast?

Cisco created all sorts of different magic inside their boxes that optimize forwarding processing of packets.

Main router function is fairly self-explanatory. Router performs IP forwarding more often called IP routing. IP routing is process of deciding where to send the packet after it was received.

IP Routing explained in detail

Logic behind IP forwarding is listed in steps here with the assumption it will be an IPv4 packet that was received. This is process switching explained in 11 steps:

A frame enters the one of router’s interface
First thing that router does is to check frame check sequence. If FCS check fails it means that there was an error and frame will be dropped.
If FCS is ok, router looks inside Ethernet Type field to get the packet type info. Packet is extracted by discarding Data Link header and trailer.
IPv4 packets header checksum is read and if there is a mismatch, the packet will be dropped. If ok, we will get to next step.
Router reads the destination IP address to see if maybe one of his own interfaces has that IP. If that’s true, packet has arrived to destination (that router). Router reads protocol field in the header and determine to which upper protocol software to send the packet payload.
Otherwise, if packet destination is not on the local router, packet is routed. If the packet TTL, written in the header, is greater than 1, packet routing proceeds. If not, packet is dropped and ICMP Time Exceed is sent to the packet source.
If ok, router looks at his own routing table for most specific prefix match for destination IP.
Match in routing table has the info about next hop IP and outgoing interface. With that info read router is able to lookup for next-hop Layer 2 address. In case of Ethernet as outgoing interface, MAC address that will be found in ARP table. ARP table keeps all IP to MAC address bindings that router needed in near past.
When MAC address deduced, router is able to generate Data Link header and trailer around the packet.
Before creating that frame from packet, router decreases TTL field value (IPv4 header checksum will need to be recalculated afterwards). After all field are ready the frame if generated together with destination MAC address and so on.
Frame gets out the interface towards destination.

So, the process is not so simple as we imagined at first but it depicts normal routing steps for all routers. There is one important thing to mention here. The router needs to search through whole routing table every time he needs to resolve a next hop address in order to forward some packets. This search considerably slows down the whole routing process particularly for routers with huge routing tables.

Advancements in route lookup process

Cisco through time invented few methods to speed up steps 8 and 9 from the list above. The idea behind next technology is all about speeding up the routing table lookup process in order to get the next hop address in as few CPU cycles possible.

CEF, Fast Switching and Process Switching are those technologies and in today’s routers Fast Switching and CEF (Cisco Express Forwarding) are used.

Fast Switching – Route one forward many

Is the older one and we can look at him as addition of caching functionality to steps 8 and 9 from above. When first frame comes into the router he does on him all steps mentioned above. Basically it does normal process switching for that frame but after that it saves the result of route table lookup from step 8 and 9 inside route cache. Route cache will be sorted in ideal way to speed up the cache lookup which will follow next. Cache keeps only destination IP, next-hop address and Data-Link header that was used with first frame. Future packets destined to the same IP will match the catch entry. This will allow router to forward the packet quickly as all needed info is already prepared in cache.

Don’t be too happy about it, it’s not used anymore with new Cisco equipment because CEF resolves some drawbacks of using Fast Switching.

CEF

CEF enables fast Layer 2 header construction and faster output interface lookup.

If you followed all the steps mentioned above you will easily notice that the most difficult and thus slowest step in the whole process of routing is Layer 2 frame rewrite. Layer 2 frame rewrite is basically route lookup and construction of the whole L2 header that is needed to send the packet to next hop router. L2 frame rewrite is the thing that CEF is all about. CEF represents a technology of pre-prepared Layer 2 header for every next-hop one router has. This enables him to adhere Layer 2 header without the need of gathering all the data that goes inside

Fast L2 header construction using adjacency table

Our CEF enabled router saves in his memory adjacency table in which stores already constructed Layer 2 headers, exactly one L2 header correlated to every single directly connected neighbour. So, one constructed Layer 2 header for every neighbour. Table with prepared L2 headers is constructed from routing table information: output interface and next-hop address. Next-hop MAC address, if not resolved jet, of those next-hops is then resolved using ARP or some similar L3 to L2 mapping table from the IP addresses and used in L2 header construction.

Routing process becomes selecting one entry from adjacency table to encapsulate the packet and forward it really fast.

But is the process of selecting one entry from adjacent table also up to speed?

Fast lookup using FIB

CEF enabled router uses FIB table to find the right entry from adjacency table really fast. It is an Forwarding Information Base table which stores only pointers to one of adjacency table entries for every destination IP. Every FIB entry shows us which L2 header from adjacency table will be used to encapsulate the packet if he needs to be forwarded to particular IP destination.

FIB table is filled up by reading data from Routing table and sorting it and normalizing for faster lookup. Route table, or RIB in this case, is not really fast lookup friendly and, the situations where recursive lookups are needed to deduce real next-hop address, are making it even worse.

FIB resolves all that. If CEF FIB is used for lookups, RIB is only used to construct FIB when something in routing changes.

Altogether about the magic

CEF is technology that uses FIB table and adjacency table to make routing decisions and L2 frame constructions several times faster and thus making routing faster.

CEF can be implemented in software of the router or if even faster high end routing is needed it can be implemented in hardware by using TCAM memory modules. In software or in hardware the FIB speeds the lookup of desired destination prefix but if the hardware is used then CEF technology is enabling FIB lookup process to get us with desired destination IP in only one search iteration, it always finds the result at first try, magically.

If you want to know more about TCAM memory used to speed up FIB lookup using hardware look further at this one: TCAM and CAM memory usage inside networking devices