Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-18
2002-07-16
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06421660
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method and an apparatus for searching variable bit chains in storage; this invention can be used in high speed networks for routing IPV4 or IPV6 (Internet Protocol Version 4 and Internet Protocol Version 6) datagrams which requires searching in a routing table for the longest matching prefix of a variable bit chain address. This process has been recommended for IP datagram address routing by the IETF organization (Internet Engineering Task Force) on the basis of the ‘Classless Inter-Domain Routing’ (CIDR) adopted as RFC-1466 in May, 1993. It needs to be implemented, for instance, in network routers which have also to sustain higher and higher media speed lines in the current networking environment.
One conventional way of sustaining media speed for searching large bit chains is a hardware assist based on a CAM (Content Addressable Memory) hardware device. The CAM components are available in the networking industry and operable as follows: a key is given as input and the result of the search is provided in a time quite convenient for high speed IP datagram processing. However, to find the longest matching prefix of a bit chain address, the CAM user has to implement many masks which need to be applied to the CAM entries. Both processing and storage requirements in such devices are severely impacted by this usage of masks. Consequently, the use of CAM is generally too expensive for networking equipment.
One other solution to have an efficient searching function is to use a binary tree data base structure. A problem of the binary trees is that they are difficult to manage, the delete and insert entry operations being much too complex. Radix tries, providing a per bit test are well adapted to variable bit chain searching. In the IBM PCT international filing WO 96/00945 dated Jun. 30, 1996 and the publication ‘IEEE/ACM transactions on networking’, Vol. 4, No. 1, dated February 1996, the article of Willibad Doeringer, Günter Karjoth and Mehdi Nassehi discloses dynamic prefix tries for longest matching prefix search. Searching based on the longest matching prefix is required in network equipment for IP datagram routing: the IPV4 address which is read in the router is 32 bits long. A search is performed in the routing table to find the address having the longest bit chain part in common with the IP address. One advantage of the solution described in the IEEE article is to provide a maintenance of the data structure; however, even if logically entries can be suppressed in the trie, a garbage collection has to be applied to the trie to clean up old node storage areas. Furthermore, this solution is rather software oriented: no simple and inexpensive hardware implementation is considered. One other problem is that the storage space for each node of the trie is not foreseeable as well as the displacement for searching in the trie. These two parameters have a direct impact of the amount of storage and processing time which cannot be foreseen.
It is therefore an object of the present invention to have a corresponding apparatus for searching the longest matching prefix of variable bit chains in a table having bit chain entries.
It is a second object of the invention to have a simple and limited cost oriented hardware implementation of the solution.
It is one other object of the invention to provide a method for inserting and deleting data entries without any need for further garbage collection.
Finally, it is also an object of the invention to have a deterministic knowledge of storage used and processing time required for searching.
SUMMARY OF THE INVENTION
In brief, this object is achieved by a method for searching input variable bit chain keys having a maximum length value in a patricia tree based data base, each node in the data base storing a direct parent address pointing to a previous node, two addresses pointing to following nodes, a data value or a pointer to a data value, a bit chain key zero padded up to said maximum length value, the length of said key and the rank of a bit to be tested at this node in the input key; said method comprising the steps of:
A. pointing to the root node of the tree,
B. padding the input key with zeros up to the maximum length value and reading the bit to test in the input key and according to the value of the bit to test pointing to the following node address,
C. repeating step B and reaching the following nodes until the rank of the bit to test of a following node is equal to or greater than the rank of the bit to test of the previous rank,
D. comparing the key stored in said previous node on its stored length with the zero padded input key,
E. if a match is not found, pointing to the parent node using the direct parent address,
F. repeating step E until the root is reached or a match is found,
G. reading the pointer or the data value of said previous node.
The invention further enables insertion operations of the input variable bit chain keys in the data base by extending the searching method with the following steps:
1. performing the searching steps according to the searching method of the invention up to step C,
2. comparing the key length of the just reached node with the length key of its parent node,
3. if the length of the parent node key is smaller than the length of the key to be inserted, comparing the key of the just reached node on its key length with the key of its parent node,
4. if a match is found swapping the two key values between the just reached node and its parent node while restoring the node branching;
5. repeating steps
2
to
4
until the root is reached.
The invention also enables deletion operations of the input variable bit chain keys in the data base by extending the searching method with the following steps:
I. performing the searching steps according to the searching method of the invention up to step C,
II. comparing the key in the previous node on the maximum length value with the zero padded input key,
III. if a match is found, swapping the key read in the following node and the key read in the previous node between the following node read and the previous node read while restoring the node branching, and
IV. suppressing the previous node read by updating its following node.
Also provided is an extended patricia tree data base for storing variable bit chain keys having a maximum length value, each node in the data base storing a direct parent address pointing to a previous node, two following node addresses, a data value or a pointer to a data value, a bit chain key zero padded up to said maximum length value, the rank of a bit to be tested at this node in the input key and the length of said key, the key length stored in one node being always greater than the one stored in a parent node if a match is found when comparing the key in said one node on its key length with the key of the parent node.
The invention provides a searching apparatus for searching variable bit chain keys having a maximum length in a patricia tree based data base, said apparatus comprising:
a processor interface for receiving from a processor acting as a controlling device, a searching request and a variable bit chain input key zero padded up to the maximum length,
a state machine for starting the search operation when receiving signals and data through the processor interface,
an internal storage repetitively accessed by said state machine through a multiplexor and adder, for reading a current node in the tree, starting from the root,
first testing means for testing the bit to test in the input key and thus defining the next node to be accessed,
means for advising the state machine that the following node has to be accessed only if the rank of the bit to test in the current node is smaller than the rank in the previous node,
means for comparing on the key length stored in the previous node the input key and the key stored in the previous node, only if the rank of the bit to test in the current node is equal to or greater than the rank in the previous node, said means further advising the
Herndon Jerry W.
Metjahic Safet
Pardo Thuy N.
LandOfFree
Enhanced searching method and apparatus for variable bit chains does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced searching method and apparatus for variable bit chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced searching method and apparatus for variable bit chains will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2837659