[go: up one dir, main page]

EP1678632A1 - Dispositif de memoire de type trie avec mecanisme de compression - Google Patents

Dispositif de memoire de type trie avec mecanisme de compression

Info

Publication number
EP1678632A1
EP1678632A1 EP03767854A EP03767854A EP1678632A1 EP 1678632 A1 EP1678632 A1 EP 1678632A1 EP 03767854 A EP03767854 A EP 03767854A EP 03767854 A EP03767854 A EP 03767854A EP 1678632 A1 EP1678632 A1 EP 1678632A1
Authority
EP
European Patent Office
Prior art keywords
cell
stage
memory
analysis
register
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
EP03767854A
Other languages
German (de)
English (en)
Inventor
Joel Lattmann
Christian Duret
Valéry LASPRESES
Francis Rischette
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Orange SA
Original Assignee
France Telecom SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom SA filed Critical France Telecom SA
Publication of EP1678632A1 publication Critical patent/EP1678632A1/fr
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup; Address filtering
    • H04L45/74591—Address table lookup; Address filtering using content-addressable memories [CAM]

Definitions

  • the present invention relates to associative memories, and in particular memories of the "TRIE" type (from the English verb "reTRIEve”).
  • ACM Communications of the ACM, Vol. 3, No. 9, September 1960, pages 490-499). It consists of cutting the bit strings to be recognized into successive slices of fixed length (of K bits) and integrating them into 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 section of the chain and a cell in the register is associated with the value (V), between 0 and 2 K -1 of this section.
  • the register assigned to the first section of the chain which is also the entry point of the table, is called a porter.
  • the data to be analyzed in the form of bit strings, that is to say to compare with the content of the TRIE memory, will also be called routes below.
  • the succession of chained cells associated with a route will be called path in the table.
  • Each register of the table will be said to be of order i> 0 if it is assigned to the (i + 1) th section of one or more stored routes.
  • the gatekeeper register is therefore of order 0.
  • the memory ⁇ TRîE ⁇ associates with each of its registers of order i> 0 a unique sequence of iK bits corresponding to the first iK bits of each route whose path in the table passes through a cell of the register in question.
  • TRIE can be presented as shown in Figure 1, where the underlined data is status.
  • the patterns 45A4, 45AB, 67AB, 788A and 788BD are respectively represented 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].
  • the analysis rank i is set to 0 and the gate register R 0 is selected as register r.
  • the content C of cell T [r, V j ] designated by the (i + 1) -th tranche V s of the route in the selected order register i is read in step 2. If this cell contains a further analysis pointer, as indicated in test 3 by the value 1 of a bit FP (C) stored in the cell, the order register i + 1 designated by this pointer Ptr (C) is selected as register r for the next iteration in step 4, and rank i is incremented.
  • the status Ref (C) read in the cell concerned is returned to step 5 as a result of consulting the table.
  • This algorithm allows the analysis of routes comprising any number of sections.
  • the same table can be used for several types of analyzes by managing the data from different gatekeepers.
  • it allows to control the time of data analysis: the analysis of a number
  • N of K-bit slices will last at most N times the duration of an iteration.
  • the algorithm of FIG. 2 can be implemented very quickly by a hardware component managing access to the memory table.
  • a hardware component managing access to the memory table.
  • the packet header is analyzed on the fly by the component, and the status associated with a route designates, for example, an output port of the router to which the packets carrying a destination address conforming to this route must be routed.
  • Such a router can be multi-protocol.
  • the reference in question can also trigger timers or jumps of a determined number of bits in the analyzed header in order to be able to choose which portion of the header should then be analyzed.
  • a certain number of analyzes are generally executed successively, to trigger the operations required by the supported protocols according to the content of the headers.
  • One of these analyzes will relate to the destination address to perform the routing function proper.
  • the fact of being able to chain several elementary analyzes with programmable hops between them gives great flexibility to the process, particularly for the treatment of protocols encapsulated according to several layers of the ISO model.
  • the on-the-fly analysis of the header slices as they arrive also provides great speed.
  • TRIE tables Another advantage of the TRIE tables is that it allows routing constraints to be taken into account on the basis of the longest recorded path corresponding to a prefix of the route to be recognized, a constraint encountered in particular in the context of IP routing (see EP -A-0 989 502).
  • EP-A-1 030 493 describes a TRIE memory, the content of which includes, in addition to the references proper associated with the packet headers, a program consisting of the sequence of elementary analyzes to be carried out according to the different configurations taken into account by Memory. These sequences are fully programmable. The user can arbitrarily define, at each step of the process, which portion of the header should be examined and from which register of the TRIE memory, which provides great processing flexibility.
  • a TRIE memory can also be described in tree form, with nodes distributed in several successive stages corresponding to the analysis orders i previously mentioned. Each node of a stage i represents a decision to be made during the analysis of the (i + 1) th section of a route.
  • the root node of the tree corresponds to the gatekeeper register, the leaf nodes to the status, and the intermediate nodes to the registers designated by the further analysis pointers.
  • the tree representation makes it easy to visualize the paths.
  • the tree in FIG. 3 thus shows the paths recorded in the table in FIG. 1, the root and the intermediate nodes being represented by circles (registers) and the leaves by rectangles (status).
  • the tree representation makes it possible to design compression methods aimed at reducing the memory size required to implement a TRIE table. This reduction is particularly useful for rapid implementations of large tables using static memory circuits (SRAM).
  • SRAM static memory circuits
  • a hardware implementation in the form of a table where each register contains 2 K cells is ineffective in terms memory occupation because such a table has many empty cells, as shown in Figure 1.
  • the nodes close to the root have a number of descendants valid close the number of possible descendants (2).
  • the average number of valid descendants of a given node decreases considerably and tends towards 1 (or 2 if we take into account a default status). In this case, there are only between 10% and 15% of useful cells in the memory.
  • path compression consists in aggregating at a node Y a stage i the non-empty nodes of stages i + 1 to i + j-1 (j ⁇ 2) which are descendants of this node Y when each of these nodes of stages i to i + j-1 has a single non-empty descendant (register or status). See also US-A-6,014,659 or US-A-6,505,206.
  • level compression consists in aggregating at a node Z of a stage i the non-empty nodes of stages i + 1 to i + j-1 (j ⁇ 2) which are descendants of this node Z when each of these nodes of stages i + 1 to i + j-1 itself has at least one non-empty descendant (register or status).
  • the length of the slice to be analyzed in relation to the compressed node Z is multiplied by j; - compression in extent ("width compression” or "pointer compression”) consists in eliminating the empty descendants of a given node, see also US-A-5,781,772, EP-A-0 458 698 or WO 00/75804 . It is useless to reserve a register of 2 K cells to analyze a slice having only L ⁇ 2 K valid values in paths recorded in the TRIE memory: we can be satisfied with a compressed area of L cells, associated with map data showing values valid of the range.
  • This cartographic data typically takes the form of a bitmap vector of 2 K bits set to 1 at the L positions corresponding to the L valid values of the slice and at 0 at the 2 K -L other positions.
  • the modification during analysis of the length of the slices cut out in the data to be analyzed does not lend itself to rapid implementation in a specific hardware component. It essentially makes it possible to reduce the memory size required by a software implementation, which by nature is slower.
  • the extended compression method does not suffer from this limitation. However, it requires that the actual analysis of a section be preceded by the analysis of the associated bitmap to validate the value of the section and locate the corresponding cell.
  • This method can be implemented in a fast hardware module, but a limitation to this speed is that its complexity increases strongly with the width K of the slice. Indeed, the function used to obtain the address of the successor of a given node requires resources (size of the nodes) of complexity proportional to 2.
  • a TRIE table is suitable for parallel processing in pipeline mode, as mentioned in the article "Putting Routing Tables in Silicon", by TB. Pei et al., IEEE Network Magazine, January 1992, pages 42-50.
  • M the maximum number of stages in the tree
  • the available memory space can be divided into N memory planes, with N ⁇ M.
  • Each memory plan P: of level j (0 ⁇ j ⁇ N) is reserved for the nodes of one or more consecutive stages of the tree.
  • N operators operate in parallel with each a respective buffer containing a data chain to analyze.
  • This pipeline processing by the N operators increases the maximum processing rate of the device.
  • An object of the present invention is to propose an efficient method for compressing a TRIE memory, which facilitates high speed processing of strings of data to be analyzed and can be implemented by a hardware component of limited complexity.
  • the invention thus provides a TRIE memory device, comprising means for storing binary patterns associated with respective references, and means for analyzing data strings by successive K-bit slices to extract one of the references during a agreement between an analyzed data string and a stored binary pattern associated with this reference (K> 1).
  • the storage means comprise several successive stages, each including several memory cells.
  • Each non-empty memory cell of a stage i ⁇ 0 contains a cell type indicator and data comprising: - a pointer designating another memory cell when the cell type indicator is in a first or a second state , the pointer being accompanied by a test value on K bits when the cell type indicator is in the second state; - a reference associated with a binary pattern stored when the cell type indicator is in a third state.
  • the analysis means include: - means for reading a cell of a stage i ⁇ 0 in connection with the analysis of the (i + 1) th section of a data chain; - means for selecting a cell of stage i + 1, to be read in relation to the analysis of a (i + 2) -th slice of the data chain, in response to the first state of the indicator in said cell of stage i, the selected cell being located in relation to the cell designated by the pointer contained in said cell of stage i as a function of the value of the (i + 1) th tranche of the data string; means for selecting the cell designated by the pointer contained in said cell of stage i, to be read in relation to the analysis of a (i + 2) -th slice of the data chain, in response to the second state of the indicator in said cell of stage i when the value of the (i + 1) -th slice of the data chain coincides with the test value contained in said cell of stage i; and - means for extracting the reference contained in said cell of stage i in response to the
  • the sons of a node of the TRIE tree can in particular be located, preferably in a reversible manner, either in a register comprising all the possible successors of a given node (register of 2 K cells), or in a zone constituting a minimum register (of one or two cells) as soon as the conditions of "path compression" are met (the node has only one valid node-child).
  • a pointer then designates either the first cell of the 2 K cell register, or the cell or the first cell of the zone constituting the minimum register.
  • the device thus implements an intermediate process between compression in extent and compression of path.
  • Compression results from the fact that a tree node through which only one memorized path passes does not need to point to another register of 2 K cells. It just needs to point to a reduced area of one or two cells, which occupies less memory space.
  • An advantage of this device is that it lends itself to a simple hardware implementation given that the size of the slices analyzed remains fixed and that the analysis of a slice can be carried out in a clock cycle. However, like the extended compression method, it does not suffer from the exponential increase in the size of the nodes with the size of the slices analyzed. With a given component technology, it is then possible to increase the processing speed of the device by increasing the size of the slices without being penalized by too great a complexity.
  • the analysis means preferably return a default reference.
  • This default reference can be common to the entire TRIE tree. It is however advantageous that it depends on the node to which said cell of stage i corresponds. The default reference can then be the one associated with the longest recorded path corresponding to a prefix of the route to be recognized ("iongest match").
  • the storage means are divided into N distinct memory areas of levels 0 to N-1, N being less than a maximum number of stages of the storage means, and the analysis means are organized in pipeline in relation to the N memory areas.
  • FIG. 2 is a flow diagram of a conventional analysis procedure executed to consult the TRIE memory
  • - Figure 3 is a tree representation of the TRIE memory having the content illustrated in Figure 1
  • - Figure 4 is a block diagram of a packet router incorporating a device according to the invention
  • - Figure 5 is a diagram of a circuit forming a device according to the invention
  • - Figure 6 is a tree representation of a TRIE memory organized according to the invention
  • - Figure 7 shows in three diagrams an example of the content of a memory cell in one embodiment of the invention
  • - Figure 8 is a tree representation of a TRIE memory organized according to another embodiment of the invention
  • - Figure 9 is a flowchart illustrating a software-based embodiment of a device functionally similar to that of Figure 5.
  • ATM Asynchronous Transfer Mode
  • the router 10 shown in FIG. 4 operates with a host computer 11.
  • the host computer 11 can send and receive packets, in particular for managing the routing process. For this, it has a virtual channel (VC) at the input and output of router 10.
  • VC virtual channel
  • the router 10 comprises a forwarding module 12 which routes the received packets according to instructions, hereinafter called “routing references” or "final status", obtained by an analysis module 13 from of a memory 14 organized as a TRIE memory table.
  • the routing module 12 can essentially carry out a translation of the virtual path identifiers VPI / VCI (Virtual Path Identifier / Virtual Channel Identifier), the fusion of the virtual channels according to the virtual paths, and the delivery of the packets on the output ports of the router. For this, it needs to know the VPI / VCI pairs of outgoing packets, which can constitute the routing references stored in the TRIE memory 14.
  • Each ATM cell containing the header of a packet to be routed passes through a buffer memory 15 to which the analysis unit 13 has access to analyze portions of these headers by means of the TRIE memory 14.
  • Configuring the router 10 consists in recording the relevant data in the TRIE memory 14. This operation is carried out by a unit (not shown) for managing the TRIE memory under the control of the computer. host 11.
  • the configuration commands can be received in packets transmitted over the network and intended for the router 10.
  • EP-A-0 989 502. In the example of router shown in FIG. 4, the analysis unit
  • the router 13 cooperates with a PLC 16 programmed to perform certain checks and certain actions on the packet headers, in a manner dependent on the communication protocols supported by the router. Apart from this automaton 16, the operation of the router 10 is independent of the packet transport protocols.
  • FIG. 5 shows a TRIE memory device according to the invention.
  • each elementary cell of the TRIE memory occupies
  • FIG. 5 Found in FIG. 5 is the analysis unit 13, the TRIE memory 14, as well as the buffer memory 15 intended to receive a data chain to be analyzed by K-bit slices.
  • the TRIE memory comprises a memory plane 14, advantageously produced in SRAM ("Static Random Access Memory") technology.
  • This memory plane comprises a data bus D of width 32 bits, as well as an address bus AD, the width of which depends on the quantity of data to be stored in the memory TRIE.
  • Each register includes one or more memory cells of 32-bit size, addressable by the AD bus.
  • FIG. 6 shows a way in accordance with the invention of organizing the cells of a TRIE tree from a root node of a stage ⁇ .
  • the register 100 is the gatekeeper register of the memory.
  • the cells marked S in FIG. 6 are of the status type and contain a reference associated with one of the saved paths.
  • the cells marked R each contain a pointer in "register” mode, which designates a register of 2 K cells of the next stage. The pointer in register mode therefore designates, explicitly or implicitly, the first cell of this register of the next stage.
  • the cells marked L each contain a pointer in "linear" mode, which designates a cell isolated from the next stage.
  • the other cells, not marked in FIG. 6, do not contain useful information relating to recorded paths. It can be seen that the use of the linear mode makes it possible to reduce the number of these empty cells, and therefore to optimize the use of the available memory space.
  • pointer In register mode, the operation of pointers is identical to that described in the introduction.
  • the pointer locates the register in which the analysis will be to continue, and the value of the current section of K bits makes it possible to locate the cell of this register which will be read to continue the analysis.
  • FIG. 7 shows the content of a memory cell in a particular exemplary embodiment.
  • the first four bits of the cell represent an FP flag whose value indicates in particular the type (status, pointer in register mode or pointer in linear mode) of the data stored in the cell.
  • the 28 remaining bits of the cell constitute the Ref reference used in the operation of routing packets and / or commands intended for the PLC 16.
  • the address calculation logic 21 proceeds to concatenate the pointer PtrR and the value V j of the next slice to be analyzed to generate the address AD at which the next cell will be read in the memory 14.
  • the address calculation logic 21 provides on the address bus AD of memory 14 an address corresponding to the pointer PtrL received from the detection 20 so that the isolated cell designated by the pointer is read in relation to the slice V j . If V j ⁇ Val, the analysis ends by indicating that the analyzed chain does not correspond to any path recorded in the TRIE memory. the above description, the unoccupied cells of the tree
  • TRIE (or the cells eliminated in linear mode) give rise, when they are encountered during the analysis, to an indication of error interpreted as the absence of recorded pattern corresponding to the analyzed chain.
  • these cells are associated with a default reference which the detection circuit 20 returns when such a cell is encountered.
  • the default reference may, in certain applications, be the same for the entire TRIE tree. In this case, it is not necessary to store it in the nodes of the tree, so that one can use the data structure shown diagrammatically in figure 6.
  • this default reference can vary depending on the mother cell whose pointer designates such a default reference. This advantageously makes it possible to integrate the constraints linked to the "longest match" into the analysis.
  • the memory 14 can in particular receive a data structure such as that illustrated in FIG. 8.
  • the TRIE tree represented in this FIG. 8 contains the same paths as that of FIG.
  • FIG. 6 Each unoccupied cell in FIG. 6 is now occupied by a default reference, which is symbolized by the letter D in FIG. 8.
  • cells marked D contain the same default reference, which depends on the mother cell pointing to this register.
  • linear mode the cells are no longer isolated, but grouped in pairs.
  • the first cell of the pair has the same content as the isolated cell according to Figure 6, while the other cell contains a default reference, returned when V j ⁇ Val during the analysis of the upstream node.
  • the two cells of such a pair have consecutive addresses. Consequently, the analysis can be carried out using the circuit of the figure: it suffices that the address calculation logic 21 completes the pointer PtrL in linear mode by concatenating therein the bit v delivered by the comparator 22 to produce the address of the next cell to be read in linear mode.
  • FIG. 9 A software-based embodiment of this latter embodiment of the invention is illustrated in FIG. 9.
  • the flow diagram illustrates the operation of the circuit of FIG. 5, and can be used to produce an emulator.
  • the preferred embodiments of the invention are based on hardware, but it can also be envisaged, for applications which are not too fast, to use software.
  • the analysis rank i is set to 0 and the gate register R 0 is selected as register r.
  • the variable v of K bits receives the value V s of the current slot.
  • step 41 the algorithm returns to step 32 above. Its execution ends when a status is encountered (34), or on an error (43) if a cell type cannot be decoded (FP (C) ⁇ L in test 38).
  • the mode of compression and storage of the data of the TRIE memory which has just been described makes it possible to perform the analysis of the data strings in pipeline mode in order to increase the rate of analysis of the data, the memory 14 being distributed. in N distinct memory zones of levels 0 to N-1, as indicated above.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

