Brevet FR2907994A1 — publié le 20080502

PROCEDE ET SYSTEME DE CLASSIFICATION DE DONNEES APPARTENANT A UN FLUX. L'invention concerne un procédé et un système de classification, lesdites données appartenant à un flux et comprenant des champs, les données étant classées par rapport à un ensemble de règles, une règle définissant, pour au moins un champ des données, au moins une valeur à satisfaire par ce champ. Elle concerne également un dispositif de classification et un programme d'ordinateur mettant en oeuvre ce procédé. Comme il est bien connu de l'homme du métier, la plupart des réseaux de données, et en particulier internet, sont basés sur la transmission de données par paquet. Un échange de données entre deux machines d'un réseau IP se traduit par la transmission d'un flux de paquets ayant des caractéristiques communes de circuit, d'origine, de destination et de service. Le trafic en un point est observé à travers des techniques d'analyse de flux qui, généralement, regroupent les informations décrivant un flux dans un ticket de flux, puis regroupent les tickets par bloc et expédient chaque bloc vers un serveur de collecte chargé d'analyser les tickets. Un outil d'analyse de flux très connu de l'homme du métier est appelé Netflow (marque déposée de la société Cisco Inc.). II équipe les routeurs de cette société. Par extension, ce terme désigne souvent les outils d'analyse de flux des équipements d'autres sociétés qui reproduisent ses fonctionnalités. Dans les réseaux de données, l'analyse de flux s'appuie sur la classification en temps réel des flux. Elle est notamment utilisée par des techniques de filtrage nécessaires à la sécurité (règles de pare-feu, surveillance de trafic, etc.), par des techniques de routage basées sur des politiques précises et par des techniques de gestion de qualité de service. Le principe général de la classification est d'identifier les paquets de données, en général des paquets IP, dont les champs répondent à une ou plusieurs règles. Cette classification s'effectue en temps réel, c'est-à-dire que la recherche et les traitements associés doivent être effectués dans un temps très court pour assurer le traitement de l'intégralité des éléments reçus et pour permettre un traitement immédiat des actions à engager (filtrage, mise à jour de compteurs, etc.). 2907994 2 Une technique de mise en oeuvre de procédés de classification est connue sous le nom de Lucent bit vector algorithm . Un Lucent bit vector est une séquence de bits de taille finie n permettant de connaître la correspondance, ou non, d'un élément tel qu'un paquet IP à une ou plusieurs 5 occurrences d'un ensemble de n règles. Chaque bit d'un vecteur est donc relatif à une règle. La valeur 0 pour le bit de rang i dans un vecteur indique que l'élément ne correspond pas à la règle R; et, réciproquement, la valeur 1 du bit de rang i indique que l'élément correspond à la règle R. A titre d'exemple, un vecteur de règles dont la valeur est 01001001 10 indique que l'élément auquel il se rapporte correspond aux règles R2, R5 et R8 et ne correspond pas aux règles R1, R3, R4, R6 et R7. On notera que dans l'exemple précédent, comme dans la suite de ce document, on prendra par convention que le bit de poids fort, ou le plus à gauche, est d'indice 1, l'indice étant incrémenté en direction des poids faibles, 15 ou vers la droite. De même, et par convention, les exemples seront donnés en logique positive. L'homme du métier saura sans difficulté généraliser ces explications à d'autres logiques ou d'autres modes d'indexation. De façon générale, la classification consiste donc à rechercher, pour un paquet de données reçu, les règles auxquelles correspond chacun des 20 champs impliqués dans la classification. Pour chaque champ impliqué, un vecteur de règles indique les règles auxquelles correspond le champ. Le recoupement, sous forme d'une opération ET logique, bit à bit, de l'ensemble des vecteurs de règles obtenus permet d'obtenir la liste des règles auxquelles l'élément correspond. 25 Chaque champ est donc analysé bit par bit, ce parcours pouvant être représenté sous la forme d'un arbre binaire. A titre illustratif, supposons un jeu de 8 règles basées sur le code protocole et les adresses IP de destination des paquets selon le tableau suivant : Règles Code protocole Adresse IP destination Val. déc. Val. binaire Val. déc. Val. binaire Masque R 1 6 00000110 32.0.0.0/3 001 * 3 R2 17 00010001 32.0.0.0/3 001 * 3 2907994 3 R3 6 00000110 64.0.0.0/2 01* 2 R4 6 00000110 96.0.0.0/3 011* 3 R5 17 00010001 128.0.0.0/1 1* 1 R6 17 00010001 192.0.0.0/3 110* 3 R7 6 00000110 192.0.0.0/3 110* 3 R8 6 00000110 224.0.0.0/3 111* 3 Dans lequel val. déc. abrège valeur décimale et val. binaire , valeur binaire , et les adresses IP sont notées selon les règles traditionnelles dans lesquelles la valeur /x , ou masque, indique le nombre x 5 de bits de poids fort à prendre en compte pour définir le sous-réseau. Les arbres binaires de parcours correspondants sont illustrés aux figures 1A et 1B, la figure 1A pour le champ protocole et la figure 1B pour le champ d'adresse IP de destination. Pour chaque champ du paquet de données reçu, chacun des arbres 10 est parcouru en analysant bit par bit la valeur du champ concerné. Le vecteur de règles relatif au champ est obtenu au niveau du noeud terminal du parcours. Dans l'exemple précédent, le parcours pour un élément dont l'adresse IP de destination débute par les bits 10 se termine après le parcours de la branche symbolisant le premier bit à 1 (branche de droite sur la figure 1 B). En 15 effet, le noeud consécutif à cette branche n'est pas le point de départ d'une branche relative à un bit à 0. Le vecteur relatif à ce champ a donc pour valeur 00001000. Le vecteur final, relatif à l'ensemble de l'élément, est obtenu par l'opération d'un ET logique, bit à bit, entre l'ensemble des vecteurs relatifs aux 20 différents champs. La liste des règles auxquelles correspond la valeur de l'élément est obtenue à partir de ce vecteur final en considérant les bits dont la valeur est 1. Dans l'exemple précédent, un paquet de données ayant pour code protocole 6 et une adresse IP de destination 32.45.58.32, donc débutant par 25 les bits 001, obtient le vecteur de règles 10110011 pour le code protocole et le vecteur de règles 11000000 pour l'adresse IP de destination. Le résultat du ET 2907994 4 logique (10110011 & 11000000 = 10000000) indique que seule la règle R, est vérifiée pour ce paquet de données. On conçoit que le temps de parcours d'un arbre est proportionnel au nombre de bits à analyser dans le champ. Ainsi, à titre d'exemple, une 5 recherche sur une adresse IP nécessite entre 1 et 32 cycles d'horloge et statistiquement, on montre que des classifications réelles utilisent en moyenne 24 bits, ou cycles d'horloge par adresse à analyser. De la même façon, une recherche sur un champ tel que le champ code protocole qui n'est pas masquable et donc nécessite de parcourir l'intégralité de l'arbre nécessite 16 10 cycles d'horloge puisque ce champ est codé sur 2 octets. L'inconvénient principal de ce procédé est donc la consommation de ressources de calcul et de mémoire nécessaires à une recherche qui intervient sur une grande profondeur des arbres. Cependant, le temps de recherche et le volume de mémoire occupée sont bornés : la borne supérieure du temps de 15 recherche est donnée par le nombre de bits composant chacun des champs analysés et la borne supérieure de l'occupation mémoire est de 232 * taille des vecteurs de règles. Pour réduire le temps de recherche, une variante du Lucent bit vector algorithm est basée sur les octets, c'est-à-dire que les champs analysés ne 20 sont pas parcourus bits à bits mais octets par octets. Cette technique est particulièrement utilisée pour l'exécution de cet algorithme sur un ordinateur classique dont aucun élément de l'architecture matérielle n'est optimisé pour le traitement bit à bit. On conçoit aisément que le parcours d'arbre pour un champ de 32 bits, 25 soit 4 octets, est alors réduit à au plus 4 cycles d'horloge. Dans ce cas, l'arbre est une structure peu adaptée puisqu'à chaque noeud peut correspondre un maximum de 256 branches, il est remplacé par une table de vecteurs de règles par champ. Cette table a deux dimensions et elle comporte 256 abscisses, une pour chaque valeur possible d'un octet, et k 30 ordonnées, k étant la longueur, en nombre d'octets, du champ auquel se rapporte la table de recherche. Ainsi, pour un champ d'adresse de 32 bits, soit 4 octets, la taille mémoire occupée par la table est de 256 * 4 * taille du vecteur de règles, ce dernier étant égal au nombre de règles à traiter. 2907994 5 A titre d'illustration, supposons l'existence de 8 règles portant sur les champs code protocole et "adresse IP de destination" selon le tableau suivant : R1 6 10.11.12.12/30 R2 17 10.11.12.14/31 R3 6 11.11.11.11/32 R4 6 10.10.11.10/31 R5 17 12.12.12. 8/29 R6 17 11.12.13.14/32 R7 6 15.14.13.12/31 R8 6 14.15.9.8/30 5 La table associée au code protocole est alors : 6 17 4 --- 00001001 00001001 00011001 00111001 10001010 10001010 11001100 11001000 Règles Code protocole Adresse IP destination Octet 110110011 01001100 dans laquelle les cellules non représentées contiennent un vecteur de règles nul (00000000). Et pour la table associée à l'adresse IP de destination : Octet 8 9 10 11 12 13 14 15 1 --- 00000000 00000000 11010000 00100100 00001000 00000000 00000001 00000010 --- 2 --- 00000000 00000000 00010000 11100000 00001100 00000000 00000010 00000001 --~ 3 --- 00000000 00000001 00000000 00110000 11001000 00000110 00000000 00000000 --- dans laquelle les adresses masquées des sous-réseaux sont décrites 10 en positionnant à 1 les bits correspondant à l'ensemble des adresses appartenant aux sous-réseaux. Le vecteur de règles relatif à chaque champ est obtenu en réalisant un ET logique, bit à bit, entre les vecteurs de règles relatifs à chaque octet du champ. 15 Ainsi, par exemple, pour un paquet de données ayant comme code de protocole 6 et pour adresse IP de destination 10.11.12.15, - le vecteur de règles du code de protocole est 10110011, et 2907994 6 le vecteur de règles du premier octet de l'adresse est 11010000, du deuxième octet est 11100000, du troisième octet est 11001000 et du quatrième octet est 11001000. Le vecteur de règles relatif au champ est donc 11010000&11100000&11001000&11001000 soit 5 11000000. Le vecteur de règles pour le paquet de données est donc 10110011 &11000000=10000000 (vecteur de règles relatif au champ code protocole & vecteur relatif au champ adresse IP de destination). Ainsi le paquet 10 est classifié comme répondant à la règle R1 uniquement. Le procédé ainsi décrit permet donc une optimisation des temps de calcul mais a l'inconvénient de ne pas permettre différentes valeurs d'un même champ (OU logique) dans une même règle. Ainsi, par exemple, en supposant une règle R1 acceptant les adresses 15 de destination 10.10.10.10 OU 11.11.11.11, la table correspondante s'écrit Octet 9 10 11 12 1 --- -- 10000000 10000000 --- --2 --- --- 10000000 10000000 -- --- 3 --- --- 10000000 10000000 ------ 4 --- --- 10000000 10000000 --- --- Or, avec une telle table, le paquet ayant pour adresse IP de destination 10.11.10.11 est classé comme appartenant à la, règle R1 ce qui est manifestement faux. Ainsi est-il souhaitable de définir un procédé et un système de 20 classification dont la consommation mémoire et le temps nécessaire à la classification de chaque élément sont connus et constants et qui permettent d'autoriser plusieurs valeurs d'un champ dans une même règle. Un objet de l'invention est donc un procédé de classification de données par un système de classification, lesdites données appartenant à un 25 flux et comprenant des champs, lesdites données étant classées par rapport à un ensemble de règles, une règle définissant, pour au moins un champ desdites données, au moins une valeur à satisfaire par ce champ. Le procédé comporte, pour chaque donnée à classer : 2907994 7 • pour chaque champ concerné par au moins une règle, o une première étape de recherche d'au moins un index correspondant à la valeur dudit champ dans une table d'index mémorisant des ensembles d'au moins un index associés à des 5 valeurs de champ, o une seconde étape de recherche d'un ensemble d'au moins une règle correspondant à l'index trouvé dans une table de règles mémorisant des ensembles d'au moins une règle associés à des index, 10 • une étape d'intersection des ensembles d'au moins une règle trouvés pour tous les champs concernés par au moins une règle, de manière à obtenir une règle satisfaite par ladite donnée. Ainsi, le procédé permet avantageusement un temps réduit de traitement des paquets puisque, par rapport, à l'art antérieur utilisant des tables 15 indexées sur les octets des champs, la traversée de la table d'index est équivalente à la traversée de la table de vecteurs de règles de l'art antérieur. A laquelle viennent s'ajouter les étapes de recherche de l'index du groupe prédéterminé de valeurs et de traversée de la table des règles qu'un homme du métier sait optimiser pour les rendre très rapides. 20 Concernant la mémoire occupée, pour les tables d'index, elle est, pour chacun des champs concernés par au moins une règle, de 256 * k * Vi où k est le nombre d'octets composant le champ et Vi est la taille, en nombre de bits, des vecteurs d'index, c'est-à-dire le nombre de valeurs différentes du champ pouvant être mis en oeuvre par les règles de classification. Concernant les 25 vecteurs de règles, le volume mémoire utilisé est, pour chacun des champs impliqués dans la classification de Vi*Vr où Vr est la taille, en nombre de bits, des vecteurs de règles. De plus, l'utilisation des vecteurs d'index permet la mise en oeuvre de la fonction OU logique à l'intérieur d'une même règle. 30 Selon une autre caractéristique, dans le cas où un ensemble de plusieurs index est trouvé à la première étape de recherche, • la seconde étape de recherche est effectuée pour chaque index de l'ensemble, et 2907994 8 • on effectue une étape d'union des ensembles d'au moins une règle trouvés en un ensemble de règles résultant. Selon une autre caractéristique, le procédé comporte un sous procédé de création d'une nouvelle règle comportant les étapes de : 5 • recherche, pour chaque valeur à satisfaire par un des champs dans la nouvelle règle, d'une identité avec des valeurs de champs mémorisées dans la table d'index, puis, si une identité est trouvée, récupération de l'index correspondant, sinon création d'un nouvel index, • pour chaque nouvel index, ajout de celui-ci dans la table d'index en 10 association avec les valeurs de champ correspondantes, • mise à jour des vecteurs de règles correspondant au nouvel index Cela permet avantageusement d'ajouter une nouvelle règle en cours d'utilisation tout en minimisant les modifications des différents vecteurs ainsi que la taille de ceux-ci. 15 Selon une autre caractéristique du procédé, celui-ci comporte un sous procédé de suppression d'une règle comportant les étapes de : • recherche des index correspondant aux valeurs de la règle à supprimer, • mise à jour pour tous les vecteurs de règle correspondant aux index recherchés, 20 • libération de l'index correspondant aux valeurs de champ à satisfaire dans la règle à supprimer lorsque lesdites valeurs ne correspondent à aucune autre règle, par : o mise à jour de tous les vecteurs d'index correspondants aux valeurs de champs, 25 o libération de l'index. Ce qui permet avantageusement de supprimer une règle en cours d'utilisation en ne modifiant qu'a minima les différents vecteurs. Selon une autre caractéristique du procédé, le champ étant découpé en un nombre entier d'unités élémentaires, un vecteur d'index est défini pour 30 chaque valeur d'unités élémentaires et pour chaque unité élémentaire dans le champ de telle sorte que le vecteur d'index d'une valeur du champ est défini par l'intersection des vecteurs d'index d'unités élémentaires correspondants. 2907994 9 Ce qui permet avantageusement de minimiser la consommation mémoire puisque, par exemple, pour un champ de 4 octets, ou 32 bits, les vecteurs d'index passe d'une taille de 232 * 1 * Vi à 4 * 28 * Vi égal à 210 *Vi. Dans un mode de réalisation particulier, les vecteurs d'index d'unités 5 élémentaires sont organisés en un tableau à deux dimensions par champ dont la première dimension correspond à toutes les valeurs possibles d'unités élémentaires et dont la seconde dimension correspond aux différentes unités composant le champ. Ce qui permet avantageusement, une optimisation de la taille mémoire 10 tout en autorisant un accès rapide aux vecteurs d'index. Dans un autre mode particulier de réalisation, les vecteurs de règles associés à un champ sont organisés en un vecteur de vecteurs de règles indicé par un numéro d'index. Ce qui permet avantageusement, une optimisation de la taille mémoire 15 tout en autorisant un accès rapide aux vecteurs de règles. Un autre objet de l'invention est un système de classification de données appartenant à un flux et comprenant des champs par rapport à un ensemble de règles, une règle définissant, pour au moins un champ desdites données, au moins une valeur à satisfaire par ce champ, caractérisé en ce qu'il 20 comporte, pour chaque donnée à classer : • pour chaque champ concerné par au moins une règle, o des premiers moyens de recherche d'au moins un index correspondant à la valeur dudit champ dans une table d'index mémorisant des ensembles d'au moins un index associés à des 25 valeurs de champ, o des seconds moyens de recherche d'un ensemble d'au moins une règle correspondant à l'index trouvé dans une table de règles mémorisant des ensembles d'au moins une règle associés à des index, 30 des moyens de calcul d'intersection des ensembles d'au moins une règle trouvés pour tous les champs concernés par au moins une règle, de manière à obtenir une règle satisfaite par lesdites données. 2907994 10 Un autre objet de l'invention est un équipement de routage caractérisé en ce qu'il comporte un système de classification comme décrit ci-dessus. L'invention propose également un produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un 5 support lisible par ordinateur et/ou exécutable par un processeur, caractérisé en ce qu'il comprend des instructions de code de programme pour la mise en oeuvre du procédé de classification précédent. L'invention sera mieux comprise à la lecture de la description qui suit, donnée uniquement à titre d'exemple, et faites en référence aux dessins en 10 annexe dans lesquels : • les figures 1A et 1B sont des schémas des arbres de parcours associés à un exemple de classification pour l'algorithme Lucent bit vector algorithm de l'art antérieur ; • la figure 2 est un ordinogramme de création des vecteurs de bits selon 15 un mode de réalisation de l'invention ; • la figure 3 est un ordinogramme de classification d'un élément selon un mode de réalisation de l'invention ; • les figures 4 et 5 sont des ordinogrammes d'un exemple de classification d'un élément en fonction de son code protocole et de son adresse IP de 20 destination ; • la figure 6 est un ordinogramme d'un mode de réalisation du procédé de classification d'un équipement selon l'invention ; • la figure 7 est un ordinogramme d'un mode de réalisation d'un procédé de création d'une règle ; 25 • la figure 8 est un ordinogramme d'un mode de réalisation d'un procédé de suppression de règle ; • la figure 9 est une vue schématique d'un mode de réalisation d'un système de classification ; et • la figure 10 est une vue schématique d'un ordinateur. 30 En référence à la figure 2, on considère un ensemble 1 de n règles R;, i variant de 1 à n. Chaque règle R; est ainsi classée par un numéro d'ordre i dans cet ensemble de règles. 2907994 11 Chaque règle R; comporte un ou plusieurs groupes déterminés de valeurs notés G;1, i indiquant le numéro d'ordre de la règle d'appartenance et j un indice à l'intérieur de l'ensemble des groupes appartenant à cette règle R. L'ensemble des règles peut se noter{R, _ {Gu, j =1..n; =1..n}. 5 Un groupe déterminé de valeurs contient une seule valeur, par exemple une valeur de code de protocole, ou un intervalle de valeurs, par exemple une adresse IP de type 10.10.10.0/24 définissant l'intervalle des adresses IP allant de 10.10.10.0 à 10.10.10.255. On conçoit qu'un même groupe déterminé de valeurs peut être défini 10 dans plusieurs règles. Par exemple, un code de protocole 6 appartient aux règles RI, R3, R4, R7 et R8 dans l'exemple mentionné ci-dessus. Dans une première étape 3, l'ensemble de tous les groupes déterminés de valeurs G;1, pour chaque champ utilisé dans les règles, est indexé de telle sorte que chaque groupe déterminé de valeurs soit référencé 15 par un numéro d'index k, k variant de 1 à m où m est le nombre total de groupes déterminés de valeurs G;1, opération notée VG,1,G,/ û~ Gk ,k =1..m . Au préalable, on notera qu'on appelle classiquement drapeau tout symbole pouvant prendre deux positions lever/abaisser. En règle générale, un drapeau est codé sous forme d'un bit bien que, dans des contextes particuliers 20 comme la très haute sécurité, un drapeau puisse être codé sur plusieurs bits afin d'introduire des possibilités de correction d'erreur. Afin de ne pas complexifier inutilement la description ci-après, les drapeaux sont supposés codés sur un bit de manière usuelle. Dans ce cas, en logique positive, logique qui sera utilisée ci-après, le drapeau est considéré comme levé quand le bit est 25 à 1 et est considéré comme abaissé quand le bit est à 0. L'homme du métier sait faire sans difficulté la transposition à l'utilisation d'une logique négative dans laquelle le drapeau est considéré comme levé quand le bit est à 0 et est considéré comme abaissé quand le bit est à 1. Un premier ensemble de vecteurs de drapeaux, dits vecteurs d'index 30 Vx,, est créé à l'étape 5 pour chaque champ utilisé dans les règles. Ce premier ensemble comporte autant de vecteurs d'index que le champ peut prendre de 2907994 12 valeurs. Ainsi, si le champ est codé sur un octet, cet ensemble comporte 256 vecteurs d'index Vx,. Chaque vecteur d'index Vx, comporte autant de drapeaux qu'il y a de numéro d'index des groupes déterminés de valeurs Gk, soit m drapeaux. 5 Pour tout groupe déterminé de valeurs d'index k contenant la valeur du champ du vecteur d'index Vx, considéré, le drapeau dont l'indice k correspond au numéro d'index de ce groupe est levé. Ainsi Vx, _ (Ek =1 si l E Gk ,0 sin on),..., } pour tout I appartenant à l'ensemble des valeurs possibles du champ. 10 Pour chaque groupe déterminé de valeurs Gk ainsi indexé, un vecteur de règles Vrk est défini à l'étape 7 sous forme d'un vecteur de drapeaux. Ce vecteur contient autant de drapeaux qu'il y a de règles, soit n, et est tel que, pour toute règle R; contenant le groupe déterminé de valeurs Gk le drapeau d'indice i, c'est-à-dire dont l'indice correspond au numéro d'ordre de la règle, 15 est levé. Ainsi Vrk ={D,,...,(D,=lsiGk E R,,Osinon),...,D,,}. Ces différents ensembles ayant été créés pour l'ensemble des champs concernés par au moins une règle, la classification d'un paquet s'effectue de la façon suivante en référence à la figure 3. 20 La valeur de chaque champ concerné par au moins une règle est déterminée à l'étape 10 pour le paquet de données, soit Io cette valeur. Puis, pour chacun des champs concernés par au moins une règle, le vecteur d'index Vx,o correspondant à la valeur lo du champ est recherché à l'étape 12. 25 Le vecteur d'index définit ainsi un certain nombre d'index Xa, ce nombre pouvant être éventuellement nul, correspondant à cette valeur Io. Tous les vecteurs de règles Vrxa correspondant aux numéros d'index des drapeaux levés du vecteur d'index sont recherchés à l'étape 14 puis combinés à l'étape 16 dans une opération OU logique, drapeau à drapeau. 30 Cela définit un vecteur des règles mises en oeuvre par cette valeur du champ. 2907994 13 Les étapes précédentes 10, 12, 14, 16 sont répétées pour chaque champ concerné par au moins une règle. Quand les vecteurs de règles de tous les champs concernés par au moins une règle ont été obtenus à l'étape 18, le vecteur de règles pour le 5 paquet de données est alors calculé à l'étape 20. Pour obtenir le vecteur des règles mises en oeuvre par l'ensemble des valeurs des différents champs, une opération ET logique, drapeau à drapeau, est exécutée sur l'ensemble des vecteurs combinés de règles de chaque champ. 10 Ainsi est défini un procédé de classification des paquets d'un flux de paquets par rapport à un ensemble d'au moins une règle, chaque règle étant classée dans cet ensemble par un numéro d'ordre et définissant, pour au moins un champ des paquets, au moins une relation d'appartenance entre la valeur du champ et un groupe déterminé de valeurs. 15 Le procédé comporte les étapes préalables de : • indexation de tous les groupes déterminés de valeurs de toutes les règles attachant à chaque groupe déterminé de valeurs un numéro d'index, • création d'un premier vecteur de drapeaux, dit vecteur d'index, par 20 valeur possible de chaque champ, vecteur comportant autant de drapeaux qu'il y a de numéros d'index et tel que, pour tout groupe déterminé de valeurs contenant ladite valeur du champ, le drapeau dont l'indice correspond au numéro d'index dudit groupe déterminé de valeurs est levé. 25 • Création d'un second vecteur de drapeaux, dit vecteur de règles, par groupe déterminé de valeurs et associé au numéro d'index de celui-ci, vecteur comportant autant de drapeaux qu'il y a de règles et tel que, pour toute règle contenant le groupe déterminé de valeurs, le drapeau dont l'indice correspond au numéro d'ordre de la dite règle est levé. 30 Et le procédé comporte les étapes, pour un paquet à classer, de : 2907994 14 • détermination de la valeur de chaque champ concerné par au moins une règle, • pour chaque champ concerné par au moins une règle, o recherche du vecteur d'index correspondant à la valeur dudit 5 champ, o recherche de tous les vecteurs de règles correspondant aux numéros d'index des drapeaux levés du vecteur d'index, o opération logique OU, drapeau à drapeau, de tous les vecteurs de règles trouvés, puis 10 opération logique ET, drapeau à drapeau, des vecteurs de règles combinés de tous les champs associés aux règles, telle que chaque drapeau levé du vecteur résultant correspond au numéro d'ordre d'une règle satisfaite par ledit paquet. De façon générale, on a ainsi défini un procédé de classification de 15 données comprenant des champs par rapport à un ensemble de règles, une règle définissant, pour au moins un champ desdites données, au moins une valeur à satisfaire par ce champ, ledit procédé comportant pour des données à classer : • pour chaque champ concerné par au moins une règle, 20 o une première étape de recherche d'au moins un index correspondant à la valeur dudit champ dans une table d'index mémorisant des ensembles d'au moins un index associés à des valeurs de champ, o une seconde étape de recherche d'un ensemble d'au moins une 25 règle correspondant à l'index trouvé dans une table de règles mémorisant des ensembles d'au moins une règle associés à des index, • une étape d'intersection des ensembles d'au moins une règle trouvés pour tous les champs concernés par au moins une règle, de manière à 30 obtenir une règle satisfaite par lesdites données. 2907994 15 Dans un mode de réalisation, chaque champ est découpé en nombre entier d'unités élémentaires,typiquement des octets. Ainsi, une adresse IP codée sur 32 bits est découpée en 4 octets. Un vecteur d'index est alors défini pour chaque valeur d'unité élémentaire et pour chaque unité élémentaire dans 5 le champ. Le vecteur d'index correspondant à la valeur du champ est ainsi défini par le ET logique, drapeau à drapeau, des vecteurs d'index des unités élémentaires correspondantes. Dans un mode de réalisation, les vecteurs d'index sont organisés sous la forme d'une table de vecteurs d'index à deux dimensions dont l'abscisse 10 correspond à toutes les valeurs possibles d'unités élémentaires, soit 256 positions pour un octet, et l'ordonnée correspond aux différentes unités élémentaires composant le champ, soit pour un champ d'adresse IP de 32 bits 4 positions correspondant aux 4 octets de l'adresse. A titre d'exemple illustratif, nous allons supposer que les paquets 15 doivent être classifiés en fonction des règles suivantes : Règles Code protocole Adresse IP destination R1 6 10.11.12.12/30 OU 12.12.12.8/29 R2 17 10.11.12.14/31 R3 6 11.11.11.11/32 R4 6 10.10.11.10/31 R5 17 12.12.12.8/29 R6 17 11.12.13.14/32 O U 11.11.11.11 /32 R7 6 15.14.13.12/31 R8 6 14.15.9.8/30 Les arouoes déterminés de valeurs sont indexés selon suivante, en supposant que les numéros d'index sont délivrés dans l'ordre d'apparition des valeurs. Pour le champ code protocole Valeur Index 6 1 17 2 a table 2907994 16 Pour le champ adresse IP de destination : Valeur Index 10.11.12.12/30 1 12.12.12.8/29 2 10.11.12.14/31 3 11.11.11.11/32 4 10.10.11.10/31 5 11.12.13.14/32 6 15.14.13.12/31 7 14.15.9.8/30 8 Les tables d'index sont construites en tenant compte des valeurs des groupes déterminés de valeurs. Table d'index relative au code protocole 0 6 17 ---Octet1 11000000 00000000 00000000 --- Octet2 00000000 --~ 10000000 01000000 Le symbole --- symbolise les vecteurs non représentés dont la 5 valeur est un vecteur nul 00000000. Chaque vecteur d'index comporte 8 bits car il y a 8 groupes déterminés de valeurs et donc 8 valeurs d'index. Le code protocole étant codé sur 2 octets, les valeurs 6 et 17 correspondent à des valeurs nulles de l'octet 1. Le vecteur d'index 10 correspondant à la valeur 0 de l'octet 1 est donc égal à 11000000 de façon à ce qu'un ET logique avec le vecteur correspondant de l'octet 2 donne la valeur correcte d'index. Table d'index relative à l'adresse IP de destination -- 8 9 10 11 12 13 14 15 OCtetl 00000000 00000000 10101000 00010100 01000000 00000000 00000001 00000010 Octet2 00000000 00000000 00001000 10110000 01000100 00000000 00000010 00000001 ,,,,,, Octet3 .,, 00000000 00000001 00000000 00011000 11100000 00000110 00000000 00000000 ,,,,,, Octet4 01000001 01000001 01001001 00011001 11000010 11000010 11100100 11100000 ,,,,,, 2907994 17 Les tables de règles suivantes se déduisent en combinant la table des règles ainsi que les tables d'index ci-dessus. Table de règles pour le code protocole Index 1 2 3 4 5 6 7 8 Vect. de 10110011 01001100 00000000 00000000 00000000 00000000 00000000 00000000 règles Table de règles pour l'adresse IP destination Index 1 2 3 4 5 6 7 8 Vect. de 10000000 10001000 01000000 00100100 00010000 00000100 00000010 00000001 règles Soit un paquet ayant un code protocole de 6 et une adresse IP de 5 destination égale à 10.11.12.14 . Pour le code protocole, tel que représenté sur la figure 4, le vecteur d'index est donc égal à 11000000&1000000, soit 10000000. Un seul index, celui d'indice 1, est donc concerné. Le vecteur de règles pour le champ code protocole est donc 10110011. 10 Pour l'adresse IP de destination, tel que représenté sur la figure 5, le vecteur d'index est égal à 10101000&10110000&11100000&11100100 soit 10100000. Le vecteur de règles pour l'adresse IP de destination est alors le OU logique des vecteurs de règles des index 1 et 3 soit 10000000101000000=11000000. 15 En combinant les vecteurs de règles du code protocole et de l'adresse de destination, le vecteur de règles pour l'élément est 10110011&11000000 soit 10000000. Ainsi cet élément ne satisfait que la règle R1. En référence à la figure 6, un mode particulier de réalisation de l'algorithme de classification d'un paquet est représenté. 20 A l'étape 30, le vecteur de règles Vre du paquet est initialisé en positionnant tous ses bits à 1. A l'étape 32, on initialise le premier champ c à traiter et on positionne à l'étape 34 tous les bits du vecteur d'index Vxc relatif à ce champ c à la valeur 1. 2907994 18 On considère à l'étape 36 le premier octet du champ, et à l'étape 38 on effectue un ET logique entre le vecteur d'index Vxc du champ et le vecteur d'index Tind[i][Val(i)] donné par la table d'index pour la valeur du champ correspondante. 5 Si à l'étape 40, tous les octets du champ n'ont pas été traités, on passe à l'étape 41 à l'octet suivant et on recommence l'étape 38. Si à l'étape 40, tous les octets du champ ont été traités, le vecteur de règles Vrc relatif au champ est initialisé à o à l'étape 42. On considère à l'étape 44 le premier bit à 1 du vecteur d'index obtenu et on effectue à l'étape 46 un 10 OU logique entre Vrc et le vecteur de règles Treg[i] de la table de règles ayant l'indice correspondant à ce bit. On vérifie à l'étape 48 que tous les bits à 1 du vecteur d'index Vrc ont été considérés sinon on passe à l'étape 50 au bit à 1 suivant pour poursuivre l'opération 46. 15 Quand le vecteur de règles Vrc final du champ est obtenu, on effectue à l'étape 52 un ET logique avec le vecteur final de l'élément et on poursuit avec le champ suivant à l'étape 54. Quand tous les champs ont été considérés, les numéros de règles applicables à l'élément sont extraits à l'étape 56 du vecteur de règles Vre de 20 l'élément. En phase de production, il est souvent nécessaire d'ajouter, modifier ou supprimer des règles. Dans un mode particulier de réalisation, décrit par référence à la figure 7, l'ajout d'une règle s'effectue en recherchant à l'étape 70, pour chaque 25 groupe prédéterminé de valeurs de la nouvelle règle, une identité avec un groupe prédéterminé de valeurs déjà indexé. Si une identité est trouvée, à l'étape 72, le numéro d'index correspondant est récupéré à l'étape 74. Dans le cas contraire, un nouveau numéro d'index est créé à l'étape 76 puis, pour chaque vecteur d'index, un drapeau est ajouté à l'étape 78 en 30 cas de création d'un nouveau numéro d'index. 2907994 19 Les drapeaux dont l'indice correspond au numéro d'index pour tous les vecteurs d'index correspondant aux valeurs du groupe prédéterminé de valeurs sont levés à l'étape 80. Pour chaque vecteur de règle, un drapeau est ajouté. 5 Si le numéro d'ordre de la nouvelle règle est supérieure au nombre de drapeaux des vecteurs de règle, étape 82, un drapeau est ajouté à l'étape 84. Les drapeaux dont l'indice correspond au numéro d'ordre de la nouvelle règle sont levés à l'étape 86 pour les vecteurs de règles correspondant aux numéros d'index des groupes prédéterminés de valeurs de 10 cette nouvelle règle. La suppression d'une règle s'effectue, en référence à la figure 8, en recherchant à l'étape 90 les numéros d'index correspondant aux groupes prédéterminés de valeurs de la règle à supprimer. Puis le drapeau dont l'indice correspond au numéro d'ordre de la règle pour tous les vecteurs de règle 15 correspondant aux numéros d'index recherchés est abaissé à l'étape 92. Si l'un des groupes prédéterminés de valeurs de la règle à supprimer ne correspond à aucune autre règle, étape 94, le numéro d'index correspondant au groupe prédéterminé de valeurs est supprimé, par abaissement à l'étape 96 du drapeau dont l'indice correspondant au numéro 20 d'index à libérer pour tous les vecteurs d'index correspondants aux valeurs dudit groupe prédéterminé de valeurs, ou par libération en 98 du numéro d'index. Dans un mode de réalisation, la modification d'une règle s'effectue par suppression de la règle puis ajout d'une règle reprenant les modifications 25 souhaitées. Le procédé décrit est mis en oeuvre dans un système de classification des paquets d'un flux de paquets par rapport à un ensemble d'au moins une règle. Ce système comporte, figure 9, des moyens d'indexation 100 de tous 30 les groupes déterminés de valeurs de toutes les règles attachant à chaque groupe déterminé de valeurs un numéro d'index. 2907994 20 Il comporte également des premiers moyens 102 de création et de stockage d'un vecteur d'index, par exemple un second vecteur de drapeaux, par valeur possible de chaque champ, vecteur comportant autant de drapeaux qu'il y a de numéros d'index et tel que, pour tout groupe déterminé de valeurs 5 contenant ladite valeur du champ, le drapeau dont l'indice correspond au numéro d'index dudit groupe déterminé de valeurs est levé. Il comporte de plus des seconds moyens 104 de création et de stockage d'un vecteur de règles, par exemple un premier vecteur de drapeaux, par groupe déterminé de valeurs et associé au numéro d'index de celui-ci, 10 vecteur comportant autant de drapeaux qu'il y a de règles et tel que, pour toute règle contenant le groupe déterminé de valeurs, le drapeau dont l'indice correspond au numéro d'ordre de la dite règle est levé. Le système de classification comporte en outre, pour chaque paquet à classer un classificateur 106 comportant des moyens 108 de détermination de 15 la valeur de chaque champ concerné par au moins une règle. Pour chaque champ concerné par au moins une règle, il comporte des premiers moyens 110 de recherche du vecteur d'index correspondant à la valeur du champ dans les premiers moyens de stockage, et des seconds moyens 112 de recherche de tous les vecteurs de règles correspondant aux 20 numéros d'index des drapeaux levés du vecteur d'index dans les seconds moyens de stockage. Connectés à ces seconds moyens 112 de recherche, il comporte des premiers moyens 114 de calcul de l'opération logique OU, drapeau à drapeau, de tous les vecteurs de règles trouvés, et des seconds moyens 116 de calcul 25 de l'opération logique ET, drapeau à drapeau, des vecteurs de règles combinés de tous les champs associés aux règles telle que chaque drapeau levé du vecteur résultant correspond au numéro d'ordre d'une règle satisfaite par le paquet. Il est particulièrement avantageux d'inclure un tel système de 30 classification dans un équipement de routage afin de classifier des paquets de données IP. 2907994 21 Le procédé s'applique à la classification de données comportant des champs. Le procédé de classification peut être mis en oeuvre par un produit programme d'ordinateur téléchargeable depuis un réseau de communication 5 et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur tel que représenté sur la figure 10 et comportant une unité arithmétique et logique CPU, différents mémoires RAM et registres MO, M1, M2 ainsi que des entrées/sorties I/O. 10 REVENDICATIONS 1. Procédé de classification de données par un système de classification, lesdites données appartenant à un flux et comprenant des champs, lesdites données étant classées par rapport à un ensemble de règles, une règle définissant, pour au moins un champ desdites données, au moins une valeur à satisfaire par ce champ, caractérisé en ce qu'il comporte, pour chaque donnée à classer : • pour chaque champ concerné par au moins une règle, o une première étape de recherche (12) d'au moins un index correspondant à la valeur dudit champ dans une table d'index mémorisant des ensembles d'au moins un index associés à des valeurs de champ, o une seconde étape de recherche (14) d'un ensemble d'au moins une règle correspondant à l'index trouvé dans une table de règles mémorisant des ensembles d'au moins une règle associés à des index, • une étape d'intersection (20) des ensembles d'au moins une règle trouvés pour tous les champs concernés par au moins une règle, de manière à obtenir une règle satisfaite par ladite donnée. 20 2. Procédé selon la revendication 1, dans le cas où un ensemble de plusieurs index est trouvé à la première étape de recherche, • la seconde étape (14) de recherche est effectuée pour chaque index de l'ensemble, et • on effectue une étape (16) d'union des ensembles d'au moins une règle 25 trouvés en un ensemble de règles résultant. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il comporte un sous procédé de création d'une nouvelle règle comportant les étapes de : 15 2907994 23 • recherche (70), pour chaque valeur à satisfaire par un des champs dans la nouvelle règle, d'une identité avec des valeurs de champs mémorisées dans la table d'index, puis, si une identité est trouvée (72), récupération (74) de l'index correspondant, sinon création (76) d'un 5 nouvel index, • pour chaque nouvel index, ajout (78) de celui-ci dans la table d'index en association avec les valeurs de champ correspondantes, • mise à jour des vecteurs de règles correspondant au nouvel index 10 4. Procédé selon l'une quelconque des revendications 1, 2 ou 3, caractérisé en ce qu'il comporte un sous procédé de suppression d'une règle comportant les étapes de : • recherche (90) des index correspondant aux valeurs de la règle à supprimer, • mise à jour (92) pour tous les vecteurs de règle correspondant aux index recherchés, • libération de l'index correspondant aux valeurs de champ à satisfaire dans la règle à supprimer lorsque lesdites valeurs ne correspondent à aucune autre règle (94), par : o mise à jour de (96) tous les vecteurs d'index correspondants aux valeurs de champs, o libération (98) de l'index. 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que, chaque champ étant découpé en un nombre entier d'unités élémentaires, un vecteur d'index est défini pour chaque valeur d'unités élémentaires et pour chaque unité élémentaire dans le champ de telle sorte que le vecteur d'index d'une valeur du champ est défini par l'intersection des vecteurs d'index d'unités élémentaires correspondants. 2907994 24 6. Procédé selon la revendication 5, caractérisé en ce que les vecteurs d'index d'unités élémentaires sont organisés en un tableau à deux dimensions par champ dont la première dimension correspond à toutes les valeurs possibles d'unités élémentaires et dont la seconde dimension correspond aux 5 différentes unités composant le champ. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les vecteurs de règles associés à un champ sont organisés en un vecteur de vecteurs de règles indicé par le numéro d'index. 10 8. Système de classification de données appartenant à un flux et comprenant des champs, lesdites données étant classées par rapport à un ensemble de règles, une règle définissant, pour au moins un champ desdites données, au moins une valeur à satisfaire par ce champ, caractérisé en ce qu'il comporte, 15 pour chaque donnée à classer : • pour chaque champ concerné par au moins une règle, o des premiers moyens (110) de recherche d'au moins un index correspondant à la valeur dudit champ dans une table d'index mémorisant des ensembles d'au moins un index associés à des 20 valeurs de champ, o des seconds moyens (112) de recherche d'un ensemble d'au moins une règle correspondant à l'index trouvé dans une table de règles mémorisant des ensembles d'au moins une règle associés à des index, 25 • des moyens (116) de calcul d'intersection des ensembles d'au moins une règle trouvés pour tous les champs concernés par au moins une règle, de manière à obtenir une règle satisfaite par ladite donnée. 9. Equipement de routage caractérisé en ce qu'il comporte un système de 30 classification selon la revendication 8. 2907994 25 10. Produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, caractérisé en ce qu'il comprend des instructions de code de programme pour la mise en oeuvre du procédé de 5 classification selon l'une au moins des revendications 1 à 7.