Longest prefix match lookup using hash function
First Claim
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 IP destination address;
reading a 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 (unhashed) 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 tree 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 branch of the corresponding search tree;
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; and
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;
returning the longest prefix match found for the input key to a requesting application.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
28 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 IP destination address;
reading a 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 (unhashed) 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 tree 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 branch of the corresponding search tree;
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; and
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;
returning the longest prefix match found for the input key to a requesting application. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer system including a computer 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 destination address with a virtual private network number and concatenating the remaining segment of the internet protocol address;
b) inputting the hashed portion of the search key into a routing table representing nodes of search trees; and
c) determining the longest prefix match for the search key within the routing table. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A method of conducting a search through a virtual private network routing table structure for at least one search tree, comprising:
-
hashing a first segment of an internet protocol destination address with a virtual private network number, and concatenating the remaining unhashed least significant bits of the IP destination address to the result of the hash operation to form a search key;
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; and
determining a longest prefix match for a variable length search key. - View Dependent Claims (15, 16)
-
-
17. A computer readable medium containing a plurality of data structures for finding a longest prefix match for a variable length search key, comprising:
-
a pattern or key that is to be searched;
a direct table that stores a first address location for a search tree;
a plurality of pattern search control blocks 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. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
Specification