System and method for optimizing router lookup

• US 8,730,961 B1
• Filed: 04/26/2004
• Issued: 05/20/2014
• Est. Priority Date: 04/26/2004
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Wong, Yuen Fai
• Primary Examiner(s): Zhou, Yong
• Application Number:
  US10/832,086
• Time in Patent Office: 3,676 Days
• Field of Search: 370/389, 370/238, 370/363, 370/392, 370/396, 370/419, 704/240
• US Class Current: 370/392
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

A system and method for reducing the number of cycles used in CAM lookup. A network comprises a plurality of network devices connected to a router. The router comprises a media access controller which is effective to receive an input packet and a packet processor which is effective to receive the input packet from the media access controller and to extract data stored in the input packet. The router further comprises a CAM which is effective to receive the data stored in the input packet from the packet processor, a PRAM, a control processor and a bus. The control processor controls the packet processor and the CAM so that the packet processor extracts a destination address from the input packet and forwards the destination address to the CAM. The packet processor extracts a source address from the input packet and forwards the source address to the CAM. The CAM performs a lookup of the destination and source addresses in parallel. The packet processor extracts miscellaneous information, a source protocol address, and a destination protocol address from the received packet and the CAM performs a lookup of the miscellaneous information, the source protocol address, and the destination protocol address at the same time.

Claims

1. A method of performing a lookup for a packet using a content-addressable memory (CAM), the method comprising:

storing first information extracted from the packet in a first set of bits of the CAM;

storing second information extracted from the packet in a second set of bits of the CAM, the second set of bits being contiguous to the first set of bits in the CAM; and

performing, in parallel in a single clock cycle, a first lookup of the first information stored in the first set of bits of the CAM in a first database of the CAM and a second lookup of the second information stored in the second set of bits of the CAM in a second database of the CAM, the second database being different from the first database,

wherein performing the first lookup comprises using the first set of bits and the second set of bits of the CAM and applying a mask to the second set of bits of the CAM, and

wherein performing the second lookup comprises using the first set of bits and the second set of bits of the CAM and applying a mask to the first set of bits of the CAM.

2. The method of claim 1 wherein the first information comprises Layer 3 information extracted from the packet.

3. The method of claim 1 wherein the second information comprises Layer 4 information extracted from the packet.

4. A network device comprising:

a processor configured to extract first information and second information from a packet and store the first information and the second information in contiguous sets of bits of a content-addressable memory (CAM); and

the CAM configured to perform, in parallel in a single clock cycle, a first lookup of the first information in a first database of the CAM and a second lookup of the second information in a second database of the CAM, the second database being different from the first database,

wherein the CAM is further configured, in performing the first lookup, to use the contiguous sets of bits of the CAM and apply a mask to a second set of bits of the contiguous sets of bits of the CAM, and

wherein the CAM is further configured, in performing the second lookup, to use the contiguous sets of bits of the CAM and apply a mask to a first set of bits of the contiguous sets of bits of the CAM.

5. The network device of claim 4 wherein the first information comprises Layer 3 information extracted from the packet.

6. The network device of claim 4 wherein the CAM comprises a register configured to store the first information in a first set of bits of the register and the second information in a second set of bits of the register, the second set of bits being contiguous to the first set of bits in the register.

7. The network device of claim 4 wherein the second information comprises Layer 4 information extracted from the packet.

8. An apparatus for processing a packet, the apparatus comprising:

means for extracting first information and second information from the packet;

means for storing the first information and the second information in contiguous sets of bits of a content-addressable memory (CAM); and

means for performing, in parallel in a single clock cycle, a first lookup of the first information in a first database of the CAM and a second lookup of the second information in a second database of the CAM, the second database being different from the first database,

wherein the means for performing the first lookup comprise means for using the contiguous sets of bits of the CAM and applying a mask to a second set of bits of the contiguous sets of bits of the CAM, and

wherein the means for performing the second lookup comprise means for using the contiguous sets of bits of the CAM and applying a mask to a first set of bits of the contiguous sets of bits of the CAM.

9. The apparatus of claim 8 wherein the first information is Layer 3 information extracted from the packet.

10. The apparatus of claim 8 wherein the CAM comprises a register configured to store the first information in a first set of bits of the register and the second information in a second set of bits of the register, the second set of bits being continuous to the first set of bits in the register.

11. The apparatus of claim 8 wherein the second information is Layer 4 information extracted from the packet.

12. A content-addressable memory (CAM) comprising:

a memory portion configured to store first information and second information extracted from a packet in contiguous sets of bits of the memory portion; and

multiple databases for performing lookups;

wherein the CAM is configured to perform, in parallel in a single clock cycle, a first lookup of the first information in a first database of the multiple databases and a second lookup of the second information in a second database of the multiple databases, the second database being different from the first database,

wherein the CAM is further configured, in performing the first lookup, to use the contiguous sets of bits of the memory portion and apply a mask to a second set of bits of the contiguous sets of bits of the memory portion, and

wherein the CAM is further configured, in performing the second lookup, to use the contiguous sets of bits of the memory portion and apply a mask to a first set of bits of the contiguous sets of bits of the memory portion.

13. The CAM of claim 12 wherein the first information comprises Layer 3 information extracted from the packet.

14. The CAM of claim 12 wherein the second information comprises Layer 4 information extracted from the packet.

15. A network device comprising:

a processor configured to extract a source information and a destination information from a packet and store the source information and the destination information in contiguous sets of bits of a content-addressable memory (CAM); and

the CAM configured to perform, in parallel in a single clock cycle, a first lookup of the source information in a first database of the CAM and a second lookup of the destination information in a second database of the CAM, the second database being different from the first database,

wherein the CAM is further configured, in performing the first lookup, to use the contiguous sets of bits of the CAM and apply a mask to a second set of bits of the contiguous sets of bits of the CAM, the second set of bits storing the destination information, and

wherein the CAM is further configured, in performing the second lookup, to use the contiguous sets of bits of the CAM and apply a mask to a first set of bits of the contiguous sets of bits of the CAM, the first set of bits storing the source information.