METHOD AND APPARATUS FOR PACKET SWITICHING

• US 20120246400A1
• Filed: 12/12/2011
• Published: 09/27/2012
• Est. Priority Date: 03/22/2011
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Bhadra, Sandeep, Bosshart, Patrick W., Kim, Hun-Seok, Kokrady, Aman A.
• Granted Patent: US 8,874,876 B2
• Time in Patent Office: Days
• US Class Current: 711/104
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/356 for storage area networks

Abstract

A method for performing packet lookups is provided. Packets (which each have a body and a header) are received and parsed to parsing headers. A hash function is applied to each header, and each hashed header is compared with a plurality of binary rules stored within a primary table, where each binary rule is a binary version of at least one ternary rule from a first set of ternary rules. For each match failure with the plurality of rules, a secondary table is searched using the header associated with each match failure, where the secondary table includes a second set of ternary rules.

Claims

1. An apparatus comprising:

a lookup memory having a primary table and a secondary table, wherein the secondary table includes a first set of ternary rules, and wherein the primary includes a set of binary rule, and wherein each binary rule is a binary version of at least one ternary rule from a second set of ternary rules; and

a search engine that is coupled to the lookup memory, wherein the search engine includes;

an controller that is configured to receive data words; and

hash logic that is coupled to lookup memory and the controller, wherein the hash logic is configured to perform a binary search of the primary table to determine whether each data word matches at least one of the binary rules, and wherein, if there is a failed match by hash logic and primary table, the search engine is configured to perform a ternary search of the secondary table to determine whether the data word associated with the failed match matches at least one of the ternary rules from the first set of ternary rules.

2. The apparatus of claim 1, wherein the primary table further comprises:

a dynamic memory; and

stash.

3. The apparatus of claim 2, wherein the stash is a content-addressable memory (CAM).

4. The apparatus of claim 4, wherein the dynamic memory is a static random access memory (SRAM).

5. The apparatus of claim 4, wherein the secondary table further comprises a Ternary CAM (TCAM).

6. The apparatus of claim 4, wherein the apparatus further comprises:

a shared memory;

a plurality of port managers, wherein each port manager includes;

an communication circuitry that is configured to receive input data packets and that is coupled to the shared memory and the search engine; and

a parser that is coupled to the communication circuitry, wherein the parser is configured to parse each input data packet and extract its header, wherein each data word is associated with at least one header.

7. The apparatus of claim 6, wherein the apparatus further comprises an action table that is in communication with the search engine.

8. The apparatus of claim 7, wherein the communication circuitry further comprises:

a media access controller (MAC) that is coupled to the parser;

a transmit pipeline that is coupled between the shared memory and the MAC;

a receive pipeline that is coupled between the shared memory and the MAC; and

a search interface that is coupled between the parser and the search engine.

9. The apparatus of claim 8, wherein the hash logic applies a keyed hash function to each data word.

10. A method comprising:

receiving a plurality of packets, wherein each packet has a body and a header;

parsing each packet to extract its header;

applying a hash function to each header;

comparing each hashed header with a plurality of binary rules stored within a primary table, wherein each binary rule is a binary version of at least one ternary rule from a first set of ternary rules; and

for each match failure with the plurality of rules, searching a secondary table using the header associated with each match failure, wherein the secondary table includes a second set of ternary rules.

11. The apparatus of claim 10, wherein the primary table further comprises:

an SRAM; and

a CAM.

12. The method of claim 11, wherein the secondary table is a TCAM.

13. The method of claim 12, wherein the step of searching the secondary table further comprises simultaneously searching a plurality of banks within the TCAM.

14. The method of claim 11, wherein the method further comprises:

generating a new rule and a new action for each match failure; and

storing the new rule and new action in the SRAM.

15. The method of claim 14, wherein the hash function is a keyed hash function.

16. An apparatus comprising:

a primary table including a set of binary rule, and wherein each binary rule is a binary version of at least one ternary rule from a first set of ternary rules;

a secondary table including a first set of ternary rules;

a switching circuit having;

a shared memory;

a search engine including;

an controller that is configured to receive data words; and

hash logic that is coupled to lookup memory and the controller, wherein the hash logic is configured to perform a binary search of the primary table to determine whether each data word matches at least one of the binary rules, and wherein, if there is a failed match by hash logic and primary table, the search engine is configured to perform a ternary search of the secondary table to determine whether the data word associated with the failed match matches at least one of the ternary rules from the first set of ternary rules; and

a plurality of port managers that are each in communication with the search engine; and

input/output (I/O) circuit that is in communication with the switching circuit.

17. The apparatus of claim 16, wherein the primary table further comprises:

an SRAM; and

a CAM.

18. The apparatus of claim 17, wherein each port manager further comprises:

a MAC that is coupled to the I/O circuitry so as to receive input data packets;

a transmit pipeline that is coupled between the shared memory and the MAC;

a receive pipeline that is coupled between the shared memory and the MAC;

a parser that is coupled to the receive pipeline, wherein the parser is configured to parse each input data packet and extract its header, wherein each data word is associated with at least one header; and

a search interface that is coupled between the parser and the search engine.

19. The apparatus of claim 18, wherein the I/O circuitry further comprises:

a plurality of physical layer (PHY) circuits, wherein each PHY circuit is in communication with the switching circuit; and

a plurality of ports, wherein each port is in communication with at least one of the PHY circuits.

20. The apparatus of claim 19, wherein the secondary table further comprises a TCAM.