Methods systems and computer program products for processing an event based on policy rules using hashing

• US 6,820,121 B1
• Filed: 08/24/2000
• Issued: 11/16/2004
• Est. Priority Date: 08/24/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nguyen, Loan, Shannon, Diane Iupe, Yang, David Yu Pin, Callis, Gregory M., Franks, Jon Kevin, Huynh, Lap Thiet
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US09/645,651
• Time in Patent Office: 1,545 Days
• Field of Search: 709/225, 709/238, 709/228, 709/218, 709/250, 711/216, 711/221
• US Class Current: 709/225
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

Embodiments of the present invention include methods, systems and computer program products which provide for processing an event having a classification based on associated policy rules where the policy rules are conditioned on the classification. A policy rules hash table is provided including a plurality of policy rule entries, each policy rule entry being associated with a hash index. A hash index is generated using a classification hash length based on the classification of the event, the classification having an associated length at least equal to the classification hash length. A policy rule entry in the policy rules hash table is identified that corresponds to the generated hash index. It is determined if a classification field length associated with the identified policy rule corresponds to the classification hash length. The identified policy rule entry is executed if the hash length associated with the identified policy rule corresponds to the classification hash length.

Claims

1. A method for processing an event having a classification based on associated policy rules, the policy rules being conditioned on the classification, the method comprising the steps of:

providing a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

receiving the event;

generating a hash index using a classification hash length based on the classification of the event, the classification having an associated length at least equal to the classification hash length;

identifying a policy rule entry in the policy rules hash table that corresponds to the generated hash index;

determining if a classification field length associated with the identified policy rule corresponds to the classification hash length; and

executing the identified policy rule entry if the hash length associated with the identified policy rule corresponds to the classification hash length.

2. The method of claim 1 wherein the step of generating a hash index comprises the steps of:

providing a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths associated with at least one of the plurality of policy rule entries;

identifying from the provided list a classification hash length for the received event which is no greater than the associated length of the classification; and

generating the hash index using the identified classification hash length.

3. The method of claim 2 wherein the step of identifying from the provided list a classification hash length further comprises the steps of:

identifying from the provided list a classification hash length for the received event which is equal to the associated length of the classification of the received event if such a classification hash length is found in the provided list; and

selecting as the identified hash length a classification hash length which is found in the provided list as a classification hash length for the received event, the selected classification hash length being a largest length not greater than the associated length of the classification of the received event, if a classification hash length which is equal to the associated length of the classification of the received event is not found in the provided list.

4. The method of claim 1 wherein the identified policy rule entry has a plurality of associated conditions, the classification being one of the plurality of associated conditions, the method further comprising the step of determining if all of the plurality of associated conditions are met and wherein the step of executing the identified policy rule entry further comprises the step of executing the identified policy rule entry only if all of the plurality of associated conditions are met.

5. A method for processing an event having a classification based on associated policy rules, the policy rules being conditioned on the classification, the method comprising the steps of:

providing a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

receiving the event;

providing a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths found in at least one of the plurality of policy rule entries;

identifying from the provided list a classification hash length for the received event which is no greater than an associated length of the classification of the received event;

generating a hash index using the identified classification hash length;

identifying a policy rule entry in the policy rules hash table that corresponds to the generated hash index and that has an associated classification field length that corresponds to the classification hash length of the event;

determining if all conditions associated with the identified policy rule entry are met; and

executing the identified policy rule entry if all conditions associated with the identified policy rule entry are met.

6. The method of claim 5 wherein the step of identifying from the provided list a classification hash length further comprises the steps of:

identifying from the provided list a classification hash length for the received event which is equal to the associated length of the classification of the received event if such a classification hash length is found in the provided list; and

selecting as the identified hash length a classification hash length which is found in the provided list as a classification hash length for the received event, the selected classification hash length being a largest length not greater than the associated length of the classification of the received event, if a classification hash length which is equal to the associated length of the classification of the received event is not found in the provided list.

7. The method of claim 6 further comprising the steps of:

determining if another policy rule entry in the policy rules hash table corresponds to the generated hash index and has an associated classification field length that corresponds to the classification hash length of the event if a first policy rule entry in the policy rules hash table is identified that corresponds to the generated hash index and has an associated classification field length that does not correspond to the classification hash length of the event;

