Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-21
2003-04-08
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06546391
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a high-speed lookup apparatus as well as a high-speed lookup method for retrieving data at high-speed from a table in which it is stored, matching data provided.
In recent years there has been a rapid increase in the application of networks which use Internet Protocols (IP) as their network layer protocols, to the Internet and to enterprise networks. In accordance with this increase, there is a demand for more high performance in the IP routers which carry out the relaying processing on packets in the IP network. However, the relaying processing of IP packets is performed based on routing information, which manages relaying route selection for the packets in network address (network prefix) units. This network address uses one part of the IP address. That “one part” is an address value defined, for example, with a variable length from the upper part of an address, and the length (prefix length) takes different values depending upon the network address (network prefix). Namely, the field, which is used to represent a network and is a part of an address showing destination for each packet varies according to network addresses. Therefore, if a certain packet is to be relayed, in order to obtain the information corresponding to the network address (network prefix) from the destination address of the packet, it is necessary to perform a comparison process using data lengths that differ for each route entry when referencing the management table. Consequently, to make relay processing of IP packets high-speed, it is necessary to perform a high-speed lookup of the routing information holding this variable length prefix.
Thus, since the comparison object field takes on a different value with each entry, several approaches to high-speed lookup have been undertaken in the past. For example, high-speed radix tree and radish tree algorithms are employed for the network processing in Berkley Software Distribution (BSD) OSs, the Transmission Control Protocol/Internet Protocol (TCP/IP) implementation reference. With these types of algorithms, an entry is created that shows the existence of a branch object bit, in the location in the address field where an entry candidate first branches, in order from the most significant bit on downward. Then, based on the “0” or “1” value of the branch object bit (check object bit), the possible entry is classified according to the bit sequence that follows. Therefore, a lookup proceeds to a bit location where a branch candidate is to be branched, and branches depending upon the value found there, tracing through the tree in order until a point is found that has no branch, and then determines whether the arrived at entry satisfies the lookup conditions. However, with this type of tree based algorithm, the number of branches needed to arrive at a single entry is not the same for each entry. Depending upon the conditions, it may take only one branch to arrive at a certain entry, while for a different entry, in a worst case scenario it is possible that it may take as many repeating branches as the address length. Further, even if an attempt is made to perform the algorithm in hardware in order to make it high-speed, each step in the lookup process is dependent, so it is difficult to speed it up by means of pipeline processing or bubble processing. A Content Addressable Memory (CAM) is in use as a technique of performing high-speed hardware lookups. However, as explained above, routing information lookups have different lengths for each entry, so the CAM, with fixed length data lookup, cannot be used as is, but must be coupled with a route cache or other technique. A route cashe maintains as a list correspondence between an object address and its matching entry after a lookup is first performed, and it is easy to use the CAM and construct a lookup apparatus. However, the entries which is represented by a network address, namely a kind of address aggregate, are handled as their developed forms of separate address units, and to hold an equivalent amount of information, a much larger table size is needed. On the other hand, if the table size is restrained, the number of cases in which there is no hit in the cache will increase, so there is a problem in that to get high-speed with a route cache does not work well.
In addition, there are techniques of constructing a tree with multiple bit units, but the tree branch locations become fixed bit locations. For that reason, in an application in which every comparison object takes a different value for bit width, it is necessary to construct a table in which the address is developed in some form as in the case of the route cache. This means that one cannot escape a greatly enlarged table size. To avoid this problem, a structure that accommodates a portion in a cache like manner must be used, but this has poor efficiency, just like the route cache described above.
A “Masked Lookup Memory Circuit” (Japanese Patent Application Laid-open Nos. Hei 3-12896, Hei 7-143156, Hei 10-112728, etc.) exists that uses a structure in which a mask bit is added to the prior type CAM memory in order to set the comparison object bit separately for each entry. In this circuit, the data length, which is set independently for every entry indispensable for routing information lookup on the IP network, is included at the CAM level, but with the degree of semiconductor integration, etc., it is not always possible to ensure a capacity that will store all of the routing information.
SUMMARY OF THE INVENTION
Therefore, an object of the present invention is that by combining means for a masked lookup memory with a tree or a multistage indexed type memory table, to be able to perform lookup, not only will the problems of unbalanced lookup time and an increased table volume be eased, but even if only a small amount of masked lookup memory can be used, a lookup process possessing a large lookup table will be realized.
In order to solve the above object, a high-speed lookup method of the present invention comprises the steps of: dividing entries, which become lookup objects and have variable length comparison conditions, into a plurality of groups, taking a representative lookup key as lookup data for each of the groups, and storing mask data that sets a range for matching with a match candidate, as well as comparison object data in a masked lookup memory means so that setting can be made for each of said entries; and obtaining, from the masked lookup memory means, information corresponding to the groups that match the lookup conditions, and limiting the lookup object entries to the data within the object group.
This structure further comprises the steps of: classifying the entries, which become lookup objects, into a tree state, with nodes adopted at points where bit values are either “0” or “1”, in order from the first bit; and performing a lookup for matching entries after the entries, which have been classified into the tree state, are limited to the data within the object groups.
In addition, it may further comprises the steps of: constructing a tree for all of the entries as lookup objects; selecting an intermediate node location as a virtual entry representative of the lookup group by coming upstream by a fixed number of hops from the farthest point from the tip root, out of all the leaves at the distal ends of the tree; excluding branches below the node location of the selected virtual entry and repeating the procedure; storing the selected virtual entries in the masked lookup memory means until all of the entries have been covered; determining during lookup whether the virtual entry matches the conditions by referencing the masked lookup memory means; and performing further lookups using the tree.
The above high-speed lookup method further comprises the step of, when lookup occurs within the object group, performing a lookup in a table using a table lookup offset determined by the region from where the lookup key value bit string from the lookup object entry within the group first differ
Fujitsu Limited
Katten Muchin Zavis & Rosenman
Metjahic Safet
Nguyen Camlinh
LandOfFree
High-speed lookup method and high-speed lookup apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed lookup method and high-speed lookup apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed lookup method and high-speed lookup apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3097285