Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-05-11
2003-02-04
Robinson, Greta L. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C370S392000
Reexamination Certificate
active
06516319
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to systems for retrieving addresses from search keys by using tree structures and specifically relates to a parallel processing device for processing search keys based upon binary tree structures.
BACKGROUND
When routing data messages over a network that uses Internet Protocol (IP), sequential steps for determining routing addresses are frequently represented as a tree structure.
A tree is a homogeneous structure whose each element, called a node, contains information that enables selection of a link or a branch to another node. Each branch of the tree thus links a parent node to a child node. As a result, each node of the tree is both a parent node for lower branches and a child node for the top branch, except for the first node or root, which has no parent.
Among tree structures, the binary tree, in which each parent node has at most two child nodes, is used most often. A search binary tree is an ordered tree where each node is associated with a numeric key to which a function is applied for determining whether the right or the left branch is to be taken in order to go on searching. The position of nodes in the tree reflects an order relation between keys associated with them. Thus, from a node, a subtree determined by this order relation can always be defined, the number of all subtree keys corresponding to the left branch being lower than the number of keys corresponding to the right branch.
The function that applies to the key at each node is a more or less complex recursive function that may be a simple comparison, a multiple comparison or any other operation. A simple comparison may consist of determining the value of the following bit of the search key for choosing between the left branch (bit set to 0) and the right branch (bit set to 1), in which case the function to be applied to each node is the Boolean function AND between 1 and the search key bit value. On the other hand, a multiple comparison may consist of determining the value of the next K bits of the search key and selecting the left branch whenever the word made up of these K bits has a predetermined value, or selecting the right branch for any other values of the word.
When this kind of search based upon a tree structure is applied to routing within an IP network, the search key is made up of the destination address of the data packet to be sent. The router has a routing table, each entry of which comprises a prefix and a next hop. A prefix represents a group of addresses, and is made up of an IP address and a prefix length. The address lookup operation consists of searching the routing table for the longest prefix matching the packet destination address. The “next hop” field of this table entry defines how the packet is to be sent.
To implement this lookup operation, the routing table is arranged according to a tree structure in which each table prefix is represented by a leaf of the tree. Therefore, the operation consists of determining the sequence of nodes (or tree branches) to be taken from the root in order to end up at a leaf having the longest matching prefix when a destination address or a search key is known. Systems currently available for determining a routing address by using a tree structure have the disadvantage of requiring a large number of memory accesses, that depends directly on the size of the outing table. In the prior art, for example in U.S. patent applicaton Ser. No. 6,341,346 filed by the applicant, attempts were made to reduce the number of memory accesses in order to increase the system performance by processing the greatest number of bits at each node using instructions with specified parameters. The purpose of these methods is to reduce the number of nodes to be crossed when routing from the root to the leaf having the longest matching prefix. However, even if performance is increased by reducing the number of nodes, instructions must be applied sequentially, node after node, which may require considerable processing time in some cases.
SUMMARY OF THE INVENTION
Accordingly, the main purpose of the invention is to provide a searching device that is based upon a binary tree structure, which can perform look-ahead processing of predetermined subtrees within the primary tree.
The invention relates to a device for the parallel processing of subtrees within a binary tree, with the purpose of searching for the tree leaf matching a search key. Such a binary tree has a pyramidal structure starting from a root node and is made up of a plurality of nodes linked by branches in which each node is associated with a group of node keys. Each branch can have, at most, two child nodes linked to the parent node by means of a left branch and a right branch. The search process is performed at each node through the application of a recursive function associated with each node, whose parameters depend on the node for determining which branch, left or right, is to be taken in accordance with the search key. The device comprises a first plurality of subtree register blocks for storing the recursive functions associated with the nodes of a subtree within the binary tree, a second plurality of processors equal in number to at least to the first plurality for processing the recursive functions stored in the register blocks, a control unit that assigns one processor among the second plurality of processors to the processing of the recursive functions contained, among the first plurality of subtree register blocks, in a block that send the request to the control unit, and means for selecting subtrees included in the sequence of branches between the root and the leaf defined in accordance with the search key in response to the processing of blocks from the first plurality of subtree register blocks.
REFERENCES:
patent: 5664184 (1997-09-01), Ferguson et al.
patent: 6041053 (2000-03-01), Douccur et al.
patent: 6141655 (2000-10-01), Johnson et al.
patent: 6292795 (2001-09-01), Peters et al.
patent: 6334125 (2001-12-01), Johnson et al.
Benayoun Alain
Le Pennec Jean-Francois
Michel Patrick
Pin Claude
International Business Machines - Corporation
Irvin David R.
Robinson Greta L.
LandOfFree
Parallelized processing device for processing search keys... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallelized processing device for processing search keys..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallelized processing device for processing search keys... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3146680