determining if all conditions associated with the another policy rule entry are met; and

executing the another policy rule entry if all conditions associated with the another policy rule entry are met.

8. The method of claim 7 further comprising the steps of:

determining if the identified policy rule entry includes a reference to an alternate policy rule entry in the policy rules hash table if all conditions associated with the identified policy rule entry are not met;

determining if all conditions associated with the alternate policy rule entry are met; and

executing the alternate policy rule entry if all conditions associated with the alternate policy rule entry are met.

9. The method of claim 8 further comprising the steps of:

selecting as the identified hash length a next lowest classification hash length which is found in the provided list as an alternate classification hash length for the received event, the selected next lowest classification hash length being a largest length not greater than the selected classification hash length, if all conditions associated with the identified policy rule entry are not met and if the identified policy rule entry does not include a reference to an alternate policy rule entry; and

generating the hash index using the next lowest classification entry.

10. A method for processing a Web request having an associated classification at a communication server based on associated policy rules, the policy rules being conditioned on the classification, the method comprising the steps of:

providing a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

receiving the Web request at the communication server;

providing a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths found in at least one of the plurality of policy rule entries;

identifying from the provided list a classification hash length for the received Web request which is no greater than an associated length of the classification of the received Web request;

generating a hash index using the identified classification hash length;

identifying a policy rule entry in the policy rules hash table that corresponds to the generated hash index and that has an associated classification field length that corresponds to the classification hash length of the Web request;

determining if all conditions associated with the identified policy rule entry are met; and

executing the identified policy rule entry to process the Web request if all conditions associated with the identified policy rule entry are met.

11. The method of claim 10 wherein the associated classification is a Universal Resource Indicator (URI) associated with the Web request.

12. A system for processing an event having a classification based on associated policy rules, the policy rules being conditioned on the classification, the system comprising:

a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

means for receiving the event;

means for generating a hash index using a classification hash length based on the classification of the event, the classification having an associated length at least equal to the classification hash length;

means for identifying a policy rule entry in the policy rules hash table that corresponds to the generated hash index;

means for determining if a classification field length associated with the identified policy rule corresponds to the classification hash length; and

means for executing the identified policy rule entry if the hash length associated with the identified policy rule corresponds to the classification hash length.

13. The system of claim 12 wherein the means for generating a hash index further comprises:

a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths associated with at least one of the plurality of policy rule entries;

means for identifying from the provided list a classification hash length for the received event which is no greater than the associated length of the classification; and

means for generating the hash index using the identified classification hash length.

14. The system of claim 13 wherein the means for identifying from the provided list a classification hash length further comprises:

means for identifying from the provided list a classification hash length for the received event which is equal to the associated length of the classification of the received event if such a classification hash length is found in the provided list; and

means for selecting as the identified hash length a classification hash length which is found in the provided list as a classification hash length for the received event, the selected classification hash length being a largest length not greater than the associated length of the classification of the received event, if a classification hash length which is equal to the associated length of the classification of the received event is not found in the provided list.

15. The system of claim 12 wherein the identified policy rule entry has a plurality of associated conditions, the classification being one of the plurality of associated conditions, the system further comprising:

means for determining if all of the plurality of associated conditions are met; and

wherein the means for executing the identified policy rule entry further comprises means for executing the identified policy rule entry only if all of the plurality of associated conditions are met.

16. A system for processing an event having a classification based on associated policy rules, the policy rules being conditioned on the classification, the system comprising:

a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths found in at least one of the plurality of policy rule entries;

means for identifying from the provided list a classification hash length for the event which is no greater than an associated length of the classification of the event;

means for generating a hash index using the identified classification hash length;

means for identifying a policy rule entry in the policy rules hash table that corresponds to the generated hash index and that has an associated classification field length that corresponds to the classification hash length of the event;

means for determining if all conditions associated with the identified policy rule entry are met; and

means for executing the identified policy rule entry if all conditions associated with the identified policy rule entry are met.

17. The system of claim 16 wherein the means for identifying from the provided list a classification hash length further comprises:

means for identifying from the provided list a classification hash length for the event which is equal to the associated length of the classification of the event if such a classification hash length is found in the provided list; and

means for selecting as the identified hash length a classification hash length which is found in the provided list as a classification hash length for the received event, the selected classification hash length being a largest length not greater than the associated length of the classification of the event, if a classification hash length which is equal to the associated length of the classification of the event is not found in the provided list.

