Method and system for determining conformance of a data key with rules by means of memory lookups
View Patent ↗A method of comparing unmasked bits of an N-bit data key to an N-bit Rule includes dividing the key into C-bit chunks. Each of the chunks is used as an 5 address to extract from memories 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44 . The memory is preprepared, such that the data stored in the address corresponding to that chunk of the key is 1 or O according to whether a bitwise comparison of that chunk of the data key with the mask is equal to a bitwise comparison of that chunk of the mask and rule. This extracted bit therefore indicates whether the rule is obeyed for that chunk of the data key. The N/C extracted bits for each rule are compared, to determine if the rule is obeyed for the entire data key.
1. A method of comparing a data key to a rule, wherein the data key and rule are representable by bits, the method including:
generating a mask that indicates relevant bits that are relevant to identify the rule and do not care bits that are extraneous for identifying the rule;
generating a vector comprised of memory positions and at least a corresponding bit for each of the memory positions, by setting bits for those memory positions of the vector pointed to by bits of the rule when read as an address, the address including both relevant bits and do not care bits, to a value that indicates that the rule is detected;
inserting values of the bits of the vector into memory positions of a memory corresponding to the memory positions for each bit of the vector;
dividing the bits of the data key into a plurality of chunks;
extracting data from the memory at an address corresponding to the value of each of at least some of the chunks; and
examining the data extracted from each memory address corresponding to the at least some of the chunks to determine if the rule is obeyed for the entire data key determining that the rule is a particular rule from among a plurality of rules of one of a plurality of protocols.
2. The method of claim 1 , wherein the step of generating a vector comprises automatically setting the value of the corresponding bits of the vector to indicate that the rule is detected according to the following function:
Rule[I][C bits] AND Mask[I][C bits] is equal to Mask[C bits] AND J,
wherein I is the Ith rule, C is the number of bits in a chunk, and J ranges from 0 to 2 C −1.
3. The method of claim 2 , wherein the step of generating a mask generates a string of bits corresponding to the number of bits in a rule, and sets each bit in the mask that corresponds to a bit in the rule that is relevant for identifying that rule.
4. The method according to claim 1 , wherein the step of generating a vector comprises setting the value of bits corresponding to a number of bits comprising a chunk.
5. The method according to claim 1 , further comprising the step of configuring the memory into a two dimensional memory structure, a first dimension corresponding to the chunks of the data key and a second dimension corresponding to different rules.
6. The method according to claim 1 , wherein examining the data further comprises performing at least one AND operation on the data extracted from the memory corresponding to each of the chunks of the data key to determine if the rule is obeyed for the entire data key.
7. The method according to claim 1 , further comprising the step of providing the memory as separate memory devices and allocating sub sets of the different memory devices based on the number of rules to be detected.
8. The method according to claim 1 , wherein a number of rules are detected, further comprising the step of prioritizing the rules according to a predetermined order of priority for rules.
9. The method according to claim 1 , further comprising the step of parsing for parsing a packet received over a network into a data key.
10. The method according to claim 9 , further comprising the step of receiving the packet from an Internet based network.
11. A system for comparing a data key to a rule, wherein the data key and rule are representable by bits, the system including:
a memory comprised of memory positions and at least a corresponding bit for each of the memory positions making up a vector, wherein bits for those memory positions of the vector pointed to by bits of the rule when read as an address, the address including both relevant bits and do not care bits, are set to a value that indicates that the rule is detected;
an interface that divides the bits of the data key into a plurality of chunks;
a comparator that compares data from each memory address corresponding to the at least some of the chunks to determine if the rule is obeyed for the entire data key a processor that determines that the rule is a particular rule from among a plurality of rules of one of a plurality of protocols.
12. The system of claim 11 , wherein the memory is populated with the by setting the value of the corresponding bits of the vector stored in memory to indicate that the rule is detected according to the following function:
Rule[I][C bits] AND Mask[I][C bits] is equal to Mask[C bits] AND J,
wherein I is the Ith rule, C is the number of bits in a chunk, and J ranges from 0 to 2 C −1, and wherein Mask are bits set to a value indicating relevant bits that are relevant to identify the rule and do not care bits that are extraneous for identifying the rule.
13. The system of claim 12 , further comprising a mask formed of a string of bits corresponding to the number of bits in a rule, and sets each bit in the mask that corresponds to a bit in the rule that is relevant for identifying that rule.
14. The system according to claim 11 , wherein the memory stores the value of bits of the vector corresponding to a number of bits comprising a chunk.
15. The system according to claim 11 , wherein the memory is configured into a two dimensional memory structure, a first dimension corresponding to the chunks of the data key and a second dimension corresponding to different rules.
16. The system according to claim 11 , wherein the comparator includes at least one AND device that operates on data extracted from the memory corresponding to each of the chunks of the data key to determine if the rule is obeyed for the entire data key.
17. The system according to claim 11 , wherein the memory is provided as separate memory devices and further comprising a switch that allocates the which memory devices are grouped together based on the number of rules to be detected.
18. The system according to claim 11 , wherein a number of rules are detected, further comprising a prioritzer that prioritizes rules according to a predetermined order of priority for rules.
19. The system according to claim 11 , further comprising a parser for parsing a packet received over a network into a data key.
20. The system according to claim 19 , wherein the parser receives the packet from an Internet based network.
21. The system of claim 11 , wherein the memory includes only a number of individual memory units (per bit) according to the formula:
NM/(2 C L 2 C),
Wherein, N is the number of bits in the data key, M is the number of rules available for detection, C is the number of bits in a chunk and L is the width of a discrete memory device.