Electrical computers and digital processing systems: memory – Address formation – Generating a particular pattern/sequence of addresses
Reexamination Certificate
1999-02-05
2002-06-04
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Generating a particular pattern/sequence of addresses
Reexamination Certificate
active
06401188
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method for making a selection on a pattern sequence.
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 this 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 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 making a selection on a pattern sequence depending on whether this sequence belongs to a routing set, the routing set comprising at least two keys; the selection is made in a single step by means of a selection word identifying the routing set.
Proceeding in such a way leads to time sparing because the plurality of keys belonging to the routing set lead to the same further action. On the contrary, according to the prior art, in the worst case, a number of steps equal to the number of keys is required to get the same result.
According to this method, a further step is identified by a first address when the sequence belongs to the routing set.
In a preferred embodiment, the sequence is shifted by a first shifting value 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 sequence does not belong to the routing set.
In a preferred embodiment, the sequence can also be shifted by a second shifting value prior to this further step and the second address could also include a zone indication.
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 single step selection, which age word is incremented when this step is performed.
This is a way to check if the selection single 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 single step identifies the address of a step preceding the single 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 single step selection 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
pa
Benayoun Alain
Le Pennec Jean-Francois
Michel Patrick
Pin Claude
Cesari and McKenna LLP
Cisco Technology Inc.
Johnston A. Sidney
Nguyen Hiep T.
LandOfFree
Method for selection on a pattern sequence 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 selection on a pattern sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for selection on a pattern sequence will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980835