Content-based information retrieval architecture

• US 7,019,674 B2
• Filed: 08/02/2004
• Issued: 03/28/2006
• Est. Priority Date: 02/05/2004
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Cadambi, Srihari, Chakradhar, Srimat T., Ashar, Pranav, Kilian, Joseph
• Primary Examiner(s): Jeanglaude, Jean Bruner
• Application Number:
  US10/909,907
• Publication Number:
  US 20050174272A1
• Time in Patent Office: 603 Days
• Field of Search: 341/106, 341/51, 341/63, 341/60, 341/50, 380/286
• US Class Current: 341/106
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459

Abstract

A content-based information retrieval architecture is herein disclosed that can achieve correct and predictable high speed lookups while taking advantage of inexpensive conventional memory components. A content-based information retrieval architecture is herein disclosed that can achieve high speed lookups with a constant query time while taking advantage of inexpensive conventional memory components. In accordance with an embodiment of the invention, the architecture comprise a hashing module, a first table of encoded values, a second table of lookup values, and a third table of associated input values. The input value is hashed a number of times to generate a plurality of hashed values, the hashed values corresponding to locations of encoded values in the first table. The encoded values obtained from an input value encode an output value such that the output value cannot be recovered from any single encoded value.

Claims

1. A content-based information retrieval architecture comprising:

a hashing module that receives an input value and generates a plurality of hashed values from the input value;

a first table storing a plurality of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value;

a second table storing a plurality of lookup values; and

a third table storing a plurality of associated input values in a lookup set, each such input value associated with a lookup value in the second table,

where the first table is constructed so that the encoded values, obtained from the hashed values generated from an input value, encode an output value such that the output value cannot be recovered from any single encoded value and such that the output value selects a lookup value in the second table and an associated input value in the third table, thereby identifying the input value as being in the lookup set if the input value is same as the associated input value in the third table.

2. The information retrieval architecture of claim 1 wherein the encoded values in the first table encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

3. The information retrieval architecture of claim 1 wherein the lookup values are stored at unique addresses in the second table and wherein the first table of encoded values is constructed so that the output value encoded by the plurality of encoded values is an address in the second table.

4. The information retrieval architecture of claim 1 wherein the first table is constructed so that the second table has a size that is smaller than the first table and so that the width of the first table is at least log(n) where n is the number of lookup values.

5. The information retrieval architecture of claim 1 wherein the first table is segmented into a plurality of banks, each bank associated with one of the plurality of hash values generated by the hashing module.

6. The information retrieval architecture of claim 1 wherein the hashing module and the first table are pipelined into different stages from the second and third tables.

7. The information retrieval architecture of claim 1 further comprising a filtering module which receives input values and forwards the input value to the hashing module only if the input value is not a member of a filtered set of input values.

8. The information retrieval architecture of claim 7 wherein the filtered set of input values are those input values that are not recognized as being members of the lookup set of input values.

9. The information retrieval architecture of claim 7 wherein the filtered set of input values are those input values selected so as to facilitate construction of the first table of encoded values.

10. The information retrieval architecture of claim 9 wherein the filtered set of input values comprises at least one input value such that, when the hashing module generates a plurality of hashed values from the one input value, the hashed vlaues generated from the one input value correspond to not one singleton location in the first table of encoded values.

11. The information retrieval architecture of claim 7 wherein at least one input value is remapped by the filtering module into another input value that is then forwarded to the hashing module.

12. The information retrieval architecture of claim 7 wherein at least one input value, that is recognized as not being in the lookup set because the associated input value in the third table is not same as the one input value, is added to the filtered set of input values used by the filtering module.

13. The information retrieval architecture of claim 1 wherein the first table is used to perform indexing into the second table and third table while the third table is used to perform filtering.

14. A network router comprising at least one filter to perform a lookup on information in a packet header, the further thither comprising:

a hashing module that receives the information in the packet header and generates a plurality of hashed values from the information in the packet header; and

a first table storing a plurality of encoded values, each hashed value generated from the information in the packet header corresponding to a location in the first table of an encoded value, the table constructed so that the encoded values obtained from the information in the packet header encode an output value such that the output value cannot be recovered from any single encoded value and such that the output value is used to select forwarding information for the packet header.

15. The network router of claim 14 wherein the encoded values in the first table encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

16. The network router of claim 14 wherein the information in the packet header is a prefix of a pre-specified length.

17. The network router of claim 16 further comprising one or more additional filters for prefixes of different pre-specified lengths, each filter performing lookups in parallel.

