Source: https://patents.google.com/patent/US8937954B2/en
Timestamp: 2020-08-04 12:13:09
Document Index: 377343554

Matched Legal Cases: ['Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61']

US8937954B2 - Decision tree level merging - Google Patents
Decision tree level merging Download PDF
US8937954B2
US8937954B2 US13/686,269 US201213686269A US8937954B2 US 8937954 B2 US8937954 B2 US 8937954B2 US 201213686269 A US201213686269 A US 201213686269A US 8937954 B2 US8937954 B2 US 8937954B2
US13/686,269
US20130085978A1 (en
Kenneth A. Bullis
2011-08-02 Priority to US201161514400P priority Critical
2011-08-02 Priority to US201161514407P priority
2011-08-02 Priority to US201161514344P priority
2011-08-02 Priority to US201161514447P priority
2011-08-02 Priority to US201161514438P priority
2011-08-02 Priority to US201161514406P priority
2011-08-02 Priority to US201161514379P priority
2011-08-02 Priority to US201161514450P priority
2011-08-02 Priority to US201161514459P priority
2011-08-02 Priority to US201161514463P priority
2011-08-02 Priority to US201161514382P priority
2012-08-02 Priority to US13/565,784 priority patent/US8937952B2/en
2012-11-27 Priority to US13/686,269 priority patent/US8937954B2/en
2012-11-27 Application filed by Cavium LLC filed Critical Cavium LLC
2013-01-04 Assigned to Cavium, Inc. reassignment Cavium, Inc. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: BULLIS, Kenneth A., GOYAL, RAJAN
2013-04-04 Publication of US20130085978A1 publication Critical patent/US20130085978A1/en
2015-01-20 Publication of US8937954B2 publication Critical patent/US8937954B2/en
2020-02-17 Assigned to CAVIUM INTERNATIONAL reassignment CAVIUM INTERNATIONAL ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: CAVIUM, LLC
238000003066 decision tree Methods 0.000 title claims abstract description 104
This application is a continuation of U.S. application Ser. No. 13/565,784, filed Aug. 2, 2012, which claims the benefit of U.S. Provisional Application No. 61/514,344, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,382, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,379, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,400, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,406, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,407, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,438, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,447, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,450, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,459, filed on Aug. 2, 2011; and U.S. Provisional Application No. 61/514,463, filed on Aug. 2, 2011.
While building the decision tree, the method may further include, for each level of the decision tree, identifying partial duplicate nodes on a level of the decision tree. Partial duplicate nodes may be a partial duplicate of the subset of the plurality of the rules. The method may create a new node on the level of the decision tree based on one or more partial duplicate nodes being identified. The partial duplicate of the subset of the plurality of the rules may be included in the new node created and removed from the partial nodes identified.
A method may use a classifier table having a plurality of rules, the plurality of rules having at least one field, for building a decision tree structure including a plurality of nodes. Each node may include a subset of the plurality of rules. The method may determine for each level of the decision tree whether to merge grandchildren of a parent node with child nodes of the parent node based on a resulting total number of child nodes of the parent node not being more than a given threshold. The method may store the decision tree structure. The method may further merge the cuts of a child node into the cuts of the parent node resulting in new child nodes of the parent node. The cuts of the child node may be on a same field as the parent node cuts or the cuts of the child node may be on a different field than the parent node cuts. The given threshold may be adjustable. The method may iteratively adjust the given threshold and merge grandchildren of a parent node with child nodes of the parent node until a resulting number of child nodes of the parent node reaches a given threshold number of child nodes.
A non-transitory computer-readable medium may have encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to use a classifier table having a plurality of rules, the plurality of rules having at least one field, build a decision tree structure including a plurality of nodes, the plurality of nodes including a subset of the plurality of rules; determine, for each node of the decision tree, a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts; select, upon determining the number of cuts that may be made on each at one least field, a field on which to cut the node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least one field. The processor may cut the node into a number of child nodes on the selected at least field and store the decision tree structure.
FIG. 8A-C show a graphical example of merging nodes.
FIG. 10C-D illustrate a graphical example of removing duplicate buckets of rules in a node of a decision tree.
Example embodiments described herein build a decision tree data structure by carefully preprocessing a classifier. Each time a packet arrives, the runtime walker traverses the decision tree to find a leaf node that stores a small number of rules. Once the leaf node is reached, a linear search of the rules within the leaf node occurs to find a matching rule.
FIG. 3B illustrates a decision tree data structure 350 that includes a root node 352, and leaf nodes 354 a-e, and has a depth 356.
Embodiments described herein include at least three data structures that include: i) a tree, ii) buckets, and iii) a rule table. A tree includes nodes and leaf nodes. Leaf nodes may be linked to buckets. The leaf nodes may point to buckets, buckets may contain a set of rules. Embodiments described herein may store rules in common tables and the buckets pointed to by leaf nodes may contain rule numbers corresponding to the rules in the rules table. Buckets may include rules in any suitable manner as may be known to one skilled in the art. Each bucket may be a data structure that may include one or more bucket entries. A bucket entry may be a rule, an index to a rule, a pointer to a rule, a pointer to a set of rules, or a pointer to another bucket. A bucket may include a linked list to the rules. A bucket may include entries including any combination thereof. For example, a bucket may have one entry that is a pointer to a rule and one entry that is a pointer to a set of rules, etc. Rule priority may be stored with a rule or linked to a rule in any suitable manner.
FIG. 9D illustrates a decision tree data structure 981 including a tree, buckets, and rules. The set of compiled rules 980 may generate a decision tree data structure 981 including a tree 982, buckets 983 a-d, and rules 985. The tree 982 may include a root node 984, nodes 984 a-c, and leaf nodes 986 a-b. Each leaf node 986 of the tree 982 points to a bucket 983. Each bucket may include one or more bucket entries 987. A leaf node may include bucket information that may be used to locate the bucket entries or a bucket list of entries. A bucket entry may be a pointer to rule (988), or a pointer (989) to a set of rules (990). The set of rules 990 may be a sequential group of rules, or a group of rules scattered throughout the memory, either organized by a plurality of pointers or by a method used to recollect the set of rules. The set of rules 990 may also be called a chunk, or a chunk of rules. A bucket entry that points to the set of rules 990 may be called a chunk pointer.
FIG. 10C illustrates a graphical example of removing duplicate buckets of rules in a node of a decision tree (1000). As illustrated, a node 1005 has 4 leaf nodes 1002, 1004, 1006, and 1008. The node 1005 shows 4 buckets 1010 a-d containing a set of rules, the buckets 1010 a-d are pointed to (1012, 1014, 1016, 1018) by leaf nodes 1002, 1004, 1006, and 1008, respectively. Buckets 1010 a, 1010 c, and 1010 d all contain the same rules. Because the buckets 1010 a, 1010 c, and 1010 d are identified to contain the same rules, and the duplicate buckets 1010 c and 1010 d may be removed from memory, keeping only unique buckets 1010 a and 1010 b.
FIG. 10D shows node 1005 results in having two buckets (1010 a and 1010 b) containing rules that need to be stored in memory. Thus, the leaf nodes 1002, 1004, 1006, and 1008 of node 1005 only need to point to a memory location containing the set of rules in buckets 1010 a and 1010 b. For example, leaf nodes 1002, 1006, and 1008 all point (1013) to bucket 1010 a, and leaf node 1004 points (1011) to bucket 1010 b.
FIG. 10F is a graphical illustration of bucket duplication according to one embodiment. A portion of a tree (1070) is shown that includes a parent node 1072 that has child nodes 1078 a and 1078 b (leaf) and a grandchild node 1074. The child node 1078 b (leaf) and grandchild 1074 (leaf) both point to buckets 1076 and 1073 respectively. The buckets 1076 and 1073 are duplicate buckets each including a duplicate rule set (e.g., R1 and R2). The bucket 1073 may be removed by pointing the child node 1078 b to point 1071 to the bucket 1076 pointed to by the grandchild node 1074.
FIG. 10G is a graphical illustration of partial duplicate buckets of rules in a node of a decision tree. A portion of a tree (1050) is shown including a parent node 1052 and two children (leaves) 1054 and 1056 that point to buckets 1054 a and 1056 a respectively. Buckets 1054 a and 1056 a have a partial duplicate set of rules R1 and R2. The set of rules in each bucket may be split into subsets. For example, rules in the bucket 1054 a may be split into a first set 1058 a including R1 and R2 and a second set 1058 b including R3 and R4. Rules in the bucket 1056 a may be split into a first set 1058 c including R1 and R2 and a second set 1058 d including R7. The bucket entries may be replaced with a linked list of chunk pointers, or pointers to sets of rules. Bucket 1054 a′ illustrates bucket 1054 a having bucket entries replaced with a linked list of chunk pointers C0 and C1. Similarly, bucket 1056 a″ illustrates bucket 1056 a having bucket entries replaced with a linked list of chunk pointers C0 and C2. Chunk pointer C0 points to a set of rules including R1 and R2, chunk pointer C1 points to a set of rules including R3 and R4, and chunk pointer C2 points to a set of pointers including R7.
in a processor, using a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules;
determining for each level of the decision tree whether to merge grandchildren of a parent node with child nodes of the parent node based on a merge resulting in a total number of child nodes of the parent node not being more than a given threshold;
merging at each level the grandchildren of the parent node with child nodes of the parent node based on the determination; and
storing the decision tree structure in a memory.
3. The method of claim 2 further wherein each parent node has been cut on a first field set of one or more fields of the at least one field resulting in the child nodes of the parent node, and each child node has been cut on a second field set of one or more fields of the at least one field resulting in the grandchildren of the parent node, and further wherein merging cuts of each child node into cuts of the parent node includes:
determining a collective set of bits for each field of the one or more fields of the first field set and the second field set, each collective set of bits corresponding to a respective field of the first field set and the second field set, wherein a single collective set of bits corresponds to the respective field if the respective field is common to both the first field set and the second field set, each collective set of bits including:
(i) a first set of one or more bits of the respective field, the first set of one or more bits being a first set of all bits of the respective field having been used to cut the parent node on the respective field resulting in one or more of the child nodes of the parent node if the respective field is included in the first field set and not the second field set;
(ii) a second set of one or more bits of the respective field, the second set of one or more bits being a second set of all bits of the respective field having been used to cut each of the child nodes of the parent node on the respective field resulting in one or more of the grandchildren of the parent node if the respective field is included in the second field set and not the first field set; and
(iii) a third set of two or more bits of the respective field including the first set of one or more bits of the respective field and the second set of one or more bits of the respective field if the respective field is included in both the first field set and the second field set; and
re-cutting the parent node on each field of the first field set and the second field set based on the collective set of bits determined for each field.
cutting the parent node into the child nodes based on a selected one or more fields of the at least one field and a number of bits each corresponding to the selected one or more fields.
merging grandchildren of the parent node with child nodes of the parent node by further re-cutting the parent node into new child nodes, wherein the parent node is re-cut on each of the selected one or more fields based on a total number of bits each corresponding to the selected one or more fields, wherein the total number of bits each corresponding to the selected one or more fields is a sum of the number of bits each corresponding to the selected one or more fields used to cut the child nodes.
use a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules;
determine for each level of the decision tree whether to merge grandchildren of a parent node with child nodes of the parent node based on a merge resulting in a total number of child nodes of the parent node not being more than a given threshold;
merge at each level the grandchildren of the parent node with child nodes of the parent node based on the determination; and
store the decision tree structure in the memory.
10. The apparatus of claim 9 further wherein each parent node has been cut on a first field set of one or more fields of the at least one field resulting in the child nodes of the parent node, and each child node has been cut on a second field set of one or more fields of the at least one field resulting in the grandchildren of the parent node, and further wherein to merge cuts of each child node into cuts of the parent node the processor is further configured to:
determine a collective set of bits for each field of the one or more fields of the first field set and the second field set, each collective set of bits corresponding to a respective field of the first field set and the second field set, wherein a single collective set of bits corresponds to the respective field if the respective field is common to both the first field set and the second field set, each collective set of bits including:
(i) a first set of one or more bits of the respective field, the first set of one or more bits being a first set of all bits of the respective field having been used to cut the parent node on the respective field resulting in the child nodes of the parent node if the respective field is included in the first field set and not the second field set;
(ii) a second set of one or more bits of the respective field, the second set of one or more bits being a second set of all bits of the respective field having been used to cut each of the child nodes of the parent node on the respective field resulting in the grandchildren of the parent node if the respective field is included in the second field set and not the first field set; and
re-cut the parent node on each field of the first field set and the second field set based on the collective set of bits determined for each field.
12. The apparatus of claim 8 wherein the processor is further configured to:
cut the parent node into the child nodes based on a selected one or more fields of the at least one field and a number of bits each corresponding to the selected one or more fields.
merge grandchildren of the parent node with child nodes of the parent node by further re-cutting the parent node into new child nodes, wherein the parent node is re-cut on each of the selected one or more fields based on a total number of bits each corresponding to the selected one or more fields, wherein the total number of bits each corresponding to the selected one or more fields is a sum of the number of bits each corresponding to the selected one or more fields used to cut the child nodes.
15. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to:
store the decision tree structure.
16. The non-transitory computer-readable medium of claim 15 wherein the processor is further caused to merge cuts of each child node into cuts of the parent node resulting in new child nodes of the parent node.
17. The non-transitory computer-readable medium of claim 16 further wherein each parent node has been cut on a first field set of one or more fields of the at least one field resulting in the child nodes of the parent node, and each child node has been cut on a second field set of one or more fields of the at least one field resulting in the grandchildren of the parent node, and further wherein to merge cuts of each child node into cuts of the parent node the processor is further caused to:
18. The non-transitory computer-readable medium of claim 16 wherein cuts of the child node are on a same field as the parent node cuts or the cuts of the child node are on a different field than the parent node cuts.
19. The non-transitory computer-readable medium of claim 15 wherein the processor is further caused to:
cut the parent node into the child nodes based on a selected one or more fields of the at least one field a number of bits each corresponding to the selected one or more fields.
20. The non-transitory computer-readable medium of claim 19 wherein the processor is further caused to:
21. The non-transitory computer-readable medium of claim 15 wherein the given threshold is adjustable and wherein the processor is further caused to iteratively adjust the given threshold and merge grandchildren of a parent node with child nodes of the parent node.
US13/686,269 2011-08-02 2012-11-27 Decision tree level merging Active 2032-09-24 US8937954B2 (en)
US201161514344P true 2011-08-02 2011-08-02
US201161514447P true 2011-08-02 2011-08-02
US201161514438P true 2011-08-02 2011-08-02
US201161514406P true 2011-08-02 2011-08-02
US201161514379P true 2011-08-02 2011-08-02
US201161514450P true 2011-08-02 2011-08-02
US201161514459P true 2011-08-02 2011-08-02
US201161514463P true 2011-08-02 2011-08-02
US201161514382P true 2011-08-02 2011-08-02
US201161514407P true 2011-08-02 2011-08-02
US201161514400P true 2011-08-02 2011-08-02
US13/565,784 US8937952B2 (en) 2011-08-02 2012-08-02 Packet classification
US13/686,269 US8937954B2 (en) 2011-08-02 2012-11-27 Decision tree level merging
US13/565,784 Continuation US8937952B2 (en) 2011-08-02 2012-08-02 Packet classification
US20130085978A1 US20130085978A1 (en) 2013-04-04
US8937954B2 true US8937954B2 (en) 2015-01-20
ID=46642652
US13/565,784 Active 2032-12-30 US8937952B2 (en) 2011-08-02 2012-08-02 Packet classification
US13/565,749 Active 2033-01-12 US8954700B2 (en) 2011-08-02 2012-08-02 Method and apparatus for managing processing thread migration between clusters within a processor
US13/565,422 Active US8472452B2 (en) 2011-08-02 2012-08-02 Lookup cluster complex
US13/565,775 Active 2033-04-14 US9137340B2 (en) 2011-08-02 2012-08-02 Incremental update
US13/565,389 Active US9596222B2 (en) 2011-08-02 2012-08-02 Method and apparatus encoding a rule for a lookup request in a processor
US13/565,736 Active 2033-01-26 US8966152B2 (en) 2011-08-02 2012-08-02 On-chip memory (OCM) physical bank parallelism
US13/565,727 Active US8711861B2 (en) 2011-08-02 2012-08-02 Lookup front end packet input processor
US13/565,459 Active 2032-10-23 US8719331B2 (en) 2011-08-02 2012-08-02 Work migration in a processor
US13/565,735 Active 2033-02-13 US9065860B2 (en) 2011-08-02 2012-08-02 Method and apparatus for multiple access of plural memory banks
US13/565,741 Active 2034-12-22 US9391892B2 (en) 2011-08-02 2012-08-02 Method and apparatus for managing transport operations to a cluster within a processor
US13/565,743 Active 2033-10-17 US9319316B2 (en) 2011-08-02 2012-08-02 Method and apparatus for managing transfer of transport operations from a cluster in a processor
US13/565,746 Active 2032-10-09 US9525630B2 (en) 2011-08-02 2012-08-02 Method and apparatus for assigning resources used to manage transport operations between clusters within a processor
US13/565,767 Active US8606959B2 (en) 2011-08-02 2012-08-02 Lookup front end packet output processor
US13/565,406 Active 2032-08-25 US9344366B2 (en) 2011-08-02 2012-08-02 System and method for rule matching in a processor
US13/565,271 Active 2033-03-29 US10277510B2 (en) 2011-08-02 2012-08-02 System and method for storing lookup request rules in multiple memories
US13/599,276 Active 2033-09-16 US9729527B2 (en) 2011-08-02 2012-08-30 Lookup front end packet input processor
US13/664,015 Active US8934488B2 (en) 2011-08-02 2012-10-30 Identifying duplication in decision trees
US13/686,269 Active 2032-09-24 US8937954B2 (en) 2011-08-02 2012-11-27 Decision tree level merging
US13/901,220 Active 2032-08-11 US8995449B2 (en) 2011-08-02 2013-05-23 Lookup cluster complex
US14/082,365 Active 2033-01-24 US9497117B2 (en) 2011-08-02 2013-11-18 Lookup front end packet output processor
US14/138,931 Active US9031075B2 (en) 2011-08-02 2013-12-23 Lookup front end packet input processor
US14/230,698 Active 2033-10-04 US9614762B2 (en) 2011-08-02 2014-03-31 Work migration in a processor
US14/570,626 Active US9191321B2 (en) 2011-08-02 2014-12-15 Packet classification
US14/592,384 Active 2032-09-02 US9531690B2 (en) 2011-08-02 2015-01-08 Method and apparatus for managing processing thread migration between clusters within a processor
US14/604,975 Abandoned US20150143060A1 (en) 2011-08-02 2015-01-26 On-Chip Memory (OCM) Physical Bank Parallelism
US14/660,132 Active US9225643B2 (en) 2011-08-02 2015-03-17 Lookup cluster complex
US15/145,052 Active US9866540B2 (en) 2011-08-02 2016-05-03 System and method for rule matching in a processor
US (27) US8937952B2 (en)
JP (1) JP5657840B2 (en)
CN (2) CN103858392B (en)
WO (5) WO2013020002A1 (en)
US8923306B2 (en) * 2011-08-02 2014-12-30 Cavium, Inc. Phased bucket pre-fetch in a network processor
US10021026B2 (en) * 2013-01-31 2018-07-10 Hewlett Packard Enterprise Development Lp Incremental update of a shape graph
US9424366B1 (en) * 2013-02-11 2016-08-23 Marvell International Ltd. Reducing power consumption in ternary content addressable memory (TCAM)
US9270704B2 (en) * 2013-03-13 2016-02-23 FireMon, LLC Modeling network devices for behavior analysis
EP2972888B1 (en) * 2013-03-14 2019-02-06 Micron Technology, INC. Memory systems and methods including training,data organizing,and/or shadowing
KR20140131781A (en) * 2013-05-06 2014-11-14 삼성전자주식회사 Memory control apparatus and method
US9356818B2 (en) * 2013-10-30 2016-05-31 Telefonaktiebolaget Lm Ericsson (Publ) Method and computing device for packet classification
US9620213B2 (en) * 2013-12-27 2017-04-11 Cavium, Inc. Method and system for reconfigurable parallel lookups using multiple shared memories
CN103763197B (en) * 2014-01-27 2017-04-12 杭州华三通信技术有限公司 Flow table item collision detection device and method
KR101535813B1 (en) * 2014-10-17 2015-07-10 한국과학기술정보연구원 System and method for dynamic updating of event composition rule for complex event processing
JP6598188B2 (en) * 2015-02-27 2019-10-30 株式会社エヴリカ Information processing apparatus, method, and program
WO2016153477A1 (en) * 2015-03-23 2016-09-29 Hewlett Packard Enterprise Development Lp Compiling network policies
WO2016158732A1 (en) * 2015-03-27 2016-10-06 古河電気工業株式会社 Electromagnetic shield tube, electromagnetic shield structure
US10075998B2 (en) * 2015-05-14 2018-09-11 Intel IP Corporation Wireless device, method, and computer readable media for signaling a resource allocation in a high efficiency wireless local-area network
US10115463B1 (en) * 2015-06-25 2018-10-30 Xilinx, Inc. Verification of a RAM-based TCAM
US10451094B2 (en) * 2015-09-28 2019-10-22 Kubota Corporation Hydraulic system of work machine
CN105426352A (en) * 2015-11-24 2016-03-23 国家电网公司 Automatic generation method of template document
CN106209626B (en) * 2016-07-26 2019-12-06 新华三技术有限公司 Self-adaptive routing issuing method and device
US20190190930A1 (en) * 2016-07-31 2019-06-20 Fenror7 Ltd Method and System For Detecting Movement of Malware and Other Potential Threats
US10303375B2 (en) 2016-09-19 2019-05-28 Fungible, Inc. Buffer allocation and memory management
US10209900B2 (en) 2016-09-19 2019-02-19 Fungible, Inc. Buffer allocation and memory management using mapping table
US10454786B2 (en) * 2016-09-26 2019-10-22 Amazon Technologies, Inc. Multi-party updates to distributed systems
US10404594B2 (en) 2016-12-13 2019-09-03 Oracle International Corporation System and method for providing partitions of classification resources in a network device
CN106844041B (en) * 2016-12-29 2020-06-16 华为技术有限公司 Memory management method and memory management system
US10257090B2 (en) * 2017-02-21 2019-04-09 Futurewei Technologies, Inc. Packet classification using multi-dimensional splitting
US20180336063A1 (en) * 2017-05-20 2018-11-22 Cavium, Inc. Method and apparatus for load balancing of jobs scheduled for processing
CN107450495B (en) * 2017-08-25 2019-10-29 艾普工华科技（武汉）有限公司 It is a kind of flexible in artefact management business model system based on message rule engine
CN107797973A (en) * 2017-09-27 2018-03-13 西安交通大学 It is a kind of towards hard-wired GBDT disaggregated models compression method
US10540288B2 (en) 2018-02-02 2020-01-21 Fungible, Inc. Efficient work unit processing in a multicore system
CN108595370A (en) * 2018-03-30 2018-09-28 新华三信息安全技术有限公司 A kind of multi-core processor and message processing method
CN108984618A (en) * 2018-06-13 2018-12-11 深圳市商汤科技有限公司 Data processing method and device, electronic equipment and computer readable storage medium
WO2019241926A1 (en) * 2018-06-20 2019-12-26 华为技术有限公司 Access control list management method and device
US20190394291A1 (en) * 2018-06-22 2019-12-26 Avi Networks Payload matching via single pass transformation of http payload
CN108959636A (en) * 2018-07-25 2018-12-07 北京京东金融科技控股有限公司 Data processing method, device, system, computer-readable medium
US441022A (en) 1890-11-18 Method of baling cotton
CA2066724C (en) 1989-09-01 2000-12-05 Helge Knudsen Operating system and data base
JP3478820B2 (en) * 1989-09-01 2003-12-15 オブジェクトスター インターナショナル インコーポレイテッド System that executes the program
AT392555B (en) 1989-10-24 1991-04-25 Alcatel Austria Ag Method for transmitting binary information in an optical transmission network and optical transmission network
US5742843A (en) 1994-07-20 1998-04-21 Fujitsu Limited Control system for access between processing elements in a parallel computer
JP3436871B2 (en) * 1997-10-23 2003-08-18 株式会社東芝 Communication resource management method and node device
JP3027845B2 (en) 1997-11-21 2000-04-04 オムロン株式会社 Program control device and method
JP3692820B2 (en) 1999-03-10 2005-09-07 株式会社デンソー Automotive control device
GB2355084B (en) 1999-07-21 2004-04-28 Element 14 Ltd Setting condition values in a computer
GB9930849D0 (en) 1999-12-24 2000-02-16 Koninkl Philips Electronics Nv Data communications
CN100433707C (en) * 2000-11-21 2008-11-12 美商传威股份有限公司 Method for switching ATM, TDM and packet data through a single communications switch
CN100367730C (en) * 2001-02-14 2008-02-06 克利尔斯皮德科技有限公司 Interconnection system
JP2002290447A (en) * 2001-03-27 2002-10-04 Mitsubishi Electric Corp Address search method, address search circuit and address search program
SE0300894D0 (en) 2003-03-28 2003-03-28 Saab Ab Method to establish rules for a device intended to be used for generating decision support
WO2004107404A2 (en) 2003-05-23 2004-12-09 Sensory Networks, Inc. Apparatus and method for large hardware finite state machine with embedded equivalence classes
US7299227B2 (en) 2003-09-09 2007-11-20 Stmicroelectronics, Inc. Method and system for providing cascaded trie-based network packet search engines
US7706353B2 (en) 2004-01-21 2010-04-27 Alcatel-Lucent Usa Inc. Congestion control in connection-oriented packet-switching networks
EP1766929B1 (en) * 2004-07-09 2011-04-20 Panasonic Corporation Network mobility management method and corresponding apparatusses
BRPI0419214A (en) 2004-12-09 2008-04-15 Mitsubishi Electric Corp sequence matching system and program relating thereto
JP4140910B2 (en) * 2004-12-28 2008-08-27 インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｓｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ Data processing device, data management device, data processing method, data management method, data processing program, data management program, and information system
JP2006285808A (en) 2005-04-04 2006-10-19 Hitachi Ltd Storage system
US7844422B2 (en) 2006-05-30 2010-11-30 International Business Machines Corporation Method and system for changing a description for a state transition function of a state machine engine
EP2074767A2 (en) 2006-08-02 2009-07-01 University Of Florida Research Foundation, Inc. Succinct representation of static packet classifiers
SE531947C2 (en) 2006-11-03 2009-09-15 Oricane Ab A method, apparatus and system for multi-field classification in a data communications network
FR2914081A1 (en) 2007-03-23 2008-09-26 Advestigo Sa Method for protecting digital documents against unauthorized uses
WO2008129635A1 (en) 2007-04-12 2008-10-30 Fujitsu Limited Performance failure factor analysis program and performance failure factor analysis apparatus
US8219508B2 (en) 2007-07-06 2012-07-10 Lsi Corporation Systems and methods for compressing state machine instructions using a two access indexing scheme
JP4967876B2 (en) * 2007-07-18 2012-07-04 日本電気株式会社 Network, network device and transmission path redundancy method used therefor
TWI363532B (en) 2008-01-21 2012-05-01 Univ Nat Taiwan Method and system for packet classificiation with reduced memory space and enhanced access speed
US8554800B2 (en) 2008-07-30 2013-10-08 Portool Ltd. System, methods and applications for structured document indexing
US20100100936A1 (en) 2008-09-08 2010-04-22 Vladimir Alexander Brik Secure Wireless Network Using Radiometric Signatures
US9154380B2 (en) 2008-12-11 2015-10-06 International Business Machines Corporation Rules based fetching of operating platform status
TWI482083B (en) 2008-12-15 2015-04-21 Univ Nat Taiwan System and method for processing dual-phase regular expression comparison
TWI383618B (en) 2008-12-22 2013-01-21 Univ Nat Taiwan Wire configuration type regular expression comparison processing circuit
JP2012133405A (en) * 2009-07-24 2012-07-12 Hitachi Ltd Storage device and data transfer control method thereof
US8631043B2 (en) 2009-12-09 2014-01-14 Alcatel Lucent Method and apparatus for generating a shape graph from a binary trie
EP2517420B1 (en) 2009-12-22 2014-03-19 Cuneyt F. Bazlamacci Systolic array architecture for fast ip lookup
CA2786445C (en) 2010-01-13 2018-02-13 Ab Initio Technology Llc Matching metadata sources using rules for characterizing matches
CN101794271B (en) * 2010-03-31 2012-05-23 华为技术有限公司 Implementation method and device of consistency of multi-core internal memory
US8904154B2 (en) 2010-04-16 2014-12-02 Massachusetts Institute Of Technology Execution migration
JP5319626B2 (en) * 2010-08-18 2013-10-16 日本電信電話株式会社 Node, packet transfer method and communication network
US8799188B2 (en) 2011-02-08 2014-08-05 International Business Machines Corporation Algorithm engine for use in a pattern matching accelerator
2012-08-02 JP JP2014524092A patent/JP5657840B2/en active Active
2012-08-02 US US13/565,784 patent/US8937952B2/en active Active
2012-08-02 US US13/565,749 patent/US8954700B2/en active Active
2012-08-02 US US13/565,422 patent/US8472452B2/en active Active
2012-08-02 WO PCT/US2012/049406 patent/WO2013020002A1/en active Application Filing
2012-08-02 US US13/565,775 patent/US9137340B2/en active Active
2012-08-02 WO PCT/US2012/049383 patent/WO2013019981A1/en active Application Filing
2012-08-02 US US13/565,389 patent/US9596222B2/en active Active
2012-08-02 US US13/565,736 patent/US8966152B2/en active Active
2012-08-02 US US13/565,727 patent/US8711861B2/en active Active
2012-08-02 CN CN201280048291.0A patent/CN103858392B/en active IP Right Grant
2012-08-02 WO PCT/US2012/049405 patent/WO2013020001A1/en active Application Filing
2012-08-02 US US13/565,459 patent/US8719331B2/en active Active
2012-08-02 US US13/565,735 patent/US9065860B2/en active Active
2012-08-02 US US13/565,741 patent/US9391892B2/en active Active
2012-08-02 US US13/565,743 patent/US9319316B2/en active Active
2012-08-02 WO PCT/US2012/049400 patent/WO2013019996A1/en active Application Filing
2012-08-02 US US13/565,746 patent/US9525630B2/en active Active
2012-08-02 WO PCT/US2012/049408 patent/WO2013020003A1/en active Application Filing
2012-08-02 US US13/565,767 patent/US8606959B2/en active Active
2012-08-02 CN CN201280048417.4A patent/CN103858386B/en active IP Right Grant
2012-08-02 US US13/565,406 patent/US9344366B2/en active Active
2012-08-02 US US13/565,271 patent/US10277510B2/en active Active
2012-08-30 US US13/599,276 patent/US9729527B2/en active Active
2012-10-30 US US13/664,015 patent/US8934488B2/en active Active
2012-11-27 US US13/686,269 patent/US8937954B2/en active Active
2013-05-23 US US13/901,220 patent/US8995449B2/en active Active
2013-11-18 US US14/082,365 patent/US9497117B2/en active Active
2013-12-23 US US14/138,931 patent/US9031075B2/en active Active
2014-03-31 US US14/230,698 patent/US9614762B2/en active Active
2014-12-15 US US14/570,626 patent/US9191321B2/en active Active
2015-01-08 US US14/592,384 patent/US9531690B2/en active Active
2015-01-26 US US14/604,975 patent/US20150143060A1/en not_active Abandoned
2015-03-17 US US14/660,132 patent/US9225643B2/en active Active
2016-05-03 US US15/145,052 patent/US9866540B2/en active Active
Baboescu, F. and Varghese, G., "Scalable Packet Classification," Proceedings of the ACMSIGCOMM '01 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM '01), pp. 199-210 (2001).
Baboescu, F., et al., "Packet Classification for Core Routers: Is there an alternative to CAMs?", Proceedings f the 22nd IEEE Conference on Computer Communications (INFOCOM '03), vol. 1, pp. 53-63 (2003).
Baboescu, F., et al., "Packet Classification for Core Routers: Is there an alternative to CAMs?", Proceedings ƒ the 22nd IEEE Conference on Computer Communications (INFOCOM '03), vol. 1, pp. 53-63 (2003).
Fong et al., HaRP: Rapid Packet Classification via Hashing Round-Down Prefixes, IEEE Transactions on Parallel and Distributed Systems, IEEE Service Center, v. 22(7), pp. 1105-1119 (2011).
Gupta, P. and McKeown, N. "Classifying Packets With Hierarchical Intelligent Cuttings," IEEE Micro, 20(1):34-41 (2000).
Gupta, P. and McKeown, N. "Packet Classification on Multiple Fields," Proceedings of SIGCOMM '99 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM '99), pp. 147-160 (1999).
http://en.wikipedia.org/Access-control-list, downloaded Feb. 4, 2011.
http://en.wikipedia.org/Access—control—list, downloaded Feb. 4, 2011.
International Search Report in PCT/LTS2012/049408 dated Dec. 21, 2012, 6 pages, entitled "Packet Classification by an Optimised Decision Tree".
Qi, Y., et al., "Packet Classification Algorithms: From Theory to Practice," Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM '09), pp. 648-656 (2009).
Singh, S., et al., "Packet Classification Using Multidimensional Cutting," Proceedings of the ACMSIGCOMM '03 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM '03), pp. 213-224 (2003).
US20150143060A1 (en) 2015-05-21
US20130039366A1 (en) 2013-02-14
US20130036102A1 (en) 2013-02-07
US20130036285A1 (en) 2013-02-07
US20130060727A1 (en) 2013-03-07
WO2013019981A1 (en) 2013-02-07
US9191321B2 (en) 2015-11-17
US20130036288A1 (en) 2013-02-07
US9137340B2 (en) 2015-09-15
US20150195200A1 (en) 2015-07-09
JP5657840B2 (en) 2015-01-21
US20140188973A1 (en) 2014-07-03
US20130036185A1 (en) 2013-02-07
US20130036274A1 (en) 2013-02-07
US9391892B2 (en) 2016-07-12
US20130036083A1 (en) 2013-02-07
US8711861B2 (en) 2014-04-29
WO2013020001A9 (en) 2013-03-28
US8472452B2 (en) 2013-06-25
US20140215478A1 (en) 2014-07-31
US20130036477A1 (en) 2013-02-07
US9031075B2 (en) 2015-05-12
US9729527B2 (en) 2017-08-08
CN103858392B (en) 2018-12-14
US20150117461A1 (en) 2015-04-30
US9065860B2 (en) 2015-06-23
WO2013020003A1 (en) 2013-02-07
US9497117B2 (en) 2016-11-15
KR20140053272A (en) 2014-05-07
US20130036151A1 (en) 2013-02-07
CN103858386B (en) 2017-08-25
US8937952B2 (en) 2015-01-20
US20130058332A1 (en) 2013-03-07
US8995449B2 (en) 2015-03-31
US20160248739A1 (en) 2016-08-25
US8719331B2 (en) 2014-05-06
US20130036284A1 (en) 2013-02-07
US20130036152A1 (en) 2013-02-07
US20140119378A1 (en) 2014-05-01
US9596222B2 (en) 2017-03-14
US8966152B2 (en) 2015-02-24
US8606959B2 (en) 2013-12-10
US9866540B2 (en) 2018-01-09
KR20140053266A (en) 2014-05-07
US20130036471A1 (en) 2013-02-07
WO2013020002A1 (en) 2013-02-07
US9525630B2 (en) 2016-12-20
US20130034100A1 (en) 2013-02-07
US9531690B2 (en) 2016-12-27
US8934488B2 (en) 2015-01-13
JP2014524688A (en) 2014-09-22
US8954700B2 (en) 2015-02-10
US20130250948A1 (en) 2013-09-26
CN103858392A (en) 2014-06-11
US20130034106A1 (en) 2013-02-07
WO2013019996A1 (en) 2013-02-07
CN103858386A (en) 2014-06-11
US20150121395A1 (en) 2015-04-30
US9225643B2 (en) 2015-12-29
US20130085978A1 (en) 2013-04-04
US10277510B2 (en) 2019-04-30
US9614762B2 (en) 2017-04-04
US20130067173A1 (en) 2013-03-14
WO2013020001A1 (en) 2013-02-07
US9344366B2 (en) 2016-05-17
US9319316B2 (en) 2016-04-19
Qi et al. 2009 Packet classification algorithms: From theory to practice
Liu et al. 2009 TCAM Razor: A systematic approach towards minimizing packet classifiers in TCAMs
Ma et al. 2012 A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification
Fulp 2005 Optimization of network firewall policies using ordered sets and directed acyclical graphs
AU2010297968B2 (en) 2015-06-04 Methods, systems, and computer readable media for adaptive packet filtering
Bienkowski et al. 2003 A practical algorithm for constructing oblivious routing schemes
US7257590B2 (en) 2007-08-14 Method and system for classifying binary strings
US7668160B2 (en) 2010-02-23 Methods for performing packet classification
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GOYAL, RAJAN;BULLIS, KENNETH A.;REEL/FRAME:029568/0893
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:CAVIUM, LLC;REEL/FRAME:051948/0807