Hierarchical hashing for longest prefix matching

Patent metadata

Field	Value
Publication number	US-9647941-B2
Application number	US-201314046889-A
Country	US
Kind code	B2
Filing date	Oct 4, 2013
Priority date	Oct 4, 2013
Publication date	May 9, 2017
Grant date	May 9, 2017

Abstract

A system for hierarchical hashing for longest prefix matching may include a memory and a processor. The memory may be configured to store hash tables that include prefixes and associated next hop information, where the hash tables are associated with lengths of the prefixes and at least one of the hash tables is associated with a range of lengths of the prefixes. The processor may be configured to determine a destination address associated with a packet received over a first port, determine next hop information associated with a longest prefix that matches the destination address by searching at least a first hash table of the hash tables that stores a largest number of the prefixes relative to the hash tables, and prepare the packet for transmission over a second port that is determined based at least on the next hop information.

First claim

What is claimed is:

1. A method of hierarchical hashing for longest prefix matching, the method comprising:
storing prefixes and associated next hop information in hash tables that are associated with lengths of the prefixes, at least one of the hash tables storing a plurality of the prefixes having a plurality of the lengths;
determining a first hash table of the hash tables that stores a largest number of the prefixes relative to the hash tables and a second hash table of the hash tables that stores a next largest number of the prefixes relative to the hash tables;
receiving a destination address associated with a packet;
determining the next hop information associated with a longest prefix that matches the destination address by searching at least the first hash table of the hash tables and, if the next hop information cannot be determined from searching the first hash table of the hash tables, searching the second hash table of the hash tables responsive to determining that the next hop information cannot be determined from searching the first hash table of the hash tables; and
routing the packet based at least in part on the next hop information.

2. The method of claim 1 , wherein determining the next hop information associated with the longest prefix that matches the destination address by searching at least the first hash table of the hash tables further comprises:
retrieving a hash value from the first hash table by searching the first hash table using at least a portion of the destination address, wherein the hash value comprises a prefix data structure comprising a plurality of prefixes or a first pointer thereto and a next hop information data structure comprising a plurality of next hop information items or a second pointer thereto;
determining the longest prefix of the prefix data structure that matches the destination address; and
retrieving the next hop information from the next hop information data structure based at least on the longest prefix of the prefix data structure that matches the destination address.

3. The method of claim 2 , wherein the prefix data structure is stored in the first hash table and comprises at least one of a bitmap or a binary tree and the next hop information data structure is stored in the first hash table and comprises an associated array.

4. The method of claim 2 , wherein the hash tables are stored in random access memory and the prefix data structure is stored in ternary content-addressable memory.

5. The method of claim 2 , wherein a length of the portion of the destination address is equivalent to a shortest length associated with the first hash table.

6. The method of claim 1 , wherein the first hash table stores the plurality of the prefixes having the plurality of the lengths.

7. The method of claim 1 , wherein determining the next hop information associated with the longest prefix that matches the destination address by searching at least the first hash table of the hash tables, further comprises:
retrieving a first hash value from the first hash table by searching the first hash table using at least a first portion of the destination address, wherein the first hash value comprises an indicator that indicates whether the longest prefix that matches the destination address may exist in the second hash table of the hash tables that is associated with longer prefixes than the first hash table;
searching the second hash table using at least a second portion of the destination address that includes the first portion of the destination address, when the indicator indicates that the longest prefix that matches the destination address may exist in the second hash table; and
retrieving the next hop information from a second hash value returned from the second hash table when searching the second hash table using at least the second portion of the destination address returns the second hash value, otherwise retrieving the next hop information from the first hash value.

8. The method of claim 7 , wherein a first length of the first portion of the destination address is equivalent to a shortest prefix length associated with the first hash table and a second length of the second portion of the destination address is equivalent to a shortest prefix length associated with the second hash table, the first and second hash tables each being associated with a separate plurality of the lengths of the prefixes.

9. The method of claim 7 , wherein the first hash value further comprises a bitmap and an associated array and retrieving the next hop information from the first hash value further comprises:
determining an index of the bitmap that corresponds to the longest prefix that matches the destination address; and
retrieve the next hop information from the associated array based at least on the index.

10. The method of claim 1 , wherein determining the next hop information associated with a longest prefix that matches the destination address by searching at least the first hash table of the hash tables further comprises:
determining that no entries of the first hash table match at least a first portion of the destination address by searching the first hash table using the at least the first portion of the destination address;
retrieving a hash value from the second hash table by searching the second hash table using at least a second portion of the destination address, wherein the hash value comprises a prefix data structure or a first pointer thereto and a next hop information data structure or a second pointer thereto;
determining the longest prefix of the prefix data structure that matches the destination address; and
retrieving the next hop information from the next hop information data structure based at least on the longest prefix of the prefix data structure that matches the destination address.

11. The method of claim 10 , wherein the first portion of the destination address is longer than the second portion of the destination address.

12. The method of claim 10 , wherein the first portion of the destination address is shorter than the second portion of the destination address.

13. A network device comprising:
a memory configured to store hash tables comprising prefixes and associated next hop information, wherein the hash tables are associated with lengths of the prefixes and at least one of the hash tables storing multiple of the prefixes having multiple of the lengths of the prefixes;
a processor configured to:
determine a first hash table of the hash tables that stores a largest number of the prefixes relative to the hash tables and a second hash table of the hash tables that stores a next largest number of the prefixes relative to the hash tables;
determine a destination address associated with a packet received over a first port of a plurality of ports;
determine the next hop information associated with a longest prefix that matches the destination address by searching at least the first hash table of the hash tables and, if the next hop information cannot be determined from the first hash table of the hash tables, searching the second hash table of the hash tables upon determining that the next hop information cannot be determined from the first hash table of the hash tables; and
prepare the packet for transmission over a second port of the plurality of ports, the second port being determined based at least on the next hop information.

14. The network device of claim 13 , wherein the memory comprises at least one random access memory and at least one ternary content-addressable memory, the at least one random access memory storing the hash tables and the at least one t

Assignees

• Broadcom Corp
• Avago Technologies General Ip

Inventors

• Sun Yan

Classifications

• H04L45/748

  using longest matching prefix · CPC title

• H04L45/7453 Primary

  using hashing · CPC title