Compressed prefix matching database searching

• US 6,014,659 A
• Filed: 06/07/1995
• Issued: 01/11/2000
• Est. Priority Date: 07/12/1989
• Status: Expired due to Term

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Poole, Nigel T., Varghese, George, Wilkinson, III, Hugh M.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/473,135
• Time in Patent Office: 1,679 Days
• Field of Search: 395/601-603, 395/612, 395/412, 395/413, 395/414, 395/415, 340/825.03, 340/826, 340/827, 340/825.07, 707/3, 707/5, 709/238, 370/351, 370/389, 370/392
• US Class Current: 707/769
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Aspects of the invention include a method of conducting a reduced length search along a search path. A node which would otherwise occur between a previous and a following node in the search path is eliminated, and information is stored as to whether, had said eliminated node been present, the search would have proceeded to the following node. During the search, a search argument is compared with the stored information, and the search effectively progresses from the previous node directly to the following node if the comparison is positive. In preferred embodiments, some nodes provide result values for the search, and a node is eliminated only if its presence would not affect the result value for the search. In another aspect, the invention features a method of conducting a two mode search of reduced length. For a first mode of the search, nodes along a search path are provided, at least some of the nodes including one or more pointers pointing to other nodes. A search argument comprising a series of search segments is provided, some values of segments of the argument corresponding to nodes along the search path, some other values of the segments relating to a second mode of the search. Indicators associated with nodes are provided, each indicator indicating the segments corresponding to the second mode. The search path is searched by processing successive search segments by inspecting the indicator associated with each node, and proceeding to the second search mode if the indicator indicates that the segment relates to the second mode.

Claims

1. A method of conducting a search of reduced length through a stored database containing nodes and pointers leading from one of said nodes to another of said nodes in response to a search argument, said search argument defining a search path following pointers through said nodes, by eliminating an eliminated node that would otherwise occur between an immediately previous and an immediately following node in said search path, comprising the machine-implemented steps of:

storing information describing conditions under which, had said eliminated node been present, the search would have proceeded to said following node,

following said search path through said nodes,

when said search reaches said previous node,

determining whether said search argument meets the conditions of said stored information, and

causing said search to effectively progress from said previous node directly to said following node if the comparison indicates that, had said eliminated node been present, said search would have proceeded to said following node.

2. The method of claim 1, wherein

at least some of said nodes identify a result value,

said eliminated node would have provided a result value, and said following node provides a result value of said search, and

the result value that would have been provided by said eliminated node is equal to the result value that is provided by said following node.

3. The method of claim 1, wherein said information is stored in said following node.

4. The method of claim 3, wherein

said search argument comprises a series of search segments, each segment of said argument corresponding to a node along said search path,

at least one value of a segment corresponding to a given node being related to a pointer leading from said given node to another node, and some other values of said segment being related to a terminating mode of said search.

5. The method of claim 4, wherein

said stored information is a given value of a search segment corresponding to said eliminated node,

said given value being a value that would have been related to a pointer leading from said eliminated node to said following node.

6. The method of claim further comprising

associating one or more sets of indicators respectively with one or more nodes, each indicator in a given set associated with a given node indicating a value of a segment of said search argument corresponding to said given node that is related to said terminating mode, and wherein

following said search path comprises processing successive search segments of said search argument, processing of a given search segment having a given value including

retrieving the set of indicators associated with a node along said search path that is associated with said given search segment, and determining whether an indicator in said set indicates that said given value is related to said terminating mode, and

proceeding to said terminating mode if an indicator indicates that said given value relates to said terminating mode, otherwise

retrieving a pointer leading from said given node that is related to said given value, and following said pointer to a subsequent node along said search path.

7. The method of claim 6 wherein said terminating mode of said search comprises terminating said search.

8. The method of claim 7 wherein

said search argument comprises a system address in a network, and

said result values comprise routing information for transmitting packets through said network to a device designed by said address.

9. A method of conducting a search in response to a search argument, comprising the machine-implemented steps of:

storing, for a first mode of said search, a database of nodes forming search paths, at least some of said nodes including one or more pointers pointing to other said nodes to form said paths,

parsing said search argument into a series of search segments having values, each respective segment associated with a respective node along a said search path, each value of a segment identifying either;

