Method of associating forwarding references with data...

Details Method of associating forwarding references with data... Method of associating forwarding references with data...

2000-01-28

2004-03-09

Ngo, Ricky (Department: 2697)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S401000, C711S216000, C712S017000

Reexamination Certificate

active

06704313

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to associative memories and in particular memories of the <<TRIE>> type (derived from the English verb <<reTRIEve>>).
The principle of the <<TRIE>> memory was proposed by R. de la Briandais and E. Fredkin et al towards the end of the 1950s (see E. Fredkin et al.: <<Trie Memory>>, Communications of the ACM, Vol. 3, No. 9, September 1960, pages 490-499). It consists in cutting up the bit strings to be recognised into successive slices of a fixed length (of K bits) and integrating them in a two-dimensional table T. Each row of the table constitutes a register of 2
K
elementary cells. A register (R) is assigned to each slice of the string and a cell in the register is associated with the value (V), ranging between 0 and 2
K
−1 of this slice. The contents (C=T[R,V]) of the cell determined in this manner represent either the register allocated to the subsequent slice (or pointer) or an end of analysis reference (or <<status>>) if the analysis of the string must end on this slice.
The register allocated to the first slice of the string, which is also the point of entry to the table, is also referred to as the gate. The data to be analysed in the form of bit strings, i.e. to be compared with the contents of the TRIE memory, will also be referred to as routes hereafter. The term path will be used to denote the succession of concatenated cells in the table associated with a route. Each register of the table will be said to be of the order of i≧0 if it is attributed to the (i+1)-th slice of one or more stored routes. The gate register will therefore be in the order of 0. The TRIE memory associates with each of the registers in the order of i≧0 a unique sequence of iK bits corresponding to the iK first bits of each route whose path in the table passes via a cell of the register in question.
The following example will provide an illustration of how data is stored in a TRIE memory in the specific case where K=4. The value of each slice is represented by a digit in hexadecimal numbering (0,1, . . . E,F) and each of the registers contains 2
4
=16 cells.
Let us assume that the routes to be recognised are those commencing with the codes
45
A
4
,
45
AB,
67
AB,
788
A and
788
BD, to which the statuses S
0
, S
1
, S
2
, S
3
and S
0
have been allocated respectively (a same status may be shared by several routes). By using the row index for the register R and the column index for the value V of the slices and by taking the register R
0
=0 as the gate, the table of the TRIE memory will appear as illustrated in
FIG. 1
, the underlined data being the statuses. The codes
45
A
4
,
45
AB,
67
AB,
788
A and
788
BD are represented respectively in the table of
FIG. 1
by the paths:
T[
0
,
4
]→T[
1
,
5
]→T[
2
,A]→T[
3
,
4
];
T[
0
,
4
]→T[
1
,
5
]→T[
2
,A]→T[
3
,B];
T[
0
,
6
]→T[
4
,
7
]→T[
5
,A]→T[
6
,B];
T[
0
,
7
]→T[
7
,
8
]→T[
8
,
8
]→T[
9
,A];
T[
0
,
7
]→T[
7
,
8
]→T[
8
,
8
]→T[
9
,B]→T[
10
,D].
From this example, it may be seen that all the codes starting with a common part of iK bits are represented by a common initial path in the memory leading to the register of order i with which the sequence formed by these iK bits is associated.
If we consider a route to be analysed, cut up into a series of binary slices of values V
i
where 0≦i≦N and {R
i
} is the series of registers associated with the values V
i
, where R
0
still denotes the gate register, the analysis algorithm implemented may be that illustrated in FIG.
2
.
On initialisation
1
of this algorithm, the analysis rank i is set to 0 and the gate register R
0
is selected as the register R. In each iteration of rank i, the contents C of the cell T[R,V
i
], denoted by the (i+1)-th slice V
i
of the route in the register of order i selected, is read at step
2
. If this cell contains a continue analysis pointer, which is indicated at test
3
by the value 1 for a bit FP(C) stored in the cell, the register of order i+1 denoted by this pointer Ptr(C) is selected as the register R for the next iteration at step
4
and the rank i is incremented. If test
3
reveals a cell which does not contain a pointer (FP(C)=0), the status Ref(C) read in the cell concerned is returned at step
5
as a result of looking up the table.
This algorithm enables routes containing any number of slices to be analysed. A same table may be used for several types of analysis, managing data on the basis of different gates. Furthermore, it enables the analysis time of the data to be controlled: analysing a number N of slices of K bits will require at most N times the duration of one iteration.
The algorithm of
FIG. 2
may be implemented very rapidly by a hardware component managing accesses to the table memory. In particular, it will enable high-performance routers to be set up for packet-switched telecommunications networks. The header of the packets is analysed by the component on the fly and the status associated with a route designates, for example, an output port of the router to which the packets bearing a destination address conforming to this route must be routed.
Such a router may be a multi-protocol router. This being the case, the different sections of the header are analysed from different gates. For example, a first analysis of a header field (or several) indicating the protocol used and/or the version of this protocol may be analysed from a first gate. This first analysis will provide a reference which, although corresponding to a logical end of the analysis, may be embodied in the TRIE memory by a continue analysis pointer denoting another gate register to be used for analysing the rest of the header. The reference in question may also trigger time delays or skips by a given number of bits in the header being analysed in order to be able to choose which portion of the header should be analysed next. In practice, a certain number of analyses are generally run in succession in order to trigger the operations required by the protocols supported, depending on the content of the headers. One of these analyses will relate to the destination address needed to complete the routing function strictly speaking.
A router of the type outlined above is described in U.S. Pat. No. 5,781,431. On the subject of using a TRIE memory in routers, reference may be made to the article <<Putting Routing Tables in Silicon>> by T. B. Pei et al., IEEE Network Magazine, January 1992, pages 42-50.
The fact of being able to string together several elementary analyses and insert programmable skips between them lends a high degree of flexibility to the method, particularly when processing encapsulated protocols of the ISO model in several layers. Analysing slices of the header on the fly as they arrive also enhances speed.
However, in a certain number of situations, it is useful to be able to move backward in the header in order to examine certain fields in an order other than that in which they arrived. This will often allow better optimisation of the memory size required. It is also a feature required by certain protocols, such as the RSVP reservation protocol or multicast protocols.
An object of the present invention is to further improve the processing flexibility offered by TRIE memories, especially in routing applications.
SUMMARY OF THE INVENTION
Accordingly, the invention proposes a method of associating forwarding references with data packets by means of a TRIE memory, whereby different gate registers of the TRIE memory analyse in succession different portions of a header of each packet containing protocol data. When a packet arrives, its header is stored in a buff

Affiliated with

Also associated with

Rating

Method of associating forwarding references with data... 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 associating forwarding references with data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of associating forwarding references with data... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3251026