Systems and methods for high speed packet classification
View Patent ↗Systems and methods are disclosed for classifying packets with a rule. In one exemplary embodiment, the method includes receiving a packet; determining a key value for the received packet; identifying a rule corresponding to the determined key value by searching a set of rules, the set of rules being decorrelated such that there is no overlap in any key values corresponding to the decorrelated set of rules.
1. A method of classifying packets comprising:
determining a packet key value for a packet; and
identifying a rule for the packet, the rule corresponding to the determined packet key value, the identifying comprising searching a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules.
2. The method of claim 1 further comprising:
processing the packet based on the identified rule.
3. The method of claim 1 , wherein determining the packet key value further comprises:
reading a portion of the packet, the read portion being the packet key value.
4. The method of claim 1 , wherein determining the packet key value further comprises:
using a source address of the packet as the packet key value.
5. The method of claim 1 , wherein identifying the rule comprises:
searching a search tree of the set of decorrelated rules, the search tree being searchable based on the packet key value.
6. A method of classifying packets comprising:
determining a packet key value for a packet received from a first network;
determining a rule for the packet, the rule corresponding to the determined packet key value, the determining comprising searching a search tree having a set of decorrelated rules
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules; and
classifying the packet based on the determined rule, such that the determined rule may be applied to the packet.
7. The method of claim 6 , further comprising:
processing the packet based on the determined rule.
8. The method of claim 6 , further comprising:
processing the packet, such that the packet is forwarded to a second network based on the determined rule.
9. The method of claim 6 , further comprising:
processing the packet, such that the packet is discarded based on the determined rule.
10. The method of claim 6 , further comprising:
processing the packet, such that the packet is encrypted based on the determined rule.
11. The method of claim 6 , wherein decorrelating further comprises:
selecting a candidate rule.
12. The method of claim 11 , further comprising:
forming at least one other rule based on the candidate rule, the at least one other rule having a corresponding key value without any overlap with any other key values of any other rules.
13. The method of claim 6 , wherein determining the rule further comprises:
loading at least one comparator with one or more operand values, the operand values being representative of key values corresponding to the set of decorrelated rules.
14. The method of claim 13 , wherein determining the rule further comprises:
searching the search tree based on the operand values and the determined packet key value.
15. The method of claim 6 , wherein determining the rule further comprises:
loading at least one comparator and at least one register with one or more operand values, the operand values representative of key values corresponding to the set of decorrelated rules.
16. A system comprising:
means for determining a packet key value for a packet;
means for identifying a rule for the packet corresponding to the determined packet key value, the identifying comprising searching a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules.
17. A system comprising:
means for determining a packet key value for a packet received from a first network;
means for determining a rule for the packet, the rule corresponding to the determined packet key value, the determining comprising searching a search tree having a set of decorrelated rules
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules; and
means for classifying the packet based on the determined rule, such that the determined rule may be applied to the packet.
18. A system for classifying packets, the system comprising:
a processor; and
a memory,
wherein the processor and the memory are configured to perform a method comprising:
determining a packet key value for a packet; and
identifying a rule for the packet, the rule corresponding to the determined packet key value, the identifying comprising searching a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules.
19. The system of claim 18 wherein the processor and the memory are configured to perform a method further comprising:
processing the packet based on the identified rule.
20. The system of claim 18 wherein the processor and the memory are configured to perform a method further comprising:
reading a portion of the packet, the read portion being the packet key value.
21. The system of claim 18 wherein the processor and the memory are configured to perform a method further comprising:
using a source address of the packet as the packet key value.
22. The system of claim 18 wherein the processor and the memory are configured to perform a method further comprising:
searching a search tree of the set of decorrelated rules, the search tree being searchable based on the packet key value.
23. A computer-readable medium embodied with computer instructions to be executed by a computer for performing a method for classifying packets, the method comprising:
determining a packet key value for a packet; and
identifying a rule for the packet, the rule corresponding to the determined packet key value, the identifying comprising searching a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules.
24. The computer-readable medium of claim 23 wherein the method further comprises:
processing the packet based on the identified rule.
25. The computer-readable medium of claim 23 wherein the method further comprises:
reading a portion of the packet, the read portion being the packet key value.
26. The computer-readable medium of claim 23 wherein the method further comprises:
using a source address of the packet as the packet key value.
27. The computer-readable medium of claim 23 wherein the method further comprises:
searching a search tree of the set of decorrelated rules, the search tree being searchable based on the packet key value.
28. A network comprising a plurality of processors of a system interfaced to the network, the system comprising:
at least one processor; and
a memory,
wherein the processor and the memory are configured to perform a method comprising:
determining a packet key value for a packet; and
identifying a rule for the packet, the rule corresponding to the determined packet key value, the identifying comprising searching a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules.
29. A packet classification module comprising:
a processor; and
a memory,
wherein the processor and the memory are configured to perform a method comprising:
determining a packet key value for a packet received from a first network;
determining a rule for the packet the rule corresponding to the determined packet key value, the determining comprising searching a search tree having a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules; and
classifying the packet based on the determined rule, such that the determined rule may be applied to the packet.
30. A packet classification module comprising:
a processor; and
a memory,
wherein the processor and the memory are configured to perform a method comprising:
determining a packet key value for a packet received from a first network;
classifying the packet based on a rule identified by a search tree having a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules.
31. A computer-readable medium embodied with computer instructions to be executed by a computer for performing a method for classifying packets comprising:
determining a packet key value for a packet received from a first network;
determining a rule for the packet, the rule corresponding to the determined packet key value, the determining comprising searching a search tree having a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules; and
classifying the packet based on the determined rule, such that the determined rule may be applied to the packet.
32. A computer-readable medium embodied with computer instructions to be executed by a computer for performing a method for classifying packets, the method comprising:
determining a packet key value for a packet received from a first network;
classifying the packet based on a rule identified by a search tree having a set of decorrelated rules,
each of the decorrelated rules having a unique corresponding key value, and
the decorrelated rules generated by decorrelating candidate rules in a set of original rules, the decorrelating comprising modifying a candidate rule based on the corresponding key values of decorrelated members of the set of original rules so that a corresponding key value of the candidate rule does not overlap with the corresponding key values of the decorrelated members of the set of original rules.