Error detection/correction and fault detection/recovery – Pulse or data error handling – Memory testing
Reexamination Certificate
1999-09-14
2002-07-23
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Memory testing
C714S799000
Reexamination Certificate
active
06425099
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 portal register. 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 stringed cells in the table associated with a route. Each register of the table will be said to be of order i≧0 if it is attributed to the (i+1)-th slice of one or more stored routes. The portal register will therefore be of order 0. The TRIE memory associates with each of its registers of order 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 patterns
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 portal register, 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 common a 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 portal register, the analysis algorithm implemented may be that illustrated in FIG.
2
.
On initialisation
1
of this algorithm, the rank of analysis i is set to 0 and the portal 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 will indicate at test
3
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, by organising the data on the basis of different portal registers. 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 controlling the accesses to the memory array. 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 on the basis of different portal registers. 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 portal register. This first analysis will provide a reference which, although corresponding to a logical end of the analysis, may be incorporated in the TRIE memory by a continue analysis pointer denoting another portal 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 addressed needed to complete the routing function strictly speaking.
A router of the type outlined above is described in French patent 2 707 775. 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 Internet Protocol (IP) is one of the communication protocols which may be supported by the router.
The IP routing process is essentially based on analysing the destination addresses of level 3 of the protocol (see C. Huitéma: <<Le Routage dans I'Internet>>, Editions Eyrolles, 1995). The addresses of the frames to be routed are inscribed in an internal management table, called a routing table or <<forwarding table>>, where they are associated with parameters which characterise the accesses to which they are directed. In its broad lines, the routing operation consists in comparing the addresses carried by the incoming frames with those contained in the table and directing them to the correct interface.
Most of the addresses are declared in what is referred to as an aggregate form. An aggregate describes a set of addresses by means of the data in a common header and a mask which sets the bit length of the part of the address to be analysed. This presentation of the data in the table is very much linked to the way in which addresses are assigned, associating an aggregate to
Duret Christian
Guesdon Hervé
Lattmann Joël
Chung Phung M.
France Telecom
Marshall Gerstein & Borun
LandOfFree
Method of updating an associative memory of the TRIE type,... 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 updating an associative memory of the TRIE type,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of updating an associative memory of the TRIE type,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826868