Accelerating computer network policy search
Systems and methods for accelerating computer network policy searching are provided. According to one embodiment, a packet is received by a policy search engine (PSE) of a packet processing device. A set of candidate policies are identified from among multiple policies of the packet processing device by screening the multiple policies by a speculation unit of the PSE based on metadata associated with the received packet. Finally, a matching policy for the received packet is identified by a policy search processor (PSP) of the PSE by executing policy-search-specific instructions and general purpose instructions.
1. A method comprising:
building, by a processing resource of a packet processing device, a decision tree to facilitate finding a policy of a plurality of policies that matches a particular packet;
generating, by the processing resource, a plurality of hash entries within a hash table by performing hash pattern matching for each of a plurality of fields of an n-tuple of a packet received by the packet processing device, wherein the hash table represents conditions expressed by the plurality of policies in n-dimensional space corresponding to the n-tuple;
identifying, by the processing resource, an entry point to a sub-tree within the decision tree by correlating the plurality of hash entries with a set of candidate policies of the plurality of policies; and
efficiently identifying, by the processing resource, a matching policy of the plurality of policies by limiting traversal of the decision tree to the sub-tree.
2. The method of claim 1 , wherein said performing hash pattern matching comprises for each of the plurality of fields of the n-tuple of the packet:
constructing a key based on a pattern including a field identifier and a field value of the field; and
determining a hash entry identifier of the plurality of hash entries by hashing the key.
3. The method of claim 2 , wherein the plurality of fields of the n-tuple include a source Internet Protocol (IP) address field, a destination IP address field, a source port, a destination port, and a protocol.
4. The method of claim 1 , wherein said efficiently identifying, by the processing resource, a matching policy is performed by executing (i) policy-search-specific instructions that support decision tree traversal and policy evaluation operations and (ii) general purpose instructions.
5. The method of claim 4 , wherein the policy-search-specific instructions include instructions that determine an order of cutting of the n-dimensional space.
6. The method of claim 1 , wherein the processing resource comprises a co-processor that operates under direction of a general-purpose processor of the packet processing device.
7. The method of claim 1 , wherein processing resource comprises a general-purpose processor of the packet processing device.
8. The method of claim 1 , wherein the packet processing device comprises a network security device.
9. The method of claim 8 , wherein the network security device comprises a unified Threat Management (UTM) appliance.
10. A packet processing device comprising:
a processing resource; and
a non-transitory computer-readable medium, coupled to the processing resource, having stored therein instructions that when executed by the processing resource cause the processing resource to:
build a decision tree to facilitate finding a policy of a plurality of policies that matches a particular packet;
generate plurality of hash entries within a hash table by performing hash pattern matching for each of a plurality of fields of an n-tuple of a packet received by the packet processing device, wherein the hash table represents conditions expressed by the plurality of policies in n-dimensional space corresponding to the n-tuple;
identify an entry point to a sub-tree within the decision tree by correlating the plurality of hash entries with a set of candidate policies of the plurality of policies; and
efficiently identify a matching policy of the plurality of policies by limiting traversal of the decision tree to the sub-tree.
11. The packet processing device of claim 10 , wherein said performing hash pattern matching comprises for each of the plurality of fields of the n-tuple of the packet:
constructing a key based on a pattern including a field identifier and a field value of the field; and
determining a hash entry identifier of the plurality of hash entries by hashing the key.
12. The packet processing device of claim 11 , wherein the plurality of fields of the n-tuple include a source Internet Protocol (IP) address field, a destination IP address field, a source port, a destination port, and a protocol.
13. The packet processing device of claim 10 , wherein the matching policy is efficiently identified by executing (i) policy-search-specific instructions that support decision tree traversal and policy evaluation operations and (ii) general purpose instructions.
14. The packet processing device of claim 13 , wherein the policy-search-specific instructions include instructions that determine an order of cutting of the n-dimensional space.
15. The packet processing device of claim 10 , wherein the processing resource comprises a co-processor that operates under direction of a general-purpose processor of the packet processing device.
16. The packet processing device of claim 10 , wherein the processing resource comprises a general-purpose processor.
17. The packet processing device of claim 10 , wherein the packet processing device comprises a network security device.
18. The packet processing device of claim 17 , wherein the network security device comprises a unified Threat Management (UTM) appliance.