Classifying data packets processed by drivers included in a stack

• US 6,185,568 B1
• Filed: 06/15/1999
• Issued: 02/06/2001
• Est. Priority Date: 09/19/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Bernet, Yoram, Bar, Ofer
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US09/333,797
• Time in Patent Office: 602 Days
• Field of Search: 707/2-6, 707/10, 709/230-237, 709/301
• US Class Current: 707/770
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and computer program product for classifying data being processed by drivers included in a stack. The computer program product is a centralized packet classifier that receives classification requests from drivers or other clients according to a defined interface. This reduces the cost for producing a driver since less code is required initially at development time as well as a corresponding reduction in maintenance costs. The present invention groups drivers or other clients that utilize a certain body of classification information into classification families. Further, reference patterns used to make classifications are stored in separate databases depending on whether they are specific or general. There exists a single specific pattern database for all specific reference patterns regardless of classification family having a constant search time and a general pattern database for each general reference pattern for each classification family defined to the system whose search time may vary according to the amount of information contained therein. When servicing a classification request, the packet classifier will first search the specific pattern database followed by a search in the appropriate general pattern database if necessary.

Claims

1. A method for classifying data packets processed by a plurality of drivers included in a stack comprising the steps of:

storing, in a shared reference pattern database shared by multiple drivers, at least one reference pattern and corresponding classification information, the shared reference pattern database containing a specific database for all specific reference patterns regardless of classification family and, for each classification family, a general database for general reference patterns pertaining to that classification family;

searching the shared reference pattern database for a reference pattern that matches a classification pattern created from a data packet by searching first the specific database for the classification pattern followed, if necessary, by searching the general database pertaining to the classification family for the classification pattern; and

if the classification pattern matches a stored reference pattern, processing the data packet using the classification information corresponding to the matched reference pattern.

2. A method as recited in claim 1 wherein the specific database comprises a classification block structure that has references to different classification information for a given specific pattern depending on classification family and the storing step for a specific reference pattern stored for one classification family further comprises the steps of:

searching the general databases for each other classification family for a general reference pattern that matches the specific reference pattern stored; and

for each match, making a reference in the classification block for the particular classification family that references the classification information of the matched general reference pattern so that future classification patterns presented that match the specific reference pattern in other classification families will match in the specific database search without resorting to the general database thereby increasing search efficiency.

3. A method as recited in claim 1 wherein the specific database comprises a classification block structure that has references to different classification information for a given specific pattern depending on classification family and the storing step for a specific reference pattern stored for one classification family further comprises the steps of:

searching the specific database for each existing specific pattern that matches the general reference pattern installed; and

for each match, if the reference for the particular classification family corresponding to the new general reference pattern installed is null, making a reference in the classification block for the particular classification family that references the classification information of the installed general reference pattern so that future classification patterns presented that match the specific reference pattern in the classification family will match in the specific database search without resorting to the general database thereby increasing search efficiency.

4. A method as recited in claim 1 wherein the specific database comprises a classification block structure that has references to different classification information for a given specific pattern depending on classification family and the storing step for a specific reference pattern stored for one classification family further comprises the steps of:

searching the specific database for each existing specific pattern that matches the general reference pattern installed; and

for each match having a reference for the particular classification family corresponding to the new general reference pattern in the classification block structure, searching the general database of the classification family for the installed general reference pattern for the best general reference pattern matching this specific pattern and making a reference in the classification block for the particular classification family that references the classification information of the best matched general reference pattern so that future classification patterns presented that match the specific reference pattern in the classification family will match in the specific database search without resorting to the general database thereby increasing search efficiency.

5. A method as recited in claim 1 wherein the storing step for a general reference pattern further comprises the steps of:

generating the entire set of specific reference patterns corresponding to the general reference pattern; and

storing each specific reference pattern of the set of specific reference patterns into the specific database referencing the classification information provided with the general reference pattern.

6. A method as recited in claim 1 wherein each classification pattern searched is automatically stored as a specific pattern in the specific database in order to increase classification efficiency.

7. A method as recited in claim 1 wherein each classification pattern searched is automatically stored as a specific pattern in the specific database and further removed after a period of time has passed with no classifications made thereto in order to increase future classification efficiency.

8. A method for classifying data packets processed by a plurality of drivers included in a stack comprising the steps of:

installing, by a software component, at least one reference pattern and associated classification information into a means for packet classification containing a common database for storing reference patterns and corresponding classification information;

presenting, to the means for packet classification, a classification pattern from a data packet to be classified by at least one portion of code outside the means for classification through a pre-defined interface; and

if the classification pattern matches an installed reference pattern, returning, to the at least one portion of code by the means for classification, access to the classification information associated with the reference pattern so that the data packet may be processed using the classification information.

9. A method as recited in claim 8 wherein access is given by returning a pointer to the classification information corresponding to the matched reference pattern.

10. A method as recited in claim 8 further comprising a classification family and wherein the at least one portion of code outside the means for classification comprises at least two separate portions of code that share a classification family.

11. A method as recited in claim 8 wherein the means for packet classification comprises a database for storing the installed reference patterns and a match is determined by searching the database for the classification pattern.

12. A method as recited in claim 8 wherein the installed reference patterns are either general or specific reference patterns and pertain to a classification family, the means for packet classification comprises a specific database for all specific reference patterns regardless of classification family and, for each classification family, a general database for general reference patterns pertaining to that classification family, and matching a classification pattern to an installed reference pattern comprises searching first the specific database for the classification pattern followed, if necessary, by searching the general database pertaining to the classification family for the classification pattern thereby increasing matching efficiency.

