Longest prefix match lookup using hash function
First Claim
1. A computer system 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 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;
c) determining the longest prefix match for the search key within the routing table; and
d) performing the additional step of returning the longest prefix match to the requester.
0 Assignments
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
21 Claims
-
1. A computer system 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 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;
c) determining the longest prefix match for the search key within the routing table; and
d) performing the additional step of returning the longest prefix match to the requester. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method of 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:
-
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;
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. - View Dependent Claims (8, 9)
-
-
10. 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 (11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
Specification