System and method for dynamically constructing packet classification rules

• US 7,239,639 B2
• Filed: 12/27/2001
• Issued: 07/03/2007
• Est. Priority Date: 12/27/2001
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Cox, Dennis J., Dempsey, Joseph, Egbert, Stephen, Ahnstedt, Terry G., Laswell, Matthew C., Strentzsch, Scott, Smith, Brian C., Tomlinson, Alexander I.
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Boakye; Alexander O.
• Application Number:
  US10/034,435
• Publication Number:
  US 20030123452A1
• Time in Patent Office: 2,014 Days
• Field of Search: 370/395.43, 370/395.31, 370/395.52, 370/392, 370/389, 370/401, 370/397, 370/471, 370/349, 370/395.32, 370/412, 370/432, 709/238, 709/240
• US Class Current: 370/395.43
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• 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 69/22 Parsing or analysis of headers

Abstract

A system and method classifies packets with a programmably fixed network processor program and dynamically updated data structures. The network processor program selects predetermined packet field values of the packets transmitted across the network and classifies the packets by matching one or more packet field values with a data structure. New packet classifications are dynamically created by updating the data structure to associate one or more predetermined packet field values with the new packet classification. For instance, a parse tree program extracts packet header information and matches the packet header information to the data structure. A pattern tree data structure provides longest prefix matches and an ordered tree data structure provides combination matches so that classification of arbitrary Boolean combinations of extracted header fields can be formed.

Claims

1. A system for providing a service to a packet based network, comprising:

a processor having instructions to extract predetermined header information from a packet and further having instructions to perform table look-ups with the header information;

a first data structure that provides a longest match value for processor table look-ups;

a second data structure that provides a first match value for processor table look-ups of combinations of longest match values;

wherein said processor is further operable to use said longest match value and said first match value to determine a service for said packet.

2. The system of claim 1 further comprising a data structure modifier operable to dynamically update said first and second data structures to create a new packet classification.

3. The system of claim 2 wherein the new packet classification relies on the predetermined header information to avoid changes to the processor program.

4. The system of claim 1 wherein the first data structure comprises a pattern tree.

5. The system of claim 1 wherein the second data structure comprises a ordered virtual tree.

6. The system of claim 1 wherein the processor instructions comprise a parse tree that extracts header field values.

7. The system of claim 6 wherein the parse tree comprises plural nodes and plural branches, the nodes representing packet fields and the branches representing values for the packet fields.

8. The system of claim 6 wherein the leaf nodes of the parse tree comprise the table look-up instructions.

9. The system of claim 6 wherein the header field values comprise one or more of Internet Protocol source address and destination address.

10. The system of claim 6 wherein the header field values comprise one or more of Transfer Control Protocol source port and destination port.

11. The system of claim 1 wherein the processor comprises pattern processor.

12. The system of claim 11 further comprising a route/switch processor in communication with the pattern processor and operable to modify, shape and route the packet according to the classification.

13. A method for servicing packets transmitted across a network, the method comprising:

selecting predetermined packet field values from the packets;

classifying the packets by matching one or more packet field values with a data structure; and

dynamically creating a new packet classification by modifying the data structure to associate one or more of the predetermined packet field values with the new packet classification; and

selecting a service for said packet using said new packet classification.

14. The method of claim 13 wherein selecting predetermined packet field values comprises extracting packet field values from packet headers with a pattern processor having a program.

15. The method of claim 14 wherein dynamically creating a new packet classification further comprises modifying the data structure and leaving the pattern processor program fixed.

16. The method of claim 15 wherein the pattern processor program comprises a parse tree having plural nodes including a leaf node, the method further comprising:

calling a function at the leaf node, the function performing table look-ups from the data structures to determine a packet classification.

17. The method of claim 16 wherein performing table look-ups comprises:

looking up a longest match for packet header values; and

looking-up a first match for combinations of the longest match table look-up results.

18. The method of claim 13 wherein the data structure comprises an ordered virtual tree.

19. The method of claim 13 wherein the data structure comprises a pattern tree.

20. A system for servicing packets comprising:

a network processor having programmably fixed instructions that select values from predetermined packet fields;

a data structure that associates one or more packet field values with a classification; and

a data structure modifier interfaced with the data structure and operable to modify the data structure to define one or more modified classifications, each modified classification associated with one or more packet field values;

wherein said network processor is operable to use said modified classification to select a service for said packet.

21. The system of claim 20 wherein the programmably fixed instructions comprise a parse tree having plural nodes.

22. The system of claim 20 wherein the data structure comprises:

a pattern tree that determines a longest match for a packet field value; and

an ordered virtual tree that determines a first match for a combination of longest matches.