Patent ID: 7978709
Filing Date: 2011-07-12
Classification: H04L

Abstract:
1. A method of constructing a hierarchical database from an initial plurality of rules, wherein the hierarchical database is provided within a memory device, the method comprising: adding a first rule of the initial plurality of rules to a first sub-database in the memory device if a first bit of the rule is a logic ‘0’ value; adding the first rule to a second sub-database in the memory device if the first bit is a logic ‘1’ value; adding the first rule to a third sub-database in the memory device if the first bit is in a masked state, ‘X’, indicating that the first bit may be either a logic ‘1’ or a logic ‘0’ value; and adding each other rule of the initial plurality of rules to either the first sub-database, the second sub-database or the third sub-database, according to a first bit of the other rule, wherein the first sub-database, second sub-database and third sub-database form a first hierarchical level in the hierarchical database and wherein the method further comprises: after adding the first rule and each other rule of the initial plurality of rules to either the first sub-database, the second sub-database or the third sub-database, splitting the first sub-database into a second hierarchical level of sub-databases if, before splitting the first sub-database, the first sub-database contains more than a predetermined number of rules, wherein the constructed hierarchical database is configured to search a packet header for one or more matching rules.