Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-30
2002-12-03
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06490592
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to data structures used for data lookups and, more particularly, to a tree data structure for longest match lookups that is suitable for Internet Protocol network routing applications.
Presently, a switching platform that is seeking to route to a selected IP address looks up the longest match to the desired IP address from IP addresses stored or group of IP addresses in a data table. The table of IP addresses is typically arranged as a digital binary tree structure, namely a data structure having two branches that extend from each record to form respective binary sub-trees. The binary tree structure is traversed in a known manner until the longest match to the desired IP address is located.
The binary tree structure may not efficiently use memory or may not efficiently use processing time. When a large number of IP addresses are stored in the table, the resulting binary tree structure can be of great height and thus require significant time to search the binary tree. As a result, the time required to route to a desired IP address increases significantly with the number of IP addresses stored in the binary tree. Also, two pointers are stored for each IP address, thereby increasing the size of the memory required with each value stored.
Alternatively, a balanced multi-way tree (B-tree) provides a tree of lower height and can be searched more quickly. Specifically, a B-tree is comprised of multiple records where each record includes one or more nodes with each node comprising a key and associated data. Each record of the multi-way tree has M branches, where M≧2. Optimally, the multi-way tree is kept balanced, namely all the leaves of the M tree are kept on the same level, as new IP addresses are added and existing IP addresses are removed. The tree is kept balanced to prevent portions of the tree from being significantly deeper than other portions so that all branches are traversed in substantially the same time.
However, a B-tree is not well suited for a longest match lookup. When the B-tree includes one or more IP addresses whose network prefix, namely the leftmost part of the IP address, is a subset of the network prefix of another IP address, the search may traverse a branch of the tree that contains an IP address that does not include the longest match to the desired IP address and thus the longest match is not found.
It is therefore desirable to provide a multi-way tree structure that provides the advantages of a B-tree and which always enables the longest match to a desired IP address to be located.
SUMMARY OF THE INVENTION
The present invention provides a multi-way tree data structure which supports a longest match lookup and wherein data elements stored therein that have no overlapping prefixes are arranged in a standard B-tree arrangement and data elements stored therein that have overlapping prefixes are arranged within the tree such that the prefix of such a data element contains the prefixes of all such data elements that succeed it.
In accordance with the invention, a new data element is inserted into a data structure comprised of a plurality of records that includes at least a root record. Each of the records includes at least one node and includes at least one pointer that points to another of the records or to a null value. The nodes are each capable of storing a respective data element, and each of the data elements and the new data element include a prefix that represents at least one address value and associated data. The prefix includes an address portion and a prefix length portion which defines the number of bits in the prefix. At least a portion of the data structure is arranged substantially as a balanced tree. A node in a respective one of the records having a prefix that is identical to the prefix of the new data element is located, and associated data stored in the node of one of the records is replaced with the associated data of the new data element.
According to another aspect of the invention, a node in a respective record having a prefix that is contained in the prefix of the new data element and that is closest to the root record is located. When the respective record is included in a linked structure that is within the data structure and that is external to but linked to the balanced tree, the new data element is inserted into the linked structure.
According to yet another aspect of the invention, a node in a respective record having a prefix that is contained in the prefix of the new data element and that is closest to the root record is located. When the respective record is included in the balanced tree but is pointed to by a pointer extending from a linked structure that is within the data structure and that is external to the balanced tree, the new data element is inserted into the linked structure.
According to a further aspect of the invention, a node in a respective record having a prefix that is contained in the prefix of the new data element and that is closest to the root record is located. When the respective record is included in the balanced tree and is not pointed to by a pointer extending from a linked structure that is within the data structure and that is external to the balanced tree, a new linked structure is inserted at a location within the data structure that immediately precedes the respective record. A pointer that previously pointed to the respective record now point to a first record of the new linked structure, and a pointer extending from a location within the linked structure that is closest to the root record and a pointer extending from a location within the linked structure that is furthest from the root record each point to the respective record. The new data element is inserted into a node within the new linked structure nearest to the root node.
According to a still further aspect of the invention, a node of a leaf record having a prefix that contains the prefix of the new data element is located. A data element stored in the node of the leaf record is replaced by the new data element, and then the data element previously stored in the node of the leaf record is inserted into the data structure as described above.
According to yet a further aspect of the invention, a data element is deleted from the data structure. A node in a respective record having the data element is located. When the respective record is included in a linked structure that is within the structure and that is external to but linked to the balanced tree, the data element is removed from the linked structure.
According to yet a still further aspect of the invention, a data element is deleted from the data structure. A node in a respective record having the data element is located. When the respective record is not included in a linked structure, any linked structures within the data structure that have a pointer pointing to the respective record is removed so that a pointer that previously pointed to the linked structure now points to the respective record. The data element is removed from the respective record and, the balanced tree portion of the data structure is rearranged. Any data elements previously stored in the linked structure are reinserted into the data structure, one data element at a time.
Further, according to the invention, a data element is searched for in the data structure. A respective node that stores a data element having a prefix that is a best match to the prefix of the data element is located. The best match is a prefix that represents at least an address value that includes the address portion of the data element and has a maximum length of any other prefixes stored in the data structure that represent one or more address values that includes the address portion of the data element.
Additionally, according to the invention, a data element is searched for in a data structure. A current record is defined to be the root record, and a best match node is defined to be a default node. Starting from a node in the current record that is closest to the root no
Rahman Reshad R.
St. Denis Bernard B.
Tsier Yuri
Amsbury Wayne
Gibbon, Del Deo, Dolan, Griffinger & Vecchione
Nguyen Cam-Linh
Nortel Networks Limited
LandOfFree
Method of and apparatus for generating a tree data structure... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of and apparatus for generating a tree data structure..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and apparatus for generating a tree data structure... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2921502