1. A method for defining categories for a set of data comprising:
a. selecting a plurality of attributes from a group of attributes, each attribute describing a possible data item in the set of data;
b. selecting a logic template from a group of logic templates, each logic template comprising a predetermined logic expression containing one or more variables; and
c. assigning one or more selected attributes to each variable within the selected the logic template to produce a logic expression defining the data category.
2. The method of claim 1, wherein the data category comprises a category for time data andor the plurality of attributes comprise time attributes.
3. The method of claim 1, wherein the predetermined logic expression comprises two or more logic groups of one or more variables linked by a logical operator.
4. The method of claim 3, wherein the step of assigning one or more selected attributes to each variable within the selected the logic template further comprises assigning one or more selected attributes to each logic group.
5. The method of claim 4, further comprising: selecting a predetermined logic rule for governing the relationship between the attributes in each logic group, said logic rule forming part of the logic expression defining the data category.
6. The method of claim 1, further comprising: using the data category in database operations.
7. The method of claim 1, further comprising: generating a natural language statement describing the logic expression defining the data category.
8. The method of claim 1, further comprising: adding, editing or removing a logic template from the group of logic templates.
9. A system for defining categories for a set of data comprising:
a storage device for storing instructions for implementing the method of claim 1; and
a processor adapted to process said instructions.
10. A computer-program product for defining categories for a set of data comprising:
computer-program code that when implemented by a processor displays a user interface;
computer-program code that when implemented by a processor provides a first user interface component which enables a user to select a plurality of attributes from a group of attributes, each attribute describing a possible data item in the set of data;
computer-program code that when implemented by a processor provides a second user interface component which displays a group of logic templates, each logic template comprising a predetermined logic expression containing one or more variables, and which enables a user to select a particular logic template from the group; and
computer-program code that when implemented by a processor provides a third user interface component which displays the selected attributes in a format determined by the selected logic template and which enables a user to assign one or more of said attributes to each variable within said template to produce a logic expression defining the data category.
11. The computer-program product of claim 10, wherein the data category comprises a category for time data andor the plurality of attributes comprise time attributes.
12. The computer-program product of claim 10, wherein the predetermined logic expression comprises two or more logic groups of one or more variables linked by a logical operator.
13. The computer-program product of claim 12, wherein the third user interface component enables a user to assign one or more selected attributes to each logic group.
14. The computer-program product of claim 13, wherein the third user interface component displays two or more predetermined logic rules governing the relationship between the attributes in each logic group and enables a user to select one of the logic rules to form part of the logic expression defining the data category.
15. The computer-program product of claim 10, further comprising computer-program code that when implemented by a processor performs database operations, said code being configured to use the data category defined by the user.
16. The computer-program product of claim 10, further comprising computer-program code that when implemented by a processor generates a natural language statement describing the logic expression defining the data category.
17. The computer-program product of claim 10, further comprising computer-program code that when implemented by a processor provides a fourth user interface component which enables a user to add, edit or remove a logic template from the group of logic templates.
18. A user interface for defining categories for a set of data comprising:
a first user interface component which enables a user to select a plurality of attributes from a group of attributes, each attribute describing a possible data item in the set of data;
a second user interface component which displays a group of logic templates, each logic template comprising a predetermined logic expression containing one or more variables, and which enables a user to select a particular logic template from the group; and
a third user interface component which displays the selected attributes in a format determined by the selected logic template and which enables a user to assign one or more of said attributes to each variable within said template to produce a logic expression defining the data category.
19. The user interface of claim 18, wherein the data category comprises a category for time data andor the plurality of attributes comprise time attributes.
20. The user interface of claim 18, wherein the predetermined logic expression comprises two or more logic groups of one or more variables linked by a logical operator.
21. The user interface of claim 20, wherein the third user interface component enables a user to assign one or more selected attributes to each logic group.
22. The user interface of claim 21, wherein the third user interface component displays two or more predetermined logic rules governing the relationship between the attributes in each logic group and enables a user to select one of the logic rules to form part of the logic expression defining the data category.
23. The user interface of claim 18, further comprising a fourth user interface component configured to display a natural language statement describing the logic expression defining the data category.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
What is claimed is:
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.
2. The method for determining the longest prefix match of claim 1 wherein the table contains 2N entries.
3. The method of claim 1 wherein VPN number has 12 bits, and N16 bits.
4. The method of claim 1 wherein the contents of the next branch of the corresponding search tree 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 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.
9. The computer system according to claim 8 including means for performing the additional step of returning the longest prefix match to the requester.
10. The system according to claim 9 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.
11. The system according to claim 10 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.
12. The system according to claim 10 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.
13. The system according to claim 8 wherein the steps can be carried out using hardware, or software, or a combination of both.
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.
15. The method according to claim 14 wherein insertion of a route into the direct table structure comprises the steps of:
determining the direct table entry correlating to new route;
if the direct table entry is empty, adding the entry directly to 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 PSCB in place is greater than bit 28, add PSCB to resolve new VPN from existing VPN;
use bit 28 if distinguishing;
otherwise, use first distinguishing bit, then add 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;
otherwise, use first distinguishing bit and then add PSCB at bit 28 for new VPN.
16. The method according to claim 14 wherein the deletion of a route into the direct table comprises the steps of:
determining the direct table entry correlating to 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 PSCBs 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.
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.
18. The computer readable medium of claim 17 further comprising a lookup definition table that manages a tree search memory.
19. The computer readable medium of claim 18 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.
20. The computer readable medium of claim 17 wherein the lookup definition table is implemented in a plurality of memories.
21. The computer readable medium of claim 17 wherein a format for a direct table entry 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.
22. The computer readable medium of claim 17 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.
23. The computer readable medium of claim 17 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.
24. The computer readable medium of claim 21 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.
25. The computer readable medium of claim 17 wherein a pattern search control block is inserted in the search tree at a position where the leaf patterns differ.
26. The computer readable medium of claim 17 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.
27. The computer readable medium of claim 17 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.
28. The computer readable medium of claim 17, containing a program product for determining a longest prefix match for a variable length search key, comprising:
program instructions that read an IP destination address and a VPN number as a search string;
program instructions that perform a hash on the 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.