Rule engine

Abstract

A rule engine for a computer network traverses a rule mesh having path nodes and path edges in form of a tree part and a graph part. The rule engine evaluates data packets flowing through a network to determine rules matched for every packet. Subsequent packets having same expression values as an already checked packet are not rechecked against the same nodes in the rule mesh through the use of a session entry. The rule engine performs a search on every path node of rule mesh to determine the next path edge to traverse. A Tree-Id and Rule Confirmation Bitmap that are indicative of path traversed and rules matched by a packet are generated at the end of rule mesh traversal. These are appended in the packet extension for subsequent modules of Policy Agent.

1 . A system for evaluating a data packet against rules, the system comprising: 
 a. a rule mesh configured with the rules, the rule mesh being a combination of a tree data structure and a graph data structure; and    b. a policy agent, wherein the policy agent evaluates the data packet against the rules in the rule mesh.    
     
     
         2 . The system of  claim 1  further comprising a rule compiler, wherein the rule compiler generates the rule mesh.  
     
     
         3 . The system of  claim 1 , wherein the rule mesh comprises: 
 a. a path node table, wherein the path node table stores information regarding one or more tree nodes and one or more graph nodes of the rule mesh; and    b. a path edge table, wherein the path edge table stores information regarding one or more tree edges and one or more graph edges in the rule mesh.    
     
     
         4 . The system of  claim 3 , wherein each graph edge comprises: 
 a. a confirmation bitmap, the confirmation bitmap comprising bits, the bits representing the rules that are pending in the graph data structure, wherein a bit is set if taking a graph edge confirms a rule from the pending rules; and    b. an elimination bitmap, the elimination bitmap comprising bits, the bits representing the rules that are pending in the graph data structure, wherein a bit is set if taking a graph edge eliminates a rule from the pending rules.    
     
     
         5 . The system of  claim 1 , wherein the policy agent comprises: 
 a. a generic extension builder, wherein the generic extension builder processes the data packet header for obtaining information related to an Open System Interconnection (OSI) network model;    b. a session cache module, wherein the session cache module further processes the data packet header for obtaining information related to the OSI network model;    c. an application decode module, wherein the application decode module identifies information regarding an application, the application generating the data packet;    d. a rule engine module, wherein the rule engine module makes policy decisions based on the information related to the OSI network model and the information regarding the application; and    e. one or more policy entities, wherein each policy entity enforces one or more policies based on policy decisions.    
     
     
         6 . The system of  claim 5 , wherein the policy agent further comprises a policy manager, the policy manager comprising rules related to the one or more policies.  
     
     
         7 . The system of  claim 5 , wherein the rule engine module comprises: 
 a. a Rule Confirmation Bitmap (RCB), wherein the RCB indicates the rules matched in the graph data structure; and    b. a Graph Traversal Bitmap (GTB), wherein the GTB indicates conditions governing end of the traversal of the graph data structure.    
     
     
         8 . The system of  claim 5 , wherein each policy entity comprises: 
 a. a policy processing module, wherein the policy processing module enforces the one or more policies on the data packet.    
     
     
         9 . The system of  claim 8 , wherein the policy processing module comprises: 
 a. a rule lookup table, wherein the rule lookup table is indexed using an identity of the one or more tree data structures.    
     
     
         10 . A system for traversing a rule mesh for evaluating a data packet against rules, the rule mesh being a combination of a tree data structure and a graph data structure, the rules being configured in the rule mesh as comprising path nodes and path edges, the system comprising: 
 a. means for receiving the data packet;    b. means for determining a root path node for the data packet;    c. means for performing rule mesh traversal for the data packet, wherein the rule mesh traversal starts from the root path node; and    d. means for updating information in the data packet during the rule mesh traversal, wherein the information is data regarding the rules satisfied by the data packet.    
     
     
         11 . A computer program product for traversing a rule mesh for evaluating a data packet against rules, the rule mesh being a combination of a tree data structure and a graph data structure, the rules being configured in the rule mesh as nodes and path edges, the computer program product comprising a computer readable medium, the computer readable medium comprising: 
 a. computer executable instructions for receiving the data packet;    b. computer executable instructions for determining a root path node for the data packet;    c. computer executable instructions for performing rule mesh traversal for the data packet, wherein the rule mesh traversal starts from the root path node; and    d. computer executable instructions for updating information in the data packet during the rule mesh traversal, wherein the information is data regarding the rules satisfied by the data packet.    
     
     
         12 . The computer program product according to  claim 11 , wherein the computer executable instructions for determining the root path node comprises computer executable instructions for checking the data packet for a session based application.  
     
     
         13 . The computer program product according to  claim 12 , wherein the computer executable instructions for checking the data packet for the session based application comprises: 
 a. computer executable instructions for checking the presence of a session create flag if the data packet is for the session based application, wherein the session create flag indicates that the data packet is a first data packet of the session based application; and    b. computer executable instructions for assigning the root path node as the node for start of the rule mesh traversal if the data packet is not for the session based application.    
     
     
         14 . The computer program product according to  claim 13 , wherein the computer executable instructions for checking the presence of the session create flag comprises: 
 a. computer executable instructions for initializing a session entry if the session create flag is present, wherein the session entry is used for determining the root path node; and    b. computer executable instructions for retrieving the session entry if the session create flag is not present.    
     
     
         15 . The computer program product according to  claim 11 , wherein the computer executable instructions for performing the rule mesh traversal comprises: 
 a. computer executable instructions for traversing the tree data structure of the rule mesh till a start of graph path node is reached, wherein the start of graph path node indicates the start of the graph data structure in the rule mesh;    b. computer executable instructions for traversing the graph data structure of the rule mesh when the start of graph path node is reached; and    c. computer executable instructions for appending a rule lookup-id to the data packet after the rule mesh traversal, wherein the rule lookup-id contains data pertaining to the rules matched during the rule mesh traversal.    
     
     
         16 . The computer program product according to  claim 15 , wherein the computer executable instructions for traversing the tree data structure of the rule mesh comprises: 
 a. computer executable instructions for determining a root node for the tree data structure, wherein the root node is a start node for traversing the tree data structure;    b. computer executable instructions for determining a tree edge for traversing the tree data structure, wherein the step of determining the tree edge comprises performing a search indicated on the root node;    c. computer executable instructions for arriving at a next path node of the tree data structure by traversing along the tree edge;    d. computer executable instructions for iteratively repeating steps b and c until the next path node is not the start of graph path node, wherein the start of graph path node is a first node of the graph data structure in the rule mesh; and    e. computer executable instructions for retrieving a tree ID from the tree edge if the next path node is the start of graph path node.    
     
     
         17 . The computer program product according to  claim 15 , wherein the computer executable instructions for traversing the graph data structure comprises: 
 a. computer executable instructions for updating a Rule Confirmation Bitmap (RCB), wherein the RCB indicates the rules matched in the graph data structure;    b. computer executable instructions for initializing a Graph Traversal Bitmap (GTB), wherein the GTB indicates conditions governing end of the traversal of the graph data structure;    c. computer executable instructions for determining a graph edge for traversing the graph data structure based on the RCB and the GTB;    d. computer executable instructions for arriving at a next path node of the graph data structure by traversing along the graph edge; and    e. computer executable instructions for ending the rule mesh traversal if at least one of the conditions governing end of the traversal of the graph data structure is satisfied.