# US 2014/0195545 A1 · High performance hash-based lookup for packet processing in a communication network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0195545 A1
- Document ID: US20140195545A1
- Status: Published application
- Kind: A1
- Application number: 13/738,316
- Filed: 2013-01-10
- Published: 2014-07-10
- Earliest claimed: 2013-01-10
- Assignees: Telefonaktiebolaget L M Ericsson (publ)
- Inventors: Prashant Anand; Ashish Anand
- Web page: https://patentgrep.com/patent/US20140195545A1

## CPC

- G06F 16/9014: {hash tables}
- H04L 45/7453: using hashing
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The present invention relates to methods and apparatus for performing a lookup on a hash table stored in external memory. An index table stored in local memory is used to perform an enhanced lookup on the hash table stored in external memory. 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. Thus, the hash table is accessed only once during a data lookup.

## Claims

### Claim 1

A method, implemented by a packet processing node in a packet-switched network, for performing a data lookup on a hash table, said method comprising:
receiving a packet containing a flow identifier;
generating a full search key from the flow identifier;
determining a corresponding hash bucket in said hash table based on the full search key;
creating a compressed search key from signature bits extracted from predetermined bit locations in the full search key;
predicting 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 said data lookup by comparing the full search key to the hash key in the target hash entry.

### Claim 2 (depends on 1)

The method of claim 1 wherein generating a full search key from the flow identifier comprises hashing the flow identifier with a hash function.

### Claim 3 (depends on 1)

The method of claim 1 further comprising, for each hash bucket in the hash table, storing the bit locations for the signature bits and the signature patterns for the hash entries in the hash bucket in an index table.

### Claim 4 (depends on 3)

The method of claim 3 wherein determining a corresponding hash bucket in a hash table 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.

### Claim 5 (depends on 4)

The method of claim 4 further comprising determining bit locations of signature bits in the full search key using the hash bucket index to lookup the bit locations in the index table.

### Claim 6 (depends on 3)

The method of claim 3 further comprising storing the index table in a local memory.

### Claim 7 (depends on 1)

The method 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.

### Claim 8 (depends on 7)

The method 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.

### Claim 9 (depends on 8)

The method 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.

### Claim 10 (depends on 1)

The method of claim 1 further comprising:
storing the bit locations of the signature bits and the signature patterns in a local memory; and
storing the hash table in an external memory.

### Claim 11

A packet processing node in a communication network, said packet processing node comprising:
an interface circuit for receiving a packet containing a flow identifier;
a control unit 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 based on the full search key;
create a compressed search key from the 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 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
perform a data lookup by comparing the full search key to the hash key in the target hash entry.

### Claim 12 (depends on 11)

The packet processing node of claim 11 wherein the control unit is configured to hash the flow identifier with a hash function to generate the search key.

### Claim 13 (depends on 11)

The packet processing node of claim 11 wherein the control unit is further configured to, for each hash bucket in the hash table, store the bit locations for the signature bits and the signature patterns for the hash entries in the hash bucket in an index table.

### Claim 14 (depends on 13)

The packet processing node of claim 13 wherein the control unit is configured to determine a corresponding hash bucket in a hash table 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.

### Claim 15 (depends on 14)

The packet processing node of claim 14 wherein the control unit 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.

### Claim 16 (depends on 13)

The packet processing node of claim 13 wherein the control unit is configured to store the index table in a local memory.

### Claim 17 (depends on 11)

The packet processing node of claim 11 wherein the control unit is configured to pre-compute the signature patterns for the hash entries and store the pre-computed signature patterns in an index table.

### Claim 18 (depends on 17)

The packet processing node of claim 17 wherein the control unit 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.

### Claim 19 (depends on 18)

The packet processing node of claim 18 wherein the control unit 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.

### Claim 20 (depends on 11)

The packet processing node of claim 11 wherein the control unit is configured to:
store the bit locations of the signature bits and the signature patterns in a local memory; and
store the hash table in an external memory.