Double density content addressable memory (CAM) lookup scheme
View Patent ↗The number of content addressable memory (CAM) lookups is reduced from two to one. Each side (left and right sides) of a CAM is programmed with network addresses, such as IP addresses, based on certain bits of the network addresses. These bits of the network addresses (which represent packet routes) are examined and used to determine whether the particular network address is to be placed on the left or right sides of the CAM. The grouping of certain network addresses either on the left or right sides of the CAM can be performed by examining an individual bit of each network address, by performing an exclusive OR (XOR) operation on a plurality of bits of each network address, and/or by searching for bit patterns of the network address in a decision table. Network addresses that cannot be readily assigned to a particular side of the CAM using these grouping techniques are programmed into both sides of the CAM. During packet routing, techniques similar to the grouping techniques that populated the CAM are used to determine which of the two sides of the CAM is to be searched.
1. A method comprising:
providing a content addressable memory (CAM) having at least first and second portions;
providing binary first data including a plurality of bits; and
determining whether to program the first data into the first portion or the second portion of the CAM based on at least one bit of the data.
2. The method of claim 1 wherein the at least one bit is a single bit of the first data.
3. The method of claim 2 wherein if the single bit is a 1 , then programming the first data on the first portion of the CAM, and if the single bit is a zero, then programming the first data on the second portion of the CAM.
4. The method of claim 1 wherein the at least one bit is a plurality of the bits of the first data.
5. The method of claim 4 wherein determining whether to program comprises:
performing a function with the plurality of bits; and
determining whether to program the first data into the first portion or the second portion of the CAM based upon a result of performing the function.
6. The method of claim 5 wherein performing the function includes performing an XOR function with the plurality of bits.
7. The method of claim 5 wherein performing the function includes using comparing the plurality of bits to information stored in a decision table.
8. The method of claim 1 , further comprising programming the first data into both the first and second portions of the CAM.
9. The method of claim 1 wherein the first data comprises a portion of a data packet.
10. The method of claim 1 wherein the first data is a network address.
11. The method of claim 1 , further comprising providing binary second data including a plurality of bits, and determining whether to read from the first portion of the CAM or the second portion of the CAM based on at least one bit of the second data.
12. An article of manufacture, comprising:
a machine-readable medium storing instructions executable by a processor to:
determine whether to program binary first data comprising a plurality of bits into a first portion or a second portion of a content addressable memory (CAM) based on at least one bit of the first data.
13. The article of manufacture of claim 12 wherein the machine-readable medium further stores instructions executable by the processor to:
examine a network address associated with a received packet, including a determination of a value related to at least one bit of the network address associated with the packet;
use the determined value to select either the first or the second portions of the CAM to search; and
search the selected portion of the CAM for routing information to be used for forwarding the received packet.
14. The article of manufacture of claim 12 wherein the instructions include at least one of:
instructions to determine whether to program the first data into the first portion or the second portion of the CAM based on a single bit of the first data;
instructions to determine whether to program the first data into the first portion or the second portion of the CAM based on a result obtained from performing a function using the plurality of bits of the first data; and
instructions to determine whether to program the first data into the first portion or the second portion of the CAM using a decision table and the plurality of bits of the first data.
15. The method of claim 10 wherein the network address is a destination network address.
16. The method of claim 1 wherein the first portion is a first section of a row of the CAM and the second portion is a second section of the row of the CAM, wherein the first section is different from the second section.
17. The article of manufacture of claim 12 wherein the instructions comprise instructions to program the first data into both the first and second portions of the CAM.