18. The system of claim 17 further comprising:

means for determining if another policy rule entry in the policy rules hash table corresponds to the generated hash index and has an associated classification field length that corresponds to the classification hash length of the event if a first policy rule entry in the policy rules hash table is identified that corresponds to the generated hash index and has an associated classification field length that does not correspond to the classification hash length of the event;

means for determining if all conditions associated with the another policy rule entry are met; and

means for executing the another policy rule entry if all conditions associated with the another policy rule entry are met.

19. The system of claim 18 further comprising:

means for determining if the identified policy rule entry includes a reference to an alternate policy rule entry in the policy rules hash table if all conditions associated with the identified policy rule entry are not met;

means for determining if all conditions associated with the alternate policy rule entry are met; and

means for executing the alternate policy rule entry if all conditions associated with the alternate policy rule entry are met.

20. The system of claim 19 further comprising:

means for selecting as the identified hash length a next lowest classification hash length which is found in the provided list as an alternate classification hash length for the event, the selected next lowest classification hash length being a largest length not greater than the selected classification hash length, if all conditions associated with the identified policy rule entry are not met and if the identified policy rule entry does not include a reference to an alternate policy rule entry; and

means for generating the hash index using the next lowest classification entry.

21. A system for processing a Web request having an associated classification at a communication server based on associated policy rules, the policy rules being conditioned on the classification, the system comprising:

a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

means for receiving the Web request at the communication server;

a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths found in at least one of the plurality of policy rule entries;

means for identifying from the provided list a classification hash length for the received Web request which is no greater than an associated length of the classification of the received Web request;

means for generating a hash index using the identified classification hash length;

means for identifying a policy rule entry in the policy rules hash table that corresponds to the generated hash index and that has an associated classification field length that corresponds to the classification hash length of the Web request;

means for determining if all conditions associated with the identified policy rule entry are met; and

means for executing the identified policy rule entry to process the Web request if all conditions associated with the identified policy rule entry are met.

22. The system of claim 21 wherein the associated classification is a Universal Resource Indicator (URI) associated with the Web request.

23. A system for processing an event having a classification based on associated policy rules, the policy rules being conditioned on the classification, the system comprising:

a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

a hash index generator circuit that generates a hash index using a classification hash length based on the classification of the event, the classification having an associated length at least equal to the classification hash length;

a hash lookup circuit that identifies a policy rule entry in the policy rules hash table that corresponds to the generated hash index; and

a comparison circuit that determines if a classification field length associated with the identified policy rule corresponds to the classification hash length and executes the identified policy rule entry if the hash length associated with the identified policy rule corresponds to the classification hash length.

24. The system of claim 23 wherein the system is provided on a communication server of a computer network and wherein the event is a Web request received at the communication server.

25. The system of claim 24 wherein the associated classification is a Universal Resource Indicator (URI) associated with the Web request.

26. A computer program product for processing an event having a classification based on associated policy rules, the policy rules being conditioned on the classification, comprising:

a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising;

computer-readable program code which generates a hash index using a classification hash length based on the classification of the event, the classification having an associated length at least equal to the classification hash length;

computer-readable program code which identifies a policy rule entry that corresponds to the generated hash index in a policy rules hash table including a plurality of policy rule entries, each policy rule entry being associated with a hash index;

computer-readable program code which determines if a classification field length associated with the identified policy rule corresponds to the classification hash length; and

computer-readable program code which executes the identified policy rule entry if the hash length associated with the identified policy rule corresponds to the classification hash length.

27. The computer program product of claim 26 wherein the computer-readable program code which generates a hash index further comprises:

computer-readable program code which identifies a classification hash length for the event which is no greater than the associated length of the classification from a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths associated with at least one of the plurality of policy rule entries; and

computer-readable program code which generates the hash index using the identified classification hash length.

28. The computer program product of claim 27 wherein the computer-readable program code which identifies from the provided list a classification hash length further comprises:

computer-readable program code which identifies from the provided list a classification hash length for the received event which is equal to the associated length of the classification of the received event if such a classification hash length is found in the provided list; and

computer-readable program code which selects as the identified hash length a classification hash length which is found in the provided list as a classification hash length for the received event, the selected classification hash length being a largest length not greater than the associated length of the classification of the received event, if a classification hash length which is equal to the associated length of the classification of the received event is not found in the provided list.

