DOUBLE DENSITY CONTENT ADDRESSABLE MEMORY (CAM) LOOKUP SCHEME
First Claim
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.
4 Assignments
0 Petitions
Accused Products
Abstract
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.
132 Citations
33 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method, comprising:
-
associating network addresses to either first or second sections of a memory, the association to the first or to the second sections being based on a value of at least one bit of the network addresses; receiving a packet to be forwarded; examining a network address associated with the received packet, including determining a value related to at least one bit of the network address associated with the packet; using the determined value of the bit of the network address to select either the first or the second sections of the memory to search; and searching the selected section of the memory for information that pertains to the network address associated with the packet. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. An apparatus, comprising:
-
a first memory having first and second sections, the first and second sections being respectively associated with network addresses based on a value of at least one bit of the network addresses; a communication interface to receive a packet having an associated network address; and a lookup handler coupled to the communication interface to examine the network address associated with the packet to determine a value related to at least one bit of the network address associated with the packet, the lookup handler further being coupled to the first memory to use the determined value of the bit of the network address associated with the packet to select either the first or the second sections of the memory to search; and a first memory interface to search the selected section of the first memory for routing information that matches the packet address. - View Dependent Claims (25, 26, 27, 28, 29, 30)
-
-
31. An article of manufacture, comprising:
-
a machine-readable medium usable with a content addressable memory (CAM) having at least first and second portions and having instructions stored thereon, for binary first data including a plurality of bits, to; determine whether to program the first data into the first portion or the second portion based on at least one bit of the data. - View Dependent Claims (32, 33)
-
Specification