Brevet FR2865879A1 — publié le 20050805

2865879. Attribution automatique d e pretixes aux equipements d'un reseau de communication de type il'-b La présente invention est 5 type internet et plus précisemenelative aux réseaux de communication de ceux bases sur la pile protocolaire lPv6 (lnternet 'rotocol - version 6). E1lé concerne plus particulièrement la configuration automatique d'un tel réseau Un réseau de ce type est constitué d'un ensemble d'équipements, généralement appelés routeurs , dont le rôle est d'acheminer un trafic de données entre un émetteur et un destinataire. Chaque équipement de réseau dispose d'une ou plusieurs interfaces et chacune de ces interfaces lui permet decommuhiquer avec unau plusieurs autres équipements de réseau. Sur la figure 1 annexée, l'équipement RA dispose de deux interfaces 1 et 142 L'interface IA2 lui permet de communiquer avec un unique équipement Ro, vite son interface lo L'interface 1 équipements connectés au même lien, RB et Rc, via leurs interfaces respectives IB et 1c. Dans la réalité, un équipement ou routeur dispose de 2 ou 3 interfaces au minimum. II doit donc aiguiller chaque paquet de données entrant 2 depuis l'une de ses interfaces, vers l'un ou l'autre de ses autres interfaces. Ce choix n'est pàs trivial Ce mécanisme de choix est appelé routage . Afin de pouvoir acheminer correctement le trafic d'un point à un autre, chaque équipement de réseau a à sa disposition une table dite de routage qui met en correspondance un ensemble d'adresses et une interface 25 de sortie: ainsi, un équipement recevant un paquet de données ayant pour destination tel adresse, sera en mesure de déterminer vers laquelle de ses interfaces il lui faut l'envoyer. Avant qu'un réseau de communication puisse acheminer ainsi un 30 trafic de données, il est donc nécessaire de passer par une étape de 1053017/SYC/AND F:\Sa Île\Fl â5307\PRËMD ÈPFI1\projefbr.doc 2865879 2 configuration du réseau, durant laquelle notamment des adresses doivent être attribuées à chacune des interfaces de chacun des équipements de ce réseau, puis construire les tables de routage. Les spécifications d'un réseau lPv6 sont précisées dans le RFC 2460 de l'IETF (1ntemet Englneenng Task Force). Le documént IP Version 6 Addressing Architecture draft-ietf-ipv6-acldr-arch-v4-00.txt) précise plus particulièrement la façon dont les' adresses de ces interfaces doivent être constituées. Plusieurs types d'adresses existent, niais nous nous intéresserons aux adresses global unicast , c'est-à-dire celles permettent d'identifier de façon que 'une interface d'un équipement de coMmunication au sein d'un réseau. Dans le cas du reseau dit Internet reliant une pluralité de sous-réseau à travers le monde, cette unicité doit être recherchée au niveau màt,dial. Ces adresses global unicast seront par la suite simplement appelées adresses globales pOUr davantage de clarté dans le texte. Une adresse de ce type est principalement composée de deux parties, urne Première pdrtie (typiquement sur 64 bits), et seconde une partie (typiquement sur 64 bits; l'adresse globale étant alors sur 128 bits au total). La seconde partie 'est constituée a partir d'un identifiant unique de l'interface. La façon dont cette partie est constituée est précisée dans le paragraphe 2.5.1 du document 1P Version 6 Addressing Architecture . Elle peut être Constituée à partir d'un identifiant universel, par exemple du type défini par la norme iEEE 802 MAC (pour Media Access Control ) ou IEEE EUI-64 (pour Extended Universel Identifier). Cette seconde partie peut être facilement déterminée par chaque équipement de réseau de façon autonome et automatique 1 05307?YC/À t^'l' 105307\'PRÈMDÈP\FIT\projet6r. de > '6 n'existe toutefois pas de procédé automatique perméttdnt à un équipement de réS"eau de déterminer la première parfle, généralement appelée numéro de réseau . Actuellement, dans les reseaux typ IPv6cett,e partie est déterminée de façon manuelle par un opérateur en charge de la configuration du réseau. Celui-ci se connecte sur chaque équipement de. réseau afin de lui attribuer une adresse globale pour chaque interface, idéalement selon un plan d'adressage optimisé. Un tel plan d'adressage peut titre conforme à la méthodologie décrite dans le RFÇ 3177 intitulé IAB/IESG Rearreendatioris on IPv6 Ad ressAllocations o es . Cette allocation manuelle des adresses globales présente de noml5rèÉiX indanvénients. Notamment, elle nécessite un temps important et l'accupation d'une équipe de techniciens spécialisés. Elle ne permet pas non plus facilement une reconfiguration de la topologie du réseau ou l'ajout d'un nouvel équipement dans un réseau pré-existant. Surtout, elle est susceptible d'engendrer des erreurs car les techniciens aussi compétents soient-ils, sont sujets aux erreurs humaines. Ces erreurs sont d'autant plus nombreuses que le réseauest irnportant et donc difficiles a détecter puis a corriger. Un besoin d'autornatiser la configuration des:réseaux de communication, et notamment l'attribution des adresses globales des interfaces est apparu. Une première &ope vers cette automatisation a été divulguée par les documents Automatic Prefix Delegation Protacol for Internet Protocol Version 6 (IPv6) de B. Haberrnan et J. Martin (draft-habernie-ipngWOE-duto- prefix- Sao Park et Hyoung-Jun Kim (dra -by im-ipv6-hpd-00.1xt) publié en octobre 2003. Ces deux documents sont des drofts IETF, disponibles sur le site web 02.txl) publié en fevner 2002, et I-fierarchical Prefix Delegation Protoco1 for 1nternet Protoeol Version 6 (lPv6) de Byung-Yeob Kim, Kyeong-Jin Lee, Jung- 105307/s'Ïa/Mà .. . \sol FI âdiiem.ÉsÉKffi. ro. - à..c de l'IETF (Interhét Engineering Task For-ce) sous les noms fichiers indiqué entre pdrenthéses ci-avant. De ces documents, il est connu d'attribuer à un équipement de réseau un préfixe d'adresse de façon automatique à partir d'un préfixe d'adresse fourni par un autre équipement de réseau. Ce dernier est appelé délégateur d'adresses et le mecanisme est lui-rnême appele ,délégation d'adresse - Un tel mécanisme est toutefois insuffisant puisqu'il ne prend pas en compte la topologie du résectu de communication existant. Or, la demanderesse a remarqué qu'il était important de prendre en compte cette topologie, au moins pour la raison suivante: chaque Mêrit dispose d'une table de routage lui permettant d'acheminer correctement les paquets de données entrants. Limiter la taille de ces tables de routage perrnet d'une part de gagner des ressources de memorisation à l'intérieur, des équipements et d'autre part de raccourcir e temps de recherche a chaque reception d'un paquet de données. La demanderesse a remardt)é que la prise en compte de la topologie du reseau pour attribuer de façon optimale les 'préfixes d'adresses aux équipements etait importante, et qu'elle pouvait conduire à une diminution significative de. la taille des tables de routage, et, ce faisant, a une augmentation des performances' des équipements de communication. Pour ce faire, invention a pour objet un equipemen t e communication pour un reseau de communication internet, notamment lPv6, comportant un ensemble d'interfaces, chacune desdites interfaces étant connectées à un ou plusieurs autres équipements de communication, disposant de moyens pour recevoir un préfixe d'adresse depuis un premier autre équipement de communication. L'équipement se caractérise en ce qu'il dispose en outre d'un moyen d'attribution pour attribuer à au moins une partie dés autres équipements de communication, un sous-préfixe formé du Ê'.So'lle\-'É'fbËà'0\PËEMbÉKÉrt\pro.feibr.doc...... . . . 2865879 5 préfixe concaténé avec un identificateur individuel dont la longueur dépend du nombre total des autres équipements de communication, le' premier autre équipement n'appadenant pas à cette au moins une partie. Ainsi, en faisant dépendre les sous préfixes d'un préfixe. reçu, l'invention créé une hiérarchie de sous-préfixes, qui permet de prendre en compte la topologie du réseau et de limiter la taille des tables de routage. De surcroît, l'invention a pour autre avantage d'optimiser l'utilisation la ressource constituée par le nombre de bits disponibles pour numéroter le reseau: en n'utilisant pour chaque équipement que le nombre necessaire, les bits des adresses sont ainsi économises. s L'invention, ainsi que d'autres de ses avantages apparaîtront de façon plus claire dans la description qui Vas, en liaison avec les figures annexées. La figure 1, pre'cédemment commentée, schématise un réseau de communication forme de 4 e'quipements La figure 2 illustre le format d'un préfixe d'adresse, selon l'invention. La figure schématise un réseau de communication, et le dêroulernent du procédé decnt sur ce réseau. Un équipement de communication ou rquteur selon l'invention' d'attribution. Ce moyen d'attribution est en charge' comporte un moyen d'attribuer un sous-préfixe à au moins une partie des équipements de 25 communication connectés à celui-ci. I-d figure 2 permet de comprendre la façon dont sont attribués les souspréfixes, selon l'invention. 1 iào1 et/ÀND i 05307\P k.È M. bÉKFI-4roie- "ibr.do. c 2865879 6 Un préfixe initial P est foûrni à Un premier équipement de communication. Il peut être fourni par configuration manuelle, ou par tout autre moyen, sortant du cadre de la presente demande de brevet. e premier équipement attribue alors a au moins une partie des C équipements auxquels il est connecte, un sous-préfixe SP1. Ce souspréfixe SPI est constitué du préfixe P et d'une partie N1. Cette partie N1 est un identificateur individuel de l'équipement concerne: c'est elle qui permet de distinguer les équipements les uns des autres au sein de celte partie d'équipements connectés. Selon l'invention, la taillé (c'est-à-dire le nombre de bits) de cette partie N1 dépend du nombre d'équipements de la partie d'équipements connectés pour lequel un sbus-préfixè doit être attribué SI 'On appelle 1 nombre, alors la taille du champ N1 doit être log,(x) bits. Par exemple, si le premier équipement possède 4 équipements 15 auxquels un sous-préfixe doit être attribué, alors le champ NI doit être de taille Iog2(4)=21, et l'on peut par exemple avoir comme sous-préfixes P:00 P.01 F':10 P:11 (notation signifiant que le préfixe su 'va nts) "es.f cOncaféné avec lés 2 bits,. Chacun de ces équipements reçoit dOnC un sous-préfixe SP, différent pour chacun d'eux (préfixe P identique mai partie N1 différente pour chacun). Ces équipements procèdent alors de la même façon, et déterminent des souspréfixes SP2 pour d'autres equipements de communication. Ces souspréfixes sont, de façon similaire, constitués des sous-préfixes SPI (considérés comme des préfixes, en quelque sorte), et d'identificateurs F; \sa e. oc 2865879 individuels N2 differents pour chdcun de ces équipements et dont la taille dépend de leur nombre. De même, ces équipements, à leur tour, attribueront des sous-préfixes 5P3 constitués des sous-préfixes SP2 et d identificateurs individuels Le processus se poursuit ainsi, de proche en proche, jusqu'à ce que des souspréfixes aient été attribués à l'ensemble du réseau de communication. La figure 3 illustre de façon plus détaillée ce processus d'attribution 10 sur un exemple plus concret. L'équipement RI acquiert un préfixe, selob une methode'n''entrant pas' dans le cadre de cette demande de brevet. Ce préfixe est pat" exe i" le 4001:0660:3510::0/48. La signification de ce format est explicitée dans les documents précédemmenf cités sur les formdfs d'adresses dans le protocole 1Pvb Il est toutefois important de noter ici que le /48 indique la longueur en bits de ce préfixe et que celui-ci est sur 64 bits au maximum. Les signes' sont de simples separateurs pour la commodité de lecture et le signe indique que des 0 sont insérés en nombre suffisant pour coMpléffienter le préfixe aux 48' bits indiqués (un possi e unique signe n'est donc). Cet équipement de résectu RI possède des e'quipernents fils R et R3 auxquels il doit attribuer des sous-préfixes. Comme ces equipements filssont nombre de deux, un unique bit est nécessaire pour l'identificateur individuel ( log (2)=1). L'équipement R2 aura la valeur 0 comme identificateur individuel tandis que l'équipement R3 aura la valeur 1 > T. Par conséquent, les sous-préfixes des équipements R2 et R3 sont respectivement 4001-0660:3510.00000/49 et 4001:0660:3510:8000..0/49 1 053b 7 t,I'd/AN F,91le,FI'dne'\oEmb-Ép\Éf4role-tbr,doc 2865879 8 On remarqué bien que les sous-préfixes sont 1 bit plus long que le préfixe initial. Le second sous-préfixe comporte Io valeur 8' en 13e position, t à-dire 100 c'est 0 en binaire. Ce 1 correspond bien à l'identificateur individuel de 'l'équipement :5 L'équipement R2 procède exactement de même et attribue donc des sous-préfixes, dépendant du sous préfixe de R2, à ses équipements fils R4 et R5. Ces sous-préfixes sont respectivement: 4001:0660:3510:0000::o/5' o 4001:0660:351 0:4000::0/50 Pour ce second préfixe, la voleur 4 en 13' position s'écrit 0100 en binaire. Le pretnier 0 est l'identificateur individuel de l'équipement R2 et le 1 suivant est celui de l'équipement R L'équipement R3, quant à lui, possède 3 équipements fils auxquels il doit attribuer un sous-préfixe Deux bits sont donc necessaires pour affecter un identificateLfr individuel à ces '3 équipements R6, R, et R8, prenant par exemple les valeurs 00 , 10 et 11 respectivement. Les -réfixes sont alors respectivement 'mol:0 '60: 5 1 o:e000::o^s 4001.0660.3510.0000..0/5 4001:06603510: E000 0/51 Pour le troisième sous-préfixe, par exemple la valeur E s'écrit en binaire 1110 Le premier 1 représente l'identificateur individuel de 25 l'équipement R3 et les deux bits suivants 11 est l'identificateur individuel de l'équipement R8. Les équipements de communication selon l'invention attribuent les souspréfixes d'une façon optimisée. Cela implique au moins deux avantages 30 significatifs: 1 cis i'SiCiANQ F:\Salle\F105307\PIZEMDEP\FIT\proietbr.doc 2865879 9 tout d'abord, en dùdffientant la Éaille des sous-préfixes que d'une longueur strictement nécessaire, le mécanisme de l'invention permet d'économiser la ressource représentée par le préfixe d'adresse. En effet, l'accroissement du nombre de bits utilisés est limité à chaque étape, et on peut donc descendre plus bas dans l'arborescence formée par un réseau, et donc d'attribuer atmi.Duer un sous-préfixe à un plus grand nombre, d"équipenyen"fs coffiffiPhicati0n. - Ensuite, l'invention permet d'attribuer des préfixes agrégeables le préfixe de chaque équipenient contient le préfixe de son équipement 10 père- . Par exemple, sur la figure 3, l'équipement R, contient le préfixe de,:. 'R3, et donc, par réC:urrén'cé: de l'équipement Ri. Par consequent, l'équipement RI n'a pas besoin de mémoriser autant d'entrées dans sa table de routage qu'il a de. petit-fils 1I lui suffit d'autant 15 d'entrée que de fils' , soit 2 au lieu de à. En effet, si un paquet de données porte une adresse contenant le préfixe de equlpenlent de R7, il lui suffit d'avoir dans sa table de routage une entrée correspond au préfixe de l'équipement R3, pour l'acheminer correctement. Cette propriété est extrêmem-ent intéressante puisqu'elle permet de minimiser la taille des tables de routage, et donc d'augmenter la performance des équipements de communication F:\. Solle\F165301\PREMbEP\FMprolètbr.doc IO' REVENDICATIONS 1) Équipement de communication (R7) pour un réseau dè comefüriication internet, cOrf-rpôrtant un enérnble enterfcices, chacune desdites interfaces étant connédées à un ou plusieurs autres équipements de communication (RI, R3, R4, R5), disposant de moyens pour recevoir un préfixe d'adresse depuis un' premie dutre équiperhent de communication (RI), caractérise en ce qu'il dispose en outre d''un moyen d'attribution pour attribuer a au moins une partie desdits autres équipements de corrimunication un sous-pre me orme dudit pre conca ene avec un identificateur individuel dont la longueur dépend du nombre total desdits autres équipements de communication, ledit premier autre équipement n'appartenant pas à ladite au moins 'une partie. 1 5 2) Equipement de communication selon la revendicafiOn précédente compatible avec un protoco1e de type 1Pv6. 3)1"m:cédé d'attribution de prefixes au sein d'un réseau de communication de type internet, dans lequel chaque équipement de communication comporte un ensemble d'interfaces, chacune desdites - interfaces etant connectées à un ou plusieurs autres équipements de communication (RI, R3, R4, R5), disposant de moyens pour recevoir un préfixe d'adresse depuis un premier autre équipement de communication (R1) , caractense en ce que chaque équipement de communication attribue à au moins une partie desdits autres equipements de communication, un souspréfixe formé dudit préfixe concaténé avec un identificateur individuel dont la longueur dépend du nombre total desdits autres équipements de communication, ledit premier autre équipement n'appartenant pas à ladite au moins une partie. 10eâ07tiAki1 ' d