Packet classification using hash key signatures generated from interrupted hash function

• US 6,925,085 B1
• Filed: 06/07/2000
• Issued: 08/02/2005
• Est. Priority Date: 06/07/2000
• Status: Active Grant

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Krishna, Gopal S., Egbert, Chandan, Viswanath, Somnath
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/588,295
• Time in Patent Office: 1,882 Days
• Field of Search: 711/216, 370/389, 370/401, 370/392, 370/465, 370/475, 370/395.32
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

A network switch, configured for performing layer 2 and layer 3 switching in an Ethernet (IEEE 802.3) network without blocking of incoming data packets, includes network switch ports, each including a packet classifier module configured for generating a packet signature based on information within a received data packet and hash action values specified within a user-programmable template. In particular, the network switch stores a plurality of user-programmable templates, each configured for identifying a corresponding class of data packet. Each user-programmable template includes hash action values specifying initiation and termination of a hash function based on a byte offset of a received data packet. The packet classifier module includes a hash generator configured for generating hash values for selected bytes of the received data packet, and a template translator configured for controlling the hash generator for hashing the selected bytes of the received data packet based on the hash action values specified by a corresponding user-programmable template. Hence, a unique hash signature can be generated by supplying a data frame having a prescribed data values at the selected bytes of the user-programmable template; the hash signature can then be stored for comparison with incoming data packets during network switching operations. Hence, data packets can be classified at the wire rate by performing a hash-based search of selected bytes of the received data packet.

Claims

1. A method in an integrated network switch, the method comprising:

receiving a data packet on one of a plurality of network switch ports of the integrated network switch; and

generating a packet signature, by the one network switch port, of the received data packet by hashing selected portions of the received data packet based on prescribed hash action values of a user-programmable template.

2. The method of claim 1, wherein the network switch includes a hash generator, the generating step including:

hashing the selected portions based on a first group of the hash action values specifying initiating the hash generator at a beginning of the selected portions, respectively; and

halting the hash generator based on a second group of the hash action values specifying halting the hash generator at an end of the selected portions, respectively.

3. The method of claim 2, wherein the selected portions of the received data packet have prescribed data values matching the user-programmable template, the method further including storing the packet signature of the data packet in a memory for the corresponding user-programmable template.

4. The method of claim 3, further comprising:

receiving a second data packet on the one network switch port;

generating the packet signature for the second data packet by the one network switch port; and

comparing the packet signature for the second data packet with the stored packet signature for classification of the second data packet relative to the user-programmable template.

5. The method of claim 4, wherein the comparing step includes simultaneously comparing the packet signature for the second data packet with a plurality of the stored packet signatures for classification of the second data packet relative to a plurality of the user-programmable templates, respectively.

6. The method of claim 5, wherein each of the network switch ports include a packet classifier module having the hash generator, the step of simultaneously comparing the packet signature for the second data packet with a plurality of the stored packet signatures being performed in the corresponding packet classifier module of the one network switch port having received the second data packet.

7. The method of claim 1, further comprising simultaneously comparing the packet signature with a plurality of stored packet signatures for classification of the data packet relative to a plurality of the user-programmable templates, respectively.

8. The method of claim 1, wherein the selected portions of the received data packet have prescribed data values matching the user-programmable template, the method further including storing the packet signature of the data packet in a memory for the corresponding user-programmable template.

9. The method of claim 8, further comprising:

receiving a second data packet on the one network switch port;

generating the packet signature for the second data packet by the one network switch port; and

comparing the packet signature for the second data packet with the stored packet signature for classification of the second data packet relative to the user-programmable template.

10. The method of claim 9, wherein the comparing step includes simultaneously comparing the packet signature for the second data packet with a plurality of the stored packet signatures for classification of the second data packet relative to a plurality of the user-programmable templates, respectively.

11. The method of claim 1, wherein the user-programmable template includes a plurality of hash action values, the generating step including:

initiating hashing of a first of the selected portions based on a first of the hash action values specifying starting hashing at a prescribed beginning of the first of the selected portions; and

halting hashing for the first of the selected portions based on a second of the hash action values specifying halting hashing at a prescribed end of the first of the selected portions.

15. The method of claim 1, wherein the network switch is implemented on a single chip, the steps of receiving and generating being performed in the single chip.

12. A network switch comprising:

a table configured for storing user-programmable templates, each user-programmable template including hash action values that specify selected portions of a received data packet to be hashed for generation of a packet signature;

a hash generator configured for hashing the selected portions of received data packet based on the hash action values to generate the packet signature for the received data packet; and

a comparator configured for comparing the packet signature of the received data packet with at least one stored packet signature for classifying the received data packet relative to the corresponding user-programmable template and prescribed user-defined switching policies,

wherein the network switch includes a plurality of network switch ports each including the hash generator and comparator.

13. The switch of claim 12, further comprising a template controller configured for storing the packet signature of the received data packet for the corresponding user-programmable template as one of the prescribed user-defined switching policies in response to a store signal.

14. The switch of claim 12, wherein each hash action values specifies a location offset relative to a beginning of the received data packet, and one of an initiate hash action specifying initiation of hashing by the hash generator at the corresponding location offset and a halt hash action specifying halting of hashing by the hash generator at the corresponding location offset.