Brevet FR3148695A1 — publié le 20241115

Ce procédé de configuration d’un premier système autonome (AS2) dans un réseau de transit, ce procédé comportant : - une étape (E20) d’obtention d’une information selon laquelle le trafic reçu par un routeur d’entrée (REj) dudit premier système autonome (AS2) est saturé ; - une étape (E40) de détermination d’un préfixe (i) d’un sous-réseau de destination (SRDi) d’un deuxième système autonome (AS3) en aval dudit premier système autonome (AS2); - une étape (E50) d’allongement du chemin associé audit préfixe (i) sur au moins un routeur cible (REk) dudit premier système autonome (AS2) ; ledit préfixe et ledit au moins un routeur cible REk étant déterminés en optimisant une fonction objectif (FOBJ) de sorte que le chemin associé audit préfixe doit être allongé pour tous les routeurs d’entrée du premier système autonome (AS2) qui sont géographiquement plus proches du routeur saturé (REj) que ledit routeur cible (REk). Fig. 2 Procédé et système de configuration d’un système autonome L’invention se situe dans le contexte d’un réseau de transit. Elle concerne plus particulièrement un procédé et un système permettant de rééquilibrer la charge dans un système autonome (en anglais, Autonomous Systems AS) lorsqu’il est détecté que l’une de ses interfaces d’entrée est saturée. De manière équivalente, les expressions « interface d’entrée » ou « routeur d’entrée » seront utilisées. De façon connue, un tel routeur d’entrée reçoit, d’un ou plusieurs routeurs de sortie d’un système autonome dit « amont », du trafic comportant des paquets, et route chacun de ces paquets, à partir de leur adresse IP de destination, vers un sous-réseau de destination d’un système autonome dit « aval ». On rappelle que les adresses IP des équipements d’un même sous-réseau de destination appartiennent à une même plage d’adresses appelée « préfixe ». On rappelle aussi que ces réseaux de transit utilisent le protocole BGP (en anglais, Border Gateway Protocol) pour échanger des informations de routage et d'accessibilité de réseaux (appelés préfixes) entre les systèmes autonomes. Le protocole BGP définit notamment un mode de fonctionnement eBGP (en anglais, Exterior BGP) utilisé entre deux systèmes autonomes AS. Ce protocole définit des messages, chacun associé à un certain nombre d’attributs. Par exemple, une fois la connexion eBGP établie entre le routeur d’entrée d’un premier système autonome et un routeur de sortie d’un deuxième système autonome amont, le routeur d’entrée communique au routeur de sortie : - des informations sur les réseaux de destination qu'il connait et pour lesquels il propose du transit, ainsi - qu'un certain nombre d'attributs associés à ces réseaux, qui permettent d'éviter des boucles. C’est aux routeurs de sortie du deuxième système autonome amont de choisir un routeur d’entrée du premier système autonome qui offre la meilleure route vers un sous-réseau de destination. En particulier, quand plusieurs routes sont possibles vers un même sous-réseau de destination, le protocole BGP permet à un routeur de déterminer la meilleure route à utiliser et de l’annoncer à ses routeurs voisins. A cet effet, le protocole définit un attribut « AS Path » qui comporte une liste ordonnée des systèmes autonomes traversés pour atteindre un sous-réseau de destination. Toutes choses étant égales par ailleurs, le protocole BGP choisit la route avec l’attribut « AS Path » le plus court. Il est fréquent que certaines interfaces d’entrée soient saturées mais pas d’autres. Dans l’état actuel de la technique, une solution pour essayer de sortir de cette situation de saturation consiste à reconfigurer le routeur d’entrée saturé en augmentant la liste de l’attribut « AS Path » associée à un sous-réseau de destination, autrement dit à un préfixe. Les routeurs de sortie du deuxième système autonome amont déplacent alors le trafic destiné à ce préfixe vers un autre routeur d’entrée. Mais le grand nombre de préfixes ainsi que la combinatoire liée à la nature du problème font qu’il est très difficile de choisir les préfixes dont les chemins doivent être allongés. En effet, un préfixe choisi peut entrainer une saturation sur un routeur d’entrée ; il faut alors choisir des nouveaux préfixes sur ce dernier routeur d’entrée, ce qui peut entrainer de nouvelles saturations ailleurs, et ainsi de suite. L’invention vise un procédé et un système de configuration qui ne présente pas ces inconvénients. Objet et résumé de l’invention Ainsi, et selon un premier aspect, l’invention concerne un procédé de configuration d’un premier système autonome dans un réseau de transit, ce procédé comportant : - une étape d’obtention d’une information selon laquelle le trafic reçu par un routeur d’entrée du premier système autonome est saturé, ledit trafic étant reçu en provenance d’au moins un routeur de sortie d’un deuxième système autonome en amont dudit premier système autonome ; - une étape de détermination d’un préfixe d’un sous-réseau de destination d’un troisième système autonome en aval dudit premier système autonome, au moins une partie dudit trafic étant destiné à des équipements dudit sous-réseau de destination; - une étape d’allongement du chemin associé audit préfixe sur au moins un routeur cible parmi les routeurs d’entrée dudit premier système autonome ; ledit préfixe et ledit au moins un routeur cible étant déterminés en optimisant une fonction objectif dans le respect d’au moins ces contraintes, selon lesquelles : (i) pour tout routeur d’entrée du premier système autonome, le trafic en entrée dudit routeur est inférieur à un seuil de saturation ; et (ii) le chemin associé audit préfixe doit être allongé pour tous les routeurs d’entrée du premier système autonome qui sont géographiquement plus proches du routeur saturé que ledit routeur cible. Corrélativement, l’invention concerne un système de configuration d’un premier système autonome dans un réseau de transit, ce système comportant : - une unité d’optimisation configurée pour obtenir une information selon laquelle le trafic reçu par un routeur d’entrée d’un premier système autonome est saturé, ledit trafic étant reçu en provenance d’au moins un routeur de sortie d’un deuxième système autonome en amont dudit premier système autonome; - ladite unité d’optimisation étant configurée pour déterminer un préfixe d’un sous-réseau de destination d’un troisième système autonome en aval dudit premier système autonome, au moins une partie dudit trafic étant destiné à des équipements dudit sous-réseau de destination ; - une unité de contrôle configurée pour allonger le chemin associé audit préfixe sur au moins un routeur cible parmi les routeurs d’entrée dudit premier système autonome ; ledit préfixe et ledit au moins un routeur cible étant déterminés par ladite unité d’optimisation en optimisant une fonction objectif dans le respect d’au moins ces contraintes, selon lesquelles : (i) pour tout routeur d’entrée du premier système autonome, le trafic en entrée dudit routeur est inférieur à un seuil de saturation ; et (ii) le chemin associé audit préfixe doit être allongé pour tous les routeurs d’entrée du premier système autonome qui sont géographiquement plus proches du routeur saturé que ledit routeur cible. Conformément à la deuxième contrainte, le chemin associé au préfixe déterminé est au moins allongé sur le routeur saturé et éventuellement sur au moins un autre routeur cible. L’invention fait l’hypothèse que l’allongement d’un chemin associé à un préfixe sur un routeur donné a pour effet que les routeurs de sortie du deuxième système autonome amont déplacent le trafic associé à ce préfixe vers l’interface la plus proche géographiquement de ce routeur donné, ce déplacement ayant pour effet un rééquilibrage de charge au sein du premier système autonome. Conformément à l’invention, le préfixe est déterminé en optimisant une fonction objectif sous le respect de contraintes, une contrainte imposant que le chemin associé au préfixe doit être allongé pour tous les routeurs d’entrée du premier système autonome qui sont géographiquement plus proches du routeur saturé que le routeur cible. Dans un mode particulier de réalisation, l’allongement du chemin associé au préfixe sur au moins un dit routeur cible comporte : - une reconfiguration d’une table de routage du routeur cible en ajoutant au moins un système autonome à un attribut AS-Path du protocole BGP ; et - un envoi dudit attribut à au moins un routeur de sortie dudit deuxième système autonome amont. Dans un mode de réalisation de l’invention, l’optimisation de la fonction objectif consiste à minimiser le nombre de routeurs d’entrée à reconfigurer. Dans d’autres modes de réalisation de l’invention, l’optimisation de la fonction objectif peut par exemple consister à minimiser le nombre de préfixes dont on rallonge le chemin, ou à minimiser la charge de l’interface la plus chargée. La fonction objectif peut également être une combinaison linéaire d’une ou plusieurs de ces fonctions d’optimisation (minimisation du nombre de routeurs, de nombre de préfixes dont on rallonge le chemin, de la charge de l’interface la plus chargée, …). Dans un mode de réalisation: - la fonction objectif est une fonction linéaire de la forme : - et les contraintes s’expriment de façon linéaire sous la forme : CST1 : CST2 : CST3 : CST4 : CST5 : dans lesquelles : - c max est un seuil de saturation et b j est le débit maximal supporté par le routeur REj ; - p ijt est un pic de trafic associé au préfixe i sur l’interface j au cours d’une plage de temps t ; - Lj est une liste ordonnée des routeurs d’entrée du premier système autonome du plus proche au plus éloigné du routeur saturé REj ; - L(j,k) est une sous-liste de Lj comprenant les routeurs d’entrée du premier système autonome (AS2) qui sont géographiquement plus proches du routeur saturé (REj) que ledit routeur cible (REk) ; - x ijk est une variable de décision binaire égale à 1 si le trafic associé au préfixe i est routé d’un routeur REi vers un routeur REj, 0 sinon ; - y ij est une variable de décision binaire égale à 1 si le chemin associé au préfixe i est rallongé sur un routeur d’entrée REj, 0 sinon ; - z j : variable de décision binaire égale à 1 si le routeur d’entrée REi est reconfiguré, 0 sinon. Dans ce mode de réalisation, le procédé met en œuvre un programme linéaire en nombre entier (PLNE), particulièrement adapté pour les problèmes d’optimisation avec une combinatoire élevée, le PLNE étant résolu afin d’obtenir une solution qui offre une garantie d’optimalité sur le nombre de routeurs à reconfigurer. L’invention vise aussi un programme d’ordinateur comportant des instructions pour exécuter les étapes suivantes lorsque ledit programme est exécuté par un ordinateur. - obtention d’une information selon laquelle le trafic reçu par un routeur d’entrée d’un premier système autonome est saturé, ledit trafic étant reçu en provenance d’au moins un routeur de sortie d’un deuxième système autonome en amont dudit premier système autonome ; - détermination d’un préfixe d’un sous-réseau de destination d’un troisième système autonome en aval dudit premier système autonome, au moins une partie dudit trafic étant destiné à des équipements dudit sous-réseau de destination ; - envoi d’une instruction pour allonger le chemin associé audit préfixe sur au moins un routeur cible parmi les routeurs d’entrée dudit premier système autonome ; ledit préfixe et ledit au moins un routeur cible étant déterminés en optimisant une fonction objectif dans le respect d’au moins ces contraintes, selon lesquelles : (i) pour tout routeur d’entrée du premier système autonome, le trafic en entrée dudit routeur est inférieur à un seuil de saturation ; et (ii) le chemin associé audit préfixe doit être allongé pour tous les routeurs d’entrée du premier système autonome qui sont géographiquement plus proches du routeur saturé que ledit routeur cible. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, une mémoire non volatile de type flash ou encore un moyen d'enregistrement magnétique, par exemple un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. D’autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent des exemples de réalisation dépourvus de tout caractère limitatif. Sur les figures : La illustre un exemple de mise en œuvre d’un système d’équilibrage de charge conforme à un mode particulier de réalisation de l’invention. ; La représente les principales étapes d’un procédé de configuration conforme à un mode de réalisation de l’invention. La illustre de façon détaillée un exemple de mise en œuvre d’un système d’équilibrage de charge 100 conforme à l’invention. Dans le mode de réalisation décrit ici, le système d’équilibrage de charge 100 comporte une unité de collecte DC, une unité d’optimisation OPT et un contrôleur CTR. Dans le mode de réalisation de la , ces trois entités sont séparées. En variante, au moins deux d’entre elles peuvent être intégrées dans un même équipement. Elles peuvent être colocalisées ou reliées entre elles par un réseau de nature quelconque. Dans l’exemple décrit ici, un premier système autonome AS1 comporte trois routeurs de sortie RS1, RS2, RS3, et un deuxième système autonome AS2, en amont du premier système autonome AS1, comporte trois routeurs d’entrée RE1, RE2, RE3. Dans l’exemple décrit ici, chaque routeur de sortie RSi est connecté avec le routeur d’entrée REi (de même indice). Par ailleurs, dans l’exemple de la , le routeur de sortie RS1 est connecté au sein du système autonome AS1 au routeur de sortie AS2, lui-même connecté au routeur de sortie RS3. Le routeur de sortie RS1 a donc deux possibilités pour envoyer un paquet au sous réseau de destination SRD1 : - soit router ce paquet vers le routeur d’entrée RE1, - soir le router vers le routeur de sortie RS2, qui peut à son tour soit le router vers le routeur d’entrée RE2, soit vers le routeur de sortie RS3, ce dernier le routant alors vers le routeur d’entrée RE3. Dans l’exemple de réalisation décrit ici, on suppose que les trois routeurs d’entrée RE1, RE2, RE3 du système autonome AS2 sont localisés respectivement à Paris, à Londres et à Amsterdam. Dans l’exemple décrit ici, le système autonome AS3 comporte deux sous-réseaux de destination SRD1, SRD2 et d’autres sous-réseaux de destination non représentés. Chacun de ces systèmes autonomes ASi comporte en outre un ensemble Ei de routeurs R. Les adresses des équipements d’un même sous-réseau de destination ont le même préfixe. Par exemple : - le sous-réseau de destination SRD1 contient la plage d’adresses IP 10.0.0.0 à 10.0.0.255, et son préfixe peut être noté 10.0.0.0/24 ; et - le sous-réseau de destination SRD2 contient la plage d’adresses IP 20.0.0.0 à 20.0.0.255, et son préfixe peut être noté 20.0.0.0/24. Conformément au protocole BGP, chaque routeur d’entrée du premier système autonome AS2 gère une table de routage, qui comprend, pour chaque sous-réseau de destination vers lequel il peut router du trafic, un attribut AS-Path qui liste le ou les systèmes autonomes qu’un paquet doit traverser pour atteindre ce sous-réseau. Par exemple, la table de routage du routeur d’entrée RE1 comporte deux enregistrements : SRD1 : AS-Path : AS2, AS3 SRD2 : AS-Path : AS2, AS3 Conformément au protocole BGP, le routeur d’entrée RE1 (respectivement RE2, RE3) annonce au routeur de sortie RS1 (respectivement RS2, et RS3) du système autonome AS1 qu’il est capable de router le trafic vers les sous-réseaux de destination SRD1 et SRD2, ce message comportant ces informations de sa table de routage, et notamment à quelle distance ils se trouvent de chacun de ces sous-réseaux. Cette distance est propre au fonctionnement du routage IP et ne correspond pas à une distance géographique. Pour la distinguer d’une distance géographique, on nommera cette distance « distance de routage ». A titre d’exemple le routeur d’entrée RE1 envoie au routeur de sortie RS1 deux messages de type UPDATE(SRD1, AS2, AS3) et UPDATE(SRD2, AS2, AS3) pour lui indiquer qu’il peut router du trafic vers le sous-réseau de destination SRD1 (respectivement SRD2) et qu’il se trouve à une distance de routage de deux systèmes autonomes (en l’espèce AS2, AS3) du sous-réseau de destination SRD1 (respectivement SRD2). Dans l’exemple de réalisation décrit ici, le routeur d’entrée RE2 (respectivement RE3) fait les mêmes annonces au routeur de sortie RS2 (respectivement RS3). La représente les principales étapes d’un procédé de configuration conforme à un mode de réalisation de l’invention. Le procédé d’équilibrage comporte une étape générale E10 de collecte de données représentatives du trafic reçu en entrée par les routeurs d’entrée RE1, RE2, RE3 du système autonome AS2. Si la collecte des données ne peut se faire simultanément sur l’ensemble des préfixes, il peut se faire par tranches de temps par groupes de préfixes. Dans le mode de réalisation décrit ici, ces données permettent notamment de déterminer : - le pic de débit, autrement dit le débit maximal, en entrée d’un routeur d’entrée au cours d’une plage de temps ; et - le pic de débit correspondant aux paquets d’un sous-réseau de destination SRDi, autrement dit au trafic associé à un préfixe donné au cours d’une plage de temps. Dans l’exemple de réalisation décrit ici, nous considèrerons deux plages de temps, à savoir par exemple le matin et le soir. Les notations utilisées ci-après sont introduites sur un exemple. Dans l’exemple de réalisation décrit ici, on considère 2 sous-réseaux de destination SRD1, SRD2, notés SRDi, à savoir 2 préfixes i = 1 à 2. Dans l’exemple de réalisation décrit ici, le système comporte 3 routeurs d’entrée RE1, RE2, RE3, autrement dit 3 interfaces j = 1 à 3. Dans l’exemple de réalisation décrit ici, on considère deux plages de temps t = 1 à 2. On note p ijt le pic de trafic associé au préfixe i sur l’interface j au cours de la plage de temps t. On suppose pour illustrer la description, que la situation nominale est celle du tableau T1 en annexe. Par exemple, pour le routeur RE1, interface j=1, situé à Paris : - le débit maximal le matin (t=1) à destination du sous réseau SDR1 (préfixe i=1), noté p 111 , est de 3 Gbps ; - le débit maximal le matin (t=1) à destination de SDR2 (i=2), noté p 211 , est de 2 Gbps ; - le débit maximal le soir (t=2) à destination de SDR1 (i=1), noté p 112 , est de 6 Gbps ; - le débit maximal le soir (t=2) à destination de SDR2 (i=2), noté p 212 , est de 4 Gbps. On note DT jt , le débit maximal cumulé sur l’interface j au cours de la plage de temps t. On note Cj, la charge sur l’interface j, définie comme le rapport entre le débit maximal sur une ou plusieurs plages de temps et le débit maximal b j supporté par cette interface (supposé égal à 100 Gbps pour toutes les interfaces ci-après). Dans l’exemple du tableau T1, on considère que le débit maximal le matin (t=1) en entrée de l’interface 1 (routeur RE1), noté DT 11 est de 80 Gbps ; et que le soir, ce débit maximal est DT 12 = 93 Gbps. La charge C 1 du routeur RE1 est donc de 93%. Le procédé de configuration comporte une étape E20 pour déterminer si le trafic en entrée d’un routeur d’entrée REj du système autonome AS2 est saturé. Dans le mode de réalisation décrit ici, cette détermination est effectuée en comparant la charge du routeur REj avec un seuil de saturation c max . Dans l’exemple décrit ici, le seuil de saturation c max est égal à 90%. Dans l’exemple du tableau T1, le routeur d’entrée RE1 (ou l’interface 1) est déterminé comme étant saturé, car C 1 (93%) est supérieur à c max . Lorsqu’un routeur d’entrée REj est déterminé comme étant saturé, le résultat du test E20 est positif. L’invention propose de rééquilibrer la charge en allongeant le chemin associé à un préfixe sur ce routeur saturé, l’invention faisant l’hypothèse que lorsqu’un routeur de sortie du système autonome AS1 apprend que le chemin associé à un préfixe est allongé sur un routeur d’entrée REj, il déplace le trafic associé à ce préfixe sur le routeur d’entrée REk du système autonome AS2 le plus proche géographiquement de REj. Le tableau TD en annexe présente les distances géographiques entre Paris (PAR), Londres (LON) et Amsterdam (AMS). Pour un routeur d’entrée REj, autrement dit pour une interface j, on note Lj la liste ordonnée des routeurs d’entrée REk (interfaces k), de la plus proche à la plus éloignée à partir de l’interface j. Dans cet exemple : L1 = {1, 2, 3}, L2 = {2, 1, 3}, L3 = {3, 2, 1}. Dans un mode de réalisation de l’invention, pour allonger le chemin associé à un préfixe i sur un routeur d’entrée REk (interface k), on reconfigure ce routeur REk en ajoutant à l’attribut AS PATH du protocole BGP un système autonome dans la liste des systèmes autonomes à parcourir pour atteindre le sous-réseau de destination SRDi associé à ce préfixe. Par exemple, dans l’exemple décrit ici, pour allonger le chemin associé au préfixe i=1 sur le routeur d’entrée RE1, l’enregistrement de la table de routage du routeur d’entrée RE1 associé à ce préfixe peut être modifié : SRD1 : AS-Path : AS2, AS2, AS3 Cette configuration peut être effectuée par le contrôleur CTR. Conformément au protocole BGP, le routeur d’entrée REi dont la table de routage a été modifiée annonce cette reconfiguration au routeur de sortie amont auquel il est connecté. Dans cet exemple, le routeur d’entrée RE1 envoie au routeur de sortie RS1 deux messages de type UPDATE(SRD1, AS2, AS2, AS3). Le routeur de sortie RS1 prend connaissance de ce changement d’attribut et choisit de router le trafic associé au sous-réseau de destination SRDi (par exemple ici SRD1) vers un autre routeur d’entrée du système autonome AS2 offrant une route BGP plus courte vers ce sous-réseau de destination. En effet, dans le schéma de la , le routeur de sortie RS1 a deux possibilités pour envoyer un paquet au sous réseau de destination SRD1 : - soit router ce paquet vers le routeur d’entrée RE1 qui a annoncé la route AS2, AS2, AS3 (distance de routage égale à 3 AS), - soit router ce paquet vers le routeur de sortie RS2 qui le route vers le routeur d’entrée RE2 qui a annoncé la route AS2, AS2 (distance de routage égale à 2 AS) Dans cet exemple, il choisira alors la deuxième option qui est la plus courte. En reprenant l’exemple du tableau T1, nous détaillons ci-après l’effet de l’allongement du chemin associé au préfixe i=1, puis au préfixe i=2. Allongement du chemin associé au préfixe i=1 Le tableau T2 en Annexe illustre ainsi les débits en entrée de chacun des routeurs d’entrée RE1, RE2, RE3 en supposant que le chemin associé au préfixe i=1 est allongé sur le routeur RE1. Conformément à l’invention, on suppose que cet allongement de chemin a pour effet que le trafic associé au préfixe i=1 sera déplacé sur l’interface la plus proche géographiquement, soit RE2 (voir liste L1). Par conséquent, si c’est le cas : - le débit p 111 associé au préfixe i=1 en entrée de l’interface j=1 pour la plage de temps t=1 devient 0, tout le trafic associé étant routé sur l’interface 2 ; le débit total DT 11 est diminué de 3 Gbps ; - le débit p 121 associé au préfixe i=1 en entrée de l’interface j=2 qui était de 10 Gbps dans la plage t = 1 est augmenté de 3 Gbps et devient 13 Gbps ; le débit total DT 21 est également augmenté de 3 Gbps ; - le débit p 112 associé au préfixe i=1 en entrée de l’interface j=1 pour la plage de temps t=2 devient 0, tout le trafic associé étant routé sur l’interface 2 ; le débit total DT 12 est diminué de 6 Gbps ; la charge C 1 sur l’interface 1 est alors de 87%, en dessous du seuil c max ; - le débit p 122 associé au préfixe i=1 en entrée de l’interface j=2 qui était de 20 Gbps dans la plage t = 2 est augmenté de 6 Gbps et devient 26 Gbps ; le débit total DT 22 en entrée du routeur RE2 est également augmenté de 6 Gbps et devient 94 Gbps. On constate que la charge C 2 du routeur d’entrée RE2 de 94% dépasse alors le seuil de saturation C max . On suppose maintenant que le chemin associé au préfixe i=1 est également rallongé sur le routeur d’entrée RE2 et que cet allongement de chemin a pour effet que le trafic associé au préfixe i=1 sera déplacé sur l’interface la plus proche géographiquement de RE2, c’est à dire vers RE3 (voir liste L1). Le tableau T3 an Annexe illustre les débits en entrée de chacun des routeurs d’entrée RE1, RE2, RE3 en supposant que le débit associé au préfixe i=1 est rallongé sur les routeurs RE1 et RE2 et est donc routé sur le routeur d’entrée RE3. Notamment : - le débit p 121 associé au préfixe i=1 en entrée de l’interface j=2 pour la plage de temps t=1 devient 0, tout le trafic associé étant routé sur l’interface 3 ; le débit total DT 11 est diminué de 13 Gbps ; - le débit p 131 associé au préfixe i=1 en entrée de l’interface j=3 qui était de 2 Gbps dans la plage t = 1 est augmenté de 13 Gbps et devient 15 Gbps ; le débit total DT 31 est également augmenté de 13 Gbps ; - le débit p 122 associé au préfixe i=1 en entrée de l’interface j=2 pour la plage de temps t=2 devient 0, tout le trafic associé étant routé sur l’interface 3 ; le débit total DT 22 est diminué de 26 Gbps ; la charge C 1 sur l’interface 2 est alors de 70%, en dessous du seuil c max ; - le débit p 132 associé au préfixe i=1 en entrée de l’interface j=3 qui était de 2 Gbps dans la plage t = 3 est augmenté de 26 Gbps et devient 28 Gbps ; le débit total DT 32 en entrée du routeur RE2 est également augmenté de 26 Gbps et devient 96 Gbps. On constate que la charge C 3 du routeur d’entrée RE3 de 94% dépasse le seuil de saturation c max de 90%. Dans cet exemple, il n’est pas possible de router le trafic en entrée sur un autre routeur d’entrée du système autonome AS2. Par conséquent, le rallongement des chemins associés au préfixe i=1 sur les routeurs d’entrée RE1, RE2 ne permet pas d’éviter le phénomène de saturation adressé par l’invention. Allongement du le chemin associé au préfixe i=2 Le tableau T4 en Annexe illustre ainsi les débits en entrée de chacun des routeurs d’entrée RE1, RE2, RE3 en supposant que le chemin associé au préfixe i=2 est allongé sur le routeur RE1, et que ce trafic est routé vers le routeur d’entrée RE2. Notamment : - le débit p 211 associé au préfixe i=2 en entrée de l’interface j=1 pour la plage de temps t=1 devient 0, tout le trafic associé étant routé sur l’interface 2 ; le débit total DT 11 est diminué de 3 Gbps ; - le débit p 221 associé au préfixe i=2 en entrée de l’interface j=2 qui était de 3 Gbps dans la plage t = 1 est augmenté de 2 Gbps et devient 5 Gbps ; le débit total DT 21 est également augmenté de 2 Gbps ; - le débit p 212 associé au préfixe i=2 en entrée de l’interface j=1 pour la plage de temps t=2 devient 0, tout le trafic associé étant routé sur l’interface 2 ; le débit total DT 12 est diminué de 4 Gbps ; la charge C 1 sur l’interface 1 est alors de 89%, en dessous du seuil c max ; - le débit p 222 associé au préfixe i=2 en entrée de l’interface j=2 qui était 3 Gbps dans la plage t = 2 est augmenté de 4 Gbps et devient 7 Gbps ; le débit total DT 22 en entrée du routeur RE2 est également augmenté de 4 Gbps et devient 92 Gbps. On constate que la charge C 2 du routeur d’entrée RE2 de 92% dépasse le seuil de saturation C max de 90%. On suppose maintenant que le chemin associé au préfixe i=2 est également rallongé sur le routeur d’entrée RE2 et que cet allongement de chemin a pour effet que le trafic associé au préfixe i=2 est déplacé sur l’interface la plus proche géographiquement de RE2, c’est à dire vers RE3. Le tableau T5 en Annexe illustre ainsi les débits en entrée de chacun des routeurs d’entrée RE1, RE2, RE3 en supposant que le débit associé au préfixe i=2 est rallongé sur les routeurs RE1 et RE2 et routé sur le routeur d’entrée RE3. Notamment : - le débit p 221 associé au préfixe i=2 en entrée de l’interface j=2 pour la plage de temps t=1 devient 0, tout le trafic associé étant routé sur l’interface 3 ; le débit total DT 21 est diminué de 5 Gbps ; - le débit p 231 associé au préfixe i=2 en entrée de l’interface j=3 qui était de 5 Gbps dans la plage t = 1 est augmenté de 5 Gbps et devient 10 Gbps ; le débit total DT 31 est également augmenté de 5 Gbps ; - le débit p 222 associé au préfixe i=2 en entrée de l’interface j=2 pour la plage de temps t=2 devient 0, tout le trafic associé étant routé sur l’interface 3 ; le débit total DT 22 est diminué de 7 Gbps ; la charge C 2 sur l’interface 2 est alors de 85%, en dessous du seuil c max ; - le débit p 232 associé au préfixe i=2 en entrée de l’interface j=3 qui était de 5 Gbps dans la plage t = 2 est augmenté de 7 Gbps et devient 12 Gbps ; le débit total DT 32 en entrée du routeur RE2 est également augmenté de 7 Gbps et devient 77 Gbps ; la charge C 3 sur l’interface 2 est alors de 85%, en dessous du seuil c max . On constate que ce rééquilibrage de charge par allongement du chemin associé au préfixe i=2 sur les routeurs RE1 et RE2 conduit à une situation dans laquelle aucun des routeurs d’entrée RE1, RE2, RE3 n’est saturé. De façon très avantageuse, le procédé de configuration selon l’invention permet de déterminer automatiquement un préfixe (étape E40) et les routeurs d’entrée du système autonome AS2 sur lesquels les chemins associés à ce préfixe doivent être rallongés (étape E50) pour que le trafic soit rééquilibré de façon à ce qu’aucun de ces routeurs d’entrée ne soit saturé. Conformément à l’invention, cette détermination est effectuée en optimisant une fonction objectif FOBJ dans le respect d’un ensemble de contraintes. Dans le mode de réalisation décrit ici, l’optimisation de la fonction objectif FOBJ consiste à minimiser le nombre de routeurs d’entrée (ou d’interfaces) à reconfigurer. Dans le mode de réalisation décrit ici, la fonction d’optimisation respecte 5 contraintes : - la première contrainte CST1 impose que le trafic associé à un préfixe i est routé sur un et un seul routeur d’entrée ; - la deuxième contrainte CST2 interdit de déclencher le routage du trafic associé à , un préfixe i vers un routeur d’entrée REk tout en allongeant le chemin associé à ce préfixe sur ce routeur d’entrée ; - la troisième contrainte CST3 impose que si le trafic associé à un préfixe i est basculé d’un routeur d’entrée REj vers un routeur d’entrée REk, alors le chemin associé à ce préfixe doit être allongé sur tous les routeurs d’entrée classés entre ces deux routeurs REj (inclus) et REk (exclus) dans la liste Lj ; - la quatrième contrainte CST4 impose que, quelle que soit la plage de temps t, l’ensemble du trafic entrant sur un routeur d’entrée REj ne doit pas dépasser le seuil de saturation C max ; et - la cinquième contrainte CST5 impose que si on allonge au moins un chemin associé à un préfixe sur un routeur d’entrée, alors ce routeur d’entrée doit être reconfiguré. Dans un mode de réalisation de l’invention, cette optimisation est mise en œuvre par l’exécution d’un programme linéaire, la fonction objectif ainsi que les contraintes étant exprimées sous forme de fonctions linéaires par rapport à des variables de décision. Dans un mode de réalisation, on introduit les notations suivantes : p ijt :pic de trafic associé au préfixe i sur l’interface j au cours d’une plage de temps t. Lj : liste ordonnée des routeurs d’entrée du premier système autonome du plus proche au plus éloigné du routeur saturé REj. L(j,k) : sous-liste de Lj comprenant les routeurs d’entrée du premier système autonome qui sont géographiquement plus proches du routeur saturé REj que ledit routeur cible REk. x ijk : variable de décision binaire égale à 1 si le trafic associé au préfixe i est rerouté de l’interface j à l’interface k, 0 sinon ; y ij est une variable de décision binaire égale à 1 si le préfixe i a son chemin rallongé sur l’interface j, 0 sinon. z j est une variable de décision binaire égale à 1 si l’interface j est reconfigurée, 0 sinon. On introduit les notations suivantes : est un seuil de saturation et b j est le débit maximal supporté par le routeur REj. x ijk est une variable de décision binaire égale à 1 si le trafic associé au préfixe i est routé d’un routeur REi vers un routeur REj, 0 sinon ; y ij est une variable de décision binaire égale à 1 si le chemin associé au préfixe i est rallongé sur un routeur d’entrée REj, 0 sinon ; z j est une variable de décision binaire égale à 1 si le routeur d’entrée REi est reconfiguré, 0 sinon. Avec ces notations : - la fonction objectif FOBJ consistant à minimiser le nombre de routeurs d’entrée (ou d’interfaces) à reconfigurer s’exprime : FOBJ : - les 5 contraintes CST1 à CST5 s’expriment : CST1 : CST2 : CST3 : CST4 : CST5 : Dans un mode de réalisation de l’invention, l’optimisation de la fonction objection FOBJ sous le respect des contraintes CST1 à CST5 linéarisées telles que ci-dessus peut par exemple être mise en œuvre par un solveur CPLEX version 12.56 édité par IBM (marque déposée), ou par un solveur CBC (pour Coin-or Branch and Cut en anglais) distribué à l’adresse https://www.coin-or.org/Cbc. Le procédé d’optimisation fournit le préfixe i et les interfaces j (ou routeurs d’entrée REj) pour lesquels le chemin associé à ce préfixe i doit être rallongé. Dans le mode de réalisation décrit ici, et comme mentionné précédemment, l’allongement d’un chemin associé à un préfixe i sur un routeur d’entrée REk (étape E50) comporte : - une reconfiguration de ce routeur en ajoutant au moins un système autonome à un attribut AS-Path du protocole BGP ; et - un envoi dudit attribut aux routeurs de sortie du système autonome amont. Dans le mode de réalisation décrit ici, en référence à la , l’unité d’optimisation OPT a l’architecture matérielle d’un ordinateur. Elle comporte notamment un processeur 10, une mémoire vive 11, une mémoire morte 12 et des moyens de communication 13. La mémoire morte 12 constitue un support d’enregistrement au sens de l’invention. Elle comporte un programme d’ordinateur PG conforme à l’invention. Ce programme d’ordinateur PG comporte des instructions pour exécuter les étapes suivantes lorsque ledit programme est exécuté par un ordinateur. - obtention, du dispositif de collecte DC, d’une information selon laquelle le trafic reçu par un routeur d’entrée d’un premier système autonome est saturé ; - détermination d’un préfixe d’un sous-réseau de destination d’un système autonome en aval dudit premier système autonome ; - envoi d’une instruction pour allonger le chemin associé audit préfixe sur au moins un routeur cible parmi les routeurs d’entrée dudit premier système autonome. Cette instruction peut par exemple être envoyée au contrôleur CTR pour que celui-ci allonge le chemin associé au préfixe i sur un routeur d’entrée du système autonome. Dans un mode de réalisation particulier, le programme d’ordinateur PG met en œuvre le programme linéaire en nombre entier PLNE décrit précédemment pour déterminer le préfixe et les routeurs à reconfigurer. ANNEXE Tableau T1 : p ijt (Gbps) interface j = 1 interface j = 2 interface j = 3 Plage de temps t = 1 préfixe i = 1 p 111 = 3 p 121 =10 p 131 =2 préfixe i = 2 p 211 = 2 p 221 =3 p 231 =5 DT j1 DT 11 = 80 DT 21 = 80 DT 31 = 80 Plage de temps t = 2 préfixe i = 1 p 112 = 6 p 122 =20 P 132 =2 préfixe i = 2 p 212 = 4 p 222 =3 p 232 =5 DT j2 DT 12 = 93 DT 22 = 88 DT 32 = 70 Charge Cj C 1 = 93% C 2 = 88% C 3 = 80% Tableau T2 : p ijt (Gbps) interface j = 1 interface j = 2 interface j = 3 Plage de temps t = 1 préfixe i = 1 p 111 = 0 p 121 =13 p 131 =2 préfixe i = 2 p 211 = 2 p 221 =3 p 231 =5 DT j1 DT 11 = 77 DT 21 = 83 DT 31 = 80 Plage de temps t = 2 préfixe i = 1 p 112 = 0 p 122 =26 P 132 =2 préfixe i = 2 p 212 = 4 p 222 =3 p 232 =5 DT j2 DT 12 = 87 DT 22 = 94 DT 32 = 70 Charge Cj C 1 = 87% C 2 = 94% C 3 = 80% Tableau T3 : p ijt (Gbps) interface j = 1 interface j = 2 interface j = 3 Plage de temps t = 1 préfixe i = 1 p 111 = 0 p 121 =0 p 131 =15 préfixe i = 2 p 211 = 2 p 221 =3 p 231 =5 DT j1 DT 11 = 77 DT 21 = 70 DT 31 = 93 Plage de temps t = 2 préfixe i = 1 p 112 = 0 p 122 =0 P 132 =28 préfixe i = 2 p 212 = 4 p 222 =3 p 232 =5 DT j2 DT 12 = 87 DT 22 = 68 DT 32 = 96 Charge Cj C 1 = 87% C 2 = 70% C 3 = 80% Tableau T4 : p ijt (Gbps) interface j = 1 interface j = 2 interface j = 3 Plage de temps t = 1 préfixe i = 1 p 111 = 3 p 121 =10 p 131 =2 préfixe i = 2 p 211 = 0 p 221 =5 p 231 =5 DT j1 DT 11 = 78 DT 21 = 82 DT 31 = 80 Plage de temps t = 2 préfixe i = 1 p 112 = 6 p 122 =20 P 132 =2 préfixe i = 2 p 212 = 0 p 222 =7 p 232 =5 DT j2 DT 12 = 89 DT 22 = 92 DT 32 = 70 Charge Cj C 1 = 89% C 2 = 92% C 3 = 80% Tableau T5 : p ijt (Gbps) interface j = 1 interface j = 2 interface j = 3 Plage de temps t = 1 préfixe i = 1 p 111 = 3 p 121 =10 p 131 =2 préfixe i = 2 p 211 = 0 p 221 =0 p 231 =10 DT j1 DT 11 = 78 DT 21 = 77 DT 31 = 85 Plage de temps t = 2 préfixe i = 1 p 112 = 6 p 122 =20 P 132 =2 préfixe i = 2 p 212 = 0 p 222 =0 p 232 =12 DT j2 DT 12 = 89 DT 22 = 85 DT 32 = 77 Charge Cj C 1 = 89% C 2 = 85% C 3 = 85% Tableau TD : PAR LON AMS PAR 0 345 km 357 km LON 345 km 0 355 km AMS 357 km 355 km 0 Procédé de configuration d’un premier système autonome (AS2) dans un réseau de transit, ce procédé comportant : - une étape (E20) d’obtention d’une information selon laquelle le trafic reçu par un routeur d’entrée (REj) dudit premier système autonome (AS2) est saturé, ledit trafic étant reçu en provenance d’au moins un routeur de sortie (RSj) d’un deuxième système autonome (AS1) en amont dudit premier système autonome (AS2) ; - une étape (E40) de détermination d’un préfixe (i) d’un sous-réseau de destination (SRDi) d’un troisième système autonome (AS3) en aval dudit premier système autonome (AS2), au moins une partie dudit trafic étant destiné à des équipements dudit sous-réseau de destination (SRDi); - une étape (E50) d’allongement du chemin associé audit préfixe (i) sur au moins un routeur cible (REk) parmi les routeurs d’entrée dudit premier système autonome (AS2) ; ledit préfixe et ledit au moins un routeur cible (REk) étant déterminés en optimisant une fonction objectif (FOBJ) dans le respect d’au moins ces contraintes (CST4, CST3), selon lesquelles : (i) pour tout routeur d’entrée du premier système autonome (AS2), le trafic en entrée dudit routeur est inférieur à un seuil de saturation (c max ) ; et (ii) le chemin associé audit préfixe doit être allongé pour tous les routeurs d’entrée du premier système autonome (AS2) qui sont géographiquement plus proches du routeur saturé (REj) que ledit routeur cible (REk). Procédé de configuration selon la revendication 1, caractérisé en ce que l’allongement (E50) du chemin associé audit préfixe (i) sur au moins un dit routeur cible (REk) comporte : - une reconfiguration d’une table de routage dudit routeur cible (REk) en ajoutant au moins un système autonome à un attribut AS-Path du protocole BGP ; et - un envoi dudit attribut à au moins un routeur de sortie (RS) dudit deuxième système autonome amont (AS1). Procédé de configuration selon la revendication 1 ou 2, caractérisé en ce que l’optimisation de la fonction objectif (FOBJ) consiste à minimiser le nombre de routeurs d’entrée à reconfigurer. Procédé de configuration selon la revendication 1 ou 2, caractérisé en ce que l’optimisation de la fonction objectif (FOBJ) consiste à minimiser le nombre de préfixes dont on rallonge le chemin, ou à minimiser la charge de l’interface la plus chargée. Procédé de configuration selon l’une quelconque des revendications 1 à 4, caractérisé en ce que : - ladite fonction objectif (FOBJ) est une fonction linéaire de la forme : - et en ce que lesdites contraintes s’expriment de façon linéaire sous la forme : CST1 : CST2 : CST3 : CST4 : CST5 : dans lesquelles : - c max est un seuil de saturation et b j est le débit maximal supporté par le routeur saturé (REj) ; - p ijt est un pic de trafic associé au préfixe i sur une interface j au cours d’une plage de temps t ; - Lj est une liste ordonnée des routeurs d’entrée du premier système autonome du plus proche au plus éloigné du routeur saturé (REj) ; - L(j,k) est une sous-liste de Lj comprenant les routeurs d’entrée du premier système autonome (AS2) qui sont géographiquement plus proches du routeur saturé (REj) que ledit routeur cible (REk) ; x ijk est une variable de décision binaire égale à 1 si le trafic associé au préfixe i est routé d’un routeur d’entrée (REj) vers un routeur cible (REk), 0 sinon ; y ij est une variable de décision binaire égale à 1 si le chemin associé au préfixe i est rallongé sur un routeur d’entrée (REj), 0 sinon ; z j est une variable de décision binaire égale à 1 si le routeur d’entrée (REj) est reconfiguré, 0 sinon. Système (100) de configuration d’un premier système autonome (AS2) dans un réseau de transit, ce système comportant : - une unité d’optimisation (OPT) configurée pour obtenir une information selon laquelle le trafic reçu par un routeur d’entrée (REj) d’un premier système autonome (AS2) est saturé, ledit trafic étant reçu en provenance d’au moins un routeur de sortie (RSj) d’un deuxième système autonome (AS1) en amont dudit premier système autonome (AS2) ; - ladite unité (OPT) d’optimisation étant configurée pour déterminer un préfixe d’un sous-réseau de destination (SRDi) d’un troisième système autonome (AS3) en aval dudit premier système autonome (AS2), au moins une partie dudit trafic étant destiné à des équipements dudit sous-réseau de destination (SRDi) ; - une unité (CTR) de contrôle configurée pour allonger le chemin associé audit préfixe sur au moins un routeur cible (REk) parmi les routeurs d’entrée dudit premier système autonome (AS2) ; ledit préfixe et ledit au moins un routeur cible (REk) étant déterminés par ladite unité d’optimisation (OPT) en optimisant une fonction objectif (FOBJ) dans le respect d’au moins ces contraintes (CST4, CST3), selon lesquelles: (i) pour tout routeur d’entrée du premier système autonome (AS2), le trafic en entrée dudit routeur est inférieur à un seuil de saturation (c max ) ; et (ii) le chemin associé audit préfixe (i) doit être allongé pour tous les routeurs d’entrée du premier système autonome (AS2) qui sont géographiquement plus proches du routeur saturé (REj) que ledit routeur cible (REk). Programme d’ordinateur (PG) comportant des instructions pour exécuter les étapes suivantes lorsque ledit programme est exécuté par un ordinateur : - obtention (E20) d’une information selon laquelle le trafic reçu par un routeur d’entrée (REj) d’un premier système autonome (AS2) est saturé, ledit trafic étant reçu en provenance d’au moins un routeur de sortie (RSj) d’un deuxième système autonome (AS1) en amont dudit premier système autonome (AS2) ; - détermination (E20) d’un préfixe d’un sous-réseau de destination (SRDi) d’un troisième système autonome (AS3) en aval dudit premier système autonome (AS2), au moins une partie dudit trafic étant destiné à des équipements dudit sous-réseau de destination (SRDi); - envoi d’une instruction pour allonger le du chemin associé audit préfixe (i) sur au moins un routeur cible (REk) parmi les routeurs d’entrée dudit premier système autonome (AS2) ; ledit préfixe (i) et ledit au moins un routeur cible REk étant déterminés en optimisant une fonction objectif (FOBJ) dans le respect d’au moins ces contraintes (CST4, CST3), selon lesquelles: (i) pour tout routeur d’entrée du premier système autonome (AS2), le trafic en entrée dudit routeur est inférieur à un seuil de saturation (cmax) ; et (ii) le chemin associé audit préfixe (i) doit être allongé pour tous les routeurs d’entrée du premier système autonome (AS2) qui sont géographiquement plus proches du routeur saturé (REj) que ledit routeur cible (REk). Support d’enregistrement lisible par un ordinateur sur lequel est enregistré un programme d’ordinateur (PG) selon la revendication 7.