Longest prefix match lookup using hash function

• US 7,702,630 B2
• Filed: 02/14/2006
• Issued: 04/20/2010
• Est. Priority Date: 04/06/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Davis, Gordon T., Basso, Claude, Calvignac, Jean L., Patel, Piyush C.
• Primary Examiner(s): Fleurantin; Jean B
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US11/353,841
• Publication Number:
  US 20060173831A1
• Time in Patent Office: 1,526 Days
• Field of Search: 707/1, 707/3, 707/10, 707100-102, 707/104.1, 707/6, 370392-393, 370400-401, 370/238
• US Class Current: 707/769
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus are used for finding the longest prefix match in a variable length prefix search when searching a direct table within a routing table structure of a network processor. The search through the routing table structure is expedited by hashing a first segment of an internet protocol address with a virtual private network number followed by concatenating the unhashed bits of the IP address to the result of the hash operation to form an input key. Patterns are compared a bit at a time until an exact match or the best match is found. The search is conducted in a search tree that provides that the matching results will be the best possible match.

Claims

1. A computer readable storage medium containing a plurality of data structures for finding a longest prefix match for a variable length search key, when conducting a search through a Virtual Private Network (VPN) routing table for at least one search tree, comprising:

a pattern or key that is to be searched;

program instructions for hashing N most significant bits of an Internet Protocol (IP) destination address with a virtual private network number and for concatenating the remaining least significant bits of Internet Protocol destination address to the result of the hash operation to form said pattern or key;

a direct table that stores a first address location for a search tree;

program instructions for inputting the hashed portion of the search key into a direct table within the routing table structure wherein the direct table represents a plurality of root nodes of search trees to thereby determine the longest prefix match;

each entry inputted into direct table includes at least one search control block;

a next pattern address that points to a next pattern search control block, a leaf control block address that points to a leaf or result, a next bit or bits to test, and a direct leaf;

a plurality of pattern search control blocks (PSOBs) that each represent a branch in the search tree; and

a plurality of leaves wherein each leaf is an address location for the result of a search.

2. The computer readable storage medium of claim 1 further comprising a lookup definition table that manages a tree search memory.

3. The computer readable storage medium of claim 2 wherein the lookup definition table comprises entries that define a physical memory that the tree resides in, a size of the key and leaf, and a type of search to be performed.

4. The computer readable storage medium of claim 1 wherein the lookup definition table is implemented in a plurality of memories.

5. The computer readable storage medium of claim 1 wherein a format for a pattern search control block includes at least one of a search control block;

a next pattern address that point to a next pattern search control block;

a leaf control block address that points to a leaf or result; and

a next bit or bits to test.

6. The computer readable storage medium of claim 1 wherein a leaf data structure includes at least one of a leaf chaining pointer;

a prefix length;

a pattern to be compared to the search key; and

variable user data.

7. The computer readable storage medium of claim 1 wherein the direct leaf is stored directly in a direct table entry and includes a search control block and a pattern to be compared to a search key.

8. The computer readable storage medium of claim 1 wherein a pattern search control block is inserted in the search tree at a position where the leaf patterns differ.

9. The computer readable storage medium of claim 1 wherein a pattern search control block has a shape defined by a width of one and a height of one and is stored in a memory that has a line length of at least 64 bits.

10. The computer readable storage medium of claim 1 wherein a pattern search control block has a shape defined by a width of one and a height of two and is stored in a memory of at least 36 bits.

11. The computer readable storage medium of claim 1, containing a program product for determining a longest prefix match for a variable length search key, comprising:

program instructions that read an internet protocol (IP) destination address and a virtual private network (VPN) number as a search string;

program instructions that perform a hash on the number (N) most significant bits of the IP destination address and the VPN number to form an input key;

program instructions that use the N most significant bits of the input key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;

program instructions that determine if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;

program instructions that read the next branch contents if the pointer does not point to the leaf of the corresponding search tree and compare the prefix represented by the next branch with the input key to find a distinguishing bit position;

program instructions that read a leaf pattern when the leaf of a corresponding search tree is reached and compare the leaf pattern with the input key to determine if the leaf pattern matches the input key; and

