Double density content addressable memory (CAM) lookup scheme

• US 7,953,923 B2
• Filed: 12/16/2009
• Issued: 05/31/2011
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Singh, Ram Dular
• Primary Examiner(s): Le; Vu A
• Application Number:
  US12/639,762
• Publication Number:
  US 20100161894A1
• Time in Patent Office: 531 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 system comprising:

a memory comprising a first portion and a second portion; and

a lookup handler configured to;

determine a value based upon one or more bits of a packet;

select, based upon the determined value, one of the first portion and the second portion to be used for the packet; and

cause the selected portion of the memory to be accessed for processing the packet.

2. The system of claim 1 wherein the one or more bits are from a network address included in the packet.

3. The system of claim 2 wherein the lookup handler is configured to determine the value based upon 26^th and 27^th bits of the network address.

4. The system of claim 2 wherein the lookup handler is configured to determine the value based upon 28^th, 27^th, and 26^th bits of the network address.

5. The system of claim 2 wherein the lookup handler is configured to determine the value based upon 28^th bit of the network address.

6. The system of claim 2 wherein the network address is a destination address of the packet.

7. The system of claim 1 wherein:

the one or more bits comprise a plurality of bits; and

the lookup handler is configured to determine the value by performing an operation on the plurality of bits.

8. The system of claim 7 wherein the operation is an exclusive OR (XOR) operation.

9. The system of claim 1 wherein the lookup handler is configured to:

use the value to determine data stored in a decision table; and

use the data from the decision table to select one of the first portion and the second portion.

10. The system of claim 1 wherein the memory is an N-bit memory and the first portion corresponds to upper N/2 bits portion of the memory and the second portion corresponds to lower N/2 bits portion of the memory.

11. The system of claim 1 wherein the memory is a content addressable memory (CAM).

12. The system of claim 1 further comprising a forwarding component configured to forward the packet using information obtained from accessing the selected portion of the memory.

13. A method comprising:

determining, by a network device, a value based upon one or more bits of a packet received by the network device;

selecting, based upon the determined value, one of a first portion and a second portion of a memory in the network device to be used for the packet; and

causing the selected portion of the memory determined to be accessed for processing the packet.

14. The method of claim 13 wherein the one or more bits are from a network address included in the packet.

15. The method of claim 14 wherein determining the value comprises determining the value using 26^th and 27^th bits of the network address.

16. The method of claim 14 wherein determining the value comprises determining the value using 28^th, 27^th, and 26^th bits of the network address.

17. The method of claim 14 wherein determining the value comprises determining the value using the 28^th bit of the network address.

18. The method of claim 14 wherein the network address is a destination address of the packet.

19. The method of claim 13 wherein:

the one or more bits comprise a plurality of bits; and

determining the value comprises determining the value by performing an operation on the plurality of bits.

20. The method of claim 19 wherein the operation is an exclusive OR (XOR) operation.

21. The method of claim 13 wherein selecting one of the first portion and the second portion comprises:

using the value to determine data stored in a decision table; and

using the data from the decision table to select one of the first portion and the second portion.

22. The method of claim 13 wherein the memory is an N-bit memory and the first portion corresponds to upper N/2 bits portion of the memory and the second portion corresponds to lower N/2 bits portion of the memory.

23. The method of claim 13 wherein the memory is a content addressable memory (CAM).

24. The method of claim 13 further comprising forwarding the packet using forwarding information obtained from accessing the selected portion of the memory.

25. A network device comprising:

a content-addressable memory (CAM) comprising a first side and a second side; and

one or more components configured to;

determine whether to use the first side or the second side based upon contents of a packet received by the network device;

obtain forwarding information for the packet using the side of the CAM determined to be used; and

forward the packet using the forwarding information.