Apparatus and method using a register scheme for efficient evaluation of equations in a network switch

• US 6,678,272 B1
• Filed: 05/24/2000
• Issued: 01/13/2004
• Est. Priority Date: 05/24/2000
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Tzeng, Shr-jie
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): WAHBA, ANDREW W
• Application Number:
  US09/577,321
• Time in Patent Office: 1,329 Days
• Field of Search: 370/389, 370/392, 370/400, 370/401, 370/402, 370/403, 370/404, 370/405, 370/406
• US Class Current: 370/392
• CPC Class Codes: H04L 49/604 Hybrid IP/Ethernet switches

Abstract

A network switch, configured for performing layer 2 and layer 3 switching in an Ethernet (IEEE 802.3) network includes a network switch port having a filter configured for evaluating an incoming data packet. The filter includes a min term memory configured for storing min term values. Each min term value is stored based on a location of a corresponding selected byte of the incoming data packet for comparison. Each min term is stored as a table entry having an expression portion specifying a corresponding comparison operation and a template identifier field that specifies templates that use the corresponding min term. The template identifier field includes an equation identifier. A min term generator is configured for simultaneously comparing a received byte of the incoming data packet with the min terms that correspond to the received byte and generates respective min term comparison results. An equation core is configured for evaluating equations and generates a frame tag identifying the incoming data packet based on the min term comparison results relative to the templates. The equation core is configured to identify equations which are no longer relevant. An equation reduction module includes a plurality of register arrays. Each register array includes equation identifiers corresponding to the corresponding byte. The equation reduction module includes logic configured to compare the equation identifiers of equations which are no longer relevant to equation identifiers in the register arrays and based on the comparison, to set vectors. A min term controller is configured to read the vectors and based thereon, to send necessary min terms to the min term generator.

Claims

1. A method of evaluating an incoming data packet at a network switch port, the method comprising:

storing a plurality of templates for equations configured for identifying respective data formats, each template having at least one min term configured for comparing a corresponding prescribed value to a corresponding selected byte of the incoming data packet,

simultaneously comparing, to the selected byte, min terms that correspond to the selected byte as the selected byte is received by the network switch port,

identifying an obsolete equation which needs no further evaluation based on a comparison of the min terms with the selected byte,

storing, in a register array corresponding with each byte, equation identifier information corresponding to min terms which are necessary to be compared with a corresponding byte,

comparing the equation identifier of the obsolete equation with the equation identifier information in each register array, and

based on the comparison, identifying equations which need no further evaluation.

2. The method of claim 1, wherein the simultaneously comparing step includes:

loading the min terms corresponding to a first of the data bytes into a min term generator;

comparing in parallel the min terms loaded in the min term generator with the first of the data bytes; and

outputting comparison results for the min terms loaded in the min term generator to an equation core, and wherein the step of identifying an obsolete equation occurs at the equation core and the equation core sends the equation identifier of the obsolete equation simultaneously to each register array.

3. The method of claim 1, further comprising:

generating a comparison result that identifies the incoming data packet, and

outputting a frame tag to a switch fabric configured for selectively switching the incoming data packet based on the corresponding frame tag.

4. The method according to claim 1, wherein the step of identifying equations which need no further evaluation includes setting an output vector which identifies equations which need no further evaluation as obsolete equations and identifies equations which require further evaluation as valid equations.

5. The method according to claim 4, further comprising:

reading the output vector, and

based on the output vector, performing the comparing step by comparing only necessary min terms.

6. The method according to claim 1, wherein the data packet has an Internet Protocol (IP) format.

7. The method according to claim 1, wherein the step of comparing the equation identifier of the obsolete equation includes using an exclusive OR gate.

8. A network switch port filter configured for evaluating an incoming data packet, comprising:

a min term memory configured for storing min term values, each min term value being stored based on a location of a corresponding selected byte of the incoming data packet for comparison, each min term being stored as a table entry having an expression portion specifying a corresponding comparison operation and a template identifier field that specifies templates that use the corresponding min term, the template identifier field including an equation identifier;

a min term generator configured for simultaneously comparing a received byte of the incoming data packet with the min terms that correspond to the received byte and generating respective min term comparison results;

an equation core configured for evaluating equations and generating a frame tag identifying the incoming data packet based on the min term comparison results relative to the templates, the equation core being configured to identify equations which are no longer relevant,

a equation reduction module including a plurality of register arrays, each register array including equation identifiers corresponding to the corresponding byte, the equation reduction module including logic configured to compare the equation identifiers of equations which are no longer relevant to equation identifiers in the register arrays and based on the comparison, to set output vectors, and

a min term controller configured to read the output vectors and based thereon, to send necessary min terms to the min term generator.

9. The filter according to claim 8, wherein the min term controller is configured for fetching the min terms from the min term memory corresponding to a selected byte of the IP frame within the incoming data packet.

10. The filter according to claim 8, wherein the logic includes exclusive OR gates.

11. The filter according to claim 8, wherein the vectors identify equations which need no further evaluation as obsolete equations and identifies equations which require further evaluation as valid equations using one bit.

12. The filter according to claim 8, further comprising a frame identifier configured for identifying a type of layer 2 packet, the selected byte of the incoming data packet is determined based on the identified type of layer 2 packet.

13. The filter according to claim 12, wherein the location of each stored min term value is relative to a beginning of an IP frame within the layer 2 packet.

14. The filter according to claim 12, wherein the equation core generates the frame tag at a wire rate of the incoming data packet and prior to an end of the incoming data packet.