# US 9,438,561 B2 · Processing of finite automata based on a node cache > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,438,561 B2 - Document ID: US9438561B2 - Status: Granted - Kind: B2 - Application number: 14/252,390 - Filed: 2014-04-14 - Published: 2015-10-15 - Granted: 2016-09-06 - Earliest claimed: 2014-04-14 - Assignees: Cavium, Inc. - Applicants: Cavium, Inc. - Inventors: Rajan Goyal; Satyanarayana Lakshmipathi Billa; Abhishek Dikshit - Web page: https://patentgrep.com/patent/US9438561B2 ## CPC - H04L 63/0209: {Architectural arrangements, e.g. perimeter networks or demilitarized zones} - H04L 43/00: Arrangements for monitoring or testing data switching networks - H04L 63/1408: {by monitoring network traffic (monitoring network traffic per se H04L43/00)} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Nodes of a per-pattern NFA may be stored amongst one or more of a plurality of memories based on a node distribution determined as a function of hierarchical levels mapped to the plurality of memories and per-pattern NFA storage allocation settings configured for the hierarchical levels. At least one processor may be configured to cache one or more nodes of the per-pattern NFA in the node cache based on a cache miss of a given node of the one or more nodes and a hierarchical node transaction size associated with a given hierarchical level mapped to a given memory in which the given node is stored, optimizing run time performance of the walk. ## Claims ### Claim 1 A method comprising: in at least one processor operatively coupled to at least one network interface, a plurality of memories in a memory hierarchy, and a node cache, in a security appliance operatively coupled to a network: storing a plurality of nodes of at least one finite automaton in the plurality of memories for identifying existence of at least one regular expression pattern in an input stream received via the at least one network interface; and caching a given node and one or more additional nodes, of the plurality of nodes, stored in a given memory of the plurality of memories at a hierarchical level in the memory hierarchy, in the node cache based on a cache miss of the given node, the one or more additional nodes cached based on a hierarchical node transaction size associated with the hierarchical level, optimizing match performance of the at least one processor for identifying the existence of the least one regular expression pattern in the input stream. ### Claim 2 (depends on 1) The method of claim 1, wherein the hierarchical node transaction size associated with the hierarchical level denotes a maximum number of nodes to fetch from the given memory at the hierarchical level based on a read access of the given memory by the at least one processor. ### Claim 3 (depends on 1) The method of claim 1, wherein the hierarchical node transaction size associated with the hierarchical level is inversely proportional to a ranking of the hierarchical level in the memory hierarchy and a highest ranked hierarchical level in the memory hierarchy is associated with a smallest hierarchical node transaction size and a lowest ranked hierarchical level in the memory hierarchy is associated with a largest hierarchical node transaction size. ### Claim 4 (depends on 1) The method of claim 1, wherein the memory hierarchy includes multiple hierarchical levels and further comprising: configuring the node cache to store at least a threshold number of nodes of the at least one finite automaton; and denoting the hierarchical node transaction size associated with a lowest ranked hierarchical level of the multiple hierarchical levels to enable the at least one processor to cache the threshold number of nodes. ### Claim 5 (depends on 1) The method of claim 1, wherein the memory hierarchy includes multiple hierarchical levels and wherein caching the one or more nodes includes evicting all nodes cached in the node cache if the given memory is at a lowest ranked hierarchical level of the multiple hierarchical levels. ### Claim 6 (depends on 1) The method of claim 1, wherein the memory hierarchy includes multiple hierarchical levels and wherein caching the one or more nodes includes employing a least recently used (LRU) or round-robin replacement policy to evict one or more cached nodes from the node cache, if the hierarchical level is higher than a lowest ranked hierarchical level of the multiple hierarchical levels, a number of the one or more cache nodes evicted determined based on the hierarchical level. ### Claim 7 (depends on 1) The method of claim 1, wherein the at least one finite automaton includes a per-pattern NFA generated for a respective regular expression pattern and the one or more nodes cached are arranged in a consecutive manner within the per-pattern NFA. ### Claim 8 (depends on 1) The method of claim 1, further including walking the one or more nodes cached with segments of a payload of an input stream to match the respective regular expression pattern in the input stream. ### Claim 9 (depends on 1) The method of claim 1 wherein the memory hierarchy including multiple hierarchical levels; and the plurality of memories includes a first memory, a second memory, and a third memory, the first and second memories co-located on a chip with the at least one processor and the third memory located off the chip and at a lowest ranked hierarchical level of the multiple hierarchical levels. ### Claim 10 A security appliance operatively coupled to a network, the security appliance comprising: at least one network interface; a plurality of memories in a memory hierarchy configured to store a plurality of nodes of at least one finite automaton for identifying existence of at least one regular expression pattern in an input stream received via the at least one network interface; a node cache configured to store at least a threshold number of nodes of the at least one finite automaton; and at least one processor operatively coupled to the at least one network interface, the plurality of memories, and the node cache, and configured to cache a given node and one or more additional nodes, of the plurality of nodes, stored in a given memory of the plurality of memories at a hierarchical level in the memory hierarchy, in the node cache based on a cache miss of the given node, the one or more additional nodes cached based on a hierarchical node transaction size associated with the hierarchical level, optimizing match performance of the at least one processor for identifying the existence of the at least one regular expression pattern in the input stream. ### Claim 11 (depends on 10) The security appliance of claim 10, wherein the hierarchical node transaction size associated with the hierarchical level denotes a maximum number of nodes to fetch from the given memory at the hierarchical level based on a read access of the given memory by the at least one processor. ### Claim 12 (depends on 11) The security appliance of claim 11, wherein the hierarchical node transaction size associated with the hierarchical level is inversely proportional to a ranking of the hierarchical level in the memory hierarchy and a highest ranked hierarchical level in the memory hierarchy is associated with a smallest hierarchical node transaction size and a lowest ranked hierarchical level in the memory hierarchy is associated with a largest hierarchical node transaction size. ### Claim 13 (depends on 10) The security appliance of claim 10, wherein the memory hierarchy includes multiple hierarchical levels and the hierarchical node transaction size associated with a lowest ranked hierarchical level of the multiple hierarchical levels enables the at least one processor to cache the threshold number of nodes. ### Claim 14 (depends on 10) The security appliance of claim 10, wherein the memory hierarchy includes multiple hierarchical levels and to cache the one or more nodes the at least one processor is further configured to evict the threshold number of nodes cached in the node cache if the given memory is at a lowest ranked hierarchical level of the multiple hierarchical levels. ### Claim 15 (depends on 10) The security appliance of claim 10, wherein the memory hierarchy includes multiple hierarchical levels and to cache the one or more nodes the at least one processor is further configured to employ a least recently used (LRU) or round-robin replacement policy to evict one or more cached nodes from the node cache, if the hierarchical level is higher than a lowest ranked hierarchical level of the multiple hierarchical levels, a number of the one or more cache nodes evicted determined based on the hierarchical level. ### Claim 16 (depends on 10) The security appliance of claim 10, wherein the at least one finite automaton includes a per-pattern non-deterministic finite automaton (NFA) generated for a respective regular expression pattern and the one or more nodes cached are arranged in a consecutive manner within the per-pattern NFA. ### Claim 17 (depends on 10) The security appliance of claim 10, wherein the at least one processor is further configured to walk the one or more nodes cached with segments of a payload of an input stream to match the respective regular expression pattern in the input stream. ### Claim 18 (depends on 10) The security appliance of claim 10, wherein the memory hierarchy includes multiple hierarchical levels and the plurality of memories includes a first memory, a second memory, and a third memory, the first and second memories co-located on a chip with the at least one processor and the third memory located off the chip and at a lowest ranked hierarchical level of the multiple hierarchical levels. ### Claim 19 A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, the processor operatively coupled to at least one network interface, a plurality of memories in a memory hierarchy, and a node cache, causes the processor to: store a plurality of nodes of at least one finite automaton in the plurality of memories for identifying existence of at least one regular expression pattern in an input stream received via the at least one network interface; and cache a given node and one or more additional nodes, of the plurality of nodes, stored in a given memory of the plurality of memories at a hierarchical level in the memory hierarchy, in the node cache based on a cache miss of the given node, the one or more additional nodes cached based on a hierarchical node transaction size associated with the hierarchical level, optimizing match performance of the processor for identifying the existence of the at least one regular expression pattern in the input stream.