# US 2019/0171582 A1 · Managing cache memory in a network element based on costs associated with fetching missing cache entries > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0171582 A1 - Document ID: US20190171582A1 - Status: Published application - Kind: A1 - Application number: 15/830,021 - Filed: 2017-12-04 - Published: 2019-06-06 - Earliest claimed: 2017-12-04 - Assignees: Mellanox Technologies Tlv Ltd. - Applicants: Mellanox Technologies TLV Ltd. - Inventors: Gil Levy; Fima Kravchik - Web page: https://patentgrep.com/patent/US20190171582A1 ## CPC - G06F 12/126: with special data handling, e.g. priority of data or instructions, handling errors or pinning - G06F 16/24562: {Pointer or reference processing operations} - G06F 2212/1016: Performance improvement - G06F 2212/1044: Space efficiency improvement - G06F 2212/154: Networked environment - G06F 2212/601: Reconfiguration of cache memory - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A network element includes a data structure, a cache memory and circuitry. The data structure is configured to store multiple rules specifying processing of packets received from a communication network. The cache memory is configured to cache multiple rules including a subset of the rules stored in the data structure. Each rule that is cached in the cache memory has a respective cost value corresponding to a cost of retrieving the rule from the data structure. The circuitry is configured to receive one or more packets from the communication network, to process the received packets in accordance with one or more of the rules, by retrieving the rules from the cache memory when available, or from the data structure otherwise, to select a rule to be evicted from the cache memory, based on one or more respective cost values of the rules currently cached, and to evict the selected rule. ## Claims ### Claim 1 A network element, comprising: a data structure, configured to store multiple rules specifying processing of packets received from a communication network; a cache memory, configured to cache multiple rules comprising a subset of the rules stored in the data structure, wherein each rule that is cached in the cache memory has a respective cost value corresponding to a cost of retrieving the rule from the data structure; and circuitry, configured to: receive one or more packets from the communication network; process the received packets in accordance with one or more of the rules, by retrieving the rules from the cache memory when available, or from the data structure otherwise; select a rule to be evicted from the cache memory, based on one or more respective cost values of the rules currently cached; and evict the selected rule. ### Claim 2 (depends on 1) The network element according to claim 1, wherein the circuitry is configured to retrieve a rule from the data structure, to cache the retrieved rule in the cache memory, and to store a respective cost value in association with the rule cached. ### Claim 3 (depends on 1) The network element according to claim 1, wherein the cost value comprises a function of an actual number of memory-access operations required to perform a lookup operation of the respective rule in the data structure. ### Claim 4 (depends on 3) The network element according to claim 3, wherein the cost value comprises two or more cost levels corresponding to a quantized version of the actual number of memory-access operations. ### Claim 5 (depends on 1) The network element according to claim 1, wherein the cost value of a given rule comprises a latency incurred in retrieving the given rule from the data structure. ### Claim 6 (depends on 1) The network element according to claim 1, wherein the circuitry is configured to select from the cache memory multiple candidate rules for which the respective cost values fall within a predefined range of cost values, and to select the rule to be evicted from among the candidate rules. ### Claim 7 (depends on 1) The network element according to claim 1, wherein the circuitry is configured to select from the cache memory multiple candidate rules, independently of the cost values, and to select the rule to be evicted, from among the candidate rules, based on the respective cost values of the candidate rules. ### Claim 8 (depends on 1) The network element according to claim 1, wherein the circuitry is configured to select the rule to be evicted randomly, with a predefined probability. ### Claim 9 (depends on 1) The network element according to claim 1, wherein the circuitry is configured to assign to the rules currently cached respective eviction attributes, to select from the cache memory multiple candidate rules based on the assigned eviction attributes, to calculate for the candidate rules respective combined costs as a function of the respective cost values and eviction attributes, and to select the rule to be evicted based on the combined costs. ### Claim 10 (depends on 1) The network element according to claim 1, wherein the circuitry is configured to estimate the cost of retrieving a given rule from the data structure, and to determine the respective cost value based on the estimated cost. ### Claim 11 A method, comprising: in a network element, storing in a data structure multiple rules specifying processing of packets received from a communication network; caching in a cache memory multiple rules comprising a subset of the rules stored in the data structure, wherein each rule that is cached in the cache memory has a respective cost value corresponding to a cost of retrieving the rule from the data structure; receiving one or more packets from the communication network, and processing the received packets in accordance with one or more of the rules, by retrieving the rules from the cache memory when available, or from the data structure otherwise; selecting a rule to be evicted from the cache memory, based on one or more respective cost values of the rules currently cached; and evicting the selected rule. ### Claim 12 (depends on 11) The method according to claim 11, and comprising retrieving a rule from the data structure, caching the retrieved rule in the cache memory, and storing a respective cost value in association with the rule cached. ### Claim 13 (depends on 11) The method according to claim 11, wherein the cost value comprises a function of an actual number of memory-access operations required to perform a lookup operation of the respective rule in the data structure. ### Claim 14 (depends on 13) The method according to claim 13, wherein the cost value comprises two or more cost levels corresponding to a quantized version of the actual number of memory-access operations. ### Claim 15 (depends on 11) The method according to claim 11, wherein the cost value of a given rule comprises a latency incurred in retrieving the given rule from the data structure. ### Claim 16 (depends on 11) The method according to claim 11, wherein the circuitry is configured to select from the cache memory multiple candidate rules for which the respective cost values fall within a predefined range of cost values, and to select the rule to be evicted from among the candidate rules. ### Claim 17 (depends on 11) The method according to claim 11, wherein selecting the rule to be evicted comprises selecting from the cache memory multiple candidate rules, independently of the cost values, and selecting the rule to be evicted, from among the candidate rules, based on the respective cost values of the candidate rules. ### Claim 18 (depends on 11) The method according to claim 11, wherein selecting the rule to be evicted comprises selecting the rule to be evicted randomly, with a predefined probability. ### Claim 19 (depends on 11) The method according to claim 11, and comprising assigning to the rules currently cached respective eviction attributes, wherein selecting the rule to be evicted comprises selecting from the cache memory multiple candidate rules based on the assigned eviction attributes, calculating for the candidate rules respective combined costs as a function of the respective cost values and eviction attributes, and selecting the rule to be evicted based on the combined costs. ### Claim 20 (depends on 11) The method according to claim 11, wherein and comprising estimating the cost of retrieving a given rule from the data structure, and determining the respective cost value based on the estimated cost.