13. A method as recited in claim 12 wherein the specific database comprises a classification block structure that has references to different classification information for a given specific pattern depending on classification family and the installing step for a specific reference pattern installed for one classification family further comprises the steps of:

searching the general databases for each other classification family for a general reference pattern that matches the specific reference pattern installed; and

for each match, making a reference in the classification block for the particular classification family that references the classification information of the matched general reference pattern so that future classification patterns presented that match the specific reference pattern in other classification families will match in the specific database search without resorting to the general database thereby increasing search efficiency.

14. A method as recited in claim 12 wherein the specific database comprises a classification block structure that has references to different classification information for a given specific pattern depending on classification family and the installing step for a general reference pattern installed for one classification family further comprises the steps of:

searching the specific database for each existing specific pattern that matches the general reference pattern installed; and

for each match, if the reference for the particular classification family corresponding to the new general reference pattern installed is null, making a reference in the classification block for the particular classification family that references the classification information of the installed general reference pattern so that future classification patterns presented that match the specific reference pattern in the classification family will match in the specific database search without resorting to the general database thereby increasing search efficiency.

15. A method as recited in claim 12 wherein the specific database comprises a classification block structure that has references to different classification information for a given specific pattern depending on classification family and the installing step for a general reference pattern installed for one classification family further comprises the steps of:

searching the specific database for each existing specific pattern that matches the general reference pattern installed; and

for each match having a reference for the particular classification family corresponding to the new general reference pattern in the classification block structure, searching the general database of the classification family for the installed general reference pattern for the best general reference pattern matching this specific pattern and making a reference in the classification block for the particular classification family that references the classification information of the best matched general reference pattern so that future classification patterns presented that match the specific reference pattern in the classification family will match in the specific database search without resorting to the general database thereby increasing search efficiency.

16. A method as recited in claim 12 wherein the installing step for a general reference pattern further comprises the steps of:

generating the entire set of specific reference patterns corresponding to the general reference pattern; and

installing each specific reference pattern of the set of specific reference patterns into the specific database referencing the classification information provided with the general reference pattern.

17. A method as recited in claim 12 wherein each classification pattern presented to the means for packet classification is automatically installed as a specific pattern into the specific database.

18. A method as recited in claim 12 wherein each classification pattern presented to the means for packet classification is automatically installed as a specific pattern into the specific database and further de-installed after a period of time has passed with no classifications made thereto.

19. A method for classifying data packets processed by a plurality of drivers included in a stack comprising the steps of:

installing, by a software component, at least one reference pattern and associated classification information organized into a means for packet classification, the at least one reference pattern and associated classification information organized into classification families and the means for packet classification containing;

a database for each classification family for storing general reference patterns and corresponding classification information; and

a common constant time database for storing specific reference patterns and corresponding classification information regardless of classification family;

presenting, to the means for classification, a classification pattern from a data packet to be classified by a driver through a pre-defined interface; and

if the classification pattern matches an installed reference pattern, returning, to the driver, access to the classification information associated with the reference pattern so that the data packet may be processed using the classification information.

20. A computer-readable medium having computer-executable program code means embodied in said medium for classifying data packets processed by a plurality of drivers in a stack based on a classification pattern from a particular data packet, said computer readable program code means comprising:

an interface means for interfacing with other portions of code and receiving requests for installation of a reference pattern and a corresponding classification information in a classification family, receiving requests for classification of a classification pattern from a packet to be classified, and returning an access means to classification information;

a general database means for storing general reference patterns and associated classification information upon receipt by the interface means of an installation request for each classification family;

a constant search time database means for storing specific reference patterns and associated classification information upon receipt by the interface means of an installation request without regard to classification family; and

a matching means for comparing a classification pattern received by the interface means to the reference patterns stored in both database means based on a classification request, and if a matching reference pattern is found, returning access to the classification information corresponding to the matched reference pattern through the interface means to allow the data packet to be processed using the classification information.

21. A method for classifying data packets processed by one or more drivers included in a stack comprising the acts of:

storing in a shared reference pattern database shared by multiple drivers, at least one reference pattern and corresponding classification information, the shared reference pattern database containing a specific database for all specific reference patterns regardless of classification family and, for each classification family, a general database for general reference patterns pertaining to that classification family;

receiving a classification pattern from a first driver;

searching the shared reference pattern database for a reference pattern matching the classification pattern by searching first the specific database for the classification pattern followed, if necessary, by searching the general database pertaining to an identified classification family for the classification pattern; and

if a matching reference pattern is found;

returning, to the first driver, a classification handle to classification information associated with the matched reference pattern; and

processing the data packet using specific classification information from the matched reference pattern that corresponds to the identified classification family.

22. A method as recited in claim 21 further comprising the act of, in place of conducting a subsequent search, using the classification handle to access the classification information associated with the matched reference pattern.

23. A method as recited in claim 22 wherein the classification information associated with the matched reference pattern has been altered in some way.

24. A method as recited in claim 23 wherein a classification family corresponding to the matched reference pattern is added.

25. A method as recited in claim 23 wherein a classification family corresponding to the matched reference pattern is deleted.

26. A method as recited in claim 23 wherein specific classification information within one or more classification families is altered in some way.

27. A method as recited in claim 22 wherein the classification handle is used within the first driver to access the classification information associated with the matched reference pattern.

28. A method as recited in claim 22 further comprising the acts of:

passing the classification handle to a second driver; and

using the classification handle within the second driver to access the classification information associated with the matched reference pattern.