Double density content addressable memory (CAM) lookup scheme

• US 7,657,703 B1
• Filed: 04/28/2005
• Issued: 02/02/2010
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks Incorporated (Broadcom, Inc.)
• Inventors: Singh, Ram Dular
• Primary Examiner(s): LE, VU ANH
• Application Number:
  US11/118,697
• Time in Patent Office: 1,741 Days
• Field of Search: 711/108, 711/113, 365/49.1
• US Class Current: 711/108
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/7453 using hashing

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.

Claims

1. A method, comprising:

examining at least one bit of a network address associated with received data;

based on the at least one bit of the network address, determining which of first or second portions of a memory to search to obtain information; and

using the information obtained from the searched first or second portion of the memory to forward the received data.

2. The method of claim 1 wherein determining which of first or second portions of the memory to search includes determining which of first or second sides of a content addressable memory (CAM) to search.

3. The method of claim 1 wherein determining which of first or second portions of the memory to search based on the at least one bit includes determining which portion of the memory to search based on a value of a single bit of the network address associated with the received data.

4. The method of claim 1 wherein determining which of first or second portions of the memory to search based on the at least one bit includes performing an operation on a plurality of bits of the network address associated with the received data and determining which portion of the memory to search based on a result obtained from performing the operation.

5. The method of claim 4 wherein performing the operation includes performing an exclusive OR (XOR) operation on the plurality of bits.

6. The method of claim 1 wherein determining which of the first or second portions of the memory to search includes comparing a plurality of bits of the network address with data in a decision table, and determining a portion of the memory to search based on the comparison.

7. The method of claim 1, further comprising determining whether to program the information for the network address in the first portion or the second portion of the memory based on at least one bit of the network address.

8. The method of claim 7, further comprising programming both the first and second portions of the memory with same information.

9. The method of claim 1 wherein using the information obtained from the searched first or second portion of the memory comprises searching another memory using the obtained information.

10. The method of claim 1 wherein using the information obtained from the searched first or second portion of the memory comprises:

using the obtained information to locate a memory location in another memory; and

using the information stored in the memory location in the another memory to forward the received data.

11. The method of claim 5 wherein performing the XOR operation comprises performing the XOR operation on the 26^th and 27^th bits of the network address.

12. The method of claim 6 wherein comparing the plurality of bits comprises comparing the 28^th, 27^th, and 26^th bits of the network address with the data in the decision table.

13. A system comprising:

a first memory having first and second sections;

a communication interface configured to receive a packet having an associated network address;

a lookup handler coupled to the communication interface, the lookup handler configured to

examine at least one bit of the network address associated with the packet, and

select, based upon the at least one bit, one of the first or second sections of the first memory; and

a first memory interface configured to search the selected section of the first memory to obtain information for forwarding the packet.

14. The system of claim 13 wherein the first memory is a content addressable memory (CAM).

15. The system of claim 13 wherein the lookup handler is configured to:

perform an operation on a plurality of bits of the network address associated with the packet; and

select one of the first and second sections of the first memory based on a result obtained from performing the operation.

16. The system of claim 15 wherein the lookup handler is configured to perform an exclusive OR (XOR) operation on the plurality of bits.

17. The system of claim 16 wherein the lookup handler is configured to perform the XOR operation on the 26^th and 27^th bits of the network address.

18. The system of claim 13 wherein the lookup handler is configured to:

compare a plurality of bits of the network address with data in a decision table; and

select one of the first and second sections of the first memory based on the comparison.

19. The system of claim 18 wherein the lookup handler is configured to compare the 28^th, 27^th, and 26^th bits of the network address with the data in the decision table.

20. The system of claim 13 wherein the lookup handler is configured to determine whether to program the information for the network address in the first section or the second section of the first memory based on at least one bit of the network address.

21. The system of claim 13 further comprising:

a second memory; and

a second memory interface configured to use the information obtained from searching the first memory to locate a memory location in the second memory, the memory location in the second memory storing information used to forward the data packet.