Longest prefix match lookup using hash function

• US 7,089,240 B2
• Filed: 06/29/2004
• Issued: 08/08/2006
• 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): Corrielus, Jean
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US10/879,964
• Publication Number:
  US 20040236720A1
• Time in Patent Office: 770 Days
• Field of Search: 707/10, 707/100, 707 1- 6, 370/230, 370/235, 370/392, 370/401, 370/383, 370/335
• US Class Current: 1/1
• 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 method for determining a longest prefix match for a variable length search key by a computer processing device, comprising the acts of:

reading an internet protocol (IP) destination address;

reading a virtual private network (VPN) number;

performing a hash on the 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 an input key;

using the hashed portion of the input key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry in the table contains a pointer to a next branch in the search free or a leaf;

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

use a next-bit-to-test field in the entry to find a distinguishing bit position in the search key, and determine if that bit is a one or a zero;

responsive to the state of the identified distinguishing bit, reading either the first half or second half of the next branch contents if the pointer points to a next brunch of the corresponding search free;

storing intermediate leaf pointers and corresponding prefix length as determined by distinguishing bit position;

reading a leaf pattern when the leaf of a corresponding search tree is reached and comparing the leaf pattern with the input key to determine if the leaf pattern matches the input key;

if leaf pattern matches, identifying the leaf as the longest prefix match;

if leaf pattern does not match, identifying previously stored leaf pointer with distinguishing bit greater than least significant bit of mismatch as the longest prefix match; and

returning the Longest prefix match found for the input key to a requesting application.

2. The method for determining the longest prefix march of claim 1 wherein the table contains 2^N entries wherein N represents the number of bits.

3. The method of claim 1 wherein VPN number has 12 bits, and N=16 bits.

4. The method of claim 1 wherein the contents of the next branch of the corresponding search free points to another next branch.

5. The method of claim 1 wherein the contents of the next branch points to a leaf of the corresponding search tree.

6. The method of claim 5 wherein the leaf represents a partial prefix match of the input key.

7. The method for determining the longest prefix match of claim 1 further comprising the act of terminating the search for the longest prefix match when the bit number of the next branch exceeds the length of the input key.

8. A method of conducting a search through a virtual private network routing table structure for at least one search tree, comprising:

performing a hash operation on a first segment of an internet protocol destination address with a virtual private network number to provide an output, and concatenating the remainder of the internet protocol destination address to the output of the hash operation to form a search key;

inputting the first segment of the search key into a direct table within the routing table structure wherein said direct table represents a plurality of root nodes of search frees; and

determining a longest prefix match for a variable length search key;

further including inserting a new route into the direct table structure comprises the steps of;

determining the direct table entry correlating to the 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 the entry 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 another pattern search control block to resolve new virtual private network from existing virtual private network; and

use bit 28 if distinguishing;

otherwise, use first distinguishing bit, then add a new pattern search control block at bit 28 for each virtual private network;

if the first pattern search control block in place is less than bit 28 thus indicating that multiple virtual private networks are already in place

use bit 28 if distinguishing; and

otherwise, use first distinguishing bit and then add pattern search control block at bit 28 for new virtual private network.

9. A method of conducting a search through a virtual private network routing table structure for at least one search tree, comprising:

performing a hash operation on a first segment of an internet protocol destination address with a virtual private network number to provide an output and concatenating the remainder of the internet protocol destination address to the output of the bash operation to form a search key;

inputting the first segment of the search key into a direct table within the routing table structure wherein said direct table represents a plurality of root nodes of search trees; and

determining a longest prefix match for a variable length search key;

further including deleting a route from the direct table comprises 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 the route normally;

if the distinguishing bit position is bit 28, or if next pattern search control block is with only one choice at bit 28;

if no previous pattern search control blocks are in place, remove the pattern search control blocks, and use the direct table entry to point directly;

if at least one previous pattern search control block is in place, remove the pattern search control block normally; and

if the distinguishing bit position has one or more subsequent pattern search control blocks prior to the pattern search control block at bit 28, remove the pattern search control block normally.