[go: up one dir, main page]

EP2944059A1 - High performance hash-based lookup for packet processing in a communication network - Google Patents

High performance hash-based lookup for packet processing in a communication network

Info

Publication number
EP2944059A1
EP2944059A1 EP14702080.4A EP14702080A EP2944059A1 EP 2944059 A1 EP2944059 A1 EP 2944059A1 EP 14702080 A EP14702080 A EP 14702080A EP 2944059 A1 EP2944059 A1 EP 2944059A1
Authority
EP
European Patent Office
Prior art keywords
hash
search key
signature
bucket
packet processing
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
EP14702080.4A
Other languages
German (de)
French (fr)
Other versions
EP2944059B1 (en
Inventor
Prashant Anand
Ashish Anand
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Telefonaktiebolaget LM Ericsson AB
Original Assignee
Telefonaktiebolaget LM Ericsson AB
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Telefonaktiebolaget LM Ericsson AB filed Critical Telefonaktiebolaget LM Ericsson AB
Publication of EP2944059A1 publication Critical patent/EP2944059A1/en
Application granted granted Critical
Publication of EP2944059B1 publication Critical patent/EP2944059B1/en
Not-in-force legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup; Address filtering
    • H04L45/7453—Address table lookup; Address filtering using hashing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS
    • H04L47/2441—Traffic characterised by specific attributes, e.g. priority or QoS relying on flow classification, e.g. using integrated services [IntServ]

Definitions

  • the present invention relates generally to flow-based packet processing in a packet-switched network and, more particularly, to hash-based lookup tables for determining rules applied by a packet processing node to different packet flows.
  • each packet flow is associated with a unique flow identifier.
  • the flow identifier is hashed by a hashing function to generate a hash key.
  • the hash key is associated with one or more rules and is stored in a hash table.
  • the hash table is stored in an external memory, such as a DDR3 SDRAM.
  • the hash-based lookup function compares the search key with each entry in the hash table until a match is found. This process may require many memory accesses, and each memory access adds to the processing delay. In a high speed packet processing node, it is generally desirable to reduce these delays as much as possible.
  • the hash table may be divided into a plurality of buckets.
  • Each bucket comprises a plurality of hash entries forming a hash chain.
  • Flow identifiers are assigned to buckets in a deterministic manner. Therefore, the packet processing node needs to search a single bucket to find a matching hash entry. In this case, the number of memory accesses is dependent on the link of the hash chains in each hash bucket. Even when hash buckets are used, the packet processing node may need to access the memory multiple times to perform a lookup. Therefore, new techniques that reduce or minimize the number of memory accesses required to perform a data lookup are needed.
  • the present invention relates to methods and apparatus for performing a lookup on a hash table stored in external memory.
  • the hash table is divided into a plurality of buckets. Each bucket comprises a plurality of hash entries. Each hash entry contains a hash key and associated data.
  • An index table stored in local memory is used to perform an enhanced lookup on the hash table.
  • the index table stores signature patterns that are derived from the hash keys stored in the hash entries. Using the stored signature patterns, the packet processing node predicts which hash key is likely to store the desired data. The prediction may yield a false positive, but will never yield a false negative. As a result, the hash table is accessed only once during a data lookup.
  • Exemplary embodiments of the invention comprise a method, implemented by a packet processing node in a packet-switched network, for performing a data lookup on a hash table.
  • One exemplary method comprises a packet containing a flow identifier is received and a full search key is generated from the flow identifier.
  • a corresponding hash bucket in the hash table is determined based on the full search key.
  • the bit locations of signature bits in the full search key are determined.
  • a compressed search key is created from the signature bits in the full search key.
  • a hash entry index for a target hash entry in the hash bucket is predicted by comparing the compressed search key to signature patterns that are mapped one-to-one to hash entries in the hash bucket.
  • the target hash entry comprises a hash key and associated data.
  • a data lookup is performed by comparing the full search key to the hash key in the target hash entry.
  • the packet processing node comprises an interface circuit for receiving a packet containing a flow identifier, and a control unit for processing the packet.
  • the control unit is configured to generate a full search key from the flow identifier and to determine a corresponding hash bucket in a hash table based on the full search key.
  • the control determines bit locations, for the corresponding hash bucket, of signature bits in the full search key and creates a compressed search key from the signature bits in the full search key.
  • the control unit predicts a hash entry index for a target hash entry in the hash bucket by comparing the compressed search key to signature patterns that are mapped one-to-one to hash entries in the hash bucket.
  • the target hash entry comprises a hash key and associated data.
  • the control unit then performs a data lookup on the hash table by comparing the full search key to the hash key in the target hash entry.
  • Embodiments of the present invention allow faster hash lookups to be performed by reducing the number of times the external memory needs to be accessed to perform the lookup.
  • the index table used for performing enhanced hash lookup as herein described can be stored in internal registers, LI cash, or L2 cash, which can be accessed in fewer processing cycles than the external memory. Even with additional processing instructions, the enhanced lookup can be performed in significantly less times than a conventional lookup.
  • Fig. 1 illustrates an exemplary packet processing node according to an exemplary embodiment.
  • Fig. 2 illustrates data structures for performing a lookup on a hash table according to an exemplary embodiment.
  • Fig. 3 illustrates an exemplary method of performing a lookup on a hash table according to an exemplary embodiment.
  • Fig. 4 illustrates the main processing components for performing a lookup on a hash table according to an exemplary embodiment.
  • Fig. 5 illustrates an exemplary method for determining a type of lookup to perform according to an exemplary embodiment.
  • Fig. 6 illustrates an enhance lookup method according to an exemplary embodiment.
  • Fig. 7 illustrates an exemplary method for computing signature patterns according to an exemplary embodiment.
  • Fig. 8 illustrates an exemplary method of adding entries to a hash table according to an exemplary embodiment.
  • Fig. 9 illustrates an exemplary method of deleting entries from a hash table according to an exemplary embodiment.
  • Fig. 1 illustrates the main functional elements in a packet processing node 10 according to one exemplary embodiment.
  • the packet processing node comprises an interface circuit 15 including an input circuit 20 and output circuit 25, a control unit 30, a local memory 35, and an external memory 40.
  • the interface circuit 15 connects the packet processing node 10 to a communication network.
  • the interface circuit 15 may comprise, for example, an Ethernet interface or other IP-based interface.
  • the control unit 30 controls the operation of the packet processing node 10 as hereinafter described.
  • the control unit 30 may comprise one or more processors, microcontrollers, hardware circuits, firmware, or a combination thereof.
  • the local memory 35 may comprise register files, LI cache, L2 cache or another memory array in a microprocessor.
  • the local memory 35 is used to store an index table 48 (Fig. 2) for performing hash-based lookups as hereinafter described.
  • the control unit 30 and local memory 35 are embodied in a single microprocessor.
  • the external memory 40 may comprise a random access memory (RAM), read-only memory (ROM), Flash memory, or other type of memory that is external to the control unit 30.
  • the external memory 40 is used to store a hash table 42 (Fig. 2) that contains the rules or other data for processing different packet flows.
  • the external memory 40 may, for example, comprise a synchronous dynamic RAM (SDRAM), such as a DDR3 SDRAM.
  • SDRAM synchronous dynamic RAM
  • Fig. 2 illustrates the data structures used to perform the hash-based lookup in one exemplary embodiment.
  • the data structures include a hash table 42 that is stored in external memory 40 and an index table 48 that is preferably stored in local memory 35.
  • the hash table 42 is divided into a plurality of hash buckets 44.
  • Each hash bucket 44 contains a plurality of hash entries 46 that are logically connected to form a hash chain.
  • Each hash entry 46 contains a hash key and associated data.
  • Each hash key stored in the hash table 42 is derived by hashing the flow identifier for a packet flow with a hash function.
  • the associated data is used by the packet processing node 10 to process data packets belonging to the corresponding packet flow. Ideally, the associated data is distributed evenly across the hash buckets 44. Given the hash key and number of buckets (i.e., bucket array size), a bucket index may be computed as follows:
  • INDEX HASH _ KEY% ARRAY _ SIZE Eq. (2) where % denoted the modulo function and ARRAY SIZE denotes the number of buckets.
  • Eq (2) functions as a mapping algorithm to map the hash key to a particular bucket.
  • the index computed according to Eq. 2 identifies the hash bucket 44 where associated data for a given packet flow, if it exists, is stored.
  • the packet processing node 10 When a packet flow arrives at the packet processing node 10, the packet processing node 10 computes a full search key according to Eq. (1) and computes a bucket index according to Eq. (2).
  • the bucket index indicates the hash bucket 44 where desired data, if it exists, is stored.
  • the packet processing node 10 performs a data lookup by searching for a matching hash entry 46 in the identified hash bucket 44 identified beginning with the first hash entry 46 and continuing until a match is found.
  • the packet processing node 10 traverses the hash chain 48 in the identified hash bucket 44 and compares the computed hash key with the stored hash key in each hash entry 46 until a match is found.
  • Each compare operation requires that the packet processing node 10 retrieve the hash entry 46 from external memory.
  • the average number of memory accesses to perform a data lookup is proportional to the length of the hash chain.
  • Each comparison operation increases the costs of a data lookup in terms of time and processing resources.
  • the index table 48 is used to perform an enhanced data lookup.
  • the index table 48 may, in some embodiments, be stored in local memory 35, which can be accessed in fewer processing cycles as compared to external memory 40.
  • the index table 48 stores signature patterns that are derived from the hash keys stored in the hash entries 46. As will be described in greater detail below, certain bits designated as signature bits in each hash key are used to compute the signature pattern for the hash entry 46. Using the stored signature patterns, the packet processing node 10 predicts which hash key 46 is likely to store the desired data. The prediction may yield a false positive, but will never yield a false negative.
  • the packet processing node 10 retrieves the predicted hash entry 46 from external memory and compares the full search key computed according to Eq. (1) to the hash key in the predicted hash entry 46. If the search key matches the stored hash key, the search is successful. If the search key does not match the stored hash key, then the desired data is not stored in the hash table 42.
  • the hash table 42 is accessed only once during a data lookup. As a result, the index table 48 significantly reduces the time and processing resources required to perform a fast data lookup.
  • Fig. 2 illustrates the structure of the index table 48 in one embodiment.
  • the index table 48 stores, for each hash bucket 44, a control bit, a plurality of bit indices, and a plurality of signature patterns corresponding to the hash entries 46 in the hash bucket 44.
  • the control bit indicates whether enhanced lookup is enabled.
  • the bit indices indicate the bit locations of signature bits used to compute signature patterns.
  • the signature patterns are used for comparison with a compressed search key to predict the hash entry 46 where desired data is stored.
  • Fig. 3 illustrates a general method 100 implemented by the packet processing node 10 for performing a enhanced lookup according to an exemplary embodiment.
  • the process begins when a packet is received by the packet processing node 10 (block 105).
  • the packet processing node 10 extracts a flow identifier form the received packet and generates a full search key from the flow identifier (block 110).
  • the full search key may be computed according to Eq. (1).
  • the packet processing node 10 uses the full search key to determine a hash bucket 44 where the desired data, if it exists, is stored (block 115).
  • the hash bucket 44 may be determined by computing a bucket index according to Eq (2).
  • Eq (2) functions as a mapping algorithm to map the full search key to a particular bucket.
  • the packet processing node 10 then creates a compressed search key (block 120).
  • the compressed search key comprises selected bits in the full search key.
  • the packet processing node 10 uses the compressed search key to predict the hash entry 46 containing the desired data (block 125). The prediction may yield a false positive, but will never yield a false negative.
  • the packet processing node 10 then performs a data lookup by comparing the full search key to the hash key stored in the predicted hash entry 46 (block 130).
  • Fig. 4 illustrates the main processing components of the control circuit 30 in one exemplary embodiment that are involved in performing lookups on the hash table 42.
  • the main processing components include a hash calculator 45, key generator 50, index calculator 55, lookup circuit 60, memory controller 65, and comparison circuit 70.
  • the processing components shown in Fig, 4 may be implemented by software, hardware, or a combination thereof.
  • the flow identifier (FI) is extracted from the incoming packet and input to the hash calculator 45.
  • the hash calculator 45 computes a full search key (SK) using a hash function, such as the MD5 and SUA hashing algorithms.
  • the full search key (SK) is input to the key generator 50 and index calculator 55.
  • the full search key (SK) may be computed, for example, according to Eq. (2).
  • the index calculator 55 computes a bucket index (BI) based on the full search key (SK).
  • the key generator 50 computes a compressed search key (CSK) from the full search key (SK).
  • the bucket index (BI) provided by the index calculator 55 is used to lookup the bit indices for the signature bits, which are stored in the index table 48 in local memory 35.
  • the signature bits are extracted from the full search key (SK) and combined to form the compressed search key (CSK).
  • SK full search key
  • CSK compressed search key
  • the compressed search key (CSK) in this example is "100" (which corresponds to the 30th, 28th and 31st bits in the full search key above).
  • the compressed search key (CSK) is provide to the lookup circuit 60.
  • the lookup circuit 60 compares the compressed search key (CSK) to the signature bit patterns for the hash bucket 44 indicated by the bucket index (BI). If a match is found, the lookup circuit 60 outputs the hash entry index (I) that identifies an hash entry 46 in the hash bucket BI.
  • the memory controller 65 accesses the external memory 40 to retrieve the hash entry 46 identified by the pair ⁇ BI, I ⁇ .
  • the comparison circuit 70 compares the full search key to the hash key for the retrieved hash entry. If the full search key (SK) matches the hash key, the search is successful. Otherwise, the search fails.
  • the packet processing node 10 can be configured to perform both a normal lookup and an enhanced lookup.
  • a different type of lookup may be performed depending on the hash bucket 44.
  • the enhanced lookup may be disabled if the signature patterns for two hash entries 46 are the same.
  • the index table 48 may store a control bit to indicate the type of lookup to be performed.
  • the control bit can be set to a value of "1" to indicate that an enhanced lookup should be used, and to set a value of "0" to indicate that a normal lookup should be used.
  • Fig. 5 illustrates an exemplary method 150 implemented by a packet processing node 10 for determining the type of lookup to perform.
  • the packet processing node 10 extracts the flow identifier from the packet header (block 155), computes the full search key (block 160), and determines the hash bucket 44 to be searched by computing a hash bucket index (block 165).
  • the packet processing node 10 determines what type of lookup to perform by checking the control bit from the index table (block 175).
  • the packet processing node 10 accesses the index table 48 to determine if the enhanced lookup method is enabled (block 180). If so, the packet processing node 10 performs an enhanced lookup (block 190). If enhanced lookup is not enabled, the packet processing node 10 performs a normal lookup (block 195).
  • Fig. 6 illustrates a enhanced lookup method 200 performed at block 190 when the enhanced lookup is enabled.
  • the packet processing node 10 determines the location of the signature bits (block 205). The bit locations for the signature bits are stored in the index table 48. The packet processing node 10 then extracts the signature bits from the search key and combines the signature bits to obtain a compressed search key (block 210). In one embodiment, the signature bits are combined to form the compressed search key. After the compressed search key is obtained, the packet processing node 10 searches the index table 48 for a matching signature pattern (block 215). A match indicates a hash entry 46 in the hash bucket 44 that is predicted to contain the desired data. At block 220, the packet processing node determines whether a match is found in the index table 48.
  • the search fails (block 245). If a match is found in the index table 48, the packet processing node 10 retrieves the predicted hash entry 46 from the hash table 42 in external memory (block 225) and compares the full search key to the hash key stored in the hash entry 46 (block 230). At block 235, the packet processing node 10 determines whether the search key matches the stored hash key (block 235). If the search key matches the stored hash key, the search is successful (block 240). Otherwise the search fails (block 245).
  • Fig. 7 illustrates an exemplary method 300 for computing the signature patterns for hash entries 46 in a hash bucket 44.
  • the packet processing node 10 identifies the signature bits (block 310). To identify the signature bits, the packet processing node 10 sorts the hash keys for the hash entries 46 in a given hash bucket in ascending order (block 320). After sorting, the packet processing node 10 computes a set of differentiating bit sequences by computing the exclusive or (XOR) of consecutive ones of the hash keys (block 330). For example, the XOR of the first and second hash keys is computed to get a first differentiating bit sequence. The XOR of the second and third hash keys is then computed to get a second differentiating bit sequence.
  • XOR exclusive or
  • the packet processing node 10 identifies the bit location in each differentiating bit sequence of the most significant bit (MSB) that is set to "1" (block 340). These bit locations are used to determine the signature bits in each hash key. Finally, the packet processing node 10 computes the signature patterns for each hash entry 46 by extracting and concatenating the signature bits in each hash key (block 350).
  • MSB most significant bit
  • hash bucket 44 contains 4 hash entries 46 with the following 32-bit hash keys (HKs):
  • Hash Key 1 00000100 00100101 00000000 00000000
  • Hash Key 2 00100000 00101000 00000000 00000000
  • Hash Key 3 00101000 00101100 00000000 00000000
  • the hash keys are already sorted in ascending order.
  • the packet processing node 10 computes the XOR of consecutive hash keys to obtain the following differentiating bit sequences: Sequence 1 00100100 00001101 00000000 00000000
  • the MSB set to "1" is bit 30.
  • the MSB set to "1” is bit 28.
  • the MSB set to "1” is bit 31. Therefore, the signature bits are given by the triplet ⁇ 30, 28, 31 ⁇ . These bit locations are stored in the index table 48.
  • the packet processing node 10 After determining the signature bits, the packet processing node 10 computes the signature pattern for each hash entry 46 by extracting and combining the signature bits in the hash keys.
  • the signature patterns are as follows:
  • FIG. 8 shows an exemplary method 400 for adding hash entries 46 to a hash table 42 stored in external memory 40. It is assumed that the flow identifier and associated data are given.
  • the packet processing node 10 computes a hash key for a new hash entry from the flow identifier using a hash function (block 405).
  • the packet processing node 10 determines whether the hash key already exists in the hash table 42 (block 410). The enhanced lookup procedures herein described may be used to search for the hash key. If the hash key exists, the process ends (block 430).
  • the packet processing node creates a new hash entry 46 and inserts it into the hash table 42 (block 415). After inserting the hash entry, new signature bit locations and signature patterns are computed (block 420). The new signature bit locations and signature patterns are then stored in the index table (block 425) and the process ends (block 430).
  • Fig. 9 illustrates an exemplary method 450 for deleting a hash entry 46 from the hash table 42. It is assumed that a flow identifier is given.
  • the packet processing node 10 computes a hash key for the hash entry 46 to be deleted (block 455).
  • the packet processing node 10 searches the hash table 42 to determine whether a matching hash entry 46 exists (block 460).
  • the enhanced lookup procedures herein described may be used to search for the hash key. If no matching hash entry 46 is found, the process ends (block 480). If a matching hash entry 46 is found, the matching hash entry 46 is deleted (block 465).
  • the packet processing node 10 then computes new signature bit locations and signatures patterns based on the remaining hash entries 46 in the hash bucket 44 (block 470). Finally, the packet processing node 10 updates the index table (block 475) and the process ends (block 480).
  • Embodiments of the present invention allow faster hash lookups to be performed by reducing the number of times the external memory needs to be accessed to perform the lookup.
  • the index table 48 used for performing enhanced hash lookup as herein described can be stored in internal registers, LI cache, or L2 cache, which can be accessed in fewer processing cycles than the external memory. Even with additional processing instructions, the enhanced lookup can be performed in significantly less times than a conventional lookup.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Computer And Data Communications (AREA)

Abstract

The present invention relates to methods s and apparatus (10) for performing a lookup on a hash table (42) stored in external memory (40). An index table (48) stored in local memory (35) is used to perform an enhanced lookup on the hash table (42) stored in external memory (40). The index table (48) stores signature patterns that are derived from the hash keys stored in the hash entries. Using the stored signature patterns, the packet processing node (10) predicts which hash key is likely to store the desired data. The prediction may yield a false positive, but will never yield a false negative. Thus, the hash table (42) is accessed only once during a data lookup.

Description

HIGH PERFORMANCE HASH-BASED LOOKUP FOR PACKET PROCESSING IN A COMMUNICATION NETWORK
TECHNICAL FIELD
The present invention relates generally to flow-based packet processing in a packet-switched network and, more particularly, to hash-based lookup tables for determining rules applied by a packet processing node to different packet flows.
BACKGROUND
In software defined networks, and in policy-based fourth generation (4G) wireless communication networks, there is an increasing demand for flow-based packet processing, flow-based policy enforcement, and flow level isolation. In such networks, different roles may be applied to different packet flows. When a packet arrives at a packet processing node, the packet processing node needs to determine the appropriate rule set to apply to the packet flow. It is known to use a hash table to look up the rules to apply to a given packet flow. In general, each packet flow is associated with a unique flow identifier. The flow identifier is hashed by a hashing function to generate a hash key. The hash key is associated with one or more rules and is stored in a hash table. When a packet arrives at the packet processing node, the packet processing node extracts the flow identifier from the packet, hashes the flow identifier to obtain a search key, and uses the search key to look up the rules to apply to the packet flow.
Typically, the hash table is stored in an external memory, such as a DDR3 SDRAM. The hash-based lookup function compares the search key with each entry in the hash table until a match is found. This process may require many memory accesses, and each memory access adds to the processing delay. In a high speed packet processing node, it is generally desirable to reduce these delays as much as possible.
Various techniques are known to speed up the lookup operation on a hash table. For example, the hash table may be divided into a plurality of buckets. Each bucket comprises a plurality of hash entries forming a hash chain. Flow identifiers are assigned to buckets in a deterministic manner. Therefore, the packet processing node needs to search a single bucket to find a matching hash entry. In this case, the number of memory accesses is dependent on the link of the hash chains in each hash bucket. Even when hash buckets are used, the packet processing node may need to access the memory multiple times to perform a lookup. Therefore, new techniques that reduce or minimize the number of memory accesses required to perform a data lookup are needed.
SUMMARY
The present invention relates to methods and apparatus for performing a lookup on a hash table stored in external memory. The hash table is divided into a plurality of buckets. Each bucket comprises a plurality of hash entries. Each hash entry contains a hash key and associated data. An index table stored in local memory is used to perform an enhanced lookup on the hash table. The index table stores signature patterns that are derived from the hash keys stored in the hash entries. Using the stored signature patterns, the packet processing node predicts which hash key is likely to store the desired data. The prediction may yield a false positive, but will never yield a false negative. As a result, the hash table is accessed only once during a data lookup.
Exemplary embodiments of the invention comprise a method, implemented by a packet processing node in a packet-switched network, for performing a data lookup on a hash table. One exemplary method comprises a packet containing a flow identifier is received and a full search key is generated from the flow identifier. A corresponding hash bucket in the hash table is determined based on the full search key. The bit locations of signature bits in the full search key are determined. A compressed search key is created from the signature bits in the full search key. A hash entry index for a target hash entry in the hash bucket is predicted by comparing the compressed search key to signature patterns that are mapped one-to-one to hash entries in the hash bucket. The target hash entry comprises a hash key and associated data. A data lookup is performed by comparing the full search key to the hash key in the target hash entry.
Other embodiments of the invention comprise a packet processing node configured to perform a data lookup on a hash table. In one exemplary embodiment, the packet processing node comprises an interface circuit for receiving a packet containing a flow identifier, and a control unit for processing the packet. The control unit is configured to generate a full search key from the flow identifier and to determine a corresponding hash bucket in a hash table based on the full search key. The control determines bit locations, for the corresponding hash bucket, of signature bits in the full search key and creates a compressed search key from the signature bits in the full search key. The control unit predicts a hash entry index for a target hash entry in the hash bucket by comparing the compressed search key to signature patterns that are mapped one-to-one to hash entries in the hash bucket. The target hash entry comprises a hash key and associated data. The control unit then performs a data lookup on the hash table by comparing the full search key to the hash key in the target hash entry.
Embodiments of the present invention allow faster hash lookups to be performed by reducing the number of times the external memory needs to be accessed to perform the lookup. The index table used for performing enhanced hash lookup as herein described can be stored in internal registers, LI cash, or L2 cash, which can be accessed in fewer processing cycles than the external memory. Even with additional processing instructions, the enhanced lookup can be performed in significantly less times than a conventional lookup.
BRIEF DESCRIPTION OF THE DRAWINGS
Fig. 1 illustrates an exemplary packet processing node according to an exemplary embodiment.
Fig. 2 illustrates data structures for performing a lookup on a hash table according to an exemplary embodiment.
Fig. 3 illustrates an exemplary method of performing a lookup on a hash table according to an exemplary embodiment.
Fig. 4 illustrates the main processing components for performing a lookup on a hash table according to an exemplary embodiment.
Fig. 5 illustrates an exemplary method for determining a type of lookup to perform according to an exemplary embodiment.
Fig. 6 illustrates an enhance lookup method according to an exemplary embodiment.
Fig. 7 illustrates an exemplary method for computing signature patterns according to an exemplary embodiment.
Fig. 8 illustrates an exemplary method of adding entries to a hash table according to an exemplary embodiment. Fig. 9 illustrates an exemplary method of deleting entries from a hash table according to an exemplary embodiment.
DETAILED DESCRIPTION
Referring now to the drawings, Fig. 1 illustrates the main functional elements in a packet processing node 10 according to one exemplary embodiment. The packet processing node comprises an interface circuit 15 including an input circuit 20 and output circuit 25, a control unit 30, a local memory 35, and an external memory 40. The interface circuit 15 connects the packet processing node 10 to a communication network. The interface circuit 15 may comprise, for example, an Ethernet interface or other IP-based interface. The control unit 30 controls the operation of the packet processing node 10 as hereinafter described. The control unit 30 may comprise one or more processors, microcontrollers, hardware circuits, firmware, or a combination thereof. The local memory 35 may comprise register files, LI cache, L2 cache or another memory array in a microprocessor. The local memory 35 is used to store an index table 48 (Fig. 2) for performing hash-based lookups as hereinafter described. In one exemplary embodiment, the control unit 30 and local memory 35 are embodied in a single microprocessor. The external memory 40 may comprise a random access memory (RAM), read-only memory (ROM), Flash memory, or other type of memory that is external to the control unit 30. The external memory 40 is used to store a hash table 42 (Fig. 2) that contains the rules or other data for processing different packet flows. The external memory 40 may, for example, comprise a synchronous dynamic RAM (SDRAM), such as a DDR3 SDRAM.
Fig. 2 illustrates the data structures used to perform the hash-based lookup in one exemplary embodiment. The data structures include a hash table 42 that is stored in external memory 40 and an index table 48 that is preferably stored in local memory 35. The hash table 42 is divided into a plurality of hash buckets 44. Each hash bucket 44 contains a plurality of hash entries 46 that are logically connected to form a hash chain. Each hash entry 46 contains a hash key and associated data.
Each hash key stored in the hash table 42 is derived by hashing the flow identifier for a packet flow with a hash function. The hash key for a given packet flow is given by: HASH _KEY = HASH (FLOW _ID) Eq. (1) where FLOW ID is the flow identifier for the packet flow. The associated data is used by the packet processing node 10 to process data packets belonging to the corresponding packet flow. Ideally, the associated data is distributed evenly across the hash buckets 44. Given the hash key and number of buckets (i.e., bucket array size), a bucket index may be computed as follows:
INDEX = HASH _ KEY% ARRAY _ SIZE Eq. (2) where % denoted the modulo function and ARRAY SIZE denotes the number of buckets. Eq (2) functions as a mapping algorithm to map the hash key to a particular bucket. The index computed according to Eq. 2 identifies the hash bucket 44 where associated data for a given packet flow, if it exists, is stored.
When a packet flow arrives at the packet processing node 10, the packet processing node 10 computes a full search key according to Eq. (1) and computes a bucket index according to Eq. (2). The bucket index indicates the hash bucket 44 where desired data, if it exists, is stored. In conventional packet processing, the packet processing node 10 performs a data lookup by searching for a matching hash entry 46 in the identified hash bucket 44 identified beginning with the first hash entry 46 and continuing until a match is found. The packet processing node 10 traverses the hash chain 48 in the identified hash bucket 44 and compares the computed hash key with the stored hash key in each hash entry 46 until a match is found. Each compare operation requires that the packet processing node 10 retrieve the hash entry 46 from external memory. The average number of memory accesses to perform a data lookup is proportional to the length of the hash chain. Each comparison operation increases the costs of a data lookup in terms of time and processing resources.
In exemplary embodiments of the present invention, the index table 48 is used to perform an enhanced data lookup. The index table 48 may, in some embodiments, be stored in local memory 35, which can be accessed in fewer processing cycles as compared to external memory 40. The index table 48 stores signature patterns that are derived from the hash keys stored in the hash entries 46. As will be described in greater detail below, certain bits designated as signature bits in each hash key are used to compute the signature pattern for the hash entry 46. Using the stored signature patterns, the packet processing node 10 predicts which hash key 46 is likely to store the desired data. The prediction may yield a false positive, but will never yield a false negative. Based on the prediction, the packet processing node 10 retrieves the predicted hash entry 46 from external memory and compares the full search key computed according to Eq. (1) to the hash key in the predicted hash entry 46. If the search key matches the stored hash key, the search is successful. If the search key does not match the stored hash key, then the desired data is not stored in the hash table 42. In embodiments of the present invention, the hash table 42 is accessed only once during a data lookup. As a result, the index table 48 significantly reduces the time and processing resources required to perform a fast data lookup.
Fig. 2 illustrates the structure of the index table 48 in one embodiment. In the exemplary embodiment shown in Fig. 2, the index table 48 stores, for each hash bucket 44, a control bit, a plurality of bit indices, and a plurality of signature patterns corresponding to the hash entries 46 in the hash bucket 44. The control bit indicates whether enhanced lookup is enabled. The bit indices indicate the bit locations of signature bits used to compute signature patterns. The signature patterns are used for comparison with a compressed search key to predict the hash entry 46 where desired data is stored.
Fig. 3 illustrates a general method 100 implemented by the packet processing node 10 for performing a enhanced lookup according to an exemplary embodiment. The process begins when a packet is received by the packet processing node 10 (block 105). The packet processing node 10 extracts a flow identifier form the received packet and generates a full search key from the flow identifier (block 110). The full search key may be computed according to Eq. (1). The packet processing node 10 uses the full search key to determine a hash bucket 44 where the desired data, if it exists, is stored (block 115). The hash bucket 44 may be determined by computing a bucket index according to Eq (2). Eq (2) functions as a mapping algorithm to map the full search key to a particular bucket. The packet processing node 10 then creates a compressed search key (block 120). In one exemplary embodiment, the compressed search key comprises selected bits in the full search key. The packet processing node 10 uses the compressed search key to predict the hash entry 46 containing the desired data (block 125). The prediction may yield a false positive, but will never yield a false negative. The packet processing node 10 then performs a data lookup by comparing the full search key to the hash key stored in the predicted hash entry 46 (block 130).
Fig. 4 illustrates the main processing components of the control circuit 30 in one exemplary embodiment that are involved in performing lookups on the hash table 42. The main processing components include a hash calculator 45, key generator 50, index calculator 55, lookup circuit 60, memory controller 65, and comparison circuit 70. The processing components shown in Fig, 4 may be implemented by software, hardware, or a combination thereof.
When a packet arrives at the packet processing node 10, the flow identifier (FI) is extracted from the incoming packet and input to the hash calculator 45. The hash calculator 45 computes a full search key (SK) using a hash function, such as the MD5 and SUA hashing algorithms. The full search key (SK) is input to the key generator 50 and index calculator 55. The full search key (SK) may be computed, for example, according to Eq. (2). The index calculator 55 computes a bucket index (BI) based on the full search key (SK). The key generator 50 computes a compressed search key (CSK) from the full search key (SK). The bucket index (BI) provided by the index calculator 55 is used to lookup the bit indices for the signature bits, which are stored in the index table 48 in local memory 35. The signature bits are extracted from the full search key (SK) and combined to form the compressed search key (CSK). As an example, assume that the full search key (SK) is four bytes long and is given by:
00100000 00101000 00000000 00000000 and that the bit indices for the signature bits are {30, 28, 31 } . In this example, the first signature bit indicates the most significant bit. The compressed search key (CSK) in this example is "100" (which corresponds to the 30th, 28th and 31st bits in the full search key above). The compressed search key (CSK) is provide to the lookup circuit 60. The lookup circuit 60 compares the compressed search key (CSK) to the signature bit patterns for the hash bucket 44 indicated by the bucket index (BI). If a match is found, the lookup circuit 60 outputs the hash entry index (I) that identifies an hash entry 46 in the hash bucket BI. The memory controller 65 accesses the external memory 40 to retrieve the hash entry 46 identified by the pair {BI, I} . The comparison circuit 70 compares the full search key to the hash key for the retrieved hash entry. If the full search key (SK) matches the hash key, the search is successful. Otherwise, the search fails.
In some embodiments, the packet processing node 10 can be configured to perform both a normal lookup and an enhanced lookup. A different type of lookup may be performed depending on the hash bucket 44. For example, the enhanced lookup may be disabled if the signature patterns for two hash entries 46 are the same. As previously noted, the index table 48 may store a control bit to indicate the type of lookup to be performed. For example, the control bit can be set to a value of "1" to indicate that an enhanced lookup should be used, and to set a value of "0" to indicate that a normal lookup should be used.
Fig. 5 illustrates an exemplary method 150 implemented by a packet processing node 10 for determining the type of lookup to perform. When a packet arrives at the packet processing node 10, the packet processing node 10 extracts the flow identifier from the packet header (block 155), computes the full search key (block 160), and determines the hash bucket 44 to be searched by computing a hash bucket index (block 165). Before continuing the data lookup, the packet processing node 10 determines what type of lookup to perform by checking the control bit from the index table (block 175). After the hash bucket 44 is identified, the packet processing node 10 accesses the index table 48 to determine if the enhanced lookup method is enabled (block 180). If so, the packet processing node 10 performs an enhanced lookup (block 190). If enhanced lookup is not enabled, the packet processing node 10 performs a normal lookup (block 195).
Fig. 6 illustrates a enhanced lookup method 200 performed at block 190 when the enhanced lookup is enabled. The packet processing node 10 determines the location of the signature bits (block 205). The bit locations for the signature bits are stored in the index table 48. The packet processing node 10 then extracts the signature bits from the search key and combines the signature bits to obtain a compressed search key (block 210). In one embodiment, the signature bits are combined to form the compressed search key. After the compressed search key is obtained, the packet processing node 10 searches the index table 48 for a matching signature pattern (block 215). A match indicates a hash entry 46 in the hash bucket 44 that is predicted to contain the desired data. At block 220, the packet processing node determines whether a match is found in the index table 48. If no match is found, the search fails (block 245). If a match is found in the index table 48, the packet processing node 10 retrieves the predicted hash entry 46 from the hash table 42 in external memory (block 225) and compares the full search key to the hash key stored in the hash entry 46 (block 230). At block 235, the packet processing node 10 determines whether the search key matches the stored hash key (block 235). If the search key matches the stored hash key, the search is successful (block 240). Otherwise the search fails (block 245).
Fig. 7 illustrates an exemplary method 300 for computing the signature patterns for hash entries 46 in a hash bucket 44. The packet processing node 10 identifies the signature bits (block 310). To identify the signature bits, the packet processing node 10 sorts the hash keys for the hash entries 46 in a given hash bucket in ascending order (block 320). After sorting, the packet processing node 10 computes a set of differentiating bit sequences by computing the exclusive or (XOR) of consecutive ones of the hash keys (block 330). For example, the XOR of the first and second hash keys is computed to get a first differentiating bit sequence. The XOR of the second and third hash keys is then computed to get a second differentiating bit sequence. This process continues until the last final hash key is reached. It will be appreciated that the number of differentiating bit sequences will be one less than the number of hash keys. The packet processing node 10 then identifies the bit location in each differentiating bit sequence of the most significant bit (MSB) that is set to "1" (block 340). These bit locations are used to determine the signature bits in each hash key. Finally, the packet processing node 10 computes the signature patterns for each hash entry 46 by extracting and concatenating the signature bits in each hash key (block 350).
As an example, assume that the hash bucket 44 contains 4 hash entries 46 with the following 32-bit hash keys (HKs):
Hash Key 1 00000100 00100101 00000000 00000000
Hash Key 2 00100000 00101000 00000000 00000000
Hash Key 3 00101000 00101100 00000000 00000000
Hash Key 4 01001000 00101101 11001100 01010100
In this example, the hash keys are already sorted in ascending order. The packet processing node 10 computes the XOR of consecutive hash keys to obtain the following differentiating bit sequences: Sequence 1 00100100 00001101 00000000 00000000
Sequence 2 00001000 00000100 00000000 00000000
Sequence 3 01100000 00000001 11001100 01010100
For Sequence 1, the MSB set to "1" is bit 30. For Sequence 2, the MSB set to "1" is bit 28. And for Sequence 3, the MSB set to "1" is bit 31. Therefore, the signature bits are given by the triplet {30, 28, 31} . These bit locations are stored in the index table 48.
After determining the signature bits, the packet processing node 10 computes the signature pattern for each hash entry 46 by extracting and combining the signature bits in the hash keys. In this example, based on the triplet {30, 28, 31 } corresponding to the 30th, 28th and 31st bits of each hash key (see the bold and underlined digits above) the signature patterns are as follows:
Signature Pattern 1 000
Signature Pattern 2 100
Signature Pattern 3 110
Signature Pattern 4 101
These signature patterns are stored in the index table 48.
Those skilled in the art will appreciate that the bit locations and signature bits need to be recomputed whenever a new hash entry 46 is entered into a hash bucket 44. Fig. 8 shows an exemplary method 400 for adding hash entries 46 to a hash table 42 stored in external memory 40. It is assumed that the flow identifier and associated data are given. The packet processing node 10 computes a hash key for a new hash entry from the flow identifier using a hash function (block 405). The packet processing node 10 then determines whether the hash key already exists in the hash table 42 (block 410). The enhanced lookup procedures herein described may be used to search for the hash key. If the hash key exists, the process ends (block 430). If no matching entry 46 is found, the packet processing node creates a new hash entry 46 and inserts it into the hash table 42 (block 415). After inserting the hash entry, new signature bit locations and signature patterns are computed (block 420). The new signature bit locations and signature patterns are then stored in the index table (block 425) and the process ends (block 430).
Fig. 9 illustrates an exemplary method 450 for deleting a hash entry 46 from the hash table 42. It is assumed that a flow identifier is given. The packet processing node 10 computes a hash key for the hash entry 46 to be deleted (block 455). The packet processing node 10 searches the hash table 42 to determine whether a matching hash entry 46 exists (block 460). The enhanced lookup procedures herein described may be used to search for the hash key. If no matching hash entry 46 is found, the process ends (block 480). If a matching hash entry 46 is found, the matching hash entry 46 is deleted (block 465). The packet processing node 10 then computes new signature bit locations and signatures patterns based on the remaining hash entries 46 in the hash bucket 44 (block 470). Finally, the packet processing node 10 updates the index table (block 475) and the process ends (block 480).
Embodiments of the present invention allow faster hash lookups to be performed by reducing the number of times the external memory needs to be accessed to perform the lookup. The index table 48 used for performing enhanced hash lookup as herein described can be stored in internal registers, LI cache, or L2 cache, which can be accessed in fewer processing cycles than the external memory. Even with additional processing instructions, the enhanced lookup can be performed in significantly less times than a conventional lookup.
Thus, the foregoing description and the accompanying drawings represent non- limiting examples of the methods and apparatus taught herein. As such, the present invention is not limited by the foregoing description and accompanying drawings. Instead, the present invention is limited only by the following claims and their legal equivalents.

Claims

CLAIMS What is claimed is:
1. A method (100), implemented by a packet processing node (10) in a packet- switched network, for performing a data lookup on a hash table (42), said method (100) comprising:
receiving (105) a packet containing a flow identifier;
generating (110) a full search key from the flow identifier;
determining (115) a corresponding hash bucket in said hash table (42) based on the full search key;
said method characterized by:
creating (120) a compressed search key from signature bits extracted from predetermined bit location in the full search key;
predicting (125) a hash entry index for a target hash entry in the hash bucket by comparing the compressed search key to signature patterns that are mapped one-to-one to hash entries in the hash bucket, wherein the target hash entry comprises a hash key and associated data; and
performing (130) said data lookup by comparing the full search key to the hash key in the target hash entry.
2. The method (100) of claim 1 wherein generating (110) a full search key from the flow identifier comprises hashing the flow identifier with a hash function.
3. The method (100) of claim 1 further comprising, for each hash bucket in the hash table (42), storing the bit locations for the signature bits and the signature patterns for the hash entries in the hash bucket in an index table (48).
4. The method (100) of claim 3 wherein determining (115) a corresponding hash bucket in a hash table (42) based on the full search key comprises computing a hash bucket index from the full search key as a function of the hash bucket size.
5. The method (100) of claim 4 further comprising determining the bit locations of signature bits in the full search key using the hash bucket index to lookup the bit locations in the index table (48).
6. The method (100) of claim 3 further comprising storing the index table (48) in a local memory (35).
7. The method (100) of claim 1 further comprising pre-computing the signature patterns for the hash entries and storing the pre-computed signature patterns in an index table (48).
8. The method (100) of claim 7 wherein pre-computing the signature patterns comprises:
computing the bit locations for the signature bits based on the hash entries in the hash bucket; and
computing signature patterns for each hash entry based on the signature bits in the hash entry.
9. The method (100) of claim 8 wherein computing the bit locations for the signature bits based on the hash entries in the hash bucket comprises:
sorting the hash keys for the hash entries in a hash bucket in ascending order; computing the exclusive or (XOR) of consecutive ones of said hash keys to obtain a set of differentiating bit sequences;
identifying the bit location of the most significant bit in each differentiating bit sequence.
10. The method (100) of claim 1 further comprising:
storing the bit locations of the signature bits and the signature patterns in a local memory (35); and
storing the hash table (42) in an external memory (40).
11. A packet processing node (10) in a communication network, said packet processing node (10) comprising:
an interface circuit (15) for receiving a packet containing a flow identifier; a control unit (30) for processing the packet, said control unit configured to: generate a full search key from the flow identifier;
determine a corresponding hash bucket in a hash table (42) based on the full search key;
said control unit (30) characterized by being configured to:
create a compressed search key from signature bits extracted from predetermined bit locations in the full search key;
predict a hash entry index for a target hash entry in the hash bucket by compare the compressed search key to signature patterns that are mapped
one-to-one to hash entries in the hash bucket, wherein the target hash
entry comprises a hash key and associated data; and
perform a data lookup by comparing the full search key to the hash key in the target hash entry.
12. The packet processing node (10) of claim 11 wherein the control unit is configured to hash the flow identifier with a hash function to generate the search key.
13. The packet processing node (10) of claim 11 wherein the control unit (30) is further configured to, for each hash bucket in the hash table (42), store the bit locations for the signature bits and the signature patterns for the hash entries in the hash bucket in an index table (48).
14. The packet processing node (10) of claim 13 wherein the control unit (30) is configured to determine a corresponding hash bucket in a hash table (42) based on the full search key by computing a hash bucket index from the full search key as a function of the hash bucket size.
15. The packet processing node (10) of claim 14 wherein the control unit (30) is further configured to determine the bit locations of the signature bits in the full search key by using the hash bucket index to lookup the bit locations in the index table (48).
16. The packet processing node (10) of claim 13 wherein the control unit (30) is configured to store the index table (48) in a local memory (35).
17. The packet processing node (10) of claim 11 wherein the control unit (30) is configured to pre-compute the signature patterns for the hash entries and store the pre- computed signature patterns in an index table (48).
18. The packet processing node (10) of claim 17 wherein the control unit (30) is configured to pre-compute the signature patterns by:
computing the bit locations for the signature bits based on the hash entries in the hash
bucket; and
computing signature patterns for each hash entry based on the signature bits in the
hash entry.
19. The packet processing node (10) of claim 18 wherein the control unit (30) is configured to compute the bit locations for the signature bits based on the hash entries in the hash bucket by:
sorting the hash keys for the hash entries in a hash bucket in ascending order; computing the exclusive or (XOR) of consecutive ones of said hash keys to obtain a set
of differentiating bit sequences;
identifying the bit location of the most significant bit in each differentiating bit sequence.
20. The packet processing node (10) of claim 11 wherein the control unit (30) is configured to: store the bit locations of the signature bits and the signature patterns in a local memory (35); and
store the hash table (42) in an external memory (40).
EP14702080.4A 2013-01-10 2014-01-06 High performance hash-based lookup for packet processing in a communication network Not-in-force EP2944059B1 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US13/738,316 US9009165B2 (en) 2013-01-10 2013-01-10 High performance hash-based lookup for packet processing in a communication network
PCT/IB2014/058078 WO2014108822A1 (en) 2013-01-10 2014-01-06 High performance hash-based lookup for packet processing in a communication network

Publications (2)

Publication Number Publication Date
EP2944059A1 true EP2944059A1 (en) 2015-11-18
EP2944059B1 EP2944059B1 (en) 2018-08-01

Family

ID=50030392

Family Applications (1)

Application Number Title Priority Date Filing Date
EP14702080.4A Not-in-force EP2944059B1 (en) 2013-01-10 2014-01-06 High performance hash-based lookup for packet processing in a communication network

Country Status (4)

Country Link
US (1) US9009165B2 (en)
EP (1) EP2944059B1 (en)
CN (1) CN104904167B (en)
WO (1) WO2014108822A1 (en)

Families Citing this family (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2012117471A1 (en) * 2011-03-01 2012-09-07 日本電気株式会社 Virtual server system, management server device, and system management method
US20140215094A1 (en) * 2013-01-29 2014-07-31 Anders Nordin Method and system for data compression
JP6273780B2 (en) * 2013-11-06 2018-02-07 富士通株式会社 Transmission apparatus, transmission method, and transmission program
US9769290B2 (en) * 2014-05-23 2017-09-19 Intel Corporation Packet flow classification
US10063487B2 (en) * 2014-12-30 2018-08-28 Cisco Technology, Inc. Pattern matching values of a packet which may result in false-positive matches
US20160241474A1 (en) * 2015-02-12 2016-08-18 Ren Wang Technologies for modular forwarding table scalability
US10924403B2 (en) 2015-07-21 2021-02-16 Hewlett Packard Enterprise Development Lp Using a single cache table
US10019382B2 (en) * 2015-10-20 2018-07-10 Sap Se Secondary data structures for storage class memory (scm) enables main-memory databases
EP3516540B1 (en) * 2016-09-22 2024-07-17 Visa International Service Association Techniques for in-memory data searching
US11392600B2 (en) 2016-09-22 2022-07-19 Visa International Service Association Techniques for in memory key range searches
US10462059B2 (en) 2016-10-19 2019-10-29 Intel Corporation Hash table entries insertion method and apparatus using virtual buckets
US10394784B2 (en) 2016-12-22 2019-08-27 Intel Corporation Technologies for management of lookup tables
KR102509913B1 (en) * 2017-01-25 2023-03-14 삼성전자주식회사 Method and apparatus for maximized dedupable memory
US11310158B2 (en) * 2017-12-08 2022-04-19 Corsa Technology Inc. Packet classification using fingerprint hash table
CN109189808B (en) * 2018-09-18 2021-08-31 腾讯科技（深圳）有限公司 Data query method and related equipment
EP3906645A4 (en) * 2019-01-04 2022-06-01 Proofpoint, Inc. SYSTEM AND METHOD FOR SCALABLE FILE FILTERING USING WILDLIFE
CN110516121A (en) * 2019-08-28 2019-11-29 中国银行股份有限公司 Method for reading data and device
US12007971B2 (en) * 2020-04-27 2024-06-11 Sap Se Pageable hash index for document store
US11416462B2 (en) * 2020-07-13 2022-08-16 EMC IP Holding Company LLC Techniques for efficient data deduplication
CN113449159B (en) * 2021-06-29 2024-02-02 乐视云网络技术(北京)有限公司 Node data processing method, device, equipment and computer readable storage medium
CN115525650A (en) * 2022-09-16 2022-12-27 山东云海国创云计算装备产业创新中心有限公司 Method, device, equipment and medium for improving Hash lookup performance
CN118981174B (en) * 2024-07-29 2025-08-12 苏州新施诺半导体设备有限公司 Input/output service systems and overhead crane systems in industrial control

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7103794B2 (en) * 1998-06-08 2006-09-05 Cacheflow, Inc. Network object cache engine
US6067547A (en) * 1997-08-12 2000-05-23 Microsoft Corporation Hash table expansion and contraction for use with internal searching
US6567817B1 (en) * 2000-09-08 2003-05-20 Hewlett-Packard Development Company, L.P. Cache management system using hashing
US8370936B2 (en) * 2002-02-08 2013-02-05 Juniper Networks, Inc. Multi-method gateway-based network security systems and methods
US7116664B2 (en) 2002-05-13 2006-10-03 International Business Machines Corporation Lookups by collisionless direct tables and CAMs
US7356033B2 (en) * 2002-11-21 2008-04-08 Lucent Technologies Inc. Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures
US8271564B2 (en) * 2008-07-14 2012-09-18 Symbol Technologies, Inc. Lookup table arrangement and related management method for accommodating concurrent processors
CN101350788B (en) * 2008-08-25 2011-10-26 中兴通讯股份有限公司 Method for mixed loop-up table of network processor inside and outside
US8212695B2 (en) * 2009-02-05 2012-07-03 Polytechnic Institute Of New York University Generating a log-log hash-based hierarchical data structure associated with a plurality of known arbitrary-length bit strings used for detecting whether an arbitrary-length bit string input matches one of a plurality of known arbitrary-length bit strings
US8321385B2 (en) 2010-03-12 2012-11-27 Lsi Corporation Hash processing in a network communications processor architecture

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO2014108822A1 *

Also Published As

Publication number Publication date
US9009165B2 (en) 2015-04-14
CN104904167B (en) 2018-02-13
WO2014108822A1 (en) 2014-07-17
CN104904167A (en) 2015-09-09
EP2944059B1 (en) 2018-08-01
US20140195545A1 (en) 2014-07-10

Similar Documents

Publication Publication Date Title
US9009165B2 (en) High performance hash-based lookup for packet processing in a communication network
US11102120B2 (en) Storing keys with variable sizes in a multi-bank database
US20210367887A1 (en) Flow classification apparatus, methods, and systems
JP4614946B2 (en) System and method for efficiently searching a forwarding database divided into a limited number of sub-databases having a limited size
CN105122745B (en) Efficient Longest Prefix Matching Technique for Network Devices
US6665297B1 (en) Network routing table
CN104866502B (en) Data matching method and device
KR100962653B1 (en) Method and apparatus for searching IP address using bloom filter and multiple hashing structure
US20040255045A1 (en) IP address lookup method and hardware architecture using hashing
US20030204703A1 (en) Multi-pass hierarchical pattern matching
JP5960863B1 (en) SEARCH DEVICE, SEARCH METHOD, PROGRAM, AND RECORDING MEDIUM
CN108287840B (en) A Data Storage and Query Method Based on Matrix Hash
US11182365B2 (en) Systems and methods for distributed storage of data across multiple hash tables
CN101140592A (en) Keyword storage, search method and device
US20200228449A1 (en) Exact match and ternary content addressable memory (tcam) hybrid lookup for network device
US20140019486A1 (en) Logic Content Processing for Hardware Acceleration of Multi-Pattern Search
US6731633B1 (en) Network unit including address hashing
CN101594319A (en) Table item lookup method and device
WO2016184029A1 (en) Storage and lookup methods and apparatuses supporting hash lookup and routing lookup, and storage medium
US10997140B2 (en) Method and apparatus for acceleration of hash-based lookup
KR101587756B1 (en) Apparatus and method for searching string data using bloom filter pre-searching
CN108093024B (en) Classified routing method and device based on data frequency
CN110191057B (en) Route searching method and route equipment
JP6205463B2 (en) SEARCH DEVICE, SEARCH METHOD, PROGRAM, AND RECORDING MEDIUM

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20150720

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR

AX Request for extension of the european patent

Extension state: BA ME

DAX Request for extension of the european patent (deleted)
STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: EXAMINATION IS IN PROGRESS

17Q First examination report despatched

Effective date: 20170321

REG Reference to a national code

Ref country code: DE

Ref legal event code: R079

Ref document number: 602014029464

Country of ref document: DE

Free format text: PREVIOUS MAIN CLASS: H04L0012741000

Ipc: G06F0017300000

RIC1 Information provided on ipc code assigned before grant

Ipc: H04L 12/851 20130101ALI20180329BHEP

Ipc: H04L 12/743 20130101ALI20180329BHEP

Ipc: G06F 17/30 20060101AFI20180329BHEP

GRAP Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOSNIGR1

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: GRANT OF PATENT IS INTENDED

INTG Intention to grant announced

Effective date: 20180507

RIN1 Information on inventor provided before grant (corrected)

Inventor name: ANAND, PRASHANT

Inventor name: ANAND, ASHISH

GRAS Grant fee paid

Free format text: ORIGINAL CODE: EPIDOSNIGR3

GRAA (expected) grant

Free format text: ORIGINAL CODE: 0009210

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE PATENT HAS BEEN GRANTED

AK Designated contracting states

Kind code of ref document: B1

Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR

REG Reference to a national code

Ref country code: GB

Ref legal event code: FG4D

REG Reference to a national code

Ref country code: CH

Ref legal event code: EP

Ref country code: AT

Ref legal event code: REF

Ref document number: 1025132

Country of ref document: AT

Kind code of ref document: T

Effective date: 20180815

REG Reference to a national code

Ref country code: IE

Ref legal event code: FG4D

REG Reference to a national code

Ref country code: DE

Ref legal event code: R096

Ref document number: 602014029464

Country of ref document: DE

REG Reference to a national code

Ref country code: DE

Ref legal event code: R079

Ref document number: 602014029464

Country of ref document: DE

Free format text: PREVIOUS MAIN CLASS: G06F0017300000

Ipc: G06F0016000000

REG Reference to a national code

Ref country code: NL

Ref legal event code: MP

Effective date: 20180801

REG Reference to a national code

Ref country code: LT

Ref legal event code: MG4D

REG Reference to a national code

Ref country code: AT

Ref legal event code: MK05

Ref document number: 1025132

Country of ref document: AT

Kind code of ref document: T

Effective date: 20180801

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: IS

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20181201

Ref country code: RS

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: NL

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: PL

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: LT

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: GR

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20181102

Ref country code: FI

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: SE

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: NO

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20181101

Ref country code: BG

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20181101

Ref country code: AT

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: HR

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: LV

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: AL

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: RO

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: IT

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: CZ

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: EE

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: ES

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

REG Reference to a national code

Ref country code: DE

Ref legal event code: R097

Ref document number: 602014029464

Country of ref document: DE

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: SK

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: SM

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: DK

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

PLBE No opposition filed within time limit

Free format text: ORIGINAL CODE: 0009261

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: NO OPPOSITION FILED WITHIN TIME LIMIT

26N No opposition filed

Effective date: 20190503

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: SI

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

Ref country code: MC

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

REG Reference to a national code

Ref country code: CH

Ref legal event code: PL

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: LU

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20190106

REG Reference to a national code

Ref country code: BE

Ref legal event code: MM

Effective date: 20190131

REG Reference to a national code

Ref country code: IE

Ref legal event code: MM4A

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: BE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20190131

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: LI

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20190131

Ref country code: CH

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20190131

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: IE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20190106

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: TR

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: PT

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20181201

Ref country code: MT

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20190106

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: CY

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: HU

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT; INVALID AB INITIO

Effective date: 20140106

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: MK

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20180801

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: FR

Payment date: 20230125

Year of fee payment: 10

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: GB

Payment date: 20230127

Year of fee payment: 10

Ref country code: DE

Payment date: 20230127

Year of fee payment: 10

P01 Opt-out of the competence of the unified patent court (upc) registered

Effective date: 20230523

REG Reference to a national code

Ref country code: DE

Ref legal event code: R119

Ref document number: 602014029464

Country of ref document: DE

GBPC Gb: european patent ceased through non-payment of renewal fee

Effective date: 20240106

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: DE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20240801

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: GB

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20240106

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: FR

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20240131

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: GB

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20240106

Ref country code: FR

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20240131

Ref country code: DE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20240801