Brevet FR2911457A1 — publié le 20080718

PROCEDE, PROGRAMME D'ORDINATEUR ET DISPOSITIF DE DETERMINATION D'EVENEMENTS AU SEIN D'UN RESEAU GLOBAL La présente invention concerne le domaine des réseaux de réseaux de communication, typiquement le domaine du réseau de réseaux Internet. Les différents réseaux qui composent Internet sont regroupés au sein d'entités appelées systèmes autonomes (AS). Les AS administrent les différents réseaux et routeurs sous heur responsabilité de manière autonome. Toutefois, afin que les réseaux de différents AS puissent communiquer ensemble, il est nécessaire que les AS s'interconnectent et s'échangent des informations sur les moyens de joindre les réseaux qu'ils hébergent. Une fonctionnalité de routage doit ainsi être mise en place entre les systèmes autonomes. De nos jours, cette fonctionnalité est assurée par le protocole BGP (Border Gateway Protocol). Les différents AS qui composent Internet sont donc interconnectés les uns aux autres au moyen de routeurs spécialisés, qui implémentent le protocole BGP. Deux routeurs BGP communiquent par échange de messages. Chaque message contient l'adresse d'un ou plusieurs réseaux ainsi qu'une séquence de numéros qui identifient les AS à traverser successivement pour joindre ce ou ces réseaux. Un routeur BGP ayant reçu plusieurs messages indiquant des chemins vers un réseau donné, compare ces différents chemins et sélectionne celui qu'il considère le meilleur. Cette sélection se base sur de nombreux critères, notamment sur des critères économiques relatifs à des accords d'interconnexion établis entre un AS et les AS voisins. Un routeur BGP recevant un message indiquant que son meilleur chemin vers un réseau est indisponible ou annonçant un nouveau chemin, meilleur que le précédent, sélectionne un nouveau meilleur chemin vers ce réseau et envoie un message cle mise à jour aux routeurs BGP voisins. Par conséquent, tout événement affectant la structure d'interconnexion des AS (panne sur un lien entre deux routeurs BGP voisins, panne d'un routeur E3GP, modification d'accord d'interconnexion entre AS, panne d'un ou plusieurs réseaux d'un AS, etc.) a pour conséquence l'envoi de nombreux messages de mises à jour à travers le réseau Internet. La figure 1 représente les systèmes autonomes AS1, AS2, AS3, AS4, ASn et des routeurs BGP RI, R2, R3 et R4. A titre d'illustration de l'échange de messages entre routeurs BGP de systèmes autonomes, considérons que le routeur BGP R1 du système autonome AS1 sélectionne un nouveau chemin Chv à destination d'un réseau \/ d'un système autonome ASn. Ce chemin Chv comprend une liste ordonnée d'identifiants des systèmes autonomes à traverser pour atteindre le réseau V. [)ans le cas présent, ce chemin débute par l'identifiant k du système autonome ASk voisin du système autonome AS1, comporte ensuite les identifiants des systèmes autonomes à traverser pour atteindre le système autonome ASn depuis le système autonome ASk et se termine par l'identifiant n du système autonome ASn. Dans un mode de réalisation, le chemin Chv est représenté par la liste des identifiants des systèmes autonomes successivement traversés, avec en tête de liste l'identifiant n du système autonome ASn et en queue de liste l'identifiant k du système autonome Sk. Le routeur BGP R1 du système autonome AS1 envoie alors au routeur E3GP R2 du système autonome AS2 et au routeur BGP R3 du système autonome AS3 un message de misse à jour indiquant un identifiant Idv du réseau V, et le chemin pour atteindre pour atteindre le réseau V. Ce chemin comporte le chemin Chv suivi de l'identifiant 1 du système autonome AS1, soit est représenté par la liste identifiée Chv1. Ensuite, sur réception de ce message de mise à jour, le routeur BGP R3 du système autonome AS3 sélectionne comme meilleur chemin le chemin (Chvl) indiqué par le message reçu pour atteindre le réseau V depuis le routeur R3 et envoie alors au routeur BGP R2 du système autonome AS2 un rnessage de mise à jour indiquant un identifiant Idv du réseau V, et ce meilleur chemin Chvl sélectionné par le routeur R3 pour atteindre le réseau V. Ce chemin comporte le chemin Chvl suivi de l'identifiant 3 du système autonome AS3, soit ChvI3. Le routeur BGP R2 du système autonome AS2 reçoit du routeur R1 et du routeur R3 deux chemins différents pour atteindre le réseau V. Il sélectionne le chemin Chvl parmi ces deux chemins, puis envoie au routeur BGP R4 du système autonome AS4 un message de mise à jour indiquant un identifiant Idv du réseau V, et le chemin pour atteindre pour atteindre le réseau V. Ce chemin comporte le chemin Chv1 suivi de l'identifiant 2 du système autonome AS, soit Chv12. Supposons qu'alors le lien entre les systèmes autonomes voisins AS1 5 et AS2 subisse une défaillance. Le routeur BGP R2 du système autonome AS2 sélectionne le chemin Chv13 et envoie alors au routeur BGP R4 du système autonome AS4 un message de mise à jour indiquant un identifiant Idv du réseau V, et le nouveau chemin pour atteindre pour atteindre le réseau V, qui est le chemin représenté 10 par la liste Chv132. Lorsqu'un événement non désiré affectant la structure d'interconnexion des AS survient (par exemple une rupture de liaison inter AS telle que évoquée ci-dessus), il est nécessaire de détecter cet événement et d'identifier le ou les systèmes autonomes ou lien(s) entre systèmes autonomes voisins sur lequel 15 ou lesquels cet événement est survenu. Cette identification n'est pas aisée puisqu'il n'y a pas de supervision opérationnelle globale du réseau internet, ruais seulement des supervisions par système autonome, voire par réseau compris dans ces systèmes autonomes. Néanmoins, il est souhaitable, pour un fournisseur de services d'un système autonome, d'identifier les incidents 20 survenant dans d'autres systèmes autonomes et affectant les voies de transmissions utilisées par le fournisseur de services. Les opérations de détection et d'identification d'événements sont généralement mises en oeuvre à partir de la collecte des messages de mises à jour reçus au niveau de routeurs BGP et de l'analyse des messages collectés. 25 Le volume des messages à traiter est très important et l'interprétation de ce volume de messages est très complexe. Il existe plusieurs types d'approches pour appréhender le problème de la détection, de l'identification et/ou de la localisation des événements affectant la structure d'interconnexion entre AS. 30 On connaît les approches analytiques (cf. par exemple Locating internet routing instabilities , Anja Feldman et al., http://www.acm.org/sigs/sigcomm/sigcomm2004/papers/p479-feldmann 11.pdf), basées sur les étapes de principe suivantes, étant donné un ensemble de rnessages de mises à jour collectés au niveau de routeurs pendant une certaine période de temps : - partitionner l'ensemble des messages collectés tel que chaque groupe de messages formé contienne les messages résultant d'un même 5 événement ; - localiser au sein de chacun des groupes formés, les systèmes autonomes responsables de l'événement. Une hypothèse considérée dans ces approches analytiques pour l'étape de partitionnement des messages est que des messages qui arrivent à 10 des dates proches sont liés à un même événement. Toutefois, l'analyse de I"arrivée des messages au niveau des routeurs montre que les messages arrivent de manière continue dans le temps. Ce qui varie, c'est le nombre de rnessages reçus par unité de temps. II a donc été proposé d'utiliser des valeurs seuils basées sur la 15 fréquence d'arrivée des messages ou la quantité de messages reçus, afin de définir des périodes de temps telles qu'on considère que les messages qui arrivent pendant chaque période sont la conséquence d'un même événement. Toutefois, ces valeurs seuils ont une incidence directe sur la façon dont sont groupés les messages et donc sur le résultat final de la détermination des 20 événements. De plus, des événements peuvent survenir à des dates proches, ce qu'une telle approche ne peut prendre en compte efficacement. Il existe donc un risque important de regrouper ensemble des messages qui appartiennent à des événements différents ou au contraire de scinder un ensemble de messages liés à un même événement. 25 Par ailleurs, une hypothèse considérée dans ces approches analytiques pour l'étape de localisation des AS responsables d'un événement est que, lorsqu'un événement survient, un routeur peut être amené à élire de nouveaux meilleurs chemins à destination de certains réseaux. On appellera anciens meilleurs chemins, les meilleurs chemins d'un routeur avant la 30 survenue d'un événement et nouveaux meilleurs chemins, ces meilleurs chemins après la survenue de l'événement. Les systèmes autonomes responsables de l'événement se situent sur les anciens ou les nouveaux veilleurs chemins. Dès lors, les systèmes autonomes qui apparaissent dans la rnajorité des chemins sont le plus susceptibles d'être à l'origine de l'événement. Un problème est que l'analyse de l'arrivée des messages au niveau des routeurs montre que, lorsqu'un routeur est amené à élire de nouveaux veilleurs chemins, il peut passer par plusieurs meilleurs chemins temporaires avant de se stabiliser sur un nouveau meilleur chemin. On collecte généralement les messages de mise à jour au niveau de quelques dizaines de routeurs BGP. Par nature du protocole BGP, chacun de ces routeurs, avant de retransmettre un message, ajoute le numéro du système autonome auquel il appartient, en tête du chemin contenu dans le message. Il y a donc un biais de rnesure qui peut influencer l'identification des responsables en défaveur des systèmes autonomes d'où proviennent les messages analysés. Une solution proposée est d'utiliser des valeurs seuils basées sur la fréquence d'arrivée des messages pour déterminer l'ancien et le nouveau veilleur chemin. Une limitation de cette solution est toutefois que rien n'assure qu'un routeur converge de façon similaire (durée de la convergence, nombre d'états transitoires, etc.) pour chaque chemin perturbé par un événement. Des différences de convergence peuvent conduire à identifier de manière erronée des meilleurs chemins stables, ce qui aura une incidence sur l'identification des responsables. De plus une identification uniquement basée sur des considérations quantitatives risque d'identifier majoritairement les systèmes autonomes où sont collectées les données. Par ailleurs, il existe un autre inconvénient inhérent à ce type d'approches, qui réside dans le fait qu'elles ne peuvent permettre la génération d'alertes pertinentes au plus tôt. En effet, comme elles se basent généralement sur des valeurs seuils liées à la fréquence d'arrivée des messages ou au volume de messages reçus, elles nécessitent qu'un événement soit suffisamment installé (réception des nouveaux meilleurs chemins stables , par exemple) avant de pouvoir lever une alarme. Cette alarme a pour effet d'avertir l'AS responsable de l'événement détecté, en vue de sa correction. On connaît également les approches visuelles (cf. par exemple Visualizing Internet routing dynarnics using link rank , Mohit Lad et al., http://www.cs.ucla.edu/ûmohit/cameraReady/LinkRank.pdf), qui représentent visuellement les changements de chemins, c'est-à-dire les conséquences des événements affectant la structure d'interconnexion des AS, sans toutefois déterminer les événements à l'origine de ces changements. Dans le cas où une approche visuelle propose en outre une technique de localisation d'événements, celle-ci est similaire à celles décrites ci-dessus pour les approches analytiques et présente donc les mêmes inconvénients. Ainsi, à l'heure actuelle, les administrateurs des réseaux ne disposent pas de solution leur permettant d'identifier et de diagnostiquer précisément des événements impactant le routage entre systèmes autonomes à partir des messages de mises à jour échangés entre les routeurs BGP à traiter. Ne pouvant identifier les problèmes au moment où ils surviennent, ils se retrouvent souvent contraints d'attendre des plaintes de clients pour pouvoir localiser et régler la panne. Suivant un premier aspect, la présente invention vise à proposer un procédé de détermination d'événements au sein d'un réseau global comprenant une pluralité de réseaux regroupés dans des entités respectives et des modules de cheminement adaptés pour échanger entre eux des messages de mise à jour de cheminement. Un message de mise à jour de cheminement envoyé par un module de cheminement indique un réseau accessible parmi la pluralité de réseaux et un chemin actuellement retenu par le module de cheminement pour atteindre le réseau indiqué. Le chemin comprend une liste ordonnée d'entités. Un procédé selon l'invention comprend les étapes consistant à : - associer, dans une phase préalable, un chemin de référence respectif, dit chemin primaire, à chaque module de cheminement pour chaque réseau accessible par ledit 30 module ; en fonction de messages de mise à jour échangés par les modules de cheminement, déterminer des chemins primaires indisponibles, un chemin primaire étant indisponible lorsque, dans un message envoyé par un module de cheminement, le chemin indiqué comme actuellement retenu par le module de cheminement pour atteindre le réseau indiqué est différent du chemin primaire associé au module de cheminement pour ledit réseau indiqué ; regrouper les chemins primaires indisponibles déterminés en arborescences, des chemins primaires appartenant à une même arborescence lorsqu'ils permettent d'atteindre un ou des réseaux d'une même entité ; pour au moins une arborescence, on calcule l'intersection des chemins primaires indisponibles regroupés dans l'arborescence ; on estime la localisation d'au moins un événement en fonction de ladite intersection calculée. Ainsi selon l'invention, on réalise la détermination des événements en fonction de l'indisponibilité de chemins primaires associés durablement à des modules de cheminement, typiquement des routeurs BGP. On ne considère pas, comme dans l'art antérieur, que lors d'un événement, il y a passage d'une configuration de chemins stables à une autre configuration de chemins stables. Selon l'invention, les anciens chemins stables et les nouveaux chemins stables sont les mêmes et ils correspondent aux chemins primaires. Lorsqu'un message de mise à jour de cheminement indique un changement de chemin par rapport à un chemin primaire associé à un module de cheminement et un réseau de destination, ce message est interprété selon l'invention comme signalant une indisponibilité d'un chemin primaire. L'étude sur de longues périodes (plusieurs mois) des chemins utilisés par des routeurs BGP à destination des différents réseaux de l'Internet, confirme la validité de cette approche. En effet, on constate que chaque routeur possède un chemin préférentiel vers chaque réseau accessible. Ce chemin est celui majoritairement utilisé sur de longues périodes de temps (plusieurs mois). Un événement n'a que des effets temporaires (plus ou moins longs) sur les meilleurs chemins utilisés par un routeur. Selon l'invention, on aborde donc le problème de la détermination des événements en termes d'indisponibilité de chemins primaires et non plus simplement en termes d'arrivée de messages de mise à jour de cheminement. Le problème à résoudre peut donc être reformulé de la manière suivante : étant donné un ensemble de chemins primaires indisponibles à un instant t, détecter les événements à l'origine de ces indisponibilités et localiser ces événements. La légitimité du regroupement des chemins primaires indisponibles selon l'arborescence à laquelle ils appartiennent et du calcul de leur intersection se présentant sous la forme d'un ou plusieurs sous-chemins d'AS est également confirmée par l'étude sur de longues périodes (plusieurs mois) des chemins utilisés par des routeurs à destination des différents réseaux de l'Internet. Cette étude montre qu'un routeur utilise généralement le même chemin primaire pour joindre les réseaux au sein d'un même système autonome. Ce résultat montre que les réseaux au sein d'un même système autonome sont joints de la même manière. Ils sont donc fortement susceptibles d'être victimes des mêmes événements. Réaliser l'intersection des chemins primaires d'une même arborescence conformément à l'invention permet de : - supprimer le biais de mesure explicité précédemment en référence aux approches analytiques. En effet, dés qu'une arborescence contient plus de deux éléments, réaliser l'intersection des chemins primaires contenus dans cette arborescence supprime des sources possibles des événements étudiés, les systèmes autonomes dans lesquels se trouvent les routeurs émettant un message de mise à jour de cheminement. Ces systèmes autonomes ne seront donc pas pris en compte plus que nécessaire. orienter la localisation des systèmes autonomes à l'origine d'un ou d'événements observés. Supposons qu'un événement survienne au niveau d'un système autonome ASx. Cet événement va rendre indisponible plusieurs chemins primaires, notamment des chemins primaires à destination des réseaux au sein du système autonome ASx. L'arborescence associée à ASx contiendra vraisemblablement de nombreux chemins primaires indisponibles et l'intersection de ces chemins primaires sera vraisemblablement de faible longueur (idéalement l'intersection ne devrait contenir que le système autonome ASx). En outre, le fait de n'exploiter que les messages indiquant les débuts d'indisponibilité des chemins primaires, ainsi que les fins d'indisponibilité des chemins primaires (et non les messages retraçant les différents changements de chemins sur la période d'indisponibilité) permet de diminuer de manière importante le nombre de données à manipuler, ce qui est très important pour pouvoir effectuer un traitement en temps réel d'un événement. En outre, le fait d'estimer la localisation d'événements sur les 10 intersections de chemins primaires permet là encore de réduire considérablement le volume de données à traiter. De plus, la solution proposée exempte d'utiliser des valeurs seuils arbitraires. La solution proposée permet donc de lever les limitations majeures des 15 approches antérieures discutées plus haut. Là où les approches antérieures suivaient un raisonnement grouper les messages puis analyser , l'invention propose d'analyser les messages au fur et à mesure de leur arrivée et de lever une alarme dès qu'un événement est identifié. La technique développée permet donc de générer des alarmes 20 pertinentes au plus tôt. Dans un mode de réalisation, les modules de cheminement échangent des messages conformément au protocole BGP. En effet, le procédé est particulièrement adapté au cas des échanges BGP, puisqu'il permet de réduire considérablement le nombre de données à traiter, qui est très important dans le 25 cas BGP. Dans un mode de réalisation, pour chaque arborescence regroupant des chemins primaires indisponibles, on calcule l'intersection desdits chemins primaires indisponibles et on estime la localisation d'au moins un événement en fonction des intersections respectives calculées. A ce stade, on peut alors 30 expliquer toutes les indisponibilités observées en considérant qu'il y avait eu autant d'événements que d'arborescences, le présent procédé permettant d'estimer la localisation de chacun de ces événements. Cette disposition permet en outre de faciliter la distinction d'événements différents qui apparaissent à des dates proches, par rapport à l'art antérieur. En effet, supposons que deux événements surviennent à des dates proches, l'un sur le système autonome ASx, l'autre sur le système autonome ASy. On s'attend à ce que les intersections des chemins primaires indisponibles contenus dans l'arborescence d'AS ASx et dans l'arborescence d'AS ASy soient de petites tailles. La probabilité que les deux intersections obtenues possèdent des systèmes autonomes AS en commun est donc faible. La probabilité de détermination de deux événements disjoints est par conséquent importante. Dans un mode de réalisation, on compare entre elles les intersections calculées pour les arborescences respectives en vue d'estimer si l'indisponibilité des chemins primaires de plusieurs arborescences est explicable par un même événement. Cette étape permet donc de préciser la détermination des événements. Dans un mode de réalisation, la phase de comparaison des intersections comprend une étape selon laquelle on considère que les événements ont lieu uniquement au niveau de liaisons entre entités voisines. Cette étape est particulièrement efficace car les problèmes affectant les liaisons entre les entités, typiquement les liaisons entre les systèmes autonomes, sont ceux rencontrés en pratique le plus fréquemment. Dans un mode de réalisation, la phase de comparaison des intersections comprend une étape selon laquelle on considère que les événements ont lieu uniquement au niveau des entités et non au niveau des liaisons entre entités. Effectuer cette étape à la suite de l'étape indiquée précédemment permet de préciser encore la détermination d'un événement. Dans un mode de réalisation, une décision de générer une alarme relative à un événement dont la localisation a été estimée est prise en fonction d'au moins une probabilité de collecter ultérieurement des messages de mise à jour annonçant l'indisponibilité de chemins primaires dans une arborescence comprenant des chemins primaires indisponibles du fait dudit événement, étant donné le nombre de chemins primaires déjà indisponibles pour cette arborescence et la durée depuis la dernière réception d'un message indiquant l'indisponibilité d'un chemin primaire pour cette arborescence. Cette disposition permet de définir le moment au plus tôt pour générer une alarme afin de résoudre l'événement tout en disposant des meilleures informations possibles de détermination de l'événement. Ainsi une alarme est générée dès que l'on détermine qu'on ne peut pas avoir de meilleure identification de l'événement, même en recevant encore des messages, ou dès qu'il devient peu probable que l'on reçoive de nouveaux messages liés à cet événement (i.e. on ne dispose éventuellement que d'une identification incomplète de l'événement, mais il est peu probable que des messages à venir permettent de préciser l'identification). Suivant un deuxième aspect, l'invention propose un programme d'ordinateur à installer dans un dispositif de détermination d'événements au sein d'un réseau global comprenant une pluralité de réseaux regroupés dans des entités respectives et des modules de cheminement adaptés pour échanger entre eux des messages de mise à jour de cheminement, un message de mise à jour de cheminement envoyé par un module de cheminement indiquant un réseau accessible parmi la pluralité de réseaux et un chemin actuellement retenu par le module de cheminement pour atteindre le réseau indiqué et comprenant une liste ordonnée d'entités, ledit programme comprenant des instructions pour mettre en oeuvre les étapes qui incombent au dispositif, d'un procédé suivant le premier aspect de l'invention lors d'une exécution du programme par des moyens de traitement dudit dispositif. Suivant un troisième aspect, l'invention propose un dispositif de détermination d'événements au sein d'un réseau global comprenant une pluralité de réseaux regroupés dans des entités respectives et des modules de cheminement adaptés pour échanger entre eux des messages de mise à jour de cheminement. Un message de mise à jour de cheminement envoyé par un module de cheminement indique un réseau accessible parmi la pluralité de réseaux et un chemin actuellement retenu par le module de cheminement pour atteindre le réseau indiqué et comprenant une liste ordonnée d'entités. Un chemin de référence respectif, dit chemin primaire, a été associé dans une phase préalable, à chaque module de cheminement pour chaque réseau accessible par ledit module. Un dispositif selon l'invention comprend les moyens suivants : des moyens pour, en fonction de messages de mise à jour échangés par les modules de cheminement, déterminer des chemins primaires indisponibles, un chemin primaire étant indisponible lorsque, dans un message envoyé par un module de cheminement, le chemin indiqué comme actuellement retenu par le module de cheminement pour atteindre le réseau indiqué est différent du chemin primaire associé au module de cheminement pour ledit réseau indiqué ; des moyens pour regrouper les chemins primaires indisponibles déterminés en arborescences, des chemins primaires appartenant à une même arborescence lorsqu'ils permettent d'atteindre un ou des réseaux d'une même entité ; des moyens pour, pour au moins une arborescence, calculer l'intersection des chemins primaires indisponibles regroupés dans l'arborescence ; 20 des moyens pour estimer la localisation d'au moins un événement en fonction de ladite intersection calculée. D'autres caractéristiques et avantages de l'invention apparaîtront encore à la lecture de la description qui va suivre. Celle--ci est purement illustrative et doit être lue en regard des dessins annexés sur lesquels : 25 la figure 2 représente un système mettant en oeuvre l'invention dans un mode de réalisation ; - la figure 3 est un organigramme d'étapes d'un procédé dans un mode de mise en oeuvre de l'invention. Considérons, en référence à la figure 2, une partie 1 du réseau Internet 30 comportant une pluralité de systèmes autonomes S1,...,Sn au sein desquels figurent des réseaux de communication respectifs. 10 15 Dans cette partie de réseau Internet, des routeurs r1,..., rn implémentant le protocole BGP communiquent de proche en proche par échange de messages de mise à jour de cheminement. Chaque message contient l'adresse d'un ou plusieurs réseaux ainsi qu'un chemin qui identifie les systèmes autonomes à traverser successivement pour joindre chacun de ces réseaux. Un certain nombre de routeurs parmi les routeurs r1 à rn, sont télésurveillés, permettant la collecte des messages de mise à jour de cheminement émis par ces routeurs. Ces routeurs sont par exemple les routeurs r1 à rp, avec (avec p Pour chaque système autonome Sx (x entier de 1 à n), on appelle Arbo(Sx), l'ensemble des chemins primaires indisponibles à destination de réseaux appartenant au système autonome Sx. Arbo(Sx) est donc un sous-ensemble de l'arborescence associée au système autonome Sx. Ces ensembles et leurs contenus sont mémorisés dans la mémoire 11 du module de surveillance 12 et sont réactualisés par le module de traitement 12. Selon les opérations réalisées lors de l'exécution du sous-bloc algorithmique B1 sur des moyens de calcul du module de traitement 12, à chaque réception d'un message annonçant l'indisponibilité d'un chemin primaire c à destination d'un réseau au sein du système autonome Sx, le module de traitement 12 du dispositif de surveillance 10 ajoute c à Arbo(Sx) s'il n'en faisait pas déjà partie. A chaque réception d'un message annonçant la fin de l'indisponibilité d'un chemin primaire c à destination d'un réseau au sein du :système autonome Sx, le module de traitement 12 du dispositif de surveillance retire c de Arbo(Sx). Puis, à l'aide du deuxième sous- bloc algorithmique B2, le module de traitement 12 calcule pour chaque arborescence contenant des chemins primaires indisponibles (ie chaque arborescence d'un système autonome Sx tel 10 que Arbo(Sx) n'est pas vide), l'intersection des chemins primaires indisponibles appartenant à cette arborescence (étape e/). Cette intersection se présente sous la forme d'un ou plusieurs sous-chemins reliant des systèmes autonomes voisins. On appelle Inter(Sx) pour x entier de 1 à n, l'ensemble contenant le résultat de l'intersection des chemins présents dans Arbo(Sx). Inter(Sx) comporte donc un ou plusieurs systèmes autonomes, et/ou un ou plusieurs tronçons, dits sous-chemins, de chemins primaires de Arbo(Sx). Un sous-chemin correspond donc à une liste ordonnée de systèmes autonomes telle que deux systèmes autonomes successifs de la liste sont reliés par un lien. On appelle Arcs(Sx), l'ensemble de couples de systèmes autonomes voisins obtenus en décomposant chaque sous-chemin de Inter(Sx) en couples de systèmes autonomes voisins. Soit un chemin primaire ou sous-chemin d'un chemin primaire c, on appelle longueur(c), la longueur en nombre de systèmes autonomes du chemin c. Soit un couple de systèmes autonomes (Sx, Sy), on appellera poids(Sx, Sy), une valeur entière représentant le nombre de chemins primaires dont l'indisponibilité peut être expliquée par un événement localisé au niveau du couple (Sx, Sy). Le sous-bloc algorithmique B2 comprend des instructions mettant en oeuvre les opérations suivantes lors d'une exécution du sous-bloc B2 par des moyens de calcul du module de traitement 12. Pour chaque arborescence Arbo(Sx) telle que le contenu de Arbo(Sx) est non nul : - on calcule Inter(Sx), l'intersection des éléments de Arbo(Sx) (Inter(Sx) est un ensemble de sous-chemins entre systèmes autonomes) ; -on détermine Arcs(Sx), l'ensemble de couples de systèmes autonomes obtenus en décomposant les sous-chemins de Inter(Sx) en couples ; - puis dans un mode de réalisation de l'invention, on calcule prob(Sx) , la probabilité de recevoir ultérieurement des messages annonçant l'indisponibilité de chemins primaires de l'arborescence associée à Sx (soit l'ajout de nouveaux éléments dans Arbo(Sx)) ; - pour chaque élément c de Inter(Sx) : ù> si la longueur(c) est égale à 1 (i.e. le contenu de Inter(Sx) est un système autonome) : - on construit le couple (c, c) et on affecte au poids (c,c) la valeur du cardinal de l'ensemble Arbo(Sx), soit poids(c,c) = lArbo(Sx) ; et - on ajoute (c, c) à Arcs(Sx) ; ù> si la longueur(c) est différente de 1 : - on construit les couples (Sy, Sz) où Sy et Sz sont deux systèmes autonomes consécutifs de l'élément c et on affecte au poids(Sy,Sz) la valeur du cardinal de l'ensemble Arbo(Sx), soit poids(Sy,Sz) = lArbo(Sx)l ; - on ajoute (Sy, Sz) à Arcs(Sx). Ainsi, après avoir effectué le calcul des intersections des chemins primaires explicité ci-dessus, on décompose chaque ensemble Arbo(Sx) en un ensemble de couples de systèmes autonomes Inter(Sx). A ce stade, on peut donc expliquer l'indisponibilité des chemins primaires compris dans une arborescence en considérant que ces chemins ont été victimes du même événement. Et on a déterminé que cet événement a pu avoir lieu sur un quelconque des chemins de Inter(Sx). A ce stade, on a donc pu expliquer toutes les indisponibilités observées, en considérant qu'il y a eu autant d'événements que d'arborescences comportant des chemins indisponibles. L'étape suivante (étape fi) consiste à comparer les différents ensembles Inter(Sx) obtenus, afin d'estimer si l'indisponibilité des chemins primaires de plusieurs arborescences peut être expliquée par un seul et même événement. Pour ce faire, on utilise, dans le cas considéré, les sous-blocs algorithmiques B3 et B4. Le sous-bloc algorithmique B3 tente d'abord d'expliquer toutes les indisponibilités uniquement au moyen d'événements ayant eu lieu sur des arcs (liens entre deux systèmes autonomes voisins). Le sous-bloc algorithmique B4 est appliqué dans l'exemple considéré à la suite du sous-bloc algorithmique B3 pour essayer d'améliorer le résultat obtenu en fusionnant certains arcs, c'est à dire en localisant les événements au niveau de systèmes autonomes eux-mêmes et non plus d'arcs reliant deux systèmes autonomes. On appelle Arborescence_l l'ensemble des différentes arborescences 15 comportant des chemins primaires indisponibles et associées à des systèmes autonomes. On appelle Expliqués(Sx,Sy) l'ensemble comprenant des systèmes autonomes tel que, pour tout système autonome St de cet ensemble Expliqués(Sx,Sy), l'indisponibilité des chemins primaires dans l'arborescence 20 associée au système autonome St (ie l'indisponibilité des chemins primaires pour atteindre un réseau dans ce système autonome) est due à un événement ayant eu lieu sur l'arc reliant le système autonome Sx au système autonome voisin Sy. A l'étape d'initialisation du sous-bloc algorithmique B3, 25 Expliqués(Sx,Sy) est fixé égal à 0, quel que soit (Sx, Sy). On appelle Equivalents(Sx,Sy) l'ensemble comprenant des arcs reliant cieux systèmes autonomes voisins Sx, Sy (c'est donc l'ensemble des couples (Sx, Sy)) tels qu'un événement survenu sur tout arc de cet ensemble impacte les mêmes arborescences qu'un événement survenu sur l'arc (Sx,Sy). 30 A l'étape d'initialisation du sous-bloc algorithmique B3, Equivalents(Sx,Sy) est fixé égal à 0, quel que soit (Sx, Sy). On appelle Resultattmp, l'ensemble des couples (Equivalents, Expliqués) obtenus à la fin du bloc algorithmique B3. Cet ensemble de couples (Equivalents, Expliqués) vise l'explication des différentes observations à partir d'événements ayant eu lieu au niveau d'arcs seulement. A l'étape d'initialisation du l'iinitialisation de l'algorithme B3, Resultattmp est fixé égal à (0, 0). Le sous-bloc algorithmique B3 mis en oeuvre par le module de traitement 12 comprend des instructions mettant en oeuvre les opérations suivantes lors d'une exécution du sous-bloc B3 par des moyens de calcul du module de traitement 12. Tant que Arborescences _1 n'est pas vide, répéter les opérations suivantes : -. Identifier Arbo(Sx) telle que Arbo(Sx)l = Maxsy cArborescence_I IArbo(Sy)I -. Pour chaque couple (Su, Sv) de Ares(Sx) : -Pour chaque Arbo (Sy) e Arborescences_l : - Si (Su, Sv) e Arcs(Sy), alors on ajoute au poids(Su, Sv) le cardinal de l'ensemble Arbo(Sy) et on ajoute le système autonome Sy à l'ensemble Expliqués(Su, Sv). - Identifier (Sa, Sb) l'élément de Arcs(Sx) tel que le poids(Sa, Sb) = MaX(Su,sv)eAres(sx))poids(SU, SV). - Pour chaque élément (Su, Sv) de Ares(Sx) : - Si l'ensemble Expliqués(Su, Sv) est égal à l'ensemble Expliqués(Sa, Sb), alors on ajoute à l'ensemble Equivalent(Sa, Sb) le couple (Su, Sv). - On ajoute alors le couple (Equivalents(Sa, Sb), Expliqués(Sa, Sb)) à l'ensemble des couples Resultattmp. - Puis pour chaque système autonome Su indiqué dans Expliqués(Sa, Sb), on 25 retire Arbo(Su) de Arborescences On obtient ainsi, après l'exécution du sousbloc algorithmique B3, par événement détecté, un couple (Equivalents, Expliqués) où Expliqués représente l'ensemble des arborescences (les arborescences associés aux systèmes autonomes éléments de l'ensemble Expliqués) dont l'indisponibilité 30 des chemins primaires est considérée comme due à l'événement détecté et où Equivalents représente l'ensemble des éléments de topologies (liens entre systèmes autonomes) considérés pouvant être, à probabilité égale, à l'origine de l'événement détecté. A ce stade, on a ainsi expliqué les différentes indisponibilités de chemins primaires à partir d'événements localisés sur des arcs entre deux systèmes autonomes. Le sous-bloc algorithmique B4 mis en oeuvre par le module de traitement 12 comprend des instructions mettant en oeuvre les opérations indiquées ci-dessous lors d'une exécution du sous-bloc B4 par des moyens de calcul du module de traitement 12. On appelle Resultatfinal, l'ensemble des couples (Equivalents, Expliques) obtenus à la fin du bloc algorithmique B4, qui vise l'amélioration du résultat de détermination d'événements obtenu par le sous-bloc B3 en fusionnant certains arcs. On affecte la valeur initiale o à l'ensemble Résultatf;nal. On appelle Expliqués(Sx) l'ensemble comprenant des systèmes autonomes tel que, pour tout système autonome St de cet ensemble Expliqués(Sx), l'indisponibilité des chemins primaires dans l'arborescence associée au système autonome St (ie l'indisponibilité des chemins primaires pour atteindre un réseau dans ce système autonome) est due à un événement ayant eu lieu sur le système autonome Sx. Expliqués(Sx) est initialisé à o lors de l'initialisation du sous-bloc algorithmique B4. On affecte la valeur initiale 0 aux poids associés au système autonome Sx, x entier de 1 à 1 soit poids(Sx) = 0 ; Selon B4, tant que l'ensemble Resultattmp n'est pas vide, répéter les opérations suivantes : -• on affecte à la valeur o à un ensemble Noeuds (destiné à contenir des systèmes autonomes) ; -, on identifie le couple (Equivalents(Sa, Sb), Expliqués(Sa, Sb)), élément de Resultattmp, tel que poids(Sa, Sb) = MaxEqujvaIents(su,sv) c Resultattmp poids(Su,Sv). - Pour chaque couple (Su, Sv) de l'ensemble Equivalents(Sa, Sb) : - on ajouter Su et Sv à l'ensemble Noeuds ; - Puis pour chaque élément Su de l'ensemble Noeuds : - pour chaque élément (Equivalents(Su',Sv'), Expliqués(Su',Sv')) de Resultattmp: ù* si Su appartient à au moins un couple de Equivalents(Su',Sv') : - on ajoute au poids(Su) le poids(Su,Sv') ; - on ajoute à l'ensemble Expliqués(Su) le contenu de l'ensemble Expliqués(Su',Sv') ; - on marque (Equivalents(Su',Sv'), Expliqués(Su', Sv')) ; .- on identifie ensuite l'élément Sc de l'ensemble Noeuds tel que poids(ASc) = IMaXSu e Noeuds poids(Su) ; -- si l'ensemble Expliqués(Sc) = Expliqués(Sa,Sb) (cela signifie que la décomposition en noeuds ne permet pas d'expliquer plus d'indisponibilités de chemin primaire dues à un même événement) : - on ajoute à l'ensemble Résultatf;nal le couple (Equivalents(Sa, Sb), Expliqués(Sa, Sb)) ; - on retire (Equivalents(Sa, Sb), Expliqués(Sa, Sb)) de l'ensemble Resultattmp ; -. si l'ensemble Expliqués(Sc) # Expkqués(Sa,Sb) (la décomposition en noeuds permet d'expliquer plus d'indisponibilités de chemins primaires) : - pour chaque élément Su de l'ensemble Noeuds : Si Expliqués(Su) = Expliqués(Sc), alors on ajoute à l'ensemble Equivalents(Sc) le système autonome Su ; - puis on ajoute à l'ensemble Resultatfinal le couple (Equivalents (Sc), Expliqués (ASc)) ; et pour chaque élément (Equivalents(Su, Sv), Expliqués(Su, Sv)) marqué de Resultattmp : - on retire (Equivalents(Su, Sv), Expliqués (Su, Sv)) de Resultattmp. On obtient ainsi un couple (Equivalents, Expliqués) par événement détecté où Expliqués représente l'ensemble des arborescences dont l'indisponibilité des chemins primaires est considérée comme due à l'événement détecté et où Equivalents représente l'ensemble des éléments de topologies (liens entre systèmes autonomes et systèmes autonomes) considérés pouvant être à l'origine de l'événement détecté, à probabilité égale. Dans un mode de réalisation, le module de traitement 12 est adapté pour déterminer dans une étape g/, de générer ou non, une alarme relative à un événement détecté, en vue d'indiquer à un centre de maintenance d'un système autonome, qu'un événement a eu lieu sur le système autonome ou sur un lien entre ce système autonome et un système autonome voisin, suite à la localisation déterminée selon le procédé décrit ci-dessus de l'événement (c'est-à-dire que le système autonore, ou un lien entre ce système autonome et son voisin a été identifié dans un ensemble Equivalents d'un couple de l'ensemble Résultatfinal)• Pour cela, une étape de décision, basée par exemple sur une inférence bayésienne, est utilisée pour générer une alarme dès que l'on constate que l'on ne peut pas avoir de meilleure identification de l'événement même en recevant encore des messages ou dès qu'il devient peu probable que des messages à venir permettent de préciser l'identification. Cette décision est effectuée en fonction de la probabilité de recevoir des messages indiquant l'indisponibilité de chemins primaires pour une arborescence donnée, étant donné le nombre de chemins primaires déjà indisponibles pour cette arborescence et la durée depuis la dernière réception d'un message indiquant l'indisponibilité d'un chemin primaire pour cette arborescence. Le sous-bloc algorithmique B5 mis en oeuvre par le module de traitement 12 comprend des instructions mettant en oeuvre les opérations indiquées ci-dessous lors d'une exécution du sous-bloc B5 par des moyens de calcul du module de traitement 12 : - pour chaque couple (Equivalents, Expliqués) de Resultatf;nal (chacun de ces couples correspondant donc à un événement distinct) : - on calcule la probabilité de pouvoir préciser cet événement, en fonction des prob(Sx), fournies par le sous-bloc algorithmique B2, des éléments Sx de l'ensemble Expliqués; - si cette probabilité est faible (par exemple si elle est inférieure à une valeur seuil de 5%), on génère une alarme pour cet événement et on retire le couple (Equivalents, Expliqués) de Resultat final. Ainsi une solution de détermination d'événements selon l'invention permet de détecter, d'identifier et de localiser des événements au sein d'un réseau global comprenant plusieurs réseaux qui sont exploités sans unité. La détermination des événements selon l'invention est effectuée sans utiliser de valeurs seuils arbitraires qui peuvent fausser les résultats. En outre, les événements peuvent être déterminés en temps réel, au fil de l'arrivée des messages de mise à jour du cheminement. Les messages ne doivent pas être d'abord groupés avant d'effectuer les calculs. La solution selon l'invention permet de réduire considérablement la puissance de calcul nécessaire, puisqu'on réduit le nombre de messages considérés et puisqu'on limite les données manipulées aux données concernant les intersections de chemins primaires indisponibles au sein des arborescences. La solution permet ainsi une réactivité accrue lors de pannes : les exploitants du réseau pourront diagnostiquer plus rapidement et plus efficacement les pannes, sans être obligés d'attendre les plaintes des clients. Hormis la détection de pannes, les exploitants du réseau pourront également isoler des problèmes récurrents, mais non cruciaux, qui affectent la qualité du service offert à un ou quelques clients en particulier. Ces phénomènes sont aujourd'hui masqués par le flot des messages reçus. A plus long terme, les résultats fournis par cette invention, permettront d'obtenir une meilleure compréhension du routage BGP. On pourra notamment identifier les motifs d'interconnexion "à problèmes" qui impactent les performances du routage. Cela permettra d'optimiser le routage en corrigeant la structure d'interconnexion existante, mais aussi d'anticiper et donc d'éviter des problèmes lors d'une restructuration partielle d'un réseau ou lors de la création d'un nouveau réseau. L'invention permet également une évaluation des systèmes autonomes. En identifiant les systèmes autonomes les plus fréquemment à l'origine d'événements ayant perturbés le routage, il pourra être décidé le cas échéant de proscrire les routes passant par ces systèmes autonomes et dans le cas de systèmes autonomes voisins il pourra être décidé de reconsidérer les rnodalités de l'accord d'interconnexion passé avec lui. L'invention a été décrite ci-dessus en référence au protocole BGP utilisé entre les routeurs des systèmes autonomes de l'internet. Néanmoins, l'invention est applicable à des messages révélateurs de modifications de chemins émis selon tout autre protocole de communication. Dans un mode de réalisation, des alarmes et autres mesures pour corriger les événements peuvent être prises dès qu'une intersection de chemins primaires a été calculée pour au moins une arborescence, l'événement affectant cette arborescence étant alors localisé sur cette intersection (les étapes effectuées ultérieurement permettant d'affiner si nécessaire le diagnostic, en identifiant précisément l'événement comme provenant d'une liaison entre deux systèmes autonomes ou d'un système autonome lui-même). Les algorithmes utilisés ci-dessus pour déterminer la localisation à partir des intersections de chemins primaires calculés ont été décrits à titre d'exemples. D'autres méthodes peuvent bien sûr être utilisées. REVENDICATIONS 1. Procédé de détermination d'événements au sein d'un réseau global comprenant une pluralité de réseaux regroupés dans des entités respectives (S1,..., Sn) et des modules de cheminement (ri, ...,rp) adaptés pour échanger entre eux des messages de mise à jour de cheminement, un message de mise à jour de cheminement envoyé par un module de cheminement indiquant un réseau accessible parmi la pluralité de réseaux et un chemin actuellement retenu par le module de cheminement pour atteindre le réseau indiqué et comprenant une liste ordonnée d'entités, ledit procédé comprenant les étapes consistant à : associer, dans une phase préalable, un chemin de référence respectif, dit chemin primaire, à chaque module de cheminement pour chaque réseau accessible par ledit module ; en fonction de messages de mise à jour échangés par les modules de cheminement, déterminer des chemins primaires indisponibles, un chemin primaire étant indisponible lorsque, dans un message envoyé par un module de cheminement, le chemin indiqué comme actuellement retenu par le module de cheminement pour atteindre le réseau indiqué est différent du chemin primaire associé au module de cheminement pour ledit réseau indiqué ; regrouper les chemins primaires indisponibles déterminés en arborescences, des chemins primaires appartenant à une même arborescence lorsqu'ils permettent d'atteindre un ou des réseaux d'une même entité ; pour au moins une arborescence, calculer l'intersection des chemins primaires indisponibles regroupés dans l'arborescence ; 20 25estimer la localisation d'au moins un événement en fonction de ladite intersection calculée. 2. Procédé selon la revendication 1, selon lequel, les modules de cheminement (ri, ...,rn) échangent des messages conformément au protocole BGP. 3. Procédé selon la revendication 1 ou la revendication 2, selon lequel pour chaque arborescence regroupant des chemins primaires indisponibles, on calcule l'intersection desdits chemins primaires indisponibles et on estime la localisation d'au moins un événement en fonction desdites intersections respectives calculées. 4. Procédé la revendication 3, selon lequel on compare entre elles les intersections calculées pour les arborescences respectives en vue d'estimer si l'indisponibilité des chemins primaires de plusieurs arborescences est explicable par un même événement. 5. Procédé selon la revendication 4, selon lequel la phase de comparaison des intersections comprend une étape selon laquelle on considère que les événements ont lieu uniquement au niveau de liaisons entre entités. 6. Procédé selon la revendication selon la revendication 4 ou la revendication 5, selon lequel la phase de comparaison des intersections comprend une étape selon laquelle on considère que les événements ont lieu uniquement au niveau des entités et non au niveau des liaisons entre entités. 7. Procédé selon l'une des revendications précédentes, selon lequel une décision de générer une alarme relative à un événement dont la localisation a été estimée est prise en fonction d'au moins une probabilité de collecterultérieurement des messages de mise à jour annonçant l'indisponibilité de chemins primaires dans une arborescence comprenant des chemins primaires indisponibles du fait dudit événement, étant donné le nombre de chemins primaires déjà indisponibles pour cette arborescence et la durée depuis la dernière réception d'un message indiquant l'indisponibilité d'un chemin primaire pour cette arborescence. 8. Programme d'ordinateur à installer dans un dispositif de détermination d'événements (10) au sein d'un réseau global comprenant une pluralité de réseaux regroupés dans des entités respectives (S1,..., Sn) et des modules de cheminement (ri, ...,rp) adaptés pour échanger entre eux des messages de mise à jour de cheminement, un message de mise à jour de cheminement envoyé par un module de cheminement indiquant un réseau accessible parmi la pluralité de réseaux et un chemin actuellement retenu par le module de cheminement pour atteindre le réseau indiqué et comprenant une liste ordonnée d'entités, ledit programme comprenant des instructions pour mettre en oeuvre les étapes qui incombent au dispositif, d'un procédé selon l'une des revendications précédentes lors d'une exécution du programme par des moyens de traitement dudit dispositif. 9. Dispositif (10) de détermination d'événements au sein d'un réseau global comprenant une pluralité de réseaux regroupés dans des entités respectives (Si,..., Sn) et des modules de cheminement (ri, .,rp) adaptés pour échanger entre eux des messages de mise à jour de cheminement, un message de mise à jour de cheminement envoyé par un module de cheminement indiquant un réseau accessible parmi la pluralité de réseaux et un chemin actuellement retenu par le module de cheminement pour atteindre le réseau indiqué et comprenant une liste ordonnée d'entités, un chemin de référence respectif, dit chemin primaire, ayant été associé 30 dans une phase préalable, à chaque module de cheminement pour chaque réseau accessible par ledit module ; 5 10 15ledit dispositif comprenant les moyens suivants : des moyens pour, en fonction de messages de mise à jour échangés par les modules de cheminement, déterminer des chemins primaires indisponibles, un chemin primaire étant indisponible lorsque, dans un message envoyé par un module de cheminement, le chemin indiqué comme actuellement retenu par le module de cheminement pour atteindre le réseau indiqué est différent du chemin primaire associé au module de cheminement pour ledit réseau indiqué ; des moyens pour regrouper les chemins primaires indisponibles déterminés en arborescences, des chemins primaires appartenant à une même arborescence lorsqu'ils permettent d'atteindre un ou des réseaux d'une même entité ; des moyens pour, pour au moins une arborescence, calculer l'intersection des chemins primaires indisponibles regroupés dans l'arborescence ; des moyens pour estimer la localisation d'au moins un événement en fonction de ladite intersection calculée...DA1: 20080718