IP lookup in Cisco Routers

[alessiagreco]

 I was curious to know where the IP lookup takes place in a Cisco router?

[bigevilbeard]

The IP lookup takes place in the firmware of a Cisco router. The firmware is the software that is responsible for the basic functionality of the router, including IP routing. The firmware contains a routing table, which is a database of IP addresses and their corresponding routes. When a router receives a packet, it looks up the destination IP address in the routing table. If the destination IP address is found in the routing table, the router knows how to route the packet to its destination.

The operating system of a Cisco router is responsible for more advanced features, such as security, QoS, and VPNs. However, the IP lookup is performed by the firmware.

Hope this helps.

[Ramblin Tech]

"I was curious to know where the IP lookup takes place in a Cisco router?"

TL;DR: Unless you are talking about a CPU-based router, it takes place in the NPU.

Too long version...

I believe that there are really two questions packed in here:

1. Where does the packet processing "engine" that performs the lookup reside when executing?
2. Where is the data structure that the engine looks into to find the next-hop?

Answers to both questions are entirely platform dependent, but some generalities hold true: The engine can be implemented in either software instructions that execute on a general purpose CPU such as x86 or ARM, or the engine can be implemented in an ASIC with either fixed functionality (behavior cannot be changed later) or programmable functionality (behavior configurable/programmable by the Network Operating System (NOS)). Programmable forwarding ASICs are also known as NPUs (Network Processing Units).

Given enough time, we can all probably write a Python script to extract the destination IP address from a binary string (ie, the packet header) and then use that extracted address to lookup in a data structure (list, tuple, dictionary, etc) a prefix with the longest mask that best matches the address. That prefix would be associated in a data structure with a next-hop IP address and the egress interface. Next, we would construct the appropriate L3 encapsulation (retain received addresses unless NAT'ing, decrement TTL, update IP header checksum) and L2 encap (source & destination MAC addresses, any required VLAN tag, etc) and switch/queue the outgoing packet to the egress interface for transmission. Software-based routers from Cisco (eg, ISRs, Cat8K) execute this same lookup functionality on their CPUs, though the code tends to be written in C for performance reasons (and I have greatly simplified what is taking place). The engine code itself is loaded from flash/SSD and executes from RAM; loading the code from flash/SSD into RAM and initiating execution is what is happening when the router boots up.

So where is the data structure that contains the prefixes for the lookups in a real router (not our Python toy)? That will be in RAM also, stored in a FIB. Think of the FIB as a structure optimized for high-speed lookups that is derived from the routing table. Unlike the routing table, the FIB does not care about which routing protocol originated the prefix, nor administrative distances, nor anything that does not have to do with the prefix, the next-hop IP address, the egress interface(s), and the egress L2 encap (again, simplifying here). The info is not necessarily stored in the FIB itself, as the FIB lookup can yield an index into other structures to glean all the necessary info.

If a CPU-based router implements its packet-processing code and FIB in RAM, where does an ASIC-based router implement them? As you would expect, an ASIC system implements its lookups within the gates of its integrated circuitry. The FIB (or portions of it) tend to be stored in expensive, specialized memory such as TCAM or static RAM directly accessible from the ASIC. This memory can return the next-hop result much more quickly than using CPU instructions to lookup in slower, cheaper dynamic RAM.

I did not touch on virtual routers in the cloud, but they tend to run in RAM, though some functions might be offloaded to NICs with some packet-processing capabilities.