Network data packet classification and demultiplexing

• US 7,200,684 B1
• Filed: 04/13/2000
• Issued: 04/03/2007
• Est. Priority Date: 04/13/2000
• Status: Expired due to Term

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Schales, Douglas Lee, Seshan, Srinivasan, Zohar, Miriam
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): JACOBS, LASHONDA T
• Application Number:
  US09/548,141
• Time in Patent Office: 2,546 Days
• Field of Search: 709/223, 709/201, 709/238, 709/200, 709/224, 709/225, 709/232, 709/252, 370/381, 370/389, 370/400, 370/401
• US Class Current: 709/252
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04Q 11/04 for time-division multiplexing H04Q11/0001 takes precedence
• CPC Class Codes: H04Q 2213/1305 Software aspects
• CPC Class Codes: H04Q 2213/13296 Packet switching, X.25, frame relay
• CPC Class Codes: H04Q 2213/13343 Neural networks

Abstract

The present invention provides methods and apparatus for classifying and demultiplexing packets in a network protocol stack. It provides extendibility for packet processing in the network protocol stack by defining a standard method for adding new functionality. It provides a method to obtain external information, from an application scheduled outside of the forwarding or interrupt context of the kernel, in order to augment packet classification and/or augment packet disposition. In some embodiments, external information augments a criteria of a node in a classification tree with additional information. It presents a way of augmenting which suspends the classification process until an application, scheduled outside of the forwarding or interrupt context of the kernel, completes. The resulting external information is used to augment the packet classification. In some embodiments of the method, the external information includes authentication of an originator of the packet by correlating a tunnel id with a userid, and/or using s/ident for out of band authentication. The classification process enables enforcement of a site policy.

Claims

1. A method for classifying a data packet, the method comprising:

receiving the data packet at a root node of a classification tree;

successively passing the data packet to each child of a first tree level until a first child of the first tree level of the classification tree indicates a satisfaction of a node-criteria packet matching function of said first child and the first child forming said data packet into a matched packet; and

repeating the step of passing and forming for a next tree level until no first child of said next level at a succeeding next level indicates satisfaction of the node-criteria packet matching function of said first child of said next level.

2. A method as recited in claim 1, wherein the step of passing includes executing a set of code which returns a status indication.

3. A method as recited in claim 2, wherein the status indication is of the pm_t type.

4. A method as recited in claim 1, wherein the step of forming includes the first child specifying a set of code to be run subsequently.

5. A method as recited in claim 4, wherein the step of specifying includes specifying the set of code to be run following satisfaction.

6. A method as recited in claim 1, further comprising dynamically adding at least one node in at least one level of the classification tree.

7. A method as recited in claim 6, wherein said at least one new child node is a Real Audio node.

8. A method as recited in claim 1, further comprising the step of parsing said matched packet and generating relevant information.

9. A method as recited in claim 1, further comprising the step of transforming said matched packet into a transformed packet.

10. A method as recited in claim 1, further comprising associating the packet with a last first child indicating satisfaction.

11. A method as recited in claim 10, further comprising executing a set of code in accordance with said last first child.

12. A method as recited in claim 1, further comprising determining a disposition of the data packet.

13. A method as recited in claim 12, further comprising employing the classification process as a firewall.

14. A method as recited in claim 1, further comprising employing the classification process for dynamic application level classification.

15. A method as recited in claim 14, further comprising employing the classification process for policy enforcement.

16. A method as recited in claim 14, further comprising employing the classification process for rate limiting.

17. A method as recited in claim 14, further comprising employing the classification process for load balancing.

18. A method as recited in claim 1, further comprising employing the classification process to shape traffic.

24. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing classification of a data packet, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

25. An article of manufacture as recited in claim 24, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect dynamically adding at least one node in at least one level of the classification tree.

19. An apparatus to classify a data packet, the apparatus comprising:

a network interface device to receive the data packet from the physical network and pass the data packet to the root node of a classification tree, and the reverse, to receive the data packet from the root node and send the data packet to the physical network;

a packet module to successively pass the packet from child node to child node at a next tree level until a first child node of the next tree level of the classification tree which indicates a satisfaction of a node-criteria of the first child node, and to form the data packet into a matched packet until no first child node of at a succeeding next level indicates satisfaction of the first node-criteria of the first child node of the succeeding next level.

20. An apparatus as recited in claim 19, wherein a portion of the apparatus is implemented as an accelerator chip.

21. An apparatus as recited in claim 19, wherein the apparatus is employed for application level classification.

22. An apparatus as recited in claim 19, wherein the apparatus is employed as a firewall.

23. An apparatus as recited in claim 19, wherein the apparatus is employed as a border server.

26. An apparatus for classifying a data packet, the apparatus comprising:

means for receiving the data packet at a root node of a classification tree;

means for successively passing the data packet to each child of a first tree level until a first child node of the first tree level of the classification tree indicates a satisfaction of a node-criteria of said first child node, and the first child node forming said data packet into a matched packet; and

means for repeating the steps of passing and forming for a next tree level until no first child node of said next tree level at a succeeding next level indicates satisfaction of the node-criteria of said first child node of said succeeding next level.