Mellanox Technologies Tlv Ltd.

Mellanox Technologies, Ltd.

Salvatore Pontarelli

Gil Levy

Pedro Reviriego

Aviv Kfir

Matty Kadosh

Amir Roitshtein

Aviad Levy

Fima Kravchik

Efim Yehiel Kravchik

A network element includes one or more ports and a packet processor. The one or more ports are to transmit and receive packets over a network. The packet processor is to apply a plurality of rules to the packets, each rule specifying (i) expected values for each header field of a group of header fields of the packets, including, for a given header field in the group, at least a set of multiple expected values, (ii) a group ID associated with the set, and (iii) an action to be applied to the packets whose header fields match the expected values.

Optimizing header-based action selection

A hashing apparatus includes a memory and circuitry. The memory stores (i) multiple hash tables storing associative entries, each including at least one entry key and a respective value, the hash tables are associated with respective different hash functions, and an associative entry is accessible by applying the relevant hash function to a key matching an entry key in the associative entry, and (ii) an affinity table that stores table-selectors for selecting hash tables with which to start a key lookup. The circuitry receives a key, reads from the affinity table, by applying an affinity function to the key, a table-selector that selects a hash table, accesses in the selected hash table an associative entry by applying the hash function associated with the selected hash table to the key, and in response to detecting that the key matches an entry key in the associative entry, outputs the respective value.

Cuckoo hashing including accessing hash tables using affinity table

A system includes a memory, including a plurality of memory locations having different respective addresses, and a processor. The processor is configured to compute one of the addresses from (i) a first sequence of bits derived from a tag of a data item, and (ii) a second sequence of bits representing a class of the data item. The processor is further configured to write the data item to the memory location having the computed address and/or read the data item from the memory location having the computed address. Other embodiments are also described.

Virtual splitting of memories

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.

Avoiding markers for longest prefix match based on binary search tree algorithm

A network device includes at least one communication ingress port, ingress packet processing circuitry and a packet-action cache memory (PACM). The at least one communication ingress port is configured to receive packets including packet headers from a network. The ingress packet processing circuitry is configured to receive the packets and to process the packets in accordance with respective packet actions specified for the packets. The PACM is configured to store one or more of the packet actions in association with one or more respective fingerprints which are calculated over the packet headers of the corresponding packets, for use by the ingress packet processing circuitry. The fingerprints are smaller than the corresponding packet headers.

Cache memory management using fingerprints

A collection of rules comprising fields that may have wildcard values. The method includes defining first and second subsets of the fields, the second subset being exclusive of the first subset. Intersections of overlapping fields of the first subset are added to the first subset to form an augmented first subset. Metadata from the augmented first subset and the fields not selected for the first subset are combined to define second parts of the rules. Data items are classified by matching a search key to one of the first parts and one of the second parts of the rules.

Field variability based TCAM splitting

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 hash function is applied to the masked destination address to access a hash table. When the number of most significant bits corresponding to the value in the hash table in one of the cache entries and in the destination address are identical, routing information for the packet is retrieved from the cache entry.

Hash table-based mask length computation for longest prefix match caching

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.

High-performance bloom filter array

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.

Field checking based caching of ACL lookups to ease ACL lookup search

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.

Efficient caching of TCAM rules in RAM

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.

IP route caching with two search stages on prefix length

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.

Jump on a match optimization for longest prefix match using a binary search tree

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.

Efficient matching of TCAM rules using hash tables in RAM

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.

Cuckoo hashing with selectable hash

A method for classification includes extracting respective classification keys from a collection of data items and receiving a corpus of rules for matching to the classification keys. At least some of the rules include masked bits in addition to the unmasked bits. Rule patterns are extracted from the corpus, defining different, respective sequences of masked and unmasked bits to which one or more of the rules conform. The rule patterns are grouped into extended rule patterns, such that the respective set of unmasked bits in any rule pattern is a superset of the unmasked bits in the extended rule pattern into which it is grouped. Rule entries corresponding to the rules are computed using the extended rule patterns and are stored in a random access memory (RAM). The data items are classified by matching the respective classification keys to the rule entries in the RAM.

Growing community of inventors

Rome, Italy

Salvatore Pontarelli