29. The computer program product of claim 26 wherein the identified policy rule entry has a plurality of associated conditions, the classification being one of the plurality of associated conditions, the computer program product further comprising:

computer-readable program code which determines if all of the plurality of associated conditions are met; and

wherein the computer-readable program code which executes the identified policy rule entry further comprises computer-readable program which code executes the identified policy rule entry only if all of the plurality of associated conditions are met.

30. A computer program product for processing an event having a classification based on associated policy rules, the policy rules being conditioned on the classification, comprising:

a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising;

computer-readable program code which identifies from a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths found in at least one of the plurality of policy rule entries, the plurality of policy rule entries being included in a policy rules hash table, each policy rule entry being associated with a hash index, a classification hash length for the event which is no greater than an associated length of the classification of the event;

computer-readable program code which generates a hash index using the identified classification hash length;

computer-readable program code which identifies a policy rule entry in the policy rules hash table that corresponds to the generated hash index and that has an associated classification field length that corresponds to the classification hash length of the event;

computer-readable program code which determines if all conditions associated with the identified policy rule entry are met; and

computer-readable program code which executes the identified policy rule entry if all conditions associated with the identified policy rule entry are met.

31. The computer program product of claim 30 wherein the computer-readable program code which identifies from the provided list a classification hash length further comprises:

computer-readable program code which identifies from the provided list a classification hash length for the event which is equal to the associated length of the classification of the event if such a classification hash length is found in the provided list; and

computer-readable program code which selects as the identified hash length a classification hash length which is found in the provided list as a classification hash length for the received event, the selected classification hash length being a largest length not greater than the associated length of the classification of the event, if a classification hash length which is equal to the associated length of the classification of the event is not found in the provided list.

32. The computer program product of claim 31 further comprising:

computer-readable program code which determines if another policy rule entry in the policy rules hash table corresponds to the generated hash index and has an associated classification field length that corresponds to the classification hash length of the event if a first policy rule entry in the policy rules hash table is identified that corresponds to the generated hash index and has an associated classification field length that does not correspond to the classification hash length of the event;

computer-readable program code which determines if all conditions associated with the another policy rule entry are met; and

computer-readable program code which executes the another policy rule entry if all conditions associated with the another policy rule entry are met.

33. The computer program product of claim 32 further comprising:

computer-readable program code which determines if the identified policy rule entry includes a reference to an alternate policy rule entry in the policy rules hash table if all conditions associated with the identified policy rule entry are not met;

computer-readable program code which determines if all conditions associated with the alternate policy rule entry are met; and

computer-readable program code which executes the alternate policy rule entry if all conditions associated with the alternate policy rule entry are met.

34. The computer program product of claim 33 further comprising:

computer-readable program code which selects as the identified hash length a next lowest classification hash length which is found in the provided list as an alternate classification hash length for the event, the selected next lowest classification hash length being a largest length not greater than the selected classification hash length, if all conditions associated with the identified policy rule entry are not met and if the identified policy rule entry does not include a reference to an alternate policy rule entry; and

computer-readable program code which generates the hash index using the next lowest classification entry.

35. A computer program product for processing a Web request having an associated classification at a communication server based on associated policy rules, the policy rules being conditioned on the classification, comprising:

a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising;

computer-readable program code which identifies from a list identifying classification hash lengths to be used for generation of a hash index for a plurality of candidate classification lengths of the classification, the list having associated classification hash lengths corresponding to classification field lengths found in at least one of a plurality of policy rule entries included in a policy rules hash table, each policy rule entry being associated with a hash index, a classification hash length for the received Web request which is no greater than an associated length of the classification of a received Web request;

computer-readable program code which generates a hash index using the identified classification hash length;

computer-readable program code which identifies a policy rule entry in the policy rules hash table that corresponds to the generated hash index and that has an associated classification field length that corresponds to the classification hash length of the Web request;

computer-readable program code which determines if all conditions associated with the identified policy rule entry are met; and

computer-readable program code which executes the identified policy rule entry to process the Web request if all conditions associated with the identified policy rule entry are met.

36. The computer program product of claim 35 wherein the associated classification is a Universal Resource Indicator (URI) associated with the Web request.