Data matching based on hash table representations of hash tables

Patent metadata

Field	Value
Publication number	US-2015242429-A1
Application number	US-201414189119-A
Country	US
Kind code	A1
Filing date	Feb 25, 2014
Priority date	Feb 25, 2014
Publication date	Aug 27, 2015
Grant date	—

Abstract

A data matching capability is presented herein. The data matching capability may be configured to support matching of a set of values of a set of data fields to a corresponding set of values of a corresponding set of data fields. The data matching capability may be configured to support matching of a set of values of a set of data fields to a corresponding set of values of a corresponding set of data fields based on use of the set of values of the set of data fields as an input and based on a hash table representation of a hash table storing the corresponding set of values of the corresponding set of data fields. The data matching capability may be used within various contexts including packet classification within telecommunication networks.

First claim

What is claimed is:

1 . An apparatus configured to match data using a set of hash functions, comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
receive a data set including a set of data fields having a respective set of data values associated therewith;
compute, for each of the hash functions, a respective set of hash values for the data set by hashing each of the data values of the data set using the respective hash function;
compute a set of hash bits for the data set based on the respective sets of hash values for the data set; and
determine whether a hash table potentially includes a match for the data set by checking a hash table representation of the hash table based on the set of hash bits for the data set.

2 . The apparatus of claim 1 , wherein, to compute the set of hash bits for the data set based on the respective sets of hash values for the data set, the processor is configured to:
for each set of hash values, compute the respective hash bit of the set of hash bits based on a concatenation of the hash values of the set of hash values.

3 . The apparatus of claim 2 , wherein, to compute the respective hash bit of the set of hash bits based on the concatenation of the hash values of the set of hash values, the processor is configured to:
concatenate the hash values of the set of hash values to form a concatenation of the hash values; and compute the respective hash bit for the set of hash values by performing a modulo m operation on the concatenation of the hash values, wherein m comprises a size of the hash table representation.

4 . The apparatus of claim 1 , wherein, to compute the set of hash bits for the data set based on the respective sets of hash values for the data set, the processor is configured to:
for each set of hash values, mask a descriptor of a class associated with the hash table with the set of hash values to form a respective set of masked hash values associated with the respective hash values of the set of hash values; and for each set of masked hash values, compute the respective hash bit of the set of hash bits for the set of hash values based on a concatenation of the masked hash values of the set of masked hash values.

5 . The apparatus of claim 4 , wherein the descriptor comprises a set of descriptor fields, wherein, to mask the descriptor of the class associated with the hash table with the set of hash values to form the set of masked hash values, the processor is configured to:
for each of the descriptor fields of the descriptor, perform a logical AND between the descriptor field of the descriptor and a corresponding one of the hash values associated with the descriptor field of the descriptor.

6 . The apparatus of claim 4 , wherein, to compute the respective hash bit of the set of hash bits based on a concatenation of the masked hash values of the set of masked hash values, the processor is configured to:
concatenate the masked hash values of the set of masked hash values to form a concatenation of the masked hash values; and compute the respective hash bit for the set of hash values by performing a modulo m operation on the concatenation of the masked hash values, wherein m comprises a size of the hash table representation.

7 . The apparatus of claim 1 , wherein, to compute the set of hash bits for the data set based on the respective sets of hash values for the data set, the processor is configured to:
for each set of hash values:
concatenate the hash values of the set of hash values to form a concatenation of the hash values; and
compute the respective hash bit for the set of hash values by performing a modulo m operation on the concatenation of the hash values, wherein m comprises a size of the hash table representation.

8 . The apparatus of claim 1 , wherein the processor is configured to:
based on a determination that the set of hash bits matches the hash table representation, search the hash table for an entry matching the data set.

9 . The apparatus of claim 1 , wherein the hash table is a first hash table associated with a first data class, the processor further configured to:
determine whether a second hash table associated with a second data class potentially includes a match for the data set by checking a second hash table representation of the second hash table based on the set of hash bits for the data set.

10 . The apparatus of claim 1 , wherein the data set comprises a tuple of a packet, wherein the hash table is configured to store a set of packet classification rules.

11 . A method for matching data using a set of hash functions, the method comprising:
using a processor and a memory for:
receiving a data set including a set of data fields having a respective set of data values associated therewith;
computing, for each of the hash functions, a respective set of hash values for the data set by hashing each of the data values of the data set using the respective hash function;
computing a set of hash bits for the data set based on the respective sets of hash values for the data set; and
determining whether a hash table potentially includes a match for the data set by checking a hash table representation of the hash table based on the set of hash bits for the data set.

12 . The method of claim 11 , wherein computing the set of hash bits for the data set based on the respective sets of hash values for the data set comprises:
for each set of hash values, computing the respective hash bit of the set of hash bits based on a concatenation of the hash values of the set of hash values.

13 . The method of claim 12 , wherein computing the respective hash bit of the set of hash bits based on the concatenation of the hash values of the set of hash values comprises:
concatenating the hash values of the set of hash values to form a concatenation of the hash values; and computing the respective hash bit for the set of hash values by performing a modulo m operation on the concatenation of the hash values, wherein m comprises a size of the hash table representation.

14 . The method of claim 11 , wherein computing the set of hash bits for the data set based on the respective sets of hash values for the data set comprises:
for each set of hash values, masking a descriptor of a class associated with the hash table with the set of hash values to form a respective set of masked hash values associated with the respective hash values of the set of hash values; and for each set of masked hash values, computing the respective hash bit of the set of hash bits for the set of hash values based on a concatenation of the masked hash values of the set of masked hash values.

15 . The method of claim 14 , wherein the descriptor comprises a set of descriptor fields, wherein masking the descriptor of the class associated with the hash table with the set of hash values to form the set of masked hash values comprises:
for each of the descriptor fields of the descriptor, performing a logical AND between the descriptor field of the descriptor and a corresponding one of the hash values associated with the descriptor field of the descriptor.

16 . The method of claim 14 , wherein computing the respective hash bit of the set of hash bits based on a concatenation of the masked hash values of the set of masked hash values comprises:
concatenating the masked hash values of the set of masked hash values to form a concatenation of the masked hash values; and computing the respective hash bit for the set of hash values by performing a modulo m operation on t

Assignees

• Alcatel Lucent

Inventors

• Varvello Matteo
• Perino Diego

Classifications

• H04L45/7453 Primary

  using hashing · CPC title

• G06F17/30109 Primary

  Physics · mapped topic

• G06F17/30864

  Physics · mapped topic

• G06F17/3033

  Physics · mapped topic

• G06F17/3053

  Physics · mapped topic