System and method for dynamically constructing packet classification rules

• US 20030123452A1
• Filed: 12/27/2001
• Published: 07/03/2003
• Est. Priority Date: 12/27/2001
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: TippingPoint Technologies, Inc. (Open Text Corporation)
• Inventors: Dempsey, Joseph F. III, Smith, Brian C., Tomlinson, Alexander I., Cox, Dennis J., Egbert, Stephen, Ahnstedt, Terry G., Laswell, Matthew C., Strentzsch, Scott
• Granted Patent: US 7,239,639 B2
• Time in Patent Office: Days
• 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, the service applying classifications that use arbitrary combinations of extracted packet header information, the system 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, the first match value determining a classification for the packet.

2. The system of claim 1 further comprising a data structure modifier operable to dynamically update the tree 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 classifying 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.

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 classifying 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 classifications, each classification associated with one or more packet field values.

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.