program instructions that return the longest prefix match found for the input key to the requesting application.

12. A computer system comprising an apparatus and including a computer processing device having the capability of conducting a search responsive to a request through a virtual private network routing table, involving the steps of:

a) forming a search key by hashing a first segment of an internet protocol (IP) destination address with a virtual private network (VPN) number to form a hashed portion and concatenating the remaining segment of the internet protocol address;

b) inputting the hashed portion of the search key into a direct table within a network routing table structure wherein the direct table represents root nodes of search trees, the inputting including determining the direct table entry correlating to a new route;

further providing that

if the direct table entry is empty, the entry is added directly to direct table;

if the distinguishing bit position is greater than bit 28, the entry is added normally;

if the distinguishing bit position is bit 28 or less;

if the first pattern search control block (PSCB) in place is greater than bit 28, the PSCB is added to resolve a new VPN from existing VPN;

using bit 28 if distinguishing;

otherwise, using first distinguishing bit, then adding PSCB at bit 28 for each VPN;

if the first PSCB in place is less than bit 28 (multiple VPNs already in place) using bit 28 if distinguishing;

otherwise, using first distinguishing bit and then adding PSCB at bit 28 for new VPN;

then

c) determining the longest prefix match for the search key within the routing table, the imputing comprising the steps of;

determining a direct table entry correlating to a new route;

if the direct table entry is empty, adding the entry directly to the direct table;

if the distinguishing bit position is greater than bit 28, insert normally;

if the distinguishing bit position is bit 28 or less;

if the first pattern search control block (PSCB) in place is greater than bit 28, add the PSCB to resolve a new VPN from the existing VPN;

use bit 28 if distinguishing;

otherwise, use first distinguishing bit, then add a PSCB at bit 28 for each VPN;

if the first PSCB in place is less than bit 28 (multiple VPNs already in place), use bit 28 if distinguishing.

13. The computer system according to claim 12 wherein the computer processing device is capable of performing the hash on N most significant bits of the IP destination address and the VPN number and concatenating the remaining least significant bits of the IP destination address to the result of the hash operation to form the search key.

14. The system according to claim 13 further including the ability to use the hashed portion of the search key as an index into the routing table, wherein each non-empty node in the table contains a pointer to the next branch in a tree or to a leaf having a distinctive pattern.

15. The system according to claim 14 further having the capability of comparing a leaf pattern with the search key to determine if the leaf pattern matches the hashed portion of the search key.

16. The system according to claim 14 further having the capability to terminate the search for the longest prefix match when the bit number of the next branch exceeds the length of the search key.

17. The computer system according to claim 12 wherein the computer processing device is further capable of deleting a route from the direct table, comprising the steps of:

determining the direct table entry correlating to the route to be deleted;

if the route to be deleted is at the direct table entry, delete the route from the direct table normally;

if the distinguishing bit position is greater than bit 28, delete normally;

if the distinguishing bit position is bit 28, or if next PSCB is with only one choice at bit 28;

if no previous PSCBs in place

remove the PSCB, and

use direct table entry to point directly;

if at least one previous PSCB in place

remove the PSCB normally;

if the distinguishing bit position has one or more subsequent PSCBs prior to the PSCB at bit 28, remove the PSCB normally.

18. A method of executing a program on a computer system for determining a longest prefix match for a variable length search key by conducting a search through a virtual private network (VPN) routing table structure for at least one search tree, comprising:

providing a computer system;

hashing the N most significant bits of an internet protocol (IP) destination address with a virtual private network number, and concatenating the remaining least significant bits of the IP destination address to the result of the hash operation to form a search key;

thereafter deleting a route from the direct table comprising the steps of;

determining the direct table entry correlating to the route to be deleted;

if the route to be deleted is at the direct table entry, delete the route from the direct table normally;

if the distinguishing bit position is greater than bit 28, delete normally;

if the distinguishing bit position is bit 28, or if next PSCB is with only one choice at bit 28;

if no previous PSCBs in place

remove the PSCB, and

use direct table entry to point directly;

if at least one previous PSCB in place

remove the PSCB normally;

if the distinguishing bit position has one or more subsequent PSCBs prior to the PSCB at bit 28, remove the PSCB normally.