Electrical computers and digital processing systems: processing – Processing control – Logic operation instruction processing
Reexamination Certificate
1999-02-05
2002-01-22
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Logic operation instruction processing
C712S245000, C712S248000, C712S300000, C709S238000, C370S392000
Reexamination Certificate
active
06341346
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method for comparing a pattern sequence with a key whose length is not predetermined.
In several fields such as transmission media, computing engines and software, data communications and internetworking, it is necessary to move data in a network depending on routing information which is inserted in a pattern preceding these data. Typical equipments involved in this routing operation are switches and routers.
Today's data communication systems would not exist without routers which are used to link remote sites but routing is considered to be one of the major bottlenecks in these systems essentially due to the processing time and the required memory.
Routers should be considered in a very broad sense since, within the past few years, they often happen to be replaced by switches. Anyway, routing functions are still needed even on switched networks, at least at boundaries.
A first main routing function is the determination of a routing path across the network using specific protocols. The path determination is based on a variety of metrics such as the delay introduced by the network or the link cost. In addition, this determination takes into account other rules generically called filtering, such as communication restrictions or priority criteria.
A second routing function is frame forwarding, that is to say the processing of inbound data and the subsequent forwarding of these data to the appropriate outbound destination.
In the case of routers, both functions, the determination of the routing path and the frame forwarding, are performed within the same device. Nevertheless, new techniques tend to exploit the differences between these functions, separating the corresponding operations. For instance, a single routing path calculator could support several frame forwarding units.
Now, it appears that routers show some limitations.
As seen before, the processing time is relatively high and is strongly variable from one routing calculation to another one. It is therefore difficult to support many time sensitive applications such as multimedia.
One critical time consuming operation is the searching function. This operation can be seen as the retrieval of routing information located in the pattern, in particular the destination of the data corresponding to this pattern. The searching involves essentially comparisons between a part of this pattern, or sequence, and predetermined bit series, or keys, which identify appropriate routing information. For this reason, efforts have been made to optimize the speed of comparison by using parallel processing but this method has its own limitations.
Another way to speed up the searching function is to proceed with partial comparisons between a sequence and a key instead of looking for a full match.
It is therefore state of the art to search for the longest prefix shared by this sequence and this key.
As an example, such a method is disclosed in the article “Routing on longest-matching prefixes ”, IEEE/ACM Transactions on Networking, vol. 4, no. 1, February 1996, pages 86-97.
According to this method, a tree is built up which represents the searching process. This tree is made up of nodes linked together according to an arborescent structure of a binary type. Each node, apart from the root which is the top of the tree, is linked to a parent node. In addition, each node is linked with at most two children. A node represents an elementary step (a partial comparison) in the searching process.
At first, this solution needs a lot of memory for storing the required information in each node. As a consequence, this is not really favorable for the optimization of the processing time.
In other respects, the tree is an evolutional structure and it is necessary to be able to both delete and insert nodes. It appears that in the above solution it is not possible to modify the tree while a search is made.
So, it becomes difficult to manage the tree evolution and searching operations.
SUMMARY OF THE INVENTION
It is therefore a general object of the present invention to provide for a method for searching for routing information that is simple to implement and which is very fast and needs little memory.
Another object of this invention is to allow data sharing between different units involved in the determination of the routing path or in the result of this determination.
It is still a further object of this invention to make the operations associated with searching easier.
In accordance with the present invention, there is provided a method for comparing a pattern sequence with a variable length key; a first bit of the sequence being identified by a pointer, the length and the location of the key being identified by a code word, this method includes a preliminary step for identifying the sequence and then performing a comparison step.
Proceeding in such a way allows use of a unique type of step of searching keys of different lengths in the pattern.
According to this method, a further step is identified by a first address when the comparison is true.
In a preferred embodiment, the sequence is shifted by a first shifting value equal to the length of the key prior to this further step.
Thus, the further step is prepared while executing the first selection single step.
An improvement of the addressing is such that the first address includes a zone indication.
In the same way, a further step is identified by a second address when the comparison is false.
According to an advantageous arrangement, a predetermined value of a field of the first or second address identifies a part of this address as an external return address.
As an interesting feature, the second address is a predetermined function of the first address.
This solution allows not specifically providing the second address.
In addition, the method provides for an age word associated with the comparison step, which age word is incremented when this step is performed.
This is a way to check if the comparison step is used or not, which is useful information in order to manage the tree evolution. In fact, when a step is never used, it could be suitable to delete it.
In addition, a parent word associated with the comparison step identifies the address of a step preceding the comparison step.
In a preferred embodiment, the parent word includes a zone indication.
This method can also be used in conjunction with other types of steps; in this case, it is convenient to identify the above comparison step by a mode indication.
The method is advantageously implemented on a finite state machine.
REFERENCES:
patent: 3858240 (1974-12-01), Golding et al.
patent: 3891994 (1975-06-01), Phillips et al.
patent: 4212028 (1980-07-01), Drewery
patent: 4290105 (1981-09-01), Cichelli et al.
patent: 4315278 (1982-02-01), Pasdera
patent: 4459677 (1984-07-01), Porter et al.
patent: 4491861 (1985-01-01), Sochor
patent: 4500912 (1985-02-01), Bolger
patent: 4564915 (1986-01-01), Evans et al.
patent: 4580134 (1986-04-01), Campbell et al.
patent: 4612532 (1986-09-01), Bacon et al.
patent: 4633490 (1986-12-01), Goertzel et al.
patent: 4644389 (1987-02-01), Nakagawa et al.
patent: 4707729 (1987-11-01), Bruno et al.
patent: 4736287 (1988-04-01), Druke et al.
patent: 4768082 (1988-08-01), Hiratsuka et al.
patent: 4847677 (1989-07-01), Music et al.
patent: 4876541 (1989-10-01), Storer
patent: 4905297 (1990-02-01), Langdon, Jr. et al.
patent: 4956774 (1990-09-01), Shibamiya et al.
patent: 4961139 (1990-10-01), Hong et al.
patent: 5003299 (1991-03-01), Batson et al.
patent: 5020058 (1991-05-01), Holden et al.
patent: 5032987 (1991-07-01), Broder et al.
patent: 5043885 (1991-08-01), Robinson
patent: 5121494 (1992-06-01), Dias et al.
patent: 5121495 (1992-06-01), Nemes
patent: 5258983 (1993-11-01), Lane et al.
patent: 5287499 (1994-02-01), Nemes
patent: 5319682 (1994-06-01), Clark
patent: 5335345 (1994-08-01), Frieder et al.
patent: 5381145 (1995-01-01), Allen et al.
patent: 5390359 (1995-02-01), Damerau
patent: 5406281 (1995-04-01), Klayman
patent: 5424732 (1995-06-01), Iyer et al.
Benayoun Alain
Le Pennec Jean-Francois
Michel Patrick
Pin Claude
Cesari and McKenna LLP
Treat William M.
LandOfFree
Method for comparison between a pattern sequence and a... 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 for comparison between a pattern sequence and a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for comparison between a pattern sequence and a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2841789