Brevet FR3044849A1 (20170609)
REVENDICATIONS1. Procédé de détermination d'un point de terminaison d'au moins un tunnel ou segment de tunnel, dans un réseau à commutation de paquets, le réseau comprenant un ensemble de routeurs (A, B, C, D, E, F, G) et des liens entre eux, chaque lien ayant un coût associé, l'ensemble de routeurs et les liens formant une topologie du réseau dite antérieure, un routeur de transit (RTR) compris dans l'ensemble recevant des paquets destinés à un routeur de sortie (RSO) compris dans l'ensemble, un événement modifiant (E2) la topologie antérieure en une topologie du réseau dite postérieure, un chemin de secours entre le routeur de transit et le routeur de sortie étant calculé (E3) pour les paquets sur la base de la topologie postérieure, le procédé comprenant l'étape (El) suivante, antérieure à l'événement : - pour chacun des routeurs de l'ensemble, calcul d'un arbre dit initial (SPT(A), SPT(B), SPT(C), SPT(D), SPT(E), SPT(F), SPT(G)), sur la base de la topologie antérieure, ledit arbre initial ayant pour racine ledit chacun des routeurs et ayant pour branches des chemins de coût minimum entre la racine et les autres routeurs de l'ensemble, le procédé comprenant en outre au moins un cycle des étapes suivantes, postérieures à l'événement : - sélection (E4, E7) d'un routeur sur le chemin de secours, dit routeur de début (RDE(c=1), RDE(c=2)), - à partir du routeur de début, vers le routeur de sortie le long du chemin de secours, identification (E5) d'un routeur, dit dernier routeur commun (DRCO(c=1), DRCO(c=2)), pour lequel tous les liens et routeurs y compris lui-même, entre le routeur de début et lui-même, sont communs au chemin de secours et à l'arbre initial associé au routeur de début, et, si ce dernier routeur commun est différent du routeur de début, - détermination (E6) du point de terminaison du tunnel ou segment de tunnel 3044849 26 comme étant le dernier routeur commun identifié, le tunnel ou segment de tunnel étant destiné à éviter aux paquets transitant entre le routeur de début et le dernier routeur commun identifié d'entrer dans une micro-boucle causée par l'événement. 5\n<CLM>\1\tProcédé de détermination selon la revendication 1, où le chemin de secours est de coût minimum.\n<CLM>\1\tProcédé de détermination selon l'une des revendications 1 ou 2, où le routeur de 10 début sélectionné lors du premier cycle est le routeur de transit.\n<CLM>\1\tProcédé de détermination selon l'une des revendications 1 ou 2, où le routeur de début sélectionné lors du premier cycle est un routeur adjacent au routeur de transit sur le chemin de secours. 15\n<CLM>\1\tProcédé de détermination selon l'une des revendications précédentes, où le routeur de début sélectionné est le point de terminaison déterminé lors du cycle précédent, si le cycle n'est pas le premier. 20\n<CLM>\1\tProcédé de détermination selon l'une des revendications précédentes, où, si le dernier routeur commun identifié est le routeur de début, alors le point de terminaison est déterminé comme étant le routeur adjacent au routeur de début sur le chemin de secours, vers le routeur de sortie. 25\n<CLM>\1\tProcédé de détermination selon l'une des revendications précédentes, comprenant en outre une étape (E8) d'ajout où, pour chaque point de terminaison déterminé lors d'un cycle, une instruction est ajoutée à une table de commutation, l'instruction étant une instruction d'encapsulation des paquets à destination du routeur de sortie dans un tunnel correspondant au point de terminaison. 30 3044849 27\n<CLM>\1\tProcédé de détermination selon l'une des revendications précédentes, où le type du tunnel fait partie d'un groupe comprenant au moins: - tunnel MPLS; - tunnel "Segment Routing"; 5 - tunnel IP.\n<CLM>\1\tProcédé de détermination selon l'une des revendications précédentes, où l'événement modifiant la topologie antérieure est dit événement négatif et fait partie d'un groupe comprenant: 10 - augmentation du coût associé à au moins un lien ou à un préfixe IP; - disparition d'au moins un lien ou d'un préfixe IP.\n<CLM>\1\tProcédé de détermination selon l'une des revendications précédentes, où l'événement modifiant la topologie antérieure est dit événement positif et fait partie d'un 15 groupe comprenant: - diminution du coût associé à au moins un lien ou à un préfixe IP; - apparition d'au moins un lien ou d'un préfixe IP multi-homé.\n<CLM>\1\tProcédé de détermination selon la revendication 9, où l'événement est un 20 événement négatif et les cycles sont exécutés entièrement même si un nouvel événement négatif modifie la topologie postérieure avant la fin desdits cycles.\n<CLM>\1\tDispositif de détermination d'un point de terminaison d'au moins un tunnel dans un réseau à commutation de paquets, le réseau comprenant un ensemble de routeurs 25 (A, B, C, D, E, F, G) et des liens entre eux, chaque lien ayant un coût associé, l'ensemble de routeurs et les liens formant une topologie du réseau dite antérieure, un point d'encapsulation dudit au moins un tunnel étant un routeur de transit (RTR) recevant des paquets destinés à un routeur de sortie (RSO), un événement modifiant la topologie antérieure en une topologie du réseau dite 30 postérieure, 3044849 28 un chemin de secours de coût minimum étant calculé pour les paquets sur la base de la topologie postérieure, le dispositif (100) comprenant une mémoire (120) et un processeur (130,\n<CLM>\1\tapte à, et configuré pour, antérieurement à l'événement : 5 - pour chacun des routeurs de l'ensemble, calculer un arbre dit initial (SPT(A), SPT(B), SPT(C), SPT(D), SPT(E), SPT(F), SPT(G)), sur la base de la topologie antérieure, ledit arbre initial ayant pour racine ledit chacun des routeurs et ayant pour branches des chemins de coût minimum entre la racine et les autres routeurs de l'ensemble, 10 - mémoriser les arbres initiaux calculés dans une base de données (132), le processeur (130, 133,\n<CLM>\1\tétant en outre apte à, et configuré pour, postérieurement à l'événement : - sélectionner un routeur sur le chemin de secours, dit routeur de début (RDE(c=1), RDE(c=2)), 15 - à partir du routeur de début, vers le routeur de sortie le long du chemin de secours, identifier un routeur, dit dernier routeur commun (DRCO(c=1), DRCO(c=2)), pour lequel tous les liens et routeurs y compris lui-même, entre le routeur de début et lui-même, sont communs au chemin de secours et à l'arbre initial associé au routeur de début, 20 - déterminer comme point de terminaison du tunnel le dernier routeur commun identifié, le tunnel étant destiné à éviter aux paquets transitant entre le routeur de début et le dernier routeur commun identifié d'entrer dans une micro-boucle causée par l'événement. 25\n<CLM>\1\tRouteur de transit dans un réseau à commutation de paquets, apte à acheminer des paquets, le réseau comprenant un ensemble de routeurs et des liens entre eux, chaque lien ayant un coût associé, l'ensemble de routeurs et les liens formant une topologie du réseau dite antérieure, le routeur de transit (ROU) recevant des paquets destinés à un routeur de sortie, et 30 étant un point d'encapsulation d'un tunnel, 3044849 29 un événement modifiant la topologie antérieure en une topologie du réseau dite postérieure, un chemin de secours de coût minimum étant calculé pour les paquets sur la base de la topologie postérieure, 5 le routeur de transit comprenant un dispositif conforme à la revendication\n<CLM>\1\t14. Programme d'ordinateur, caractérisé en ce qu'il comprend des instructions pour la mise en oeuvre des étapes du procédé de détermination d'un point de terminaison d'au moins un tunnel dans un réseau à commutation de paquets selon la revendication 10 1, lorsque ce procédé est exécuté par un processeur.\n<CLM>\1\tSupport d'enregistrement lisible par un routeur sur lequel est enregistré le programme selon la revendication 14.