Compressed prefix matching database searching

• US 5,781,772 A
• Filed: 05/15/1995
• Issued: 07/14/1998
• Est. Priority Date: 07/12/1989
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Poole, Nigel T., Varghese, George, Wilkinson, III, Hugh M.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): TOPLU, LUCIEN
• Application Number:
  US08/441,253
• Time in Patent Office: 1,156 Days
• Field of Search: 395/600
• US Class Current: 709/242
• 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 storing and searching a hierarchical search path in response to a search argument to provide a hierarchical search through a series of hierarchal levels, comprising the machine-implemented steps of:

storing nodes to provide the hierarchial search, such storing node forming a search path, at least some of said nodes including one or more pointers indicating other nodes, at least one of the nodes along said search path including a special pointer indicating a starting node at a different one of the series of hierarchial levels,

parsing said search argument into a series of search segments as a consequence of the processing said storing nodes, successive segments of said argument corresponding to a currently, or successively, processed one of said series of nodes along said search path,

searching by processing successive respective search segments by processing the currently, or successively, processed one of the respective nodes, said processing of said node including;

retrieving one of said pointers from said node referencing a node for subsequent processing, such subsequently processed node being selected in response to a value of a search segment said node; and

, conditionally determining the number of bits in the search argument remaining to be processed to transition to a subsequent level of the hierarchial search, and,

while processing said one of the nodes, determining whether a predetermined number of bits in the search argument have been processed or a predetermined number of bits in the search argument remain unprocessed in said search argument, and if the predetermined number of bits in the search argument have been processed retrieving said special pointer from said one of the nodes and proceeding to said starting node of the subsequent one of the hierarchial levels as referenced by the pointer and continuing the search at said starting node.

2. The method of claim 1, wherein

said search argument is a system address in a computer network,

at least some of said nodes store routine information for transmitting packets through said network to a device designated by a system address, and

after following a search path in response to a search argument comprising a system address, routing information stored in a node nearest the end of said search path is used to transmit packets through said network to the device designated by said address.

3. The method of claim 1 wherein said search argument is a system address in a computer network in accordance with ISO 8348/AD2,

said hierarchical search comprises a Level-2 search at a first hierarchical level and a Level-1 search at a second hierarchical level,

a Level-2 search corresponds to a search between areas of said network and a Level-1 search to a search within an area of said network, and

after following a search path in response to a search argument comprising a system address, routing information stored in a node along said search path is used to transmit packets through said network to the device designated by said address.

4. The method of claim 1 wherein

said search argument is a system address in a computer network in accordance with ISO 8348/AD2,

said hierarchical search comprises a IDP search at a first hierarchical level and a DSP search at a second hierarchical level, and

after following a search path in response to a search argument comprising a system address, routing information stored in a node along said search path is used to transmit packets through said network to the device designated by said address.

5. Apparatus for storing and searching a hierarchical search path in response to a search argument, comprising

memory storing nodes forming said search path, at least some of said nodes including one or more pointers indicating other said nodes, at least a given node along said search path including a special pointer indicating a starting node at a different hierarchical level,

a unit for parsing a search argument into a series of search segments as a consequence of processing a series of said nodes, successive segments of said argument corresponding to successive, or a current, one of said nodes along said search path,

a controller for searching by processing successive respective search segments by processing successive, or a current one, of said respective nodes, said processing including

retrieving one of said pointers from a node in response to a value of a search segment corresponding to a successive one of said node and conditionally determining the number of bits in the search argument remaining to be processed to transition to a subsequent level of the hierarchal search, such retrieved one of said pointers referencing a node for subsequent processing with a subsequent search argument, and

while processing said given node, determining whether a predetermined number of bits in the search argument have been processed or a predetermined number of bits in the search argument remain unprocessed in said search argument, and if the predetermined number of bits in the search argument have been processed, retrieving said special pointer from said given node and proceeding to said starting node of the different hierarchial level referenced by the pointer and continuing the search at said starting node.

6. The apparatus of claim 5 wherein

said memory comprises a plurality of memory devices having differing access times and power requirements, each said device storing data of a particular type for more than one said nodes,

data types requiring rapid access are stored in memory devices with low access times, and

data types requiring less rapid access are stored in memory devices with low power consumption.