In a communication network, data is typically encapsulated and transported within the communication network in units, which in certain contexts may be called frames, packets, Internet Protocol (IP) packets, cells, or the like. Herein, such units will broadly be called “packets” for ease of nomenclature, unless for the sake of example, a particular such unit is appropriate. Each such packet includes a header with a source address and a destination address, and a payload. The destination address may, for example, indicate a network address of a next intermediate “hop” for the packet and/or a network address of the ultimate destination for the packet.
Content addressable memories (CAMs) are used for a variety of functions in many different processing environments. CAMs are typically in the form of hardware that receives a piece of data and that returns a memory address storing information pertaining to that data. One use of CAMs is in the field of packet routing over a communication network.
For instance, CAMs may be used in the following manner by network devices to forward data packets. A typical network device has multiple ports that are connected to one or more other processing systems. The ports each receive packets from and send packets to the processing system(s) connected to the port. A switching fabric in the network device connects the ports of the network device to one another to allow the network device to pass a packet received on a first port to a second port of the network device, which then transmits the packet to the processing system(s) connected to the second port. In order to forward the packet, each port has a CAM that stores the prefixes of IP addresses and/or stores data that indexes or otherwise points to locations of a memory connected to the port. In the latter case, the CAM is used to return an address in the memory that stores next hop information for the IP address. When that next hop address ultimately is obtained, the packet is routed to that hop address via the associated port of the network device.
Typically, hardware within the network device (e.g., logic circuits, FPGAs, ASICS, etc.) is required to do two CAM lookups for every packet to find the route to forward the packet. If, for instance, a CAM with a length of 64 bits or greater is used, the hardware first masks the right 32 bits and finds the best path in the left side of the CAM. Next, the hardware masks the left 32 bits of the CAM and finds the best path in the right side of the CAM. Based on an assigned preference or some other criteria, the hardware will select the best path (e.g., identify a memory location that stores the network address of the next destination for the packet) between the two best paths identified in the searches of the left and right sides of the CAM. For the processes thus described, the hardware has to either be capable of doing parallel lookups on the left and right sides of the CAM or has to be able to do two lookups, while still meeting the timing requirements for forwarding the packet.
The need to perform two CAM lookups adds to the complexity and cost of the required hardware of the network device. Moreover, performing two CAM lookups can also adversely affect timing. The required hardware can be simplified if data is only stored in one side of the CAM, such as if the data occupies only the left (or the right) 32-bits in each 64-bit CAM entry, thereby allowing use of only one mask. However, such a scheme results in waste (non-use) of 50% of the available storage space in the CAM.