a pointer in a node associated with said segment that points to a subsequent node along said search path;

or a terminating mode of said search,

associating groups of indicators with one or more nodes, each indicator in a group associated with a given node indicating whether a value of a segment of said search argument associated with said given node identifies said terminating mode, and

following said search path by processing successive search segments of said search argument, processing of a given search segment having a given value including

retrieving the set of indicators associated with a given node along said search path associated with said given search segment, and determining whether an indicator of said set indicates that said given value is associated with said terminating mode, and

proceeding to said terminating mode if an indicator indicates that said given value is associated with said terminating mode, otherwise

retrieving from said given node a pointer identified by said given value and proceeding to a subsequent node along said search path pointed to by said pointer.

10. The method of claim 9, wherein

said pointer are stored in contiguous memory space in said nodes, and no pointer are stored for values of segments of said search argument that relate to said terminating mode of said search, such that, in a given node associated with a given segment of said search argument, locations of pointers stored in said given node are determined by how many values of said given segment do not relate to said second mode, further comprising

if a value of a segment being processed does not correspond to said terminating mode, examining said indicators and said value to locate a pointer that corresponds to said value, retrieving said pointer and continuing said search to a subsequent node pointed to by said pointer.

11. The method of claim 9, wherein each said indicator is a bit in a sequence of bits associated respectively with a plurality of said segment values.

12. The method of claim 9, wherein said terminating mode of said search comprises terminating said search.

13. The method of claim 9 wherein

said search argument comprises a system address in a network, and

said search terminates with a value comprising routing information for transmitting packets through said network to the device designated by said address.

14. Apparatus for conducting a search of reduced length through a stored database containing nodes and pointers leading from one of said nodes to another of said nodes in response to a search argument, said search argument defining a search path following pointers through said nodes, by eliminating an eliminated node that would otherwise occur between an immediately previous and an immediately following node in said search path, comprising

a memory storing information describing conditions under which, had said eliminated node been present, the search would have proceeded to said following node,

a controller for following said search path through said directed graph of nodes,

a comparator for determining whether said search argument meets the conditions of said stored information when said controller reaches said previous node, wherein

said controller causes said search to effectively progress from said previous node directly to said following node if said comparator indicates that, had said eliminated node been present, said search would have proceeded to said following node.

15. The apparatus of claim 14, wherein

at least some nodes identify a result value,

said eliminated nodes would have provided a result value, and said following node provides a result value for said search, and

the result value that would have been provided by said eliminated node is the result value that is provided said following node.

16. Apparatus for conducting a search in response to a search argument, comprising

a memory storing, for a first mode of said search, nodes forming search paths, at least some of said nodes including one or more pointers pointing to other said nodes to form said paths,

a fetch unit for parsing said search argument into a series of search segments having values, each respective segment associated with a respective node along a said search path, each value of a segment identifying either:

a pointer in a node associated with said segment that points to a subsequent node along said search path;

or a terminating mode of said search,

a memory storing groups of indicators associated with one or more nodes, each indicator in a group associated with a given node indicating whether a value of a segment of said search argument associated with said given node identifies said terminating mode, and

a controller for following said search path by processing successive search segments of said search argument, processing of a given search segment having a given value including

retrieving the set of indicators associated with a given node along said search path associated with said given search segment, and determining whether an indicator of said set indicates that said given value is associated with said terminating mode, and

proceeding to said terminating mode if an indicator indicates that said given value associated with said terminating mode is set, otherwise

retrieving from said given node a pointer identified by said given value and proceeding to a subsequent node along said search path pointed to by said pointer.

17. The apparatus of claim 16, wherein

said pointers are stored in contiguous space in said memory, and no pointers are stored for values of segments of said search argument that relate to said terminating mode of said search, such that, for a given node associated with a given segment of said search argument, locations of pointers stored in said memory are determined by how many values of said given segment do not relate to said second mode, and

if indicator determines that a value of a segment being processed does not correspond to said terminating mode, said controller examines said indicators and said value to locate a pointer that corresponds to said value, and continues said search to a subsequent node.

18. The apparatus of claim 17, wherein each said indicator is a bit in a sequence of bits associated respectively with a plurality of said segment values.