IP Route Caching with Two Search Stages on Prefix Length

An apparatus, comprising:

• a network element, operative for receiving via a data network a packet having a destination address;
• a processor in the network element;
• a main memory storing a database of packet forwarding information;
• a cache memory accessible to the processor, the cache memory having cache entries therein that represent a portion of the packet forwarding information of the main memory, the destination address and the cache entries each comprising a binary number having most significant bits, wherein the processor is operative to perform the steps of;
• assigning a number M;
• making a first determination that the number M of the most significant bits of one of the cache entries and the number M of the most significant bits of the destination address are identical;
• making a second determination that an additional number M+L of the most significant bits of one of the cache entries and the additional number M+L of the most significant bits of the destination address are identical;
• responsively to the second determination retrieving routing information for from the cache memory;
• and
• processing the packet according to the routing information.