18. The network router of claim 17 further comprising an update filter for each filter, the update filter comprising a version of the first table that can be updated offline and swapped for the first table in the filters.

19. The network router of claim 17 further comprising a priority encoder that receives results from each filter and selects forwarding information based on the results from the filter handling a prefix of a longest length.

20. The network router of claim 14 wherein the first table is segmented into a plurality of banks, each bank associated with one of the plurality of hash values generated by the hashing module.

21. The network router of claim 14 wherein the hashing module and the first table are pipelined into different stages.

22. The network router of claim 16 further comprising a filtering module which receives the prefix in the packet header and forwards the prefix to the hashing module only if the prefix is not a member of a filtered set of prefixes.

23. The network router of claim 22 wherein the filtered set of prefixes are those prefixes that are not recognized as being members of a lockup set of prefixes.

24. The network router of claim 22 wherein the filtered set of prefixes are those prefixes selected so as to facilitate construction of the first table of encoded values.

25. The network router of claim 24 wherein the filtered set of prefixes comprises at least one prefix such that, when the hashing module generates a plurality of hashed values from the one prefix, the hashed values generated from the one prefix correspond to not one singleton location in the first table of encoded values.

26. The network router of claim 22 wherein at least one prefix is remapped by the filtering module into another prefix that is then forwarded to the hashing module.

27. The network router of claim 19 further comprising a second table storing the forwarding information as a forwarding value associated with each prefix.

28. The network router of claim 27 wherein each filter has an associated second table.

29. The network router of claim 27 wherein the priority encoder selects the filter handling the prefix of a longest length and then retrieves the forwarding information from a second table shared by the filters.

30. The network router of claim 27 further comprising a third table storing a plurality of associated prefixes in a lookup set, each such associated prefix associated with a forwarding value in the second table, where the output value selects a forwarding value in the second table and an associated prefix from the third table, thereby identifying the prefix in the packet header as being in the lookup set if the prefix in the packet header is same as the associated prefix in the third table.

31. The network router of claim 30 wherein the first table in the filters is constructed so that the second table has a size that is smaller than the first table and so that the width of the first table is at least log(n) where n is the number of forwarding values.

32. The network router of claim 30 further comprising a filtering module which receives the prefix in the packet header and forwards the prefix to the hashing module only if the prefix is not a member of a filtered set of prefixes, wherein at least one prefix, that is recognized as not being in the lookup set because the associated prefixes in the third table is not same as the one input value, is added to the filtered set of prefixes used by the filtering module.

33. A content-based information retrieval architecture comprising:

a hashing module that receives an input value and generates a plurality of hashed values from the input value;

a table storing a plurality of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value, the table segmented into a plurality of banks, each bank associated with one of the plurality of hash values generated by the hashing module, and the table constructed so that the encoded values obtained from the input value encode an output value such that the output value cannot be recovered from any single encoded value.

34. The information retrieval architecture of claim 33 wherein the encoded values encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

35. The information retrieval architecture of claim 33 wherein the table is stored in non-multi-ported memory.

36. A content-based information retrieval architecture comprising:

a hashing unit that receives an input value and generates a plurality of hashed values from the input value;

a memory unit that stores a table of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value; and

a logic unit that recovers an output value from the encoded values, where the encoded values obtained from the input value encode the output value such that the output value cannot be recovered from any single encoded value, and where the hashing unit and the memory unit and the logic unit are pipelined into different stages.

37. The information retrieval architecture of claim 36 wherein the encoded values encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

38. A content-based information retrieval architecture comprising:

a filtering module that receives an input value and forwards the input value only if the input value is not a member of a filtered set of input values;

a hashing module that receives the forwarded input value and generates a plurality of hashed values from the forwarded input value; and

a table storing a plurality of encoded values, each hashed value generated from the forwarded input value corresponding to a location in the table of an encoded value, the table constructed so that the encoded values obtained from the forwarded input value encode an output value such that the output value cannot be recovered from any single encoded value.

39. The information retrieval architecture of claim 38 wherein the filtered set of input values are those input values that are not recognized as being members of a lookup set of input values with associated output values encoded in the table of encoded values.

40. The information retrieval architecture of claim 38 wherein the filtered set of input values are those input values selected so as to facilitate construction of the table of encoded values.

41. The information retrieval architecture of claim 40 wherein the filtered set of input values comprises at least one input value such that, when the hashing module generates a plurality of hashed values from the one input value, the hashed values generated from the one input value correspond to not one singleton location in the table of encoded values.

42. The information retrieval architecture of claim 38 wherein at least one input value is remapped by the filtering module into another input value that is then forwarded to the hashing module.