Brevet FR2838590A1 — publié le 20031017

Procédé de routage pour un réseau de télécommunication et routeur pour la mise en _uvre dudit procédé s Domaine technique de l'invention La présente invention concerne le domaine des télécommunications et plus particulièrement un procédé de routage pour un routeur dans un réseau de o télécommunication. Etat de la technique Les réseaux de télécommunications connaissent depuis ces dernières années un développement considérable notamment avec l'essor du réseau Internet et l'accroissement des réseaux privés d'entreprises (Intranet). Tout utilisateur devient ainsi capable de communiquer avec tout autre opérateur du réseau correspondant ou serveur -, dans le but d'échanger des informations ou d'accéder à des ressources disponibles sur le réseau. Du point de vue de l'architecture du réseau Internet, I'élément de base est constitué par le routeur qui assure le transit des paquets en vue de leur acheminement jusqu'à leur destinataire. La figure 1 illustre un schéma type de topographie de réseau dans lequel on voit trois réseaux ou sous-réseaux d'entreprises (Intranet) respectivement 1, 2 et 3 - qui sont connectés par des liens à un ensemble de routeurs 10, 20, 30, 40 et 50. Plus particulièrement le routeur 10 dispose d'un premier port connecté à un lien 11 permettant la communication avec le sous-réseau 1, un second port connecté à un o lien 12 assurant l'accès au routeur 20 et par exemple un troisième port permettant la communication avec le routeur 30 via un lien 13. ST - 01-GR2-242 - 2 - 2838590 Dans la version Ipv4 du réseau Internet, I'adresse de destination de chaque paquet est codé sur quatre octets ou 32 bits et cette adresse est utilisée au sein de chaque routeur afin de permettre le transit du paquet IP entrant par un des ports dudit routeur - par exemple le port 11 du routeur 10 pour un paquet arrivant du s sous-réseau 1 - vers un des autres ports dudit routeur en vue de son acheminement vers son destinataire, par exemple un correspondant particulier du sousréseau 2. D'une manière concrète, cet acheminement du paquet vers le bon port du routeur est assuré au moyen d'une table de routage qui est disposée localement dans ce dernier et qui permet, à chaque fois qu'un paquet donné se présente avec une o adresse IP caractérisant le destinataire, de décoder cette adresse pour déterminer le port particulier parmi l'ensemble des ports disponibles du routeur auquel il convient de rediriger le paquet. Lorsque la table ne contient aucune information spécifique concernant le routage d'un paquet donné, ce même paquet est alors automatiquement dirigé vers un port par défaut, lequel est en général organisé de manière à permettre l'acheminement dudit paquet vers un routeur qui disposera d'une information plus complète permettant de router convenablement le paquet concerné. Dans l'état actuel du réseau, il est courant que les tables de routage des routeurs contiennent plusieurs dizaines de milliers d'entrées que les administrateurs réseau s'efforcent de maintenir et mettre à jour afin d'assurer un fonctionnement optimal du réseau. Si l'on considère un routeur disposant d'environ 60 000 entrées, avec une dizaine d'octets associés à chacune de ces entrées (4 octets pour l'adresse, 4 octets pour le masque de réseau et 1 octet minimum pour le port) cela conduit à une table de routage d'environ 600 Koctets. Le problème est que si l'on stocke cette table sans précaution particulière, on est contraint de devoir la parcourir dans son intégralité et ce pour chaque paquet entrant. Même sur les machines les plus sophistiquées autorisant une lecture de 64 bits en une unique opération - il faut donc au minimum deux opérations de lecture pour lire une entrée. so Avec 60 000 entrées, il faut donc envisager en moyenne plusieurs milliers d'opérations de lecture pour un paquet donné, pouvant aller même jusqu'à 120 000 opérations dans le pire des cas, ce qui accro'^t considérablement le temps de transit du paquet dans le routeur. ST- Ol-GR2-242 - 3 - 2838590 Une technique connue, décrite dans le document " IP address lookup made fast and simple " de Pierluigi Crescenzi, Leandro Dardini et Roberto Grossi, Università di Pisa, Dipartimento di informatica, Technical Report TR-99-01, permet de réduire la lecture de la table à trois opérations, mais au prix cependant d'un s accroissement considérable de la dimension de cette table, laquelle peut alors atteindre une dimension de plusieurs mégeoctets. Une telle table - réalisée avec de la mémoire vive afin de réduire au maximum les temps d'accès aux informations qui y sont stockées - est coûteuse à mettre en _uvre. En outre, une telle quantité de mémoi re vive est ho rs de proportion avec les possibilités offertes par la tech no log ie de fabrication des produits semi-conducteurs et cela interdit définitivement son intégration sur un circuit semi-conducteur. Il faut observer, en outre, que dans le système connu, la table exige une refonte complète dans le cas d'une mise à jour ce qui n'en facilite bien évidemment pas la maintenance. Une autre technique connue est décrite dans le brevet américain US 6,266, 706. Elle permet de réduire la dimension de la table à quelques centaines de kilooctets et limiter le nombre d'opérations de lecture à six. En revanche, la maintenance de cette table est rendue particulièrement délicate du fait qu'il est nécessaire de reconstruire complètement cette table à chaque mise à jour. On est donc confronté à un dilemme: soit on accepte une table de routage de grande dimension - impossible à intégrer en l'état actuel dans un circuit semi- conducteur- soit on al longe considérablement le temps req u is pou r le routage des paquets. Le problème technique à résoudre par l'objet de la présente demande consiste en l'organisation optimisée d'une table de routage de dimension particul ièreme nt réd uite - permettant d 'envisager son intég ration da ns u n ci rcu it semi-conducteur - tout en autorisant néanmoins un procédé de routage efficace et so rapide à mettre en _uvre. Il serait en outre autant que possible souhaitable que l'organisation de la table de routage facilite sa maintenance et permette une mise à jour aisée de ses entrées. ST - O 1-GR2-242 Exposé de l'invention La présente invention a pour but un procédé de routage dans un réseau de télécommunication commandé par une table de routage de dimension réduite permettant une intégration aisée dans un produit semi-conducteur. Un autre but de la présente invention consiste en la réalisation d'une table de routage et d'un routeur d'un réseau de télécommunication qui permette un routage efficace et rapide des paquets au sein de ce même routeur. C'est un autre but de la présente invention que de fournir une organisation de table de routage qui soit facile à maintenir. L'invention réalise ces buts au moyen d'un procédé de détermination du port de sortie d'un routeur destiné à recevoir des paquets comportant une adresse de destination définie par au moins un premier, un second, un troisième et un quatrième élément d'adressage. Le procédé comporte les étape de: - consultation directe d'une table de premier niveau (Level 1 table) à partir dudit premier élément d'adressage dudit paquet; consultation directe d'un table de second niveau table (LEVEL2 table) à partir desdits premier et second éléments d'adressage dudit paquet; consultation et recherche dans une table de troisième niveau (Level 3 table) permettant un troisième niveau de recherche à partir du troisième élément d'adressage dudit paquet; - consultation et recherche dans une table de quatrième niveau (Level 4 table) à partir du quatrième élément d'adressage dudit paquet. so Ainsi l' invention permet de combiner ava ntageusement u ne recherche d i recte dans les deux premières tables, et une recherche par exemple linéaire ou dichotomique vient compléter le traitement. Ces recherches ne sont effectuées dans les tables de niveau trois et quatre que lorsque cela s'avère nécessaire. Il en résulte une réduction considérable de la dimension de la table de routage - composée des ST - O1-GR2-242 - 5 - 2838590 six tables élémentaires définies ci-dessus - tout en maintenant un haut niveau de performance au niveau du procédé de routage. Dans un mode de réalisation préféré, la table de premier niveau comporte un s premier champ (VALID) déterminant si la recherche doit aboutir au premier niveau ou si celle-ci doit être poursuivie à un second niveau. Un second champs (INDEX NH) définit le port de sortie du routeur lorsque la valeur dudit premier champ définit une recherche devant aboutir et, au contraire, un troisième champ (INDEX LEVEL 2) renvoie un pointeur d'accès à la table de second niveau lorsque la valeur dudit o premier champ définit une recherche devant se poursuivre. Alternativement, les second et troisième champs sont regroupés en un unique champ interprété différemment selon la valeur dudit premier champ (VALID). s De préférence, la consultation de la table de second niveau est effectuée au moyen d'une entrée calculée à partir de la valeur du troisième champ de ladite seconde table, corrigée par une valeur lue à partir d'un accès à une table de décalage comportant un unique champ (OFFSET) renvoyant un pointeur de correction à additionner au pointeur renvoyé par le champ INDEX2 de ladite table de premier niveau. La table de second niveau comporte un premier, un second, un troisième, un quatrième et un cinquième champ. Le premier champ (VALID) détermine si la recherche doit aboutir au second niveau ou si celle-ci doit se poursuivre à un troisième niveau. Le second champ (COMBINAISON) est comparé au second élément d'adressage du paquet entrant de manière à permettre la sélection du troisième ou quatrième champ. Le troisième champ (INDEX) et le quatrième champs (INDEX2) définissent le port de sortie lorsque la valeur du premier champ de la table de second niveau définit une recherche devant aboutir ou un pointeur o d'accès à la table de troisième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre. Le cinquième champ (COUNT_LEVEL_3) définit une profondeur de recherche dans la table de niveau 3 lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre. ST - O 1 -GR2-242 - 6 - 2838590 De préférence, la table de troisième niveau comporte: - un premier champ (VALID) déterminant si la recherche doit aboutir au troisième s niveau ou si celle-ci doit se poursuivre à un quatrième niveau; - un second champ (COMBINAISON) servant à des fins de comparaison du troisième octet de l'adresse dudit paquet afin de permettre la sélection dudit troisième ou quatrième champs; - un troisième champ (INDEX) et un quatrième champs (INDEX2) définissant le port de sortie lorsque la valeur du premier champ de la table de troisième niveau définit une recherche devant aboutir ou un pointeur d'accès à la table de quatrième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre. Enfin, la table de quatrième niveau comporte: - un premier champ (COMBINAISON) servant à des fins de comparaison du quatrième octet de l'adresse dudit paquet. - un second champ (N B) définissant une profondeu r de recherche dans ladite table de quatrième niveau; - un troisième champ (INDEX_MASK) définissant un masque de bits à appliquer à l'adresse dudit paquet lors de la recherche dans ladite table de quatrième niveau; - un quatrième champ (INDEX_NH) définissant le port de sortie à utiliser. L'invention permet également la réalisation d'un dispositif de routage de paquets dans un réseau de télécommunication comportant n ports de sorties et destinés à traiter des paquets comportant une adresse de destination définie par au moins un premier, un second, un troisième et un quatrième élément d'adressage. Le dispositif est caractérisé en ce qu'il comporte: - une table de premier niveau (LEVEL_1 table) accédée à partir dudit premier élément d'adressage dudit paquet; - une table de second niveau (LEVEL_2 table) accédée à partir desdits premier et second éléments d'adressage dudit paquet; ST- O1-GR2-242 - une table de troisième niveau (LEVEL_3 table) faisant l'objet d'une recherche à partir du troisième élément d'adressage dudit paquet; - une table de quatrième niveau (LEVEL_4 table) faisant l'objet d'une recherche à partir du quatrième élément d'adressage dudit paquet. s Description des dessins D' autres caractéristiq ues, but et avantages de l' i nvention appara^'tront à la lecture de la description et des dessins ci-après, donnés uniquement à titre d'exemples non limitatifs. Sur les dessins annexés: La figure 1 illustre l'architecture d'un réseau de télécommunication composé de routeurs assurant la communication entre des sous-réseaux. Les figures 2 a à 2d illustrent respectivement le format utilisé respectivement pour la table de niveau 1, la table de niveau 2, la table de niveau 3 et la table de niveau 4. Les figures 3, 4 et 5 illustrent le procédé de routage selon un mode de réalisation préféré. Description d'un mode de réalisation préféré On décrira ci-après plus particulièrement l'organisation d'une table de routage, et le procédé de recherche et parcours de cette table pour déterminer le port de sortie d'un paquet entrant comportant une adresse de destination conforme o à la version courante du protocole en vigueur sur le réseau Internet, connue sous la dénomination Ipv4. Comme on le sait, dans ce protocole, les adresses IP - par exemple A.B.C.D. - sont constituées de quatre octets qu'il s'agit de décoder pour permettre la commande du routage au sein de chaque routeur en fonction des données contenues dans la table de routage disposée localement en ce même ST - O 1-GR2-242 - 8 routeur. Il est clair qu'il ne s'agit que d'un mode particulier de réalisation, particulièrement utile. Dans un mode de réalisation préféré, I'organisation de la table de routage est s conçue pour permettre le stockage d'un nombre d'entrées de l'ordre de 10 000, ce qui s'avère plus que suffisant pour l'organisation d'un réseau privé d'entreprise. On pourra observer que la mise en _uvre d'un aussi grand nombre d'entrées pourra être réalisée très simplement, et ce au moyen d'une architecture de table présentant une dimension réduite de manière à permettre son intégration dans un produit semi o conducteur. La figure 2 illustre plus particulièrement l'organisation d'une telle table de routage qui, comme on le voit, est basée sur un jeu de quatre tables élémentaires - respectivement une table de premier niveau, une table de second niveau, une table de troisième niveau et une table de quatrième niveau I'ensemble permettant, en combinaison avec une table de décalage (ou d'offset), de commander le procédé de routage d'un paquet entrant afin de définir le port de sortie (Nexthop) vers lequel doit être acheminé ledit paquet. L'ensemble de ces tables constituent une structure de données de dimension réduite compatible avec les capacités offertes par les circuits mémoire RAM connus. Elles permettent de fournir un index de sortie, lequel définit alors sans ambiguté un port de sortie du routeur parmi un ensemble de n ports de sortie. Une table de oremier niveau - dite table de niveau 1 (LEVEL_1 table) est illustrée dans la figure 2a et présente une dimension fixée à 256 entrées, de manière à faire correspondre chacune des 256 entrées avec une valeur du premier octet (A) de l'adresse IP du paquet à router. Pour chacune des entrées se trouve stocké un mot comportant trois champs, successivement dénommés VALID, INDEX so NH et INDEX LEVEL 2. Dans un mode de réalisation préféré, on fixe respectivement la dimension de ces champs à 1 bit, 8 bits et 13 bits. Le champ VALID est destiné à porter un bit d'information qui sera décodé dans le procédé de routage exposé ci-après comme signifiant ou non la nécessité de poursuivre la recherche dans les tables successives. Plus spécialement, si le champ VALID est ST - Ol-GR2-242 - 9 - positionné à 0, alors le procédé de routage que l'on décrit plus avant mettra un terme à la recherche et fournira dans le second champ INDEX NH un pointeur définissant le port de sortie (Nexthop) du paquet entrant. Le troisième champ INDEX LEVEL 2 est destiné à contenir une valeur qui servira de pointeur d'accès s pour la table de niveau 2 lorsque la valeur du champ VALID sera égale à 1, comme on va le voir plus en détail ci-après. La table de routage comporte ensuite une table de second niveau - dite table de niveau 2 (LEVEL_2 table) - qui est illustrée dans la figure 2b. Cette table de niveau 2 présente en général une dimension bien plus importante que celle de la première table. On y trouve couramment plusieurs milliers d'entrées en fonction du routeur particulier que l'on souhaitera réaliser. On notera en particulier qu'on pourra trouver avantage à dimensionner cette troisième table de manière confortable afin de faciliter les opérations de maintenance à chaque nouvelle entrée dans la table. On veillera à disposer d'une place suffisante pour l'écriture de nouvelles entrées consécutives correspondant à des nouvelles plages d'adresses. Pour chacune des entrces, cette table de niveau 2 renvoie un mot comportant un premier champ dit VALID, un second champ dit COMBINAISON, un troisième champ - dit INDEX -, un quatrième champ - dit INDEX2 et un cinquième champ dit COUNT_LEVEL_3. Le champ VALID sert, comme précédemment pour la table de niveau 1, à déterminer dans le procédé de routage si la recherche doit arriver à son terme ou bien s'il faut poursuivre les investigations dans la table de troisième niveau que l'on verra plus loin. Le second champ COMBINAISON est destiné à porter une valeur qui sera comparée au second octet de l'adresse IP. Les champs INDEX et INDEX2 sont dimensionnés respectivement à 17 et 8 bits, le premier servant de pointeur définissant le port de sortie du paquet lorsque la recherche pourra être considérée comme terminée au niveau de la lecture de la table de niveau 2, ou de pointeur dans la table de troisième niveau si la recherche so doit se poursuivre. Comme on le verra lors de l'exposé du procédé de routage, le champ INDEX est fixé à une valeur définissant le port de sortie (Nexthop) du paquet entrant pour toute adresse IP dont le second octet est situé entre la valeur courante du champ COMBINAISON et la valeur du champ COMBINAISON de l'entrée suivante dans la table de niveau 2. Le champ INDEX2 rendra le pointeur de sortie ST- O1-GR2-242 du paquet entrant pour toute adresse IP dont le second octet concide avec la valeur du champ COMBINAISON. Enfin, le champ COUNT_LEVEL_3 contient une valeur - typiquement de 8 bits dans un mode de réalisation préféré - laquelle définit l'étendue de la recherche - soit linéaire soit dichotomique - à effectuer lors du procédé de routage que l'on décrira ci-après. En effet, comme on le verra, si les deux premières tables sont consultées directement à partir de l'adresse de routage du paquet entrant- assurant ainsi une rapidement de traitement- les deux tables de niveau supérieur o font l'objet d'une recherche dichotomotique ou linéaire de manière à permettre une réduction significative de l'espace requis pour stocker les informations de routage. D'une manière préférée, la table de second niveau est associée à une table de décalage ou d'offset, laquelle comporte un ensemble de 65536 entrées servant à s décoder les deux premiers octets de l'adresse IP du paquet entrant. Cette table d'offset sert à corriger l'adresse de pointage de la table de niveau 2, comme on le verra ci-après dans l'exposé du procédé de routage. La table de routage comporte ensuite, outre les tables de niveau 1 et 2, une table de troisième niveau - dite de niveau 3 (LEVEL_3 table) laquelle est illustrée dans la figure 2c. Pour chacune de ses entrées, cette table de niveau 3 renvoie un mot comportant un premier champ dit VALID, un second champ dit COMBINAISON, un troisième champ - dit INDEX et un quatrième champ dit INDEX2. Le champ VALID sert, comme précédemment pour la table de niveau 1, dans le procédé de routage pour déterminer si la recherche doit arriver à son terme ou bien s'il faut poursuivre les investigations dans la table de niveau 4 que l'on verra plus loin. On complète enfin l'architecture de la table de routage au moyen d'une table de quatrième niveau - dite table de niveau 4 (LEVEL_4 table) laquelle est illustrée so dans la figure 2d. Elle comporte, pour chaque entrée correspondant aux quatre bytes de l'adresse IP, un premier champ COMBINAISON, un second champ Nb définissant la longueur de la recherche à effectuer dans cette table de niveau 4, un champ INDEX_MASK et un champ INDEX_nh. Le premier champ (COMBINAISON) est comparé au quatrième octet de l'adresse du paquet entrant. Le second champ ST - Ol-GR2-242 - 11 - 2838590 (NB) définit une profondeur de recherche dans la table de niveau 4 et le troisième champ (INDEX_MASK) définit un masque de bits à appliquer à l'adresse du paquet lors de cette même recherche. Un quatrième champ (INDEX_NH) renvoie un pointeur au port de sortie lorsque la recherche doit aboutir. s On décrira à présent, en référence avec les figures 3, 4 et 5 le procédé de routage d'un paquet comportant une adresse IP de destinataire, lequel procédé est basé sur l'exploitation successive et avantageuse des informations stockées dans les différentes tables présentées précédemment. Le procédé commence par une étape 301 dans laquelle l'adresse IP du paquet entrant est lue afin d'extraire le premier octet d'information A s'y trouvant. Dans une étape 302, le procédé réalise ensuite un accès à la table de niveau 1 à l'entrée définie par l'octet A afin d'y lire le contenu des champs VALID, INDEX NH et INDEX LEVEL 2. Dans une étape 303, la valeur du champ VALID fait l'objet d'un test. Si la valeur est égale à 0, alors le procédé renvoie, dans une étape 304, la valeur du champ INDEX NH lequel définit alors sans ambiguté le port de sortie (Nexthop) du paquet entrant. Dans cette situation, le routage est effectué en un minimum de temps, et le procédé peut alors s'achever dans une étane 305. Au contraire, si le champ VALID est égal à 1, cela signifie que la recherche doit se poursuivre à un niveau supérieur afin de déterminer plus précisément le port de sortie du paquet. Le procédé exécute alors une étape 306 au cours de laquelle les deux premiers octets A et B de l'adresse IP sont utilisés pour accéder à la table de décalage (OFFSET), laquelle renvoie alors une valeur qui, dans une étape 307, est ajoutée au contenu du champ INDEX LEVEL 2 lu précédemment dans l'étape so 302. On observera que, dans un mode de réalisation particulièrement optimisé, on pourra grouper les deux champs INDEX NH et INDEX LEVEL 2 de la table de niveau 1 en un unique champ (par exemple dénommé INDEX) lequel sera interprété différemment selon la lecture du bit VALID. On pourra ainsi réduire d'avantage, si on le souhaite, la dimension de la table de niveau 1. Le reste de la description se ST - 01-GR2-242 - 12 poursuivra, pour des raisons de clarté, en supposant la coexistence de deux champs différents INDEX NH et INDEX LEVEL 2. Dans une étape 308 la valeur calculée OFFSET + INDEX LEVEL2 est alors s utilisce pour accéder à la table de niveau 2, laquelle renvoie alors la valeur des champs VALID, COMBINAISON, INDEX, INDEX2 et COUNT_LEVEL_3 qui y sont stockés. Dans une étape 309, un test est effectué sur le champ VALID correspondant o à l'entrée lue dans la table de niveau 2. Si la valeur est égale à 0, alors le procédé poursuit avec une étape 310 o un nouveau test est effectué afin de comparer la valeur du second octet B de l'adresse IP à la valeur contenue dans le champ COMBINAISON lue à l'étape 308. Si les deux valeurs sont égales alors, dans une étape 311, le procédé renvoie la valeur du champ INDEX2 pour définir le port de sortie (Nexthop) du paquet entrant et le procédé s'achève dans une étape 312. Si la valeur de l'octet B est différente du contenu du champ COMBINAISON, alors le procédé renvoie, dans une étape 313, la valeur du champ INDEX lue à l'étape 308 pour définir le port de sortie (Nexthop) et le procédé s'achève dans une étape 314. Au contraire, si le champ VALID est égal à 1, cela signifie que la recherche doit encore se poursuivre dans la table de niveau 3 à l'entrée correspondant à la valeur stockée dans le champ INDEX lu dans l'étape 308. Dans une étane 315, on effectue une comparaison entre le 2e octet de I'adresse IP et le champ COMBINAISON lu à l'étape 308. Si les deux valeurs sont différentes, le procédé poursuit avec une étape 316 dans laquelle ia valeur du champ INDEX2 est utilisée pour définir le port de sortie du routeur (Nexthop). Le procédé s'achève ensuite dans une étape 317. Si le 2e octet de l'adresse IP et le champ COMBINAISON lu à l'étape 308 sont égaux, alors le procédé passe à l'étape 318 dans laquelle on accède à la table de niveau 3 au moyen de la valeur du champ INDEX. ST - 01-GR2-242 On effectue alors, dans une étaPe 319, une recherche dans cette table de niveau 3 à partir de l'entrée définie par la valeur du champ INDEX, et ce sur une plage de plusieurs entrées consécutives dont le nombre est défini par la valeur stockée dans le champ COUNT_LEVEL_3 lu dans l'étape 308. D'une manière s précise, le procédé recherche parmi ces COUNT_LEVEL_3 entrées celle dont le champ COMBINAISON est le plus proche inférieur de l'octet C de l'adresse IP contenu dans le paquet. Dans un mode de réalisation on effectue cette recherche d'une manière linéaire mais on pourra convenir que, alternativement, cette recherche pourra être effectuée d'une manière dichotomique. ll conviendra dans ce cas de veiller à ce que les entrées soient stockées d'une manière ordonnée croissante pour toutes les plages d'adresses définies par un moment doublet A.B. On observera en particulier que la recherche dichotomique aboutira quand bien même on venait à déplacer des plages d'adresses définies par une même valeur AB. Le procédé permet ainsi une mise à jour facile des tables de routage puisqu'il suffira de déplacer simplement toute la plage d'adresse vers un ensemble de positions disponible dans la mémoire vive. Une fois l'entrée identifiée lors d'une étaPe 320, les champs VALID, COMBINAISON, INDEX, INDEX2 sont lus dans une étape 321. Le procédé poursuit ensuite par une étape 322 au cours de laquelle un test sur le champ VALID de cette même entrée est effectué. Si ce champ VALID est égal à 0, alors le procédé poursuit par une étane 323 au cours de laquelle la valeur du troisième octet C de l'adresse IP du paquet entrant est comparée à la valeur contenue dans le champ COMBINAISON de l'entrée identifiée à l'étape 321. Si les deux valeurs sont égales, alors le procédé définit dans une étape 324 le port de sortie NH avec la valeur contenue dans le champ INDEX2 et la détermination du port de sortie s'achève dans une étaPe325. Si la valeur de l'octet C est différente du contenu du champ COMBINAISON alors, dans une étaPe 326, le port de sortie NH est défini par la valeur du champ INDEX de l'entrée identifiée à l'étape 321. La détermination du so port de sortie s'achève alors dans une étape 327. Au contraire, si le champ VALID est égal à 1 dans le test de l'étape 322, alors le procédé se poursuit par une étape 328 similaire à l'étape 323 précédente au cours de laquelle on compare la valeur du troisième octet C de l'adresse IP du ST - O 1 -GR2-242 - 14 paquet entrant avec la valeur contenue dans le champ COMBINAISON de l'entrée identifiée à l'étape 321. Si les deux valeurs sont différentes, alors le procédé définit le port de sortie NH à partir de la valeur contenue dans le champ INDEX2 dans une étape 329 et, dans une étaPe 339, s'achève. s Si les deux valeurs sont égales, alors cela signifie que la recherche doit encore se poursuivre, dans une étape 330, dans la table de niveau 4 à l'entrée correspondant à la valeur stockée dans le champ INDEX de l'entrée identifiée dans l'étape 321. Dans une étape 331, le procédé lance une recherche à partir de l'entrée définie par la valeur du champ INDEX, et ce sur une plage de plusieurs entrées consécutives dont le nombre est défini par la valeur stockée dans le champ Nb de l'entrée identifiée dans l'étape 321. Le procédé recherche parmi ces Nb entrées celle dont le champ COMBINAISON est le plus proche inférieur de l'octet D de l'adresse IP contenu dans le paquet et ce, comme précédemment, au moyen d'une recherche linéaire ou dichotomique. Cette entrée est identifiée dans une étaPe 332 et, dans une étaPe 333, on effectue un ET logique, bit à bit, entre le contenu du champ INDEX_MASK et le quatrième octet D de l'adresse du paquet à router. Dans une étape 334 on effectue un test pour déterminer si le résultat de l'étape 333 est égal au contenu du champ COMBINAISON de l'entrce identifiée dans l'étape 332. Si les deux entités sont égales, alors le procédé lit la valeur du champ so INDEX2 dans la première table NEXT-HOP dans une étape 335. Le procédé s'achève ensuite dans une étape 336. ST - O l-GR2-242 Si les deux valeurs ne sont pas égales, alors le procédé renvoie la valeur par défaut du port de sortie dans une étane 337, avant de s'achever dans une étape 338. Comme on le voit, le procédé décrit en relation avec les figures 3, 4 et 5 fournissent un index de sortie permettant de définir d'une manière non ambiguë le port de sortie du paquet entrant. D'une manière concrète, on pourra associer aux cinq tables que l'on a décrit une table supplémentaire, dite table des NEXTHOP, laquelle permet de stocker les index de référence aux ports du routeur considéré. o La dimension de cette table NEXTHOP est choisie judicieusement en fonction du nombre de ports que l'on souhaitera. Typiquement, on pourra envisager un routeur de 64 ports et on dimensionnera dans ce cas la première table à une valeur de 64 entrées. Dans le mode de réalisation préféré, la première entrée - ou entrée 0 - de cette table est choisie pour pointer vers le port par défaut du routeur vers lequel sont dirigés systématiquement les paquets ne pouvant être spécifiquement routés, en fonction de l'adresse IP contenue dans le paquet, vers un autre port du routeur. Le mécanisme qui vient d'être décrit montre de quelle façon on peut avantageusement consulter les diverses tables exposées précédemment afin de déterminer rapidement le next-hop en fonction des adresses des paquets. Il faut noter que l'on peut avantageusement combiner ce mécanisme de consultation de tables par d'autres mécanismes permettant de charger les contenus des tables avec les diverses informations échangées par les routeurs. En effet, dans le cas d'une réception d'un message de routage définissant l'attribution d'une nouvelle plage d'adresses a un next-hop donne, par exemple correspondant a un message de type il pourra être commode de prévoir dans le routeur un procede spécifique pour mettre a jour toutes les tables décrites précédemment. ST - O] -GR2-242 - 16- 2838590 Revendications Procédé de détermination du port de sortie d'un routeur de télécommunication comportant n ports de sortie et destinés à recevoir des paquets entrants comportant une adresse de destination définie par au moins un premier, un second, un troisième et un quatrième élément d'adressage; ledit procédé comportant les étapes de: - consultation directe d'une table de premier niveau (LEVEL_1 table) à partir dudit premier élément d'adressage dudit paquet; - consultation directe d'un table de second niveau table (LEVEL_2 table) à partir s desdits premier et second éléments d'adressage dudit paquet; - consultation et recherche dans une table de troisième niveau (LEVEL_3 table) permettant un troisième niveau de recherche à partir du troisième élément d'adressage dudit paquet; - consultation et recherche dans une table de quatrième niveau (LEVEL_4 table) à partir du quatrième élément d'adressage dudit paquet. 2. Procédé selon la revendication 1 caractérisé en ce que la table de premier niveau comporte: - un premier champ (VALID) déterminant si la recherche doit aboutir au premier niveau ou si celle-ci doit être poursuivie à un second niveau; - un second champ (INDEX NH) définissant le port de sortie du routeur lorsque la valeur dudit premier champ définit une recherche devant aboutir; - un troisième champ (INDEX LEVEL 2) renvoyant un pointeur d'accès à la table de second niveau lorsque la valeur dudit premier champ définit une recherche devant o se poursuivre. 3. Procédé selon la revendication 2 caractérisé en ce que ledit second et troisième champ sont regroupés en un unique champ interprété différemment selon la valeur dudit premier champ (VALID). ST - O 1-GR2-242 - 17- 2838590 4. Procédé selon la revendication 2 caractérisé en ce que la consultation de la table de second niveau est effectuée au moyen d'une entrée calculée à partir de la valeur du troisième champ de ladite seconde tabie, corrigée par une vaieur lue à partir d'un accès à une table de décalage comportant un unique champ (OFFSET) renvoyant un pointeur de correction à additionner au pointer renvoyé par le champ INDEX2 de ladite table de premier niveau. 5. Procédé selon la revendication 4 caractérisé en ce que la table de second niveau o comporte un premier, un second, un troisième, un quatrième et un cinquième champs: - ledit premier champ (VALID) déterminant si la recherche doit aboutir au second niveau ou si celle-ci doit se poursuivre à un troisième niveau; 1 5 - led it second champ (COM B I NAISON) étant comparé au second élément d'adressage dudit paquet de manière à permettre la sélection dudit troisième ou quatrième champs; - ledits troisième (INDEX) et quatrième champs (INDEX2) définissant le port de sortie lorsque la valeur du premier champ de la table de second niveau définit une recherche devant aboutirou un pointeur d'accès à la tabie de troisième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre; - iedit cinquième champ (COUNT_LEVEL_3) définissant une profondeur de recherche dans ladite table de troisième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre. 6. Procédé selon la revendication 5 caractérisé en ce que ladite table de troisième niveau comporte un premier, un second, un troisième et un quatrième champs: - ledit premier champ (VALID) déterminant si la recherche doit aboutir au troisième niveau ou si celle-ci doit se poursuivre à un quatrième niveau; ST - O1-GR2-242; ()richr nn' - 18 - ledit second champ (COMBINAISON) servant à des fins de comparaison du troisième octet de l'adresse dudit paquet afin de permettre la sélection dudit troisième ou quatrième champs; - ledits troisième champ (INDEX) et quatrième champs (INDEX2) définissant le s port de sortie lorsque la valeur du premier champ de la table de troisième niveau définit une recherche devant aboutir ou un pointeur d'accès à la table de quatrième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre. 7. Procédé selon la revendication 5 caractérisé en ce que ladite table de quatrième niveau comporte: - un premier champ (COMBINAISON) servant à des fins de comparaison du quatrième octet de l'adresse dudit paquet. - un second champ (NB) définissant une profondeur de recherche dans ladite table de quatrième niveau; - un troisième champ (INDEX_MASK) définissant un masque de bits à appliquer à l'adresse dudit paquet lors de la recherche dans ladite table de quatrième niveau; - un quatrième champ (INDEX_NH) définissant le port de sortie à utiliser. 8. Procédé selon la revendication 1 caractérisé en ce que la recherche dans lesdites tables de troisième et quatrième niveaux sont de type linéaire ou dichotomique. 9. Dispositif destiné à router des paquets entrants ayant une adresse de destination définie par au moins un premier, un second, un troisième et un quatrième élément d'adressage vers un ensemble de n ports de sortie; ledit dispositif comportant: - une table de premier niveau (LEVEL_1 table) accédée à partir dudit premier élément d'adressage dudit paquet; so - une table de second niveau (LEVEL_2 table) accédée à partir desdits premier et second éléments d'adressage dudit paquet; - une table de troisième niveau (LEVEL_3 table) faisant l'objet d'une recherche à partir du troisième élément d'adressage dudit paquet; ST - Ol-GR2-242 - 19- 2338590 - une table de quatrième niveau (LEVEL_4 table) faisant l'objet d'une recherche à partir du quatrième élément d'adressage dudit paquet. 10. Dispositif selon la revendication 9 caractérisé en ce que la table de premier niveau comporte: - un premier champ (VALID) déterminant si la recherche doit aboutir au premier niveau ou si celle-ci doit être poursuivie à un second niveau; - un second champ (INDEX NH) définissant le port de sortie du routeur lorsque la valeur dudit premier champ définit une recherche devant aboutir; - un troisième champ (INDEX LEVEL 2) renvoyant un pointeur d'accès à la table de second niveau lorsque la valeur dudit premier champ définit une recherche devant se poursuivre; 11. Dispositif selon la revendication 10 caractérisé en ce qu'il comporte une table supplémentaire de décalage (OFFSET) permettant de renvoyer une valeur de décalage à additionner à la valeur dudit troisième champ (INDEX LEVEL 2) de la table de premier niveau afin d'accéder à la table de second niveau. 12. Dispositif selon la revendication 11 caractérisé en ce que la table de second niveau comporte un premier, un second, un troisième, un quatrième et un cinquième champs: - ledit premier champ (VALID) déterminant si la recherche doit aboutir au second niveau ou si celle-ci doit se poursuivre à un troisième niveau; - ledit second champ (COMBINAISON) étant comparé au second élément d'adressage dudit paquet de manière à permettre la sélection dudit troisième ou quatrième champs; - ledits troisième champ (INDEX) et quatrième champs (INDEX2) définissant le port de sortie lorsque la valeur du premier champ de la table de second niveau so définit une recherche devant aboutir ou un pointeur d'accès à la table de troisième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre; ST - O1-GR2-242 C)cichr sOns - 20 - 2338590 - ledit cinquième champ (COUNT_LEVEL_3) définissant une profondeur de recherche dans ladite table de troisième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre. s 13. Dispositif selon la revendication 12 caractérisé en ce que ladite table de troisième niveau un premier, un second, un troisième et un quatrième champs: - ledit premier champ (VALID) déterminant si la recherche doit aboutir au troisième niveau ou si celle-ci doit se poursuivre à un quatrième niveau; - iedit second champ (COMBINAISON) servant à des fins de comparaison du troisième octet de l'adresse dudit paquet afin de permettre la sélection dudit troisième ou quatrième champs; - ledits troisième champ (INDEX) et quatrième champs (INDEX2) définissant le port de sortie lorsque la valeur du premier champ de la table de troisième niveau définit une recherche devant aboutir ou un pointeur d'accès à la table de quatrième niveau lorsque la valeur dudit premier champ de la table de second niveau définit une recherche devant se poursuivre. 14. Dispositif selon la revendication 13 caractérisé en ce que ladite table de o quatrième niveau comporte: - un premier champ (COMBINAISON) servant à des fins de comparaison du quatrième octet de l'adresse dudit paquet. - un second champ (N B) définissant une profondeur de recherche dans ladite table de quatrième niveau; - un troisième champ (INDEX_MASK) définissant un masque de bits à appliquer à l'adresse dudit paquet lors de la recherche dans ladite table de quatrième niveau; - un quatrième champ (I N DEX_N H) définissant le port de sortie à utiliser. ST - Ol-GR2-242