La mémoire stocke des motifs binaires associés à des références respectives. Des chaînes de données sont analysées par tranches successives de K bits (K > 1) pour extraire une des références lors d'une concordance avec un motif binaire mémorisé associé à cette référence. La mémoire est organisée en plusieurs étages successifs de cellules de mémoire, l'analyse de la (i+1)-ième tranche d'une chaîne comportant un accès à une cellule d'un étage i >= 0. Chaque cellule non vide d'un étage i >= 0 contient soit un pointeur de poursuite d'analyse de type "registre", désignant un registre de 2<K> cellules de l'étage i+1, soit un pointeur de poursuite d'analyse de type "linéaire", désignant une zone d'une ou deux cellules formant un registre réduit de l'étage i+1, soit une référence associée à un motif binaire mémorisé.

Description

DISPOSITIF DE MEMOIRE DE TYPE TRIE AVEC MECANISME DE COMPRESSION
La présente invention concerne les mémoires associatives, et particulièrement les mémoires de type "TRIE" (du verbe anglais "reTRIEve").
Le principe de la mémoire "TRIE" a été proposé par R. de la Briandais et E. Fredkin vers la fin des années 1950 (voir E. Fredkin et al.: "Trie Memory",
Communications of the ACM, Vol. 3, No. 9, septembre 1960, pages 490-499). Il consiste à découper les chaînes de bits à reconnaître en tranches successives de longueur fixe (de K bits) et à les intégrer dans un tableau T à deux dimensions. Chaque ligne du tableau constitue un registre de 2K cellules élémentaires. Un registre (R) est attribué à chaque tranche de la chaîne et on associe une cellule dans le registre à la valeur (V), comprise entre 0 et 2K-1 de cette tranche. Le contenu (C = T[R,V]) de la cellule ainsi déterminée représente soit le registre attribué à la tranche suivante (ou pointeur), soit une référence de fin d'analyse (ou "status") si l'analyse de la chaîne doit se terminer sur cette tranche.
Le registre attribué à la première tranche de la chaîne, qui est aussi le point d'entrée de la table, est appelé portier. Les données à analyser sous forme de chaînes de bits, c'est-à-dire à comparer avec le contenu de la mémoire TRIE, seront également nommées routes ci-après. On appellera chemin dans la table la succession des cellules chaînées associées à une route. Chaque registre de la table sera dit d'ordre i>0 s'il est attribué à la (i+1 )-ième tranche d'une ou plusieurs routes mémorisées. Le registre portier est donc d'ordre 0. La mémoirë~TRîE~ associe à chacun de ses registres d'ordre i>0 une unique séquence de iK bits correspondant aux iK premiers bits de chaque route dont le chemin dans la table passe par une cellule du registre en question.
L'exemple suivant montre une représentation du stockage des données dans une mémoire TRIE dans le cas particulier où K = 4. La valeur de chaque tranche est représentée par un digit en numérotation hexadécimale (0,1 ,...,E,F), et les registres contiennent chacun 24=16 cellules. Soit à reconnaître les routes qui débutent par les motifs 45A4, 45AB,
67AB, 788A et 788BD, auxquels on attribue respectivement les status S0, S1 ,
S2, S3 et S0 (un même status peut être partagé par plusieurs routes). En portant le registre R en indice de ligne, la valeur V des tranches en indice dé colonne, et en prenant comme portier le registre R0 = 0, la table de la mémoire
TRIE peut se présenter comme représenté sur la figure 1, où les données soulignées sont des status. Les motifs 45A4, 45AB, 67AB, 788A et 788BD sont respectivement représentés dans la table de la figure 1 par les chemins : 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].
On voit sur cet exemple que tous les motifs commençant par une partie commune de iK bits sont représentés par un début de chemin commun dans la mémoire, menant au registre d'ordre i auquel est associée la séquence formée par ces iK bits.
Si l'on considère une route à analyser, découpée en une suite de tranches binaires de valeurs Vj avec 0 < i < N et {R la suite des registres associés aux valeurs Vj, R0 désignant encore le registre portier, l'algorithme d'analyse mis en œuvre peut être celui représenté sur la figure 2.
A l'initialisation 1 de cet algorithme, le rang d'analyse i est mis à 0 et le registre portier R0 est sélectionné comme registre r. Dans chaque itération de rang i, le contenu C de la cellule T[r,Vj] désignée par la (i+1)-ième tranche Vs de la route dans le registre d'ordre i sélectionné est lu à l'étape 2. Si cette cellule contient un pointeur de poursuite d'analyse, ce qu'indique au test 3 la valeur 1 d'un bit FP(C) mémorisé dans la cellule, le registre d'ordre i+1 désigné par ce pointeur Ptr(C) est sélectionné comme registre r pour l'itération suivante à l'étape 4, et le rang i est incrémenté. Quand le test 3 révèle une cellule qui ne contient pas un pointeur (FP(C)=0), le status Ref(C) lu dans la cellule concernée est retourné à l'étape 5 comme résultat de la consultation de la table.
Cet algorithme permet l'analyse de routes comportant un nombre quelconque de tranches. Une même table peut être utilisée pour plusieurs types d'analyses en gérant les données à partir de portiers différents. De plus, il permet de maîtriser le temps d'analyse des données : l'analyse d'un nombre
N de tranches de K bits durera au plus N fois la durée d'une itération.
L'algorithme de la figure 2 peut être mis en œuvre de façon très rapide par un composant matériel gérant les accès au tableau de mémoire. Il permet notamment la réalisation de routeurs de haute performance pour des réseaux de télécommunications à commutation de paquets. L'en-tête des paquets est analysé au vol par le composant, et le status associé à une route désigne par exemple un port de sortie du routeur vers lequel doivent être acheminés les paquets portant une adresse de destination conforme à cette route. Un tel routeur peut être multi-protocoles. Pour cela, on analyse des portions différentes de l'en-tête à partir de portiers différents. Par exemple, une première analyse d'un (ou plusieurs) champ de l'en-tête désignant le protocole employé et/ou la version de ce protocole peut être analysée à partir d'un premier portier. Cette première analyse fournit une référence qui, bien . que correspondant à une fin logique d'analyse, peut être matérialisée dans la mémoire TRIE par un pointeur de poursuite d'analyse désignant un autre registre portier à utiliser pour analyser la suite de l'en-tête. La référence en question peut également déclencher des temporisations ou des sauts d'un nombre déterminé de bits dans l'en-tête analysé afin de pouvoir choisir quelle portion de l'en-tête doit être ensuite analysée. Dans la pratique, un certain nombre d'analyses sont généralement exécutées successivement, pour déclencher les opérations requises par les protocoles supportés en fonction du contenu des en-têtes. L'une de ces analyses portera sur l'adresse de destination pour accomplir la fonction de routage proprement dite. Le fait de pouvoir enchaîner plusieurs analyses élémentaires avec entre elles des sauts programmables procure une grande souplesse au procédé, particulièrement pour le traitement de protocoles encapsulés suivant plusieurs couches du modèle ISO. L'analyse au vol des tranches de l'en-tête au fur et à mesure de leur arrivée procure par ailleurs une grande rapidité.
Un autre avantage des tables TRIE est de permettre la prise en compte de contraintes de routage sur la base du plus long chemin enregistré correspondant à un préfixe de la route à reconnaître, contrainte qu'on rencontre notamment dans le contexte du routage IP (voir EP-A-0 989 502).
EP-A-1 030 493 décrit une mémoire TRIE dont le contenu intègre, outre les références proprement dites associées aux en-têtes de paquets, un programme consistant en l'enchaînement des analyses élémentaires à effectuer en fonction des différentes configurations prises en compte par la mémoire. Ces enchaînements sont entièrement programmables. L'utilisateur peut définir arbitrairement, et à chaque étape du processus, quelle portion de l'en-tête doit être examinée et à partir de quel registre de la mémoire TRIE, ce qui procure une grande souplesse de traitement. Une mémoire TRIE peut aussi être décrite sous forme arborescente, avec des nœuds répartis en plusieurs étages successifs correspondant aux ordres d'analyse i précédemment mentionnés. Chaque nœud d'un étage i représente une décision à prendre lors de l'analyse de la (i+1 )-ième tranche d'une route. Le nœud-racine de l'arbre correspond au registre portier, les nœuds-feuilles aux status, et les nœuds intermédiaires aux registres désignés par les pointeurs de poursuite d'analyse. La représentation arborescente permet de visualiser aisément les chemins. L'arbre de la figure 3 montre ainsi les chemins enregistrés dans la table de la figure 1 , la racine et les nœuds intermédiaires étant représentés par des cercles (registres) et les feuilles par des rectangles (status).
La représentation arborescente permet de concevoir des méthodes de compression visant à réduire la taille mémoire requise pour mettre en œuvre une table TRIE. Cette réduction est particulièrement utile pour des implémentations rapides de tables de taille importante au moyen de circuits de mémoire statique (SRAM). Une réalisation matérielle sous forme de table où chaque registre comporte 2K cellules est en effet peu efficace en termes d'occupatîon de mémoire puisqu'une telle table comporte de nombreuses cellules vides, comme le montre la figure 1. Quand l'arbre est occupé par un grand nombre de données aléatoires, les nœuds proches de la racine ont un nombre de descendants valides proche du nombre de descendants possibles (2 ). Par contre, lorsque l'on s'éloigne de lé racine, le nombre moyen de descendants valides d'un noeud donné diminue considérablement et tend vers 1 (ou 2 si l'on prend en compte un status par défaut). Dans ce cas, il n'y a dans la mémoire qu'entre 10% et 15% de cellules utiles.
L'article "An Expérimental Study of Compression Methods for Functional Tries" de J-P. livonen, et al., soumis à la conférence WAAPL'99 (1999) passe en revue plusieurs méthodes de compression connues, combinables entre elles: - la compression de chemin ("path compression") consiste à agréger à un nœud Y d'un étage i les nœuds non vides des étages i+1 à i+j-1 (j≥2) qui sont des descendants de ce nœud Y lorsque chacun de ces nœuds des étages i à i+j-1 possède un unique descendant non vide (registre ou status). Voir aussi US-A-6 014 659 ou US-A-6 505 206. La longueur de la tranche à analyser en relation avec le nœud comprimé Y est multipliée parj; - la compression de niveau ("level compression") consiste à agréger à un nœud Z d'un étage i les nœuds non vides des étages i+1 à i+j-1 (j≥2) qui sont des descendants de ce nœud Z lorsque chacun de ces nœuds des étages i+1 à i+j-1 possède lui-même au moins un descendant non vide (registre ou status). La longueur de la tranche à analyser en relation avec le nœud comprimé Z est multipliée parj; - la compression en étendue ("width compression" ou "pointer compression") consiste à éliminer les descendants vides d'un nœud donné, Voir aussi US-A-5 781 772, EP-A-0 458 698 ou WO 00/75804. Il est inutile de réserver un registre de 2K cellules pour analyser une tranche n'ayant que L<2K valeurs valides dans des chemins enregistrés dans la mémoire TRIE: on peut se contenter d'une zone comprimée de L cellules, associée à des données cartographiques indiquant les valeurs valides de la tranche. Ces données cartographiques prennent typiquement la forme d'un vecteur bitmap de 2K bits mis à 1 aux L positions correspondant aux L valeurs valides de la tranche et à 0 aux 2K-L autres positions. Dans les méthodes de compression de chemin et de niveau, la modification en cours d'analyse de la longueur des tranches découpées dans les données à analyser se prête mal à une implémentation rapide dans un composant matériel spécifique. Elle permet essentiellement de réduire la taille mémoire requise par une implémentation logicielle, par nature moins rapide. La méthode de compression en étendue ne souffre pas de cette limitation. Elle requiert cependant que l'analyse proprement dite d'une tranche soit précédée par l'analyse du bitmap associé pour valider la valeur de la tranche et localiser la cellule correspondante. Cette méthode peut être implémentée dans un module matériel rapide, mais une limitation à cette rapidité est que sa complexité croît fortement avec la largeur K de la tranche. En effet, la fonction servant à obtenir l'adresse du successeur d'un nœud donné nécessite des ressources (taille des nœuds) de complexité proportionnelle à 2 .
Par ailleurs, une table TRIE se prête à un traitement parallèle en mode pipeline, comme évoqué dans l'article "Putting Routing Tables in Silicon", de T-B. Pei et al., IEEE Network Magazine, janvier 1992, pages 42-50. Si le nombre maximum d'étages de l'arbre est égal à M, c'est-à-dire si les chaînes de données à analyser peuvent aller jusqu'à M*K bits, on peut répartir l'espace mémoire disponible en N plans mémoire, avec N ≤ M. Chaque plan mémoire P: de niveau j (0 ≤ j < N) est réservé aux nœuds d'un ou plusieurs étages consécutifs de l'arbre. N opérateurs fonctionnent en parallèle avec chacun un tampon respectif contenant une chaîne de données à analyser. Pendant qu'un des N opérateurs effectue une analyse à l'ordre ou aux ordres consécutifs du niveau j, en accédant au plan mémoire R, un autre opérateur peut accéder au plan mémoire Pj_1 pour effectuer l'analyse d'une chaîne de données suivante à l'ordre ou aux ordres consécutifs du niveau j-1. Ce traitement en pipeline par les N opérateurs augmente la cadence maximum de traitement du dispositif.
Un but de la présente invention est de proposer une méthode efficace de compression d'une mémoire TRIE, qui facilite des traitements à grande vitesse de chaînes de données à analyser et puisse être implémentée par un composant matériel de complexité limitée.
L'invention propose ainsi un dispositif de mémoire TRIE, comprenant des moyens de mémorisation de motifs binaires associés à des références respectives, et des moyens d'analyse de chaînes de données par tranches successives de K bits pour extraire une des références lors d'une concordance entre une chaîne de données analysée et un motif binaire mémorisé associé à cette référence (K > 1 ). Les moyens de mémorisation comportent plusieurs étages successifs incluant chacun plusieurs cellules de mémoire. Chaque cellule de mémoire non vide d'un étage i ≥ 0 contient un indicateur de type de cellule et des données comportant: - un pointeur désignant une autre cellule de mémoire lorsque l'indicateur de type de cellule est dans un premier ou un second état, le pointeur étant accompagné par une valeur de test sur K bits lorsque l'indicateur de type de cellule est dans le second état; - une référence associée à un motif binaire mémorisé lorsque l'indicateur de type de cellule est dans un troisième état.
Les moyens d'analyse comprennent: - des moyens de lecture d'une cellule d'un étage i ≥ 0 en relation avec l'analyse de la (i+1 )-ième tranche d'une chaîne de données; - des moyens de sélection d'une cellule de l'étage i+1 , à lire en relation avec l'analyse d'une (i+2)-ième tranche de la chaîne de données, en réponse au premier état de l'indicateur dans ladite cellule de l'étage i, la cellule sélectionnée étant localisée par rapport à la cellule désignée par le pointeur contenu dans ladite cellule de l'étage i en fonction de la valeur de la (i+1 )-ième tranche de la chaîne de données; - des moyens de sélection de la cellule désignée par le pointeur contenu dans ladite cellule de l'étage i, à lire en relation avec l'analyse d'une (i+2)-ième tranche de la chaîne de données, en réponse au second état de l'indicateur dans ladite cellule de l'étage i lorsque la valeur de la (i+1 )-ième tranche de la chaîne de données coïncide avec la valeur de test contenue dans ladite cellule de l'étage i; et - des moyens d'extraction de la référence contenue dans ladite cellule de l'étage i en réponse au troisième état de l'indicateur dans ladite cellule de l'étage i.
Les fils d'un nœud de l'arbre TRIE peuvent notamment être localisés, de préférence de manière réversible, soit dans un registre comportant la totalité des successeurs possibles d'un nœud donné (registre de 2K cellules), soit dans une zone constituant un registre minimum (de une ou deux cellules) dès que les conditions de "compression de chemin" sont réunies (le nœud n'a qu'un seul nœud-fils valide). Un pointeur désigne alors soit la première cellule du registre de 2K cellules, soit la cellule ou la première cellule de la zone constituant le registre minimum.
Le dispositif met ainsi en œuvre un procédé intermédiaire entre compression en étendue et compression de chemin.
La compression résulte de ce qu'un nœud de l'arbre par lequel ne passe qu'un seul chemin mémorisé n'a pas besoin de pointer vers un autre registre de 2K cellules. Il suffit qu'il pointe vers une zone réduite d'une ou deux cellules, qui occupe moins d'espace mémoire.
Un avantage de ce dispositif est qu'il se prête à une réalisation matérielle simple étant donné que la taille des tranches analysées reste fixe et que l'analyse d'une tranche peut être réalisée en un cycle d'horloge. Cependant, il ne souffre pas, comme la méthode de compression en étendue, de l'augmentation exponentielle de la taille des nœuds avec la taille des tranches analysées. Avec une technologie de composants donnée, on peut alors accroître la vitesse de traitement du dispositif en augmentant la taille des tranches sans être pénalisé par une trop grande complexité. Lorsque l'indicateur présent dans la cellule de l'étage i lue pour l'analyse de la (i+1 )-ième tranche d'une chaîne de données est dans le second état et que la valeur de la (i+1 )-ième tranche de la chaîne de données diffère de la valeur de test contenue dans cette cellule de l'étage i, les moyens d'analyse retournent de préférence une référence par défaut. Cette référence par défaut peut être commune à l'ensemble de l'arbre TRIE. Il est cependant avantageux qu'elle dépende du nœud auquel correspond ladite cellule de l'étage i. La référence par défaut peut alors être celle qui est associée au plus long chemin enregistré correspondant à un préfixe de la route à reconnaître ("iongest match"). Dans un mode de réalisation avantageux, les moyens de mémorisation sont répartis en N zones de mémoire distinctes de niveaux 0 à N-1 , N étant inférieur à un nombre maximum d'étages des moyens de mémorisation, et les moyens d'analyse sont organisés en pipeline en relation avec les N zones de mémoire. D'autres particularités et avantages de la présente invention apparaîtront dans la description ci-après d'exemples de réalisation non limitatifs, en référence aux dessins annexés, dans lesquels: - la figure 1 , précédemment commentée, montre un exemple de contenu d'une mémoire TRIE; - la figure 2, précédemment commentée, est un organigramme d'une procédure d'analyse classique exécutée pour consulter la mémoire TRIE; - la figure 3, précédemment commentée, est une représentation arborescente de la mémoire TRIE ayant le contenu illustré par la figure î; - la figure 4 est un schéma synoptique d'un routeur de paquets incorporant un dispositif selon l'invention; - la figure 5 est un schéma d'un circuit formant un dispositif selon l'invention; - la figure 6 est une représentation arborescente d'une mémoire TRIE organisée selon l'invention; - la figure 7 montre en trois diagrammes un exemple de contenu d'une cellule de mémoire dans une réalisation de l'invention; - la figure 8 est une représentation arborescente d'une mémoire TRIE organisée selon un autre mode de réalisation de l'invention; et - la figure 9 est un organigramme illustrant une réalisation à base de logiciel d'un dispositif fonctionnellement semblable à celui de la figure 5. Pour illustrer la description ci-après, on considère le cas où des paquets à acheminer par un routeur sont transportés sur un réseau à mode de transfert asynchrone (ATM), et on suppose que l'en-tête de chaque paquet est toujours contenu dans une cellule ATM.
Le routeur 10 représenté par la figure 4 fonctionne avec un ordinateur- hôte 11. L'ordinateur hôte 11 peut émettre et recevoir des paquets, notamment pour la gestion du processus de routage. Il dispose pour cela d'une voie virtuelle (VC) en entrée et en sortie du routeur 10.
Le routeur 10 comprend un module d'acheminement ("forwarding") 12 qui achemine les paquets reçus selon des instructions, ci-après appelées "références d'acheminement" ou "status final", obtenues par un module d'analyse 13 à partir d'une mémoire 14 organisée comme un tableau de mémoire TRIE. Dans le cas d'un équipement de réseau ATM, le module d'acheminement 12 peut réaliser essentiellement une traduction des identifiants de conduits et de voies virtuels VPI/VCI ("Virtual Path Identifier / Virtual Channel Identifier"), la fusion des voies virtuelles selon les conduits virtuels, et la délivrance des paquets sur les ports de sortie du routeur. Pour cela, il a besoin de connaître les couples VPI/VCI des paquets sortants, qui peuvent constituer les références d'acheminement stockées dans la mémoire TRIE 14. Chaque cellule ATM contenant l'en-tête d'un paquet à router transite par une mémoire tampon 15 à laquelle l'unité d'analyse 13 a accès pour analyser des portions de ces en-têtes au moyen de la mémoire TRIE 14. Cette analyse est par exemple effectuée par quartets (K=4) ou par octets (K = 8).
Configurer le routeur 10 consiste à enregistrer les données pertinentes dans la mémoire TRIE 14. Cette opération est réalisée par une unité (non représentée) de gestion de la mémoire TRIE sous le contrôle de l'ordinateur- hôte 11. Les commandes de configuration peuvent être reçues dans des paquets transmis sur le réseau et destinés au routeur 10. Pour une façon de gérer dynamiquement le contenu de la mémoire TRIE 14, on pourra se reporter à EP-A-0 989 502. Dans l'exemple de routeur représenté sur la figure 4, l'unité d'analyse
13 coopère avec un automate 16 programmé pour effectuer certains contrôles et certaines actions sur les en-têtes des paquets, d'une manière dépendante des protocoles de communication supportés par le routeur. En dehors de cet automate 16, le fonctionnement du routeur 10 est indépendant des protocoles de transport des paquets.
La figure 5 montre un dispositif de mémoire TRIE selon l'invention.
Dans cet exemple, chaque cellule élémentaire de la mémoire TRIE occupe
32 bits. On retrouve sur la figure 5 l'unité d'analyse 13, la mémoire TRIE 14, ainsi que la mémoire tampon 15 destinée à recevoir une chaîne de données à analyser par tranches de K bits.
La mémoire TRIE comporte un plan mémoire 14, avantageusement réalisé en technologie SRAM ("Static Random Access Memory"). Ce plan mémoire comporte un bus de données D de largeur 32 bits, ainsi qu'un bus d'adresse AD, dont la largeur dépend de la quantité de données à stocker dans la mémoire TRIE. La plan mémoire 14 est organisé sous forme d'un ensemble de zones ou registres correspondant chacun à un nœud d'un arbre tel que celui illustré par la figure 3. Ces registres sont donc logiquement distribués en étages i = 0, 1 , 2, ...etc.. Chaque registre comporte une ou plusieurs cellules de mémoire de taille 32 bits, adressables par le bus AD. La figure 6 montre une manière conforme à l'invention d'organiser les cellules d'un arbre TRIE à partir d'un nœud-racine d'un étage λ. Si λ > 0, il s'agit d'un sous-arbre déployé à partir d'un registre 100. Si λ = 0, le registre 100 est le registre portier de la mémoire. Dans l'exemple représenté, on a pris K = 3 pour éviter de surcharger le dessin. On voit sur la figure 6 que les cellules de la mémoire TRIE peuvent être soit isolées soit groupées en registres de 2K cellules. Chaque nœud de l'arbre -Λ2 - correspond alors soit à une cellule isolée, soit à un registre de 2K cellules.
Trois types de cellule sont considérés ici. Les cellules marquées S sur la figure 6 sont de type status et contiennent une référence associée à l'un des chemins enregistrés. Les cellules marquées R contiennent chacune un pointeur en mode "registre", qui désigne un registre de 2K cellules de l'étage suivant. Le pointeur en mode registre désigne donc, explicitement ou implicitement, la première cellule de ce registre de l'étage suivant. Les cellules marquées L contiennent chacune un pointeur en mode "linéaire", qui désigne une cellule isolée de l'étage suivant. Les autres cellules, non marquées sur la figure 6, ne contiennent pas d'information utile relative à des chemins enregistrés. On voit que l'utilisation du mode linéaire permet de réduire le nombre de ces cellules vides, et donc d'optimiser l'utilisation de l'espace mémoire disponible.
En mode registre, l'exploitation des pointeurs est identique à celle décrite en introduction. Le pointeur repère le registre dans lequel l'analyse sera à poursuivre, et la valeur de la tranche courante de K bits permet de localiser la cellule de ce registre qui sera lue pour poursuivre l'analyse.
En mode linéaire, il n'y a pas besoin de localiser la cellule dans un registre puisque c'est une cellule isolée qui est désignée en aval. Le pointeur est associé à une valeur de tranche en vue du test suivant : si la tranche courante de la chaîne analysée a cette valeur, l'analyse se poursuit sur la cellule isolée désignée par le pointeur ; sinon, l'analyse se termine en indiquant que la chaîne analysée ne correspond pas à un chemin enregistré dans la mémoire TRIE. En considérant la figure 6, on voit qu'une cellule isolée pointée en mode linéaire peut éventuellement être mémorisée à un emplacement disponible d'un registre adjacent du même étage, ce qui permet de gagner encore un peu d'espace mémoire.
La figure 7 montre le contenu d'une cellule de mémoire dans un exemple particulier de réalisation. Dans cet exemple, les quatre premiers bits de la cellule représentent un drapeau FP dont la valeur indique notamment le type (status, pointeur en mode registre ou pointeur en mode linéaire) des données stockées dans la cellule.
Dans le cas d'un status (FP = S), les 28 bits restants de la cellule constituent la référence Ref utilisée dans l'opération d'acheminement des paquets et/ou des commandes destinées à l'automate 16.
Dans le cas où la cellule est de type pointeur en mode registre, le drapeau FP = R est suivi par un champ contenant l'adresse PtrR dans la mémoire 14 de la cellule de l'étage suivant désignée par le pointeur. Cette cellule est alors la première cellule d'un registre de 2K cellules de l'étage suivant.
Dans le cas où la cellule est de type pointeur en mode linéaire, le drapeau FP = L est suivi par un champ de K bits contenant une valeur de test Val et par un champ contenant l'adresse PtrL dans la mémoire 14 de la cellule isolée de l'étage suivant désignée par le pointeur. Le drapeau FP est examiné par un circuit logique de détection de type de cellule 20 de l'unité d'analyse 13 (figure 5). Si la cellule est de type status (FP = S), la référence Ref qui a été lue est délivrée par l'unité 13 en tant que résultat de l'analyse de la chaîne courante. Cette détection de status libère en outre le registre tampon 15 pour qu'il puisse recevoir une prochaine chaîne de données à analyser.
Lorsque le circuit 20 détecte que les données reçues de la mémoire 14 sont de type pointeur (FP = R ou L), il fournit l'adresse PtrR ou PtrL de la cellule désignée à une logique de calcul d'adresse 21 de l'unité d'analyse 13. Il délivre également un bit L/R qui indique si le pointeur est en mode registre ou en mode linéaire.
En mode registre, la logique de calcul d'adresse 21 procède à la concaténation du pointeur PtrR et de la valeur Vj de la tranche suivante à analyser pour générer l'adresse AD à laquelle sera lue la cellule suivante dans la mémoire 14. En mode linéaire, le circuit de détection 20 extrait en outre la valeur de test Val de la cellule précédemment lue et l'adresse à une logique de comparaison 22. Celle-ci compare la valeur Val à la tranche suivante à analyser Vj, et délivre un bit v indiquant si ces deux valeurs de tranche coïncident (par exemple v = 0 si Vj = VAL et v = 1 sinon. Quand Vj = Val, la logique de calcul d'adresse 21 fournit sur le bus d'adresse AD de la mémoire 14 une adresse correspondant au pointeur PtrL reçu du circuit de détection 20 afin que la cellule isolée désignée par le pointeur soit lue en relation avec la tranche Vj. Si Vj ≠ Val, l'analyse se termine en indiquant que la chaîne analysée ne correspond à aucun chemin enregistré dans la mémoire TRIE. Dans la description qui précède, les cellules inoccupées de l'arbre
TRIE (ou les cellules éliminées en mode linéaire) donnent lieu, lorsqu'elles sont rencontrées au cours de l'analyse, à une indication d'erreur interprétée comme l'absence de motif enregistré correspondant à la chaîne analysée.
En variante, ces cellules sont associées à une référence par défaut que le circuit de détection 20 retourne lorsqu'une telle cellule est rencontrée. La référence par défaut peut, dans certaines applications, être la même pour tout l'arbre TRIE. Dans ce cas, il n'est pas nécessaire de la stocker dans les nœuds de l'arbre, de sorte qu'on peut utiliser la structure de données schématisée par la figure 6. Cependant, il est avantageux que cette référence par défaut puisse varier en fonction de la cellule-mère dont le pointeur désigne une telle référence par défaut. Ceci permet avantageusement d'intégrer à l'analyse les contraintes liées au "longest match".
Dans ce dernier cas, la mémoire 14 peut notamment recevoir une structure de données telle que celle illustrée par la figure 8. L'arbre TRIE représenté sur cette figure 8 contient les mêmes chemins que celui de la figure
6. Chaque cellule inoccupée sur la figure 6 est maintenant occupée par une référence par défaut, ce qui est symbolisé par la lettre D sur la figure 8.
Dans un registre donné, les cellules marquées D contiennent la même référence par défaut, qui dépend de la cellule-mère pointant vers ce registre. En mode linéaire, les cellules ne sont plus isolées, mais regroupées par paires. La première cellule de la paire a le même contenu que la cellule isolée selon la figure 6, tandis que l'autre cellule contient une référence par défaut, retournée quand Vj ≠ Val lors de l'analyse du nœud en amont. Les deux cellules d'une telle paire ont des adresses consécutives. En conséquence, l'analyse peut être effectuée à l'aide du circuit de la figure: il suffit que la logique de calcul d'adresse 21 complète le pointeur PtrL en mode linéaire en y concaténant le bit v délivré par le comparateur 22 pour produire l'adresse de la prochaine cellule à lire en mode linéaire. Une réalisation à base de logiciel de ce dernier mode de réalisation de l'invention est illustrée par la figure 9. L'organigramme illustre le fonctionnement du circuit de la figure 5, et peut servir à en réaliser un émulateur. Les réalisations préférées de l'invention sont à base de matériel, mais on peut aussi envisager, pour des applications pas trop rapides, d'avoir recours à du logiciel.
A l'initialisation 30 de l'algorithme, le rang d'analyse i est mis à 0 et le registre portier R0 est sélectionné comme registre r. A l'étape 31 , la variable v de K bits reçoit la valeur Vs de la tranche courante. Dans chaque itération de rang i, le contenu C de la cellule T[r,v], dont l'adresse est donnée par la concaténation des représentations binaires de r et de v, est lu à l'étape 32. Si cette cellule est de type status (FP(C) = S au test 33), la référence Ref(C) est retournée comme résultat de l'analyse à l'étape 34. Sinon, l'analyse doit se poursuivre et l'ordre d'analyse i est incrémenté d'une unité à l'étape 35. Si la cellule précédemment lue était en mode registre (FP(C) = R au test 36), le contenu du champ PtrR de cette cellule est affecté à la variable r à l'étape 37, et l'algorithme revient à l'étape 31 précitée. Sinon, l'algorithme examine à l'étape 38 si la cellule précédente C était en mode linéaire. Dans l'affirmative (FP(C) = L), le contenu du champ PtrL de cette cellule est affecté à la variable r à l'étape 39, et la prochaine tranche Vj est comparée à la valeur de test Val(C) contenue dans la cellule au test 40. Si Vj = Val(C), le bit v est mis à 0 à l'étape
41. Sinon, il est mis à 1 à l'étape 42. Après l'étape 41 ou 42, l'algorithme revient à l'étape 32 précitée. Son exécution se termine lorsqu'un status est rencontré (34), ou sur une erreur (43) si un type de cellule ne peut pas être décodé (FP(C) ≠ L au test 38).
Le mode de compression et de stockage des données de la mémoire TRIE qui vient d'être décrit permet d'effectuer l'analyse des chaînes de données en mode pipeline afin d'accroître le rythme d'analyse des données, la mémoire 14 étant répartie en N zones de mémoire distinctes de niveaux 0 à N-1 , comme indiqué plus haut.

Claims

R E V E N D I C A T I O N S
1. Dispositif de mémoire TRIE, comprenant des moyens (14) de mémorisation de motifs binaires associés à des références respectives, et des moyens (13) d'analyse de chaînes de données par tranches successives de K bits pour extraire une des références lors d'une concordance entre une chaîne de données analysée et un motif binaire mémorisé associé à ladite référence, K étant un entier plus grand que 1 , dans lequel les moyens de mémorisation (14) comportent plusieurs étages successifs incluant chacun plusieurs cellules de mémoire, dans lequel chaque cellule de mémoire non vide d'un étage i ≥ 0 contient un indicateur de type de cellule et des données comportant: - un pointeur désignant une autre cellule de mémoire lorsque l'indicateur de type de cellule est dans un premier ou un second état, le pointeur étant accompagné par une valeur de test sur K bits lorsque l'indicateur de type de cellule est dans le second état; - une référence associée à un motif binaire mémorisé lorsque l'indicateur de type de cellule est dans un troisième état, et dans lequel les moyens d'analyse (13) comprennent: - des moyens de lecture d'une cellule d'un étage i ≥ 0 en relation avec l'analyse de la (i+1)-ième tranche d'une chaîne de données; - des moyens de sélection d'une cellule de l'étage i+1 , à lire en relation avec l'analyse d'une (i+2)-ième tranche de la chaîne de données, en réponse au premier état de l'indicateur dans ladite cellule de l'étage i, la cellule sélectionnée étant localisée par rapport à la cellule désignée par le pointeur contenu dans ladite cellule de l'étage i en fonction de la valeur de la (i+1 )-ième tranche de la chaîne de données; - des moyens de sélection de la cellule désignée par le pointeur contenu dans ladite cellule de l'étage i, à lire en relation avec l'analyse d'une (i+2)-ième tranche de la chaîne de données, en réponse au second état de l'indicateur dans ladite cellule de l'étage i lorsque la valeur de la (i+1 )-ième tranche de la chaîne de données coïncide avec la valeur de test contenue dans ladite cellule de l'étage i; et - des moyens d'extraction de la référence contenue dans ladite cellule de l'étage i en réponse au troisième état de l'indicateur dans ladite cellule de l'étage i.
2. Dispositif selon la revendication 1 , dans lequel les moyens d'analyse (13) comprennent des moyens pour retourner une référence par défaut en réponse au second état de l'indicateur dans ladite cellule de l'étage i lorsque la valeur de la (i+1 )-ième tranche de la chaîne de données diffère de la valeur de test contenue dans ladite cellule de l'étage i.
3. Dispositif selon la revendication 2, dans lequel la référence par défaut dépend de la cellule de l'étage i lue en relation avec l'analyse de la
(i+1 )-ième tranche de la chaîne de données.
4. Dispositif selon la revendication 3, dans lequel les moyens pour retourner la référence par défaut sont agencés pour lire ladite référence par défaut dans une cellule localisée à une position déterminée par rapport à la cellule désignée par le pointeur contenu dans ladite cellule de l'étage i.
5. Dispositif selon l'une quelconque des revendications précédentes, dans lequel chaque cellule de mémoire désignée par un pointeur contenu dans une cellule de mémoire de l'étage i dont l'indicateur de type de cellule est dans le premier état est la première cellule d'un registre de 2K cellules adressé sur la base de la valeur de la (i+1 )-ième tranche de la chaîne de données.
6. Dispositif selon l'une quelconque des revendications précédentes, dans lequel chaque cellule de mémoire désignée par un pointeur contenu dans une cellule de mémoire de l'étage i dont l'indicateur de type de cellule est dans le second état est une cellule d'un registre réduit de deux cellules adressé sur la base d'un bit obtenu en comparant la valeur de la (i+1 )-ième tranche de la chaîne de données à la valeur de test contenue dans ladite cellule de l'étage i.
7. Dispositif selon l'une quelconque des revendications précédentes, dans lequel les moyens de mémorisation sont répartis en N zones de mémoire distinctes de niveaux 0 à N-1 , N étant inférieur à un nombre maximum d'étages des moyens de mémorisation (14), et les moyens d'analyse sont organisés en pipeline en relation avec les N zones de mémoire.
EP03767854A 2003-10-28 2003-10-28 Dispositif de memoire de type trie avec mecanisme de compression Ceased EP1678632A1 (fr)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/FR2003/003215 WO2005052812A1 (fr) 2003-10-28 2003-10-28 Dispositif de memoire de type trie avec mecanisme de compression

Publications (1)

Publication Number Publication Date
EP1678632A1 true EP1678632A1 (fr) 2006-07-12

Family

ID=34630219

Family Applications (1)

Application Number Title Priority Date Filing Date
EP03767854A Ceased EP1678632A1 (fr) 2003-10-28 2003-10-28 Dispositif de memoire de type trie avec mecanisme de compression

Country Status (4)

Country Link
US (1) US7444562B2 (fr)
EP (1) EP1678632A1 (fr)
AU (1) AU2003292288A1 (fr)
WO (1) WO2005052812A1 (fr)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2359427B1 (fr) 2008-11-18 2016-02-17 Johnson Controls Technology Company Dispositifs de stockage de l'électricité
US8561934B2 (en) 2009-08-28 2013-10-22 Teresa M. Kruckenberg Lightning strike protection
US10193797B2 (en) * 2015-05-08 2019-01-29 Oracle International Corporation Triggered-actions network processor
US10636484B2 (en) * 2018-09-12 2020-04-28 Winbond Electronics Corporation Circuit and method for memory operation

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AU620994B2 (en) * 1989-07-12 1992-02-27 Digital Equipment Corporation Compressed prefix matching database searching
US5276868A (en) 1990-05-23 1994-01-04 Digital Equipment Corp. Method and apparatus for pointer compression in structured databases
US5909440A (en) * 1996-12-16 1999-06-01 Juniper Networks High speed variable length best match look-up in a switching device
FI102426B (fi) * 1997-03-14 1998-11-30 Nokia Telecommunications Oy Menetelmä muistin toteuttamiseksi
FR2783618B1 (fr) 1998-09-23 2002-01-04 France Telecom Procede de mise a jour d'une memoire associative de type trie, et routeur mettant en oeuvre un tel procede
FR2789778B1 (fr) * 1999-02-12 2001-09-14 France Telecom Procede pour associer des references d'acheminement a des paquets de donnees au moyen d'une memoire trie, et routeur de paquets appliquant ce procede
FI991261L (fi) 1999-06-02 2000-12-03 Nokia Networks Oy Trie-rakenteeseen perustuva funktionaalinen muisti
US6691171B1 (en) * 2002-02-01 2004-02-10 Micrel, Inc. Method and system for address lookup in data communication

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO2005052812A1 *

Also Published As

Publication number Publication date
US20070011577A1 (en) 2007-01-11
WO2005052812A1 (fr) 2005-06-09
US7444562B2 (en) 2008-10-28
AU2003292288A1 (en) 2005-06-17

Similar Documents

Publication Publication Date Title
US6856981B2 (en) High speed data stream pattern recognition
EP1436718B1 (fr) Procédé de génération d&#39;un automate DFA qui regroupe des transitions en classes afin de conserver de la mémoire
EP1030493B1 (fr) Procédé pour associer des références d&#39;acheminement à des paquets de données au moyen d&#39;une mémoire TRIE, et dispositif de traitement de paquets appliquant ce procédé
US9111013B2 (en) Hierarchical associative memory-based classification system
EP0639013B1 (fr) Procédé et dispositif d&#39;analyse d&#39;informations contenues dans des structures de données
Lakshminarayanan et al. Algorithms for advanced packet classification with ternary CAMs
US7765183B2 (en) Hierarchical tree of deterministic finite automata
US6658458B1 (en) Cascading associative memory arrangement
EP0552384B1 (fr) Procédé pour réduire le nombre de bits d&#39;un mot binaire représentant une suite d&#39;adresses
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
WO2009068822A2 (fr) Procede et dispositif de tri de paquets
EP1486047B1 (fr) Procede de selection et de tri de paquets de donnees
EP1335565A2 (fr) Procédé et dispositif pour le traitement de paquets de données
EP1678632A1 (fr) Dispositif de memoire de type trie avec mecanisme de compression
WO2005024840A1 (fr) Dispositif de memoire trie avec compression en etendue
EP0857005B1 (fr) Procédé pour associer des données à des cellules ATM
EP0989502B1 (fr) Procede de mise a jour d&#39;une memoire associative de type trie, et routeur mettant en oeuvre un tel procede
EP1702275A1 (fr) Dispositif de memoire trie a mecanisme de pipeline circulaire
FR2697652A1 (fr) Procédé de détermination automatique des probabilités associées à une fonction booléenne.
Aneja et al. Optimizing packet filter firewall using duple decision scheme
Kesselman et al. Space and speed tradeoffs in TCAM hierarchical packet classification
Hummel Automata-based IP packet classification
Baysal Trie-Tree Data Structure for IP Lookup in Virtual Routers
Baysal Analysis of the pantograph arcing and its effects on the railway vehicle
Guinde Hardware support for real-time network security and packet classification using field programmable gate arrays

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20060427

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LI LU MC NL PT RO SE SI SK TR

DAX Request for extension of the european patent (deleted)
17Q First examination report despatched

Effective date: 20070129

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION HAS BEEN REFUSED

18R Application refused

Effective date: 20100221