METHODS OF HASHING FOR NETWORKS AND SYSTEMS THEREOF

• US 20120136846A1
• Filed: 11/30/2010
• Published: 05/31/2012
• Est. Priority Date: 11/30/2010
• Status: Abandoned Application

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: SONG, Haoyu, KODIALAM, Murali, HAO, Fang, LAKSHMAN, T.V.
• Application Number:
  US12/956,391
• Publication Number:
  US 20120136846A1
• Time in Patent Office: Days
• US Class Current: 707/698
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

Example embodiments are directed to methods of hashing for networks and systems thereof. At least one example embodiment provides a method of processing elements in a system. The method includes receiving a first element, generating a first plurality of hash values based on the first element and a first plurality of hash functions, determining a first plurality of buckets in a table based on the first plurality of hash values, each of the first plurality of buckets associated with a different one of the hash values, selecting one of the first plurality of buckets, storing a first associated value in the selected bucket, the first associated value being associated with the first element, and encoding an identifier (ID) of the hash function generating the hash value associated with the selected bucket into a filter based on the hash value.

Claims

1. A method of processing elements in a system, the method comprising:

receiving, by the system, a first element;

generating, by the system, a first plurality of hash values based on the first element and a first plurality of hash functions;

determining, by the system, a first plurality of buckets in a table based on the first plurality of hash values, each of the first plurality of buckets associated with a different one of the hash values;

selecting, by the system, one of the first plurality of buckets;

storing, by the system, a first associated value in the selected bucket, the first associated value being associated with the first element; and

encoding an identifier (ID) of the hash function generating the hash value associated with the selected bucket into a filter based on the hash value.

2. The method of claim 1, wherein the selecting selects an empty bucket of the first plurality of buckets.

3. The method of claim 1, further comprising:

retrieving a second element and a second associated value from the table based on a look-up request.

4. The method of claim 3, wherein the retrieving includes,

generating a second ID using the filter based on the second element,

determining a second hash value using a hash function indicated by the second ID, and

outputting the second associated value stored in the table in a bucket indexed by the second hash value.

5. The method of claim 4, wherein the retrieving includes,

generating a second plurality of hash values from a second plurality of hash functions based on the look-up request,

selecting one of the second plurality of hash values based on the second ID, and

outputting, by the table, the second associated value based on the selecting.

7. The method of claim 4, wherein the second ID is the first ID if the second element is the first element.

8. The method of claim 4, wherein the generating the second ID includes,

generating a plurality of filter hash values based on the second element and a plurality of filter hash functions, and

filtering the plurality of filter hash values, the second ID being based on the filtering.

9. The method of claim 8, wherein the filter is a Bloom filter.

10. The method of claim 9, wherein the retrieving includes,

generating a second plurality of hash values from a second plurality of hash functions based on the look-up request,

selecting one of the second plurality of hash values based on the second ID, and

outputting, by the table, the second associated value based on the selecting.

11. A method of retrieving elements from a table in a system, the method comprising:

receiving, by the system, a look-up request for a first element;

first determining, by the system, an identifier (ID) based on the look-up request, the ID identifying a hash function used to store the first element and a value associated with the first element;

second determining, by the system, whether the first element is stored in the table based on the ID; and

outputting the first element and the value associated with the first element based on the second determining.

12. The method of claim 11, wherein the first determining includes,

receiving, by the filter, the first element,

generating the ID based on the first element, and

outputting, by the filter, the ID.

13. The method of claim 12, wherein the generating the ID includes,

generating a plurality of filter hash values based on the first element and a plurality of filter hash functions, and

filtering the plurality of filter hash values, the ID being based on the filtering.

14. The method of claim 12, wherein the second determining includes,

generating, by the system, a plurality of hash values based on the first element and the plurality of hash functions, the plurality of hash values being index values for the table, and

selecting one of the plurality of hash values based on the ID.

15. The method of claim 14, wherein the selecting includes,

receiving, at a selector, the ID outputted from the filter.

16. The method of claim 14, wherein the outputting includes,

retrieving the first element and the associated value from the table, the selected hash value being an address of the table having the associated value.

17. The method of claim 16, wherein the retrieving includes,

inspecting only the address having the associated value.

18. A hashing system comprising:

a hash generator configured to receive an element and generate a plurality of hash values based on the element and a plurality of hash functions;

a selector configured to select one of a plurality of buckets in a hash table based on the plurality of hash values, each of the plurality of buckets associated with a different one of the hash values;

the hash table having the plurality of buckets, the hash table configured to store a value associated with the element in the selected bucket; and

a filter configured to encode an identifier (ID) of the hash function generating the hash value associated with the selected bucket.