-
公开(公告)号：US20180278525A1
公开(公告)日：2018-09-27
申请号：US15469530
申请日：2017-03-26
发明人： Gil Levy , Pedro Reviriego , Salvatore Pontarelli , Aviv Kfir
IPC分类号： H04L12/741 , H04L29/08
CPC分类号： H04L45/7453 , H04L45/7457 , H04L45/748
摘要： In a network element cache operation is enhanced by extracting a set of fields from a packet, constructing a hash key from the extracted fields, and identifying a subset of the fields, wherein the field values thereof fail to exist in a set of classification rules. The hash key by is modified by masking the subset of the extracted fields. A hash lookup is performed using the modified hash key in a cache memory that stores a portion of the classification rules. The packet is processed responsively to the lookup.
-
公开(公告)号：US10068034B2
公开(公告)日：2018-09-04
申请号：US15257957
申请日：2016-09-07
发明人： Gil Levy , Pedro Reviriego , Salvatore Pontarelli
IPC分类号： G06F17/30 , H04L12/743 , H04L29/06 , G11C7/10
摘要： A method includes extracting classification keys from a collection of data items. A corpus of rules for matching to the classification keys is received, each rule including a respective set of unmasked bits having corresponding bit values, and at least some of the rules also include masked bits. Rule patterns are extracted from the corpus, each rule pattern defining a respective sequence of masked and unmasked bits to which one or more of the rules conforms. Multiple hash tables are defined in a RAM, each is used for searching for a rule that matches a given classification key. A match result of a given rule in a given hash table is also indicative of which of the other hash tables are to be used for subsequent searching. The data items are classified by matching the respective classification keys to the rules using one or more of the hash tables.
-
公开(公告)号：US20170366502A1
公开(公告)日：2017-12-21
申请号：US15186477
申请日：2016-06-19
发明人： Fima Kravchik , Pedro Reviriego , Salvatore Pontarelli , Aviv Kfir , Amir Roitshtein , Gil Levy
IPC分类号： H04L29/12 , H04L29/08 , H04L12/741
CPC分类号： H04L61/6009 , H04L45/54 , H04L45/74 , H04L45/7453 , H04L67/2842
摘要： A data packet is received in a network element. The network element has a cache memory in which cache entries represent a portion of addresses stored in a main memory, The destination address and the cache entries each comprise a binary number. A first determination is made that a number M of the most significant bits of a cache entry and the destination address are identical. A second determination is made that an additional number M+L of the most significant bits of a cache entry and the destination address are identical. Routing information is then retrieved the cache memory, and the packet processed according to the routing information.
-
公开(公告)号：US20170053012A1
公开(公告)日：2017-02-23
申请号：US14827402
申请日：2015-08-17
CPC分类号： G06F16/285 , G06F16/90335 , G06N5/04 , H04L45/7453 , H04L45/7457 , H04L49/3063
摘要： A method for classification includes extracting respective classification keys from a collection of data items and defining a set of patterns for matching to the classification keys. A plurality of memory banks contain respective Bloom filters, each Bloom configured to indicate one or more patterns in the set that are candidates to match a given classification key. A respective first hash function is applied to the classification keys for each pattern in order to select, for each classification key, one of the Bloom filters to query for the pattern. The selected Bloom filters are queried by applying a respective second hash function to each classification key, so as to receive from the Bloom filters an indication of the one or more candidate patterns. The data items are classified by matching the respective classification keys against the candidate patterns.
摘要翻译： 一种用于分类的方法包括从数据项集合中提取相应的分类密钥，并且定义用于匹配分类关键字的一组模式。 多个存储体包含相应的Bloom过滤器，每个Bloom被配置为指示集合中的一个或多个模式，其是与给定分类密钥相匹配的候选。 相应的第一散列函数被应用于每个模式的分类密钥，以便为每个分类密钥选择布隆过滤器之一来查询模式。 通过对每个分类密钥应用相应的第二散列函数来查询所选择的Bloom过滤器，以便从Bloom接收过滤器中的一个或多个候选模式的指示。 通过将各个分类键与候选模式进行匹配来对数据项进行分类。
-
公开(公告)号：US20210359943A1
公开(公告)日：2021-11-18
申请号：US17224208
申请日：2021-04-07
发明人： Gil Levy , Aviv Kfir , Matty Kadosh , Salvatore Pontarelli , Pedro Reviriego
IPC分类号： H04L12/745 , H04L12/743 , H04L12/751 , H04L12/721 , H04L12/717
摘要： In one embodiment, a packet processing apparatus includes interfaces, a memory to store a representation of a routing table as a binary search tree of address prefixes, and store a marker with an embedded prefix including k marker bits providing a marker for an address prefix of a node corresponding to a prefix length greater than k, and n additional bits, such that the k marker bits concatenated with the n additional bits provide another address prefix, packet processing circuitry configured upon receiving a data packet having a destination address, to traverse the binary search tree to find a longest prefix match, compare a key with the k marker bits, extract an additional n bits from the destination address, and compare the extracted n bits with the n additional bits, and process the data packet in accordance with a forwarding action indicated by the longest prefix match.
-
公开(公告)号：US20190036821A1
公开(公告)日：2019-01-31
申请号：US15663758
申请日：2017-07-30
发明人： Gil Levy , Pedro Reviriego , Aviv Kfir , Salvatore Pontarelli
IPC分类号： H04L12/747 , G06F12/0868 , H04L12/743
摘要： Communication apparatus includes a TCAM, which stores a corpus of rules, including respective sets of unmasked and masked bits. The rules conform to respective rule patterns, each defining a different, respective sequence of masked and unmasked bits to which one or more of the rules conform. A RAM caches rule entries corresponding to rules belonging to one or more of the rule patterns that have been selected for caching. Decision logic extracts respective classification keys from data packets, each key including a string of bits extracted from selected fields in a given data packet, and classifies the data packets by first matching the respective classification keys to the cached rule entries in the RAM and, when no match is found in the RAM, by matching the respective classification keys to the rules in the TCAM.
-
公开(公告)号：US10148571B2
公开(公告)日：2018-12-04
申请号：US15186562
申请日：2016-06-20
发明人： Aviv Kfir , Pedro Reviriego , Salvatore Pontarelli , Gil Levy
IPC分类号： H04L12/745 , H04L12/753
摘要： A routing table is represented as a binary search tree ordered by prefix lengths. Markers are placed to guide accessing nodes in designated subtrees to search for a longest prefix match with destination addresses of data packet. Destination descendant nodes in remote hierarchical levels of the tree are associated with the markers. The traversal of the binary search tree is conducted by accessing the respective destination descendant nodes while avoiding accessing nodes in intermediate hierarchical levels. The packet is processed using the longest prefix match.
-
公开(公告)号：US20170286292A1
公开(公告)日：2017-10-05
申请号：US15086095
申请日：2016-03-31
发明人： Gil Levy , Salvatore Pontarelli , Pedro Reviriego
CPC分类号： G06F12/1018 , G06F12/0292 , G06F12/04 , G06F17/3033 , H04L45/7453 , H04L45/7457
摘要： In a network element a decision apparatus has a plurality of multi-way hash tables of single size and double size associative entries. A logic pipeline extracts a search key from each of a sequence of received data items. A hash circuit applies first and second hash functions to the search key to generate first and second indices. A lookup circuit reads associative entries in the hash tables that are indicated respectively by the first and second indices, matches the search key against the associative entries in all the ways. Upon finding a match between the search key and an entry key in an indicated associative entry. A processor uses the value of the indicated associative entry to insert associative entries from a stash of associative entries into the hash tables in accordance with a single size and a double size cuckoo insertion procedure.
-
公开(公告)号：US10476794B2
公开(公告)日：2019-11-12
申请号：US15663758
申请日：2017-07-30
发明人： Gil Levy , Pedro Reviriego , Aviv Kfir , Salvatore Pontarelli
IPC分类号： H04L12/747 , G06F12/0868 , H04L12/743 , H04L29/06 , H04L29/08
摘要： Communication apparatus includes a TCAM, which stores a corpus of rules, including respective sets of unmasked and masked bits. The rules conform to respective rule patterns, each defining a different, respective sequence of masked and unmasked bits to which one or more of the rules conform. A RAM caches rule entries corresponding to rules belonging to one or more of the rule patterns that have been selected for caching. Decision logic extracts respective classification keys from data packets, each key including a string of bits extracted from selected fields in a given data packet, and classifies the data packets by first matching the respective classification keys to the cached rule entries in the RAM and, when no match is found in the RAM, by matching the respective classification keys to the rules in the TCAM.
-
公开(公告)号：US10049126B2
公开(公告)日：2018-08-14
申请号：US14846777
申请日：2015-09-06
发明人： Gil Levy , Pedro Reviriego , Salvatore Pontarelli
IPC分类号： G06F17/30 , H04L12/743
摘要： Decision apparatus includes a first memory bank, containing a first table of hash composition factors, and a second memory bank, containing second and third tables of associative entries. A logic pipeline receives a sequence of data items and extracts a search key from each data item. A pre-hash circuit computes a first index by applying a first hash function to the search key. A first lookup circuit reads a hash composition factor from a location in the first memory bank indicated by the first index, and a hash circuit compute second and third indices as different combinations, determined by the hash composition factor, of second and third hash functions applied by the hash circuit to the search key. A second lookup circuit reads the entries in the second and third tables that are indicated respectively by the second and third indices.
-
-
-
-
-
-
-
-
-
搜索结果
27 条记录 (耗时 0.021 秒)
