Patent ID: 7702630
Filing Date: 2010-04-20
Classification: G06F,H04L,Y10S

Abstract:
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.