Method and apparatus for a packet classifier

• US 20030081615A1
• Filed: 10/16/2002
• Published: 05/01/2003
• Est. Priority Date: 10/22/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Kohn, Leslie D., Wong, Michael K.
• Granted Patent: US 7,248,585 B2
• Time in Patent Office: Days
• US Class Current: 370/395.42
• CPC Class Codes: G06F 1/3203 Power management, i.e. event-based initiation of a power-saving mode
• CPC Class Codes: G06F 1/3225 of memory devices
• CPC Class Codes: G06F 1/3275 Power saving in memory, e.g. RAM, cache
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 13/1689 Synchronisation and timing concerns synchronisation on a memory bus G06F13/4234
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 3/1423 controlling a plurality of local displays, e.g. CRT and flat panel display
• CPC Class Codes: G06F 9/30007 to perform operations on data operands
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: G06F 9/3891 organised in groups of units sharing resources, e.g. clusters
• CPC Class Codes: G09G 2352/00 Parallel handling of streams of display data
• CPC Class Codes: G09G 2360/121 using a cache memory
• CPC Class Codes: G09G 2370/022 Centralised management of display operation, e.g. in a server instead of locally
• CPC Class Codes: G09G 2370/20 Details of the management of multiple sources of image data
• CPC Class Codes: G11C 11/4074 Power supply or voltage generation circuits, e.g. bias voltage generators, substrate voltage generators, back-up power, power control circuits
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 : Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 : relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/9057 : Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 49/9089 : replacing packets in a storage arrangement, e.g. pushout
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

In one embodiment, a method for efficiently classifying packets for a multi-processor/mutli-thread environment is provided. The method initiates with receiving a packet. Then, header information is extracted form the received packet. Next, a first hash value is calculated. Then, a field of interest in a lookup table is determined from the first hash value. Next, a second hash value is calculated. Then, the second hash value is compared to stored hash values in the field of interest of the lookup table to determine a match between the second hash value and one of the values in the field of interest of the lookup table. If there is a match, the received packet is transmitted to a processor corresponding to the one of the values in the row location of the lookup table. A network interface card and a system for efficiently classifying packets in a multicore/multithread environment are also provided.

Claims

1. A method for efficiently classifying packets for a multi-processor/mutli-thread environment, comprising:

receiving a packet;

extracting header information from the received packet;

calculating a first hash value;

determining a field of interest in a lookup table from the first hash value;

calculating a second hash value;

comparing the second hash value to stored hash values in the field of interest of the lookup table to determine a match between the second hash value and one of the values in the field of interest of the lookup table; and

if there is a match, transmitting the received packet to a processor corresponding to the one of the values in the row location of the lookup table.

2. The method of claim 1, wherein the second hash value has a smaller bit size than the extracted header information.

3. The method of claim 1, wherein the field of interest is a row of the lookup table.

4. The method of claim 1, wherein the method operation of transmitting the received packet to a processor corresponding to the one of the values in the field of interest of the lookup table includes,

transmitting the received packet to a queue associated with the processor.

5. The method of claim 1, wherein the method operation of extracting header information from the received packet includes,

defining a key from fields of a header of the received packet.

6. The method of claim 5, wherein the fields are located in layers 2-4 of the packet header.

7. The method of claim 1, further including:

if there is not a match, performing a round robin operation to determine which processor to transmit the received packet to.

8. A method for performing optimistic hash matching, comprising:

defining a lookup table having a plurality of values stored therein, each of the plurality of values being associated with at least one processor;

receiving a packet;

extracting a key from the packet;

calculating a first hash value and a second hash value from the key;

identifying a field of interest within the lookup table corresponding to the first hash value;

comparing the second hash value to values within the field of interest to identify a match between the second hash value and one of the values within the field of interest; and

sending the received packet to a processor corresponding to the one of the values within the field of interest.

9. The method of claim 8, wherein the first and the second hash values are calculated through different hash algorithms.

10. The method of claim 9, wherein the plurality of values in the lookup table are the second hash value are derived through a common hash algorithm.

11. The method of claim 8, further including:

accessing code associated with the one of the values within the field of interest to determine an address of a processor assigned to the received packet.

12. The method of claim 8 wherein the method operation of sending the packet to a processor corresponding to the one of the values within the field of interest includes,

holding the packet in a queue associated with the processor.

13. The method of claim 8 further including:

if there is not a match between the second hash value and one of the values within the field of interest, performing a round robin operation to identify one of a plurality of processors to send the packet to.

14. A network interface card, comprising:

circuitry for receiving a packet;

packet classifier circuitry, the packet classifier circuitry configured to calculate a first hash value and a second hash value from fields of a packet header of the received packet, the first hash value indicating a field of interest associated with a lookup table in communication with the network interface card, the second hash value matching a value within the field of interest to identify a processor assigned to the packet; and

circuitry for transmitting the packet to a queue associated with the processor assigned to the packet.

15. The network interface card of claim 14, wherein the network interface card is on a multi-processor chip.

16. The network interface card of claim 15, wherein the multi-processor chip is contained within a server computer.

17. A system for efficiently classifying packets in a multicore/multithread environment, comprising:

a multi-processor chip in communication with the semiconductor chip capable of storing data, the multi-processor chip including,

a plurality of processor cores;

a network interface card (NIC) for receiving a packet from a network;

the NIC having packet classifier circuitry, the packet classifier circuitry configured to calculate a first hash value and a second hash value from a packet header of the packet, the first hash value indicating a field of interest in a table, the second hash value identifying data at a location in the field of interest, the data indicating one of the plurality of processor cores for the packet to be sent to; and

a semiconductor chip configured to store data associated with the table, the semiconductor chip in communication with the multi-processor chip.

18. The system of claim 17, wherein the table is stored in a fast cycle dynamic random access memory (FCDRAM).

19. The system of claim 17, wherein the system is a server computer.

20. The system of claim 17, further including:

a set of queues corresponding to the processor cores, such that one queue corresponds to one processor core.