FR2836314A1 - Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes - Google Patents

Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes Download PDF

Info

Publication number
FR2836314A1
FR2836314A1 FR0202437A FR0202437A FR2836314A1 FR 2836314 A1 FR2836314 A1 FR 2836314A1 FR 0202437 A FR0202437 A FR 0202437A FR 0202437 A FR0202437 A FR 0202437A FR 2836314 A1 FR2836314 A1 FR 2836314A1
Authority
FR
France
Prior art keywords
link
node
tunnel
path
bypass
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
FR0202437A
Other languages
English (en)
Inventor
Roux Jean Louis Le
Geraldine Calvignac
Renaud Moignard
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Orange SA
Original Assignee
France Telecom SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom SA filed Critical France Telecom SA
Priority to FR0202437A priority Critical patent/FR2836314A1/fr
Priority to PCT/FR2003/000513 priority patent/WO2003071745A1/fr
Priority to EP03718889A priority patent/EP1476990A1/fr
Priority to US10/505,484 priority patent/US20070011284A1/en
Priority to AU2003222925A priority patent/AU2003222925A1/en
Publication of FR2836314A1 publication Critical patent/FR2836314A1/fr
Withdrawn legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/70—Admission control; Resource allocation
    • H04L47/74—Admission control; Resource allocation measures in reaction to resource unavailability
    • H04L47/746—Reaction triggered by a failure
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/28—Routing or path finding of packets in data switching networks using route fault recovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/15—Flow control; Congestion control in relation to multipoint traffic
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/70—Admission control; Resource allocation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/70—Admission control; Resource allocation
    • H04L47/72—Admission control; Resource allocation using reservation actions during connection setup
    • H04L47/724—Admission control; Resource allocation using reservation actions during connection setup at intermediate nodes, e.g. resource reservation protocol [RSVP]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/70—Admission control; Resource allocation
    • H04L47/72—Admission control; Resource allocation using reservation actions during connection setup
    • H04L47/726—Reserving resources in multiple paths to be used simultaneously
    • H04L47/728—Reserving resources in multiple paths to be used simultaneously for backup paths
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/70—Admission control; Resource allocation
    • H04L47/82—Miscellaneous aspects
    • H04L47/825—Involving tunnels, e.g. MPLS

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

L'invention concerne une méthode de protection d'un chemin à commutation d'étiquettes dans un réseau MPLS comprenant une pluralité de noeuds reliés par des liens IP, ledit chemin commençant à un noeud d'entrée et se terminant à un noeud de sortie dudit réseau en passant par une série déterminée de noeuds et de liens dudit réseau, dits éléments dudit chemin. Lorsque ledit noeud d'entrée requiert la protection d'un élément du chemin, dans une première phase, un noeud dudit chemin, dit point PLR, en amont dudit élément à protéger détermine un chemin de secours, dit tunnel de bypass, rejoignant le chemin en aval dudit élément à protéger en un noeud, dit point PM, et, dans une seconde phase, des ressources du réseau sont réservées sur chacun des liens du tunnel de bypass pour secourir ledit chemin en cas de défaillance dudit élément.

Description

<Desc/Clms Page number 1>
La présente invention concerne une méthode de protection de chemins à commutation d'étiquettes dans un réseau MPLS (MultiProtocol Label Switching).
Plus particulièrement la présente invention a trait à une méthode de protection locale de tels chemins avec partage de ressources.
La norme MPLS, publiée sous les auspices de l'IETF (Internet Engineering Task Force) est une technique basée sur la permutation d'étiquettes (label switching) permettant de créer un réseau orienté connexion à partir d'un réseau de type datagramme comme le réseau IP. On trouvera une documentation détaillée du protocole MPLS sous le site www. ietf. org.
On a représenté de manière schématique en Fig. 1 un réseau MPLS, 100, comprenant une pluralité de routeurs dénommés LSR (Label Switching Routers) tels que 110,111, 120,121, 130, 131, 140, reliés entre eux par des liens IP. Lorsqu'un paquet IP arrive sur un noeud périphérique d'entrée 110, dénommé Ingress LSR, ce dernier lui attribue une étiquette (ici 24) en fonction de son en-tête IP et la concatène audit paquet. Le routeur qui reçoit le paquet étiqueté remplace l'étiquette (entrante) par une étiquette sortante en fonction de sa table d'acheminement (dans l'exemple en question, 24 est remplacé par 13) et le processus se répète de noeud en noeud jusqu'au routeur de sortie 140 (encore dénommé Egress LSR) qui supprime l'étiquette avant de transmettre le paquet. Alternativement, la suppression d'étiquette peut être déjà effectuée par le penultième routeur puisque le routeur de sortie n'utilise pas l'étiquette entrante.
Comme indiqué en Fig. 2, un routeur LSR utilise l'étiquette du paquet entrant (étiquette entrante) pour déterminer le port de sortie et l'étiquette du paquet sortant (étiquette sortante). Ainsi, par exemple, le routeur A remplace les étiquettes des paquets IP arrivant sur le port 3 et de valeur 16 par des étiquettes de valeur 28 puis envoie les paquets ainsi réétiquetés sur le port 2.
Le chemin parcouru par un paquet à travers le réseau du routeur d'entrée (Ingress LSR) jusqu'au routeur de sortie (Egress LSR) est appelé chemin à étiquettes commutées ou LSP (Label Switched Path). Les routeurs LSR traversés par le chemin et distincts des routeurs d'entrée et de sortie sont appelés routeurs de transit. D'autre part, on appelle classe d'équivalence ou FEC (Forward Equivalence Class) l'ensemble des paquets IP qui sont transmis le long d'un même chemin.
Un des intérêts du protocole MPLS est de pouvoir forcer les paquets IP à suivre un chemin LSP préétabli qui n'est en général pas le chemin IP optimal en terme de nombre de bonds ou de métrique de chemin. La technique de détermination du chemin
<Desc/Clms Page number 2>
ou des chemins à emprunter est appelée ingénierie de trafic ou MPLS-TE (pour MPLS
Traffic Engineering). La détermination du chemin prend en compte des contraintes sur les ressources disponibles (constraint based routing), notammment en bande passante sur les différents liens du réseau. Au contraire du routage IGP classique opérant selon un mode bond par bond (hop-by-hop routing), la détermination d'un chemin LSP est effectué selon un mode dit explicite (explicitly routed LSP ou ER-LSP) dans lequel on détermine certains ou tous les noeuds du chemin du routeur d'entrée jusqu'au routeur de sortie. Lorsque tous les noeuds du chemin sont fixés, on parle de routage explicite au sens strict. Un chemin LSP déterminé selon un mode explicite est encore appelé tunnel MPLS.
La détermination d'un ou des chemins peut se faire de manière centralisée ou distribuée.
Selon la méthode distribuée encore appelée Constraint based Routing, chaque routeur est renseigné sur la topologie du réseau et les contraintes affectant les différents liens du réseau. Pour ce faire, chaque routeur détermine transmet à ses voisins un message indiquant ses liens immédiats et les contraintes (ou attributs) qui y sont associées. Ces messages sont ensuite propagés de noeud en noeud par des messages IGP étendu, selon un mécanisme d'inondation (flooding) jusqu'à ce que tous les routeurs soient renseignés. Ainsi, chaque routeur dispose en propre d'une base de données (dite TED pour Traffic Engineering Database) lui donnant la topologie du réseau et ses contraintes.
La détermination du chemin à commutation d'étiquettes est ensuite effectuée par le routeur d'entrée (Ingress LSR) en prenant également en compte d'autres contraintes fixées par l'opérateur du réseau (par exemple éviter tel ou tel noeud ou éviter les liens de tel ou tel type). Le routeur d'entrée détermine alors, par exemple au moyen de l'algorithme de Dijkstra, le chemin le plus court satisfaisant à l'ensemble des contraintes (Constraint Shortest Path First ou CSPF), celles affectant les liens comme celles fixées par l'opérateur. Ce chemin le plus court est ensuite signalé aux noeuds du chemin LSP au moyen des protocoles de signalisation connus sous les abbréviations RSVP-TE (Resource reSerVation Protocol for Traffic Engineering) ou bien CR-LDP (Constrained Route Label Distribution Protocol). On trouvera une description du protocole RSVP-TE dans le document de D. Adwuche et al. intitulé RSVP-TE : extensions to RSVP for LSP tunnels disponible sous le site de l'IETF précité.
<Desc/Clms Page number 3>
Ces protocoles de signalisation MPLS permettent la distribution des étiquettes le long du chemin et la réservation des ressources.
Par exemple, si l'on utilise le protocole de signalisation RSVP-TE, le routeur d'entrée A transmet, comme indiqué en Fig. 3A, un message Path dans un paquet
IP au routeur de sortie F. Ce message spécifie la liste des noeuds par lesquels le chemin LSP doit passer. A chaque noeud le message Path établit le chemin et fait une réservation d'état. Lorsque le message Path atteint le routeur de sortie, un message d'acquittement Resv est renvoyé par le même chemin au routeur d'entrée, comme indiqué en Fig. 3B. A chaque noeud, la table de routage MPLS est actualisée et la réservation de ressource est effectuée. Par exemple, si la ressource est une bande passante et que l'on souhaite réserver 10 unités (MHz) pour le chemin, les bandes passantes respectivement affectées à chaque lien sont décrémentées de la valeur réservée (10) lors de la rétropropagation du message d'acquittement/réservation. Il convient de noter que la ressource en question (par exemple la bande passante) est une ressource logique sur le lien IP et non une ressource physique. Lorsque le message d'acquittement est reçu par le routeur d'entrée, le tunnel est établi.
Comme on l'a indiqué plus haut, la détermination des chemins LSP peut être réalisée de manière centralisée. Dans ce cas, un serveur a connaissance de la topologie du réseau et prend en compte les contraintes sur les liens et les contraintes fixées par l'opérateur du réseau pour déterminer des tunnels entre les routeurs d'entrée et les routeurs de sortie. Les routeurs d'entrée sont ensuite avertis par le serveur du ou des tunnels pour lesquels ils sont le noeud d'entrée. Les tunnels sont alors établis comme indiqué en Fig. 3A et 3B. La méthode de détermination centralisée présente l'avantage d'une grande stabilité et prédictibilité puisqu'un seul organe effectue le calcul préalable de tous les tunnels. Elle présente en contrepartie l'inconvénient de de pas s'adapter facilement aux variations rapides de la topologie du réseau, par exemple en cas de rupture d'une liaison physique, supprimant les liens IP qu'elle supporte.
Qu'ils aient été calculés de manière centralisée ou distribuée, les tunnels sont susceptibles d'être détruits en cas de coupure d'une liaison physique sous-jacente. Il faut alors prévoir des mécanismes de secours permettant d'établir un nouveau tunnel entre le même routeur d'entrée et le même routeur de sortie. On peut distinguer les mécanismes de restauration établissant un tunnel de secours après la coupure et les mécanismes de protection préétablissant un tunnel de secours en prévision d'une coupure possible.
<Desc/Clms Page number 4>
L'avantage des mécanismes de protection est de permettre une reprise très rapide du trafic, un tunnel de secours étant déjà disponible. En contrepartie, ils présentent l'inconvénient de mobiliser des ressources importantes du réseau. Plus précisément, les mécanismes de protection connus de l'état de la technique se divisent en méthodes de protection locale et méthodes de protection de bout en bout. Dans les premières, des tunnels de secours locaux sont préétablis en prévision d'une défaillance d'un élément (noeud, lien) du tunnel initial. Lorsque la défaillance se produit, le trafic est détourné dans le tunnel local pour contourner l'élément défaillant. Dans les méthodes de protection de bout en bout, un tunnel de secours est établi du routeur d'entrée au routeur de sortie. A l'inverse des méthodes de restauration (où les tunnels de secours sont créés à la demande), les méthodes de protection (où les tunnels de secours sont créés au préalable) sont gourmandes en ressources de réseau.
On connaît de l'état de la technique, en particulier du document intitulé FastReroute Techniques in RSVP-TE de P. Pan et al. disponible sur le site de l'IETF sus-mentionné sous la référence draft-pan-rsvp-fastreroute-OO. txt , différentes méthodes de protection locale (ou FRR pour Fast ReRoute) d'un tunnel. Le principe général de cette protection locale est rappelé en Fig. 4. Pour un élément (lien, noeud) du tunnel à protéger, on prévoit un tunnel de secours local pour le contourner. Par exemple pour contourner le lien CD, on prévoit un tunnel de secours T (CD) ayant pour chemin C, C', E. Le routeur en amont qui détecte et répare la défaillance du chemin en orientant les paquets sur le tunnel de secours est dénommé point PLR (pour Point of Local Repair ). Le routeur en aval de la défaillance où le tunnel de secours rejoint le tunnel initial est dénommé point PM (pour Point of Merging ). Dans le cas présent, le routeur C détecte la défaillance du lien CD (symbolisée par un éclair) par l'absence de messages RSVP Hello transmis à intervalles réguliers sur le lien CD par le routeur D ou par une alerte de la couche physique sous-jacente. Le routeur C réachemine alors le trafic du chemin initial sur le tunnel de bypass CC'E. La jonction entre le chemin initial et le tunnel de bypass est réalisée en E.
Une première méthode de protection locale de chemin LSP, dénommée oneto-one , consiste à créer pour chaque élément du chemin à protéger un tunnel de secours local, encore appelé détour . On a illustré en Fig. 5 une méthode de protection locale de type one-to-one . Chaque élément K du chemin est protégé par un détour noté T (K). On notera qu'un détour T (N) pour un noeud N protège également le lien en amont et le lien en aval du noeud. Si le tunnel comporte n noeuds, il peut
<Desc/Clms Page number 5>
donc y avoir jusqu'à (n-1) détours. Si plusieurs tunnels sont à protéger dans le réseau MPLS, une série de détours devra être prévue pour chacun d'entre eux. Cette méthode de protection n'est donc pas extensible (scalable).
Il est important de noter que les détours sont créés dynamiquement lors de l'établissement du chemin. En outre, les détours sont créés de manière distribuée par les routeurs de transit du chemin, à l'initiative du routeur d'entrée. Ainsi en cas de changement de topologie du réseau ou de modification des contraintes de ressources, les détours ne seront pas nécessairement les mêmes pour un même chemin. La procédure de création des détours nécessite une modification de la signalisation RSVP, comme décrit dans le document sus-mentionné.
Selon une seconde méthode de protection locale de chemin LSP, dénommée many-to-one , un tunnel de secours, dénommé tunnel de bypass, est prévu par l'opérateur pour protéger un ou plusieurs éléments (noeud, lien) du réseau MPLS. Un tunnel de bypass peut servir à secourir une pluralité de chemins empruntant ledit ou lesdits éléments. A titre d'exemple, on a illustré en Fig. 6 deux chemins à protéger Ti==ABCDE et T2=A'BCDE partageant le chemin BCDE. Dans le cas présent, l'opérateur a prévu de protéger le noeud C en configurant un tunnel de bypass ayant pour chemin BB'D'D. Ce tunnel de bypass permet de secourir les deux chemins Tl et T2 en cas de défaillance du noeud C (ou d'un des liens BC, CD). De manière générale, un tunnel de bypass permet de secourir une pluralité de chemins qui l'intersectent en amont de la défaillance en un point commun PLR et en aval de la défaillance en un point commun PM. Le tunnel de bypass tire parti de la possibilité d'empiler les étiquettes (label stacking) en leur attribuant différents niveaux de hiérarchie pour réacheminer les paquets de manière transparente. Plus précisément, comme indiqué sur la Fig. 6, les routeurs le long du chemin Tl commutent les étiquettes 12,18, 45 et 37. Lorsqu'une défaillance du noeud C intervient, le routeur B empile une étiquette (ici 67) représentant localement le tunnel de bypass. Au penultième noeud du tunnel de bypass (ici D'), l'étiquette représentant localement le tunnel de bypass (ici 38) est dépilée de sorte que le point PM reçoit une étiquette identique à celle (45) d'un paquet qui n'aurait pas été réacheminé.
On distinguera dans la suite deux types de tunnels de bypass : ceux qui protègent un lien, encore appelés NHOP bypass (pour next-hop bypass) et ceux qui protègent un noeud ou NNHOP bypass (pour next-next-hop bypass).
<Desc/Clms Page number 6>
Il est important de noter que les tunnels de bypass sont déterminés au préalable, de manière statique et/ou centralisée par un serveur spécialisé, sans tenir compte a priori des besoins en ressources des futurs chemins LSP à établir et les variations en ressources du réseau. En particulier, la bande passante du tunnel de bypass peut ne pas être suffisante pour transporter la bande requise du chemin à protéger. Ainsi, bien qu'un tunnel de bypass soit présent, il ne permettra pas de secourir efficacement le chemin à protéger.
Le problème à la base de l'invention est de proposer une méthode de protection de chemins LSP qui remédie aux inconvénients précités, en particulier qui soit extensible et qui soit adaptée à prendre en compte les variations rapides de ressources du réseau tout en garantissant une efficacité de protection.
Un problème subsidiaire à la base d'un mode de réalisation de l'invention est de proposer une méthode de protection de tunnels LSP qui consomme moins de ressources que les méthodes de protection connues de l'état de la technique.
Le problème est résolu par l'objet de l'invention, défini comme une méthode de protection d'un chemin à commutation d'étiquettes dans un réseau MPLS comprenant une pluralité de noeuds reliés par des liens IP, ledit chemin commençant à un noeud d'entrée et se terminant à un noeud de sortie dudit réseau en passant par une série déterminée de noeuds et de liens dudit réseau, dits éléments dudit chemin. Lorsque ledit noeud d'entrée requiert la protection d'un élément du chemin, dans une première phase, un noeud dudit chemin, dit point PLR, en amont dudit élément à protéger détermine un chemin de secours, dit tunnel de bypass, rejoignant le chemin en aval dudit élément à protéger en un noeud, dit point PM, et, dans une seconde phase, des ressources du réseau sont réservées sur chacun des liens du tunnel de bypass pour secourir ledit chemin en cas de défaillance dudit élément.
Lesdites ressources sur un lien du tunnel de bypass comprennent par exemple une bande passante réservée relative à ce lien.
Avantageusement, pour chaque élément physique dudit réseau, on détermine un groupe de liens dudit réseau atteints par la défaillance dudit élément physique et, réciproquement, pour chaque lien dudit réseau, on détermine la liste, dite liste SRLG, desdits groupes auxquels il appartient.
Avantageusement, le point PLR recherche, dans une première étape de la première phase, les tunnels de bypass existants dans le réseau susceptibles de protéger ledit élément.
<Desc/Clms Page number 7>
Si l'élément à protéger est un lien, le point PLR détermine si un tunnel de bypass existant est susceptible de protéger ledit lien en vérifiant que ledit tunnel ne comprend pas ledit lien et que, la liste SRLG associée à chaque lien dudit tunnel existant et la liste SRLG associée au lien à protéger ont une intesection vide.
Si l'élément à protéger est un noeud, le point PLR détermine si un tunnel de bypass existant est susceptible de protéger le noeud en vérifiant que ledit tunnel ne comprend pas ledit noeud et que la liste SRLG associée à chaque lien dudit tunnel existant et la liste SRLG associée au lien joignant le point PLR et ledit noeud ont une intersection vide.
Ensuite, pour chaque tunnel de bypass existant susceptible de protéger ledit élément, dit tunnel candidat, le point PLR simule, pour chaque lien du tunnel candidat, une augmentation de la bande passante réservée sur ce lien de la valeur de la bande passante du chemin à étiquettes commutées et vérifie si la valeur de la bande passante ainsi obtenue est inférieure à une bande passante maximale réservable sur ce lien.
Alternativement, pour chaque tunnel de bypass existant susceptible de protéger ledit élément, dit tunnel candidat, le point PLR simule une protection dudit élément par ledit tunnel candidat et détermine, pour chaque lien dudit tunnel candidat, la plus grande bande passante à réserver sur ce lien pour supporter les tunnels de bypass passant par ce lien, y compris le tunnel candidat, en cas de défaillance d'un élément physique quelconque du réseau et l'on vérifie si ladite plus grande bande passante est inférieure à une bande passante maximale réservable sur ce lien.
S'il n'existe aucun tunnel candidat ou si la vérification est négative pour au moins un lien de chaque tunnel candidat, le point PLR détermine un nouveau tunnel de bypass.
Avantageusement, dans ladite seconde phase, le point PLR transmet un premier message se propageant de noeud en noeud sur le tunnel de bypass vers le point PM et qu'un second message est retourné le long tunnel de bypass vers le point PLR, et lors du passage du premier ou du second message, on vérifie pour chaque lien du tunnel de bypass, qu'il est susceptible de protéger ledit élément et que lesdites ressources sont effectivement disponibles sur ce lien, et dans l'affirmative l'on procède à la réservation desdites ressources.
<Desc/Clms Page number 8>
L'objet de l'invention est également défini par de nouveaux messages de protocoles existants.
Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, apparaîtront plus clairement à la lecture de la description suivante de modes de réalisation, ladite description étant faite en relation avec les dessins joints, parmi lesquels :
La Fig. 1 illustre un réseau MPLS connu de l'état de la technique ;
La Fig. 2 illustre schématiquement la création d'un chemin à étiquettes commutées ;
La Fig. 3A illustre schématiquement une première phase de la procédure d'établissement d'un chemin LSP ;
La Fig. 3B illustre schématiquement une seconde phase de la procédure d'établissement d'un chemin LSP ;
La Fig. 4 illustre schématiquement le principe de réparation locale d'un chemin LSP ;
La Fig. 5 illustre schématiquement une méthode distribuée de protection locale d'un chemin LSP, connue de l'état de la technique ;
La Fig. 6 illustre schématiquement une méthode centralisée de protection locale d'un chemin LSP, connue de l'état de la technique ;
La Fig. 7 illustre le concept d'entité de risque partagé ;
La Fig. 8 illustre schématiquement une méthode distribuée de protection locale de chemins LSP selon la présente invention.
L'idée à la base de l'invention est de prévoir une méthode de génération dynamique et distribuée de tunnels de bypass. De manière générale, lorsqu'un chemin LSP doit faire l'objet d'une protection locale, le routeur d'entrée avertit le point PLR (Point of Local Repair) en amont de l'élément à protéger. Ce point détermine tout d'abord s'il existe un tunnel de bypass qui passe par lui et qui est susceptible de protéger ledit élément. Le cas échéant, il vérifie si le tunnel de bypass présente les ressources suffisantes, notamment en bande passante, pour supporter le trafic du chemin à protéger et, dans la négative, il s'assure qu'il peut les augmenter. Si aucun tunnel de bypass ne peut être retenu ou s'il n'est pas possible d'augmenter les ressources du tunnel retenu, le point PLR tente alors de déterminer un nouveau tunnel de bypass permettant de protéger l'élément en question. Avantageusement, il utilise pour ce faire des éléments de tunnels existants et en partage les ressources. Enfin, si
<Desc/Clms Page number 9>
aucun tunnel de bypass ne peut être établi, le point PLR en avertit le routeur d'entrée.
Lorsque le chemin LSP est supprimé, le routeur d'entrée peut transmettre un message de suppression au point PLR qui libère alors les ressources qui avaient été réservées pour la protection de l'élément considéré.
Les ressources qui peuvent être réservées ou libérées respectivement lors de la création et de la suppression d'un tunnel de bypass sont notamment la bande passante.
On entend ici par bande passante, une bande passante logique dédiée à la protection, sans rapport direct avec la bande passante physique. Plus précisément, une bande passante physique associée à un élément du réseau (par exemple un lien) comprend une bande passante logique dédiée au trafic normal et une bande de passante logique dédiée au trafic secouru. Cette dernière, encore appelée bande passante de protection pourra être utilisée, partiellement ou entièrement, par les tunnels de bypass. On notera RBP (L) la valeur de la bande passsante de protection sur un lien L du réseau et rBP (L) la valeur de la bande passante effectivement utilisée ou réservée par les tunnels de bypass empruntant ce lien.
Nous supposerons tout d'abord que chaque noeud (routeur LSR) du réseau a non seulement connaissance de la topologie du réseau mais également des tunnels de bypass existants, de leurs caractéristiques (liste de noeuds et liens, bande passante à protéger) et, pour chaque tunnel de bypass, de l'élément du réseau qu'il protège. Cette information peut être diffusée dans le réseau comme celle relative à la topologie du réseau par le biais de messages dont nous expliciterons plus loin le contenu. Chaque PLR ayant créé un tunnel de bypass envoie à ses voisins un message (annonce) identifiant ledit tunnel, ses caractéristiques et l'élément qu'il protège. Ce message est répercuté de noeud en noeud dans tout le réseau Lorsque le tunnel de bypass est supprimé, un message de suppression est également transmis et diffusé dans tout le réseau.
On appellera par la suite entité de risque partagé ou SRLG (pour Shared Risk Link Group) associé à un lien, l'ensemble des liens du réseau partageant une même ressource physique avec le lien précité et tous atteints par la défaillance de cette ressource physique. Ce concept d'entité de risque partagé a été introduit par K.
Kompella et al. dans un document intitulé Routing extensions in support of generalized MPLS disponible sur le site de l'IETF sous la référence draft-ietf-
<Desc/Clms Page number 10>
ccamp-gmpls-routing-01. txt . Un lien peut appartenir à plusieurs SRLG ou n'en appartenir à aucun. On définit la liste SRLG d'un lien comme la liste des SRLG dans lesquels ce lien apparaît. Deux liens présentent une diversité de SRLG si leurs listes
SRLG ont une intersection vide. En particulier deux liens n'appartenant à aucun
SRLG ont une diversité de SRLG.
Le concept de liste de SRLG sera mieux compris à l'aide de l'exemple de la Fig.
7. On suppose que trois routeurs RI, R2, R3 sont interconnectés au moyen de brasseurs optiques (OXC) 01, O2, 03. Ces brasseurs optiques sont inteconnectés au moyen de fibres optiques fi, f2 avec muliplexage WDM. Soient SI, S2, les SRLG associés respectivement aux fibres fi et f2. Le lien RIR2 utilise le seulement trajet lumineux 01- O2 sa liste SRLG est {St}. Le lien RIR3 utilise le trajet lumineux 01-02-03, sa liste
SRLG est par conséquent {Si, S2}. Le lien R2R3 utilise le trajet lumineux 02-03, sa liste SRLG se résume donc à {S2}. On constate donc que les liens RIR2 et R2R3 ont une diversité de SRLG mais que ceux-ci n'en ont pas avec le lien avec le lien RIR3.
On définit une défaillance de SRLG comme la défaillance de la ressource physique partagée par les différents éléments du SRLG. Ainsi, dans l'exemple précédent, une défaillance du SRLG S2 correspond à une défaillance de la fibre f2.
Une défaillance de SRLG peut causer la défaillance de plusieurs liens. Ainsi, dans l'exemple précédent, la défaillance du SRLG S2 entraînera la défaillance des liens RIR3 et R2R3. De manière générale, la défaillance d'un SRLG donné entraînera la défaillance des liens dont les listes de SRLG le contiennent.
Réciproquement, la défaillance d'un lien peut ne pas être liée à la défaillance d'un SRLG. Ainsi, dans l'exemple précédent, la défaillance du lien R202 connectant R2 à R3 entraîne une défaillance du lien R2R3 mais non du SRLG S2. De manière générale si un lien n'appartient pas à aucun SRLG, la défaillance de ce lien ne sera pas liée à la défaillance d'un SRLG.
La méthode de protection locale selon l'invention comprend deux phases, une première phase dite de contrôle d'admission générale ou GAC (General Admission Control) et une seconde phase dite de contrôle d'admission locale ou LAC (Local Admission Control) de tunnel de bypass. Lors de la première phase, un point PLR d'un chemin LSP détermine, à partir d'une requête du routeur d'entrée, si une protection locale est à réaliser et, le cas échéant, le type de la protection demandée (lien, noeud) ainsi que la valeur de la bande passante requise pour protéger le chemin LSP. Le point PLR détermine ensuite le chemin du tunnel de bypass tout en simulant
<Desc/Clms Page number 11>
son admission par le réseau. Dans la seconde phase, le PLR procède à la création effective du tunnel de bypass de manière similaire à celle d'un chemin LSP classique en transmettant un message analogue à un message Path le long du chemin du tunnel de bypass et en recevant le message d'acquittement Resv correspondant.
Nous exposerons tout d'abord un premier mode de réalisation de l'invention.
Le contrôle d'admission générale comprend deux étapes. Dans la première étape, le PLR détermine s'il existe un ou des tunnels de bypass existants permettant d'assurer la protection demandée. On obtient ainsi des tunnels de bypass candidats.
Les tunnels de bypass candidats ne peuvent utiliser l'élément à protéger.
- dans le cas d'un lien à protéger, le PLR détermine à partir de sa base de données locale, pour chaque lien du tunnel de bypass (NHOP) candidat, s'il présente une diversité de SRLG avec ce lien : dans la négative le tunnel de bypass candidat n'est pas compatible en terme de risque et ne peut être retenu ; - dans le cas d'un noeud à protéger, le PLR détermine à partir de sa base de données locale, pour chaque lien du tunnel de bypass (NNHOP) candidat, s'il présente une diversité de SRLG avec le lien joignant le PLR et le noeud à protéger : dans la négative le tunnel de bypass n'est pas compatible en terme de risque et ne peut être retenu.
S'il existe au moins un tunnel de bypass candidat T satisfaisant au critère de compatibilité, le noeud PLR simule une augmentation de la bande passante b (T) du tunnel de la valeur b (LSP) de la bande passante requise pour protéger le chemin LSP.
Figure img00110001

Le noeud PLR vérifie ensuite si pour chaque lien L du tunnel de bypass, la nouvelle valeur b (T) est telle que b (T) P (L). Si c'est le cas le tunnel de bypass est définitivement retenu. A défaut, les autres tunnels candidats satisfaisant au critère de compatibilité sont testés l'un après l'autre.
Si aucun des tunnels de bypass candidats ne peut être retenu pour des raisons d'incompatibilité de risque ou de bande passante insuffisante, le point PLR simule, dans une seconde étape, la création d'un nouveau tunnel de bypass.
La construction d'un nouveau tunnel de bypass est simulée de la manière suivante : à partir du point PLR jusqu'à un point PM (Point of Merging) du chemin LSP en aval de l'élément à protéger, le PLR sélectionne parmi les liens du réseau,
<Desc/Clms Page number 12>
ceux qui peuvent supporter le tunnel de bypass. Les critères d'admission utilisés pour un lien L sont les mêmes que ceux indiqués plus haut, à savoir : - le lien L doit être distinct du lien à protéger ; - si l'élément à protéger est un lien, le lien L doit présenter une diversité de
SRLG avec le lien à protéger ; - si l'élément à protéger est un noeud, le lien L doit présenter une diversité de
SRLG avec le lien joignant le PLR et le noeud à protéger.
En outre, si une protection de la bande passante est requise, le point PLR simule pour chaque lien L une augmentation de la bande passante réservée à la protection sur ce lien, soit : rBP (L) =rBP (L) +b (LSP) et teste si la condition rBP (L) < RBP (L) est vérifiée. Dans la négative, le lien ne peut accueillir le tunnel de bypass et est rejeté.
Dans l'affirmative, en revanche, le tunnel de bypass peut a priori emprunter le lien et est sélectionné.
Le résultat de la sélection précédente est un sous-réseau du réseau initial où les liens non sélectionnés ont été élagués. Le point PLR détermine alors le chemin le plus court dans le sous-réseau (CSPF), par exemple au moyen de l'algorithme de Dijkstra.
Ce chemin sera celui qu'empruntera le tunnel de bypass.
Si aucun tunnel de bypass ne peut être construit, le point PLR en avertit le routeur d'entrée via le chemin LSP.
Il convient de noter que certains noeuds du réseau pourront être exclus par l'opérateur comme ne pouvant assurer une protection locale. Autrement dit, un tel noeud ne pourra être PLR pour un chemin LSP quelconque le traversant. Dans ce cas, lorsqu'un tel noeud reçoit une requête de protection locale, il avertit le routeur d'entrée, via le chemin LSP, que la protection ne pourra être réalisée.
On a supposé dans ce qui précède qu'il fallait protéger la bande passante du chemin LSP (b (LSP)). Cependant, il peut s'avérer qu'une protection de la bande passante ne soit pas nécessaire (la protection du chemin LSP est alors de type Best Effort ). Dans ce cas, un tunnel de bypass spécifique, consacré à la protection Best Effort , sera utilisé par le PLR.
Lorsqu'un tunnel de bypass à été déterminé par le point PLR, on passe à une phase de signalisation avec un contrôle d'admission locale qui crée réellement le tunnel de bypass. Le point PLR transmet alors un message de type Path indiquant notamment le chemin du tunnel de bypass et la bande passante requise pour la protection, b (LSP). Chaque lien procède à nouveau à la vérification de sa diversité
<Desc/Clms Page number 13>
SRLG avec l'élément à protéger. Si cette diversité SRLG est vérifiée, on teste à nouveau si la condition rBP (L) < RBP (L) est vérifiée et dans l'affirmative, on procède à la modification effective de la bande passante réservée à la protection sur ce lien soit rBP (L) =rBP (L) +b (LSP). Ces nouvelles étapes de vérification s'expliquent par le fait que la situation de diversité ou les ressources du lien ont pu évoluer entre les phases de contrôle d'admission générale et locale, notamment si d'autres tunnels de bypass ont été créés dans l'intervalle. Si toutes les vérifications sont positives, on est certain d'avoir une protection efficace de la bande passante du chemin LSP. En revanche, si l'une des étapes de vérification échoue, un message d'erreur est transmis le long du tunnel de bypass au point PLR qui pourra ensuite avertir le routeur d'entrée.
Comme pour un chemin LSP classique, les tables MPLS du tunnel de bypass sont établies lors de la rétropropagation du message d'acquittement Resv .
On notera que la réservation effective de la bande passante pourra être réalisée lors de l'acheminement du message Path ou bien lors de la rétropropagation du message d'acquittement.
Nous exposerons maintenant un second mode de réalisation de l'invention.
Selon ce second mode de réalisation, la construction du tunnel de bypass est réalisée en partageant des ressources de tunnels déjà existants. Ce mode de réalisation trouve sa justification dans le fait que deux éléments physiques du réseau n'ont qu'une très faible probabilité d'être défaillants en même temps. La défaillance d'un élément physique entraîne la défaillance d'un certain nombre de liens IP et/ou de noeuds du réseau qui l'utilisent. Ainsi, en cas de défaillance d'un élément physique, seuls certains chemins seront affectés. Les ressources de protection permettant de protéger des chemins qui ne sont pas affectés en même temps par la défaillance d'un même élément physique sont susceptibles d'être partagées et par conséquent économisées.
Dans ce but, on définit un risque de défaillance ou FR (pour Failure Risk) comme un lien, un noeud ou un SRLG. Bien entendu, pour un SRLG, le risque réel de défaillance concerne la ressource physique sous-jacente mais, par souci de simplification, on associera le SRLG à la ressource physique en question.
En outre, on définit le groupe de risques de défaillance ou TFRG (pour Tunnel Failure Risk Group) d'un tunnel de bypass comme l'ensemble des risques de défaillance que protège ce tunnel. Ainsi, le TFRG d'un tunnel de bypass NHOP est l'ensemble formé par le lien en aval et la liste SRLG de ce lien. De même, le TFRG
<Desc/Clms Page number 14>
d'un tunnel de bypass NNHOP est l'ensemble formé par le noeud qu'il protège, le lien reliant le point PLR à ce noeud et la liste SRLG de ce lien.
De même, on définit le groupe de risques de défaillance ou LFRG (pour Link Failure Risk Group) d'un lien comme l'ensemble des risques de défaillance que protègent les tunnels de bypass passant par ce lien.
Figure img00140001
Enfin, on définit la bande passante de protection d'un risque de défaillance (D par un lien L d'un tunnel de bypass protégeant (D (autrement dit dont le TFRG contient < 1 > ), et on la note BP D, L), la bande passante réservée ou à réserver sur ce lien pour protéger (D. Bien entendu, cette bande passante devra être inférieure à la bande de protection sur le lien L, c'est-à-dire BP (C, L) < RBP (L).
La méthode de protection selon le second mode de réalisation comprend également une phase d'admission générale et une phase d'admission locale.
La phase d'admission générale du second mode diffère de celle du premier mode lorsqu'une protection de la bande passante est requise.
Lors de la première étape où le PLR cherche à utiliser un tunnel de bypass existant, au lieu de simuler l'augmentation de la bande passante rBP (L), on calcule pour chaque lien L du tunnel candidat la nouvelle bande passante qu'il faudrait réserver pour protéger l'élément en question du chemin LSP, soit rBP (L) =max (BP D, L où 0 e LFRG (L), étant entendu que pour ce calcul, on a supposé que le tunnel de bypass candidat passait par le lien L.
On teste ensuite si la condition rBP (L) < RBP (L) est vérifiée pour déterminer si le lien L peut encore supporter le tunnel de bypass candidat. Si cette condition est vérifiée pour tous les liens du tunnel bypass candidat, celui-ci est retenu. Les tunnels candidats satisfaisant au critère de compatibilité sont testés l'un après l'autre. Un tunnel est ensuite choisi parmi ceux retenus par exemple selon un critère de taux d'occupation de la bande passante de protection.
De même, pour la seconde étape, c'est-à-dire lorsque l'on doit simuler la construction d'un tunnel de bypass, le critère de sélection d'un lien L doit être modifié de la manière suivante : au lieu de simuler l'augmentation de la bande passante sur le lien candidat, on simule une protection de l'élément considéré et l'on calcule pour le lien L la nouvelle bande passante qu'il faudrait réserver pour accueillir le tunnel de bypass, soit rBP (L) =max (BP D, L où (D e LFRG (L), étant entendu que pour ce
<Desc/Clms Page number 15>
calcul, le tunnel de bypass est supposé passer par le lien L. Comme précédemment, on teste ensuite si la condition rBP (L) : RBP (L) est vérifiée. Dans l'affirmative, le lien candidat est sélectionné pour la détermination du CSPF.
La phase d'admission locale du second mode diffère de celle du premier mode lorsqu'une protection de la bande passante est requise. Pour un lien L donné du tunnel de bypass, on procède, après avoir vérifié la diversité du lien avec l'élément à protéger, à la modification effective de la bande passante réservée à la protection sur ce lien, soit rBP (L) =max (BP ( < 1 > , L)) et l'on teste à nouveau si la condition rBP (L) : RBP (L) est vérifiée. Comme dans le premier mode de réalisation, si toutes les vérifications sont positives, on est certain d'avoir une protection efficace de la bande passante du chemin LSP. En revanche, si l'une des étapes de vérification échoue, un message d'erreur est transmis le long du tunnel de bypass au point PLR.
La Fig. 8 illustre schématiquement la méthode de protection locale selon un exemple de réalisation de la présente invention. La demande de protection locale est demandée en 800 par le routeur d'entrée (Ingress LSR) du chemin LSP au moyen de paramètres de protection inclus dans l'objet Session~Attribute Object (SAO) du protocole RSVP-TE. La requête de protection est indiquée par un drapeau dans l'objet SAO.
En outre, un bit de protection locale LPD (Local Protection Bit) dans l'objet SAO indique à chaque PLR si un tunnel de bypass doit être recherché/construit.
Un bit de protection de noeud NPD (Node Protection Bit) dans l'objet SAO indique à chaque PLR le type de la protection demandée (NNHOP ou NHOP).
Enfin, un bit de protection de bande passante BPD (Bandwith Protection Bit) dans l'objet SAO indique à chaque PLR si le tunnel de bypass doit offrir une protection de la bande passante ou non.
Le point PLR détermine à partir du bit LPD si un tunnel de bypass est demandé et, dans l'affirmative, initie en 810 la phase de GAC. En 811, le point PLR détermine les tunnels de bypass candidats, c'est-à-dire les tunnels existants susceptibles d'assurer la protection demandée. Il vérifie en 812 la condition de diversité pour chaque lien de chaque tunnel de bypass candidat. Si pour un lien quelconque elle n'est pas vérifiée, le candidat n'est pas retenu. En 813, on teste si au moins un candidat est retenu. Dans la négative on passe directement à l'étape de construction 817. Pour
<Desc/Clms Page number 16>
chaque candidat retenu, on simule en 814 la protection du chemin LSP par le tunnel de bypass candidat et l'on calcule la nouvelle valeur de bande passante à réserver (selon le premier mode ou le second mode de réalisation) pour chaque lien du bypass. On teste en 815 si la bande passante de protection sur le lien est suffisante pour autoriser cette valeur. Le test est effectué pour chaque lien du bypass. On vérifie en 816 si le test est positif pour tous les liens du bypass candidat. Si c'est le cas, le PLR transmet un message Path et l'on passe à la phase d'admission locale. Dans le cas contraire on passe au candidat suivant jusqu'à ce qu'ils aient été tous testés. Selon une variante, si plusieurs candidats retenus satisfont à la condition de bande passante, on en choisira un selon un critère prédéterminé, par exemple un critère d'occupation de la bande passante de protection.
Si tous les candidats ont été testés et aucun finalement retenu, on simule en 817 la création d'un nouveau tunnel de bypass, en ne considérant que les liens du réseau qui satisfont aux conditions de diversité et de bande passante, comme expliqué plus haut. Le chemin CSPF est ensuite calculé en 818. Le PLR teste en 819 si un tunnel de bypass a pu être construit. Dans la négative, il en avertit le routeur d'entrée. Dans l'affirmative, le PLR transmet un message Path et l'on passe à la phase d'admission locale.
Chaque lien du tunnel de bypass initie en 820 un contrôle d'admission locale et vérifie en 821 si la condition de diversité est encore vérifiée. Dans la négative, un message d'erreur est transmis au PLR. Si elle est bien vérifiée, on teste en 822 si la condition de suffisance de bande passante de protection est vérifiée et dans l'affirmative on met à jour en 823 la valeur de bande passante réservée rBP (L). Dans la négative, on transmet un message d'erreur au PLR. Le contrôle d'admission locale se termine en 824.
La mise en oeuvre de la méthode de protection selon l'invention suppose que chaque noeud du réseau susceptible d'être PLR ait accès à un certain nombre d'informations comme la bande passante de protection RBP (L) sur chaque lien L, la bande passante réservée rBP (L), les tunnels de bypass existants et leurs caractéristiques. Ces informations font l'objet d'annonces dans le réseau et servent à mettre à jour les bases de données locales TED. Réciproquement, lorsqu'un point PLR retient un tunnel de bypass existant pour protéger un nouvel élément du réseau ou
<Desc/Clms Page number 17>
lorsqu'il crée un nouveau tunnel de bypass (utilisant ou non des ressources de tunnels existants) ce tunnel de bypass doit être signalé au réseau.
Avantageusement, les annonces sont réalisées au moyen d'une extension du protocole OSPF-TE ou bien d'une extension du protocole ISIS-TE. On trouvera notamment une description du protocole OSPF-TE dans le document de D. Katz et al. intitulé Traffic Engineering Extensions to OSPF et du protocole ISIS-TE dans le document de H. Smit et al. intitulé IS-IS extensions for Traffic Engineering . Ces deux documents sont disponibles sur le site de l'IETF précité. On rappelle que les protocoles OSPF-TE et ISIS-TE permettent de diffuser sur le réseau des informations nécessaires à l'ingéniérie de trafic comme les liens immédiats de chaque noeud et les contraintes (par exemple la bande passante maximale réservable, la métrique etc.) associées à chaque lien. Ces informations sont transmises sous forme de messages comprenant un en-tête et un certain nombre de données, chacune se présentant sous un format dit TLV (pour Type, Length, Value) indiquant le type, la longueur et la valeur de la donnée. Une donnée sous ce format, appelée encore par assimilation TLV, peut comprendre d'autre données selon un format TLV, appelées pour cette raison subTLV.
Les protocoles OSPF-TE et ISIS-TE peuvent être étendus en ajoutant de nouveaux TLV ou de nouveaux sub-TLV dans les TLV existants.
Ainsi, le TLV donnant les caractéristiques d'un lien (Link TLV dans le protocole OSPF-TE et IS reachability dans le protocole ISIS-TE) est étendu au moyen des sub-TLV suivants : sub-TLV indiquant la bande passante de protection réservable (RBP (L)) sur ce lien - sub-TLV indiquant la bande passante sur ce lien effectivement réservée à la protection rBP (L) - sub-TLV indiquant la liste SRLG de ce lien.
On introduit également un nouveau TLV, dénommé bypass TLV, donnant les caractéristiques d'un tunnel de bypass et comprenant trois sub-TLV :
<Desc/Clms Page number 18>
sub-TLV Tail Router Id donnant l'adresse IP servant à identifier le noeud
PM (Point of Merging) où le tunnel de bypass rejoint le chemin LSP protégé sub-TLV Path donnant le chemin emprunté par le tunnel de bypass - sub-TLV Information donnant le type de tunnel de bypass (NHOP,
NNHOP), l'adresse IP du noeud protégé (si type=NNHOP), les adresses IP locale (adresse IP du point PLR) et distante (adresse IP du noeud en aval du point PLR) du lien protégé (si type=NHOP) et la bande passante du tunnel de bypass.
En outre, la phase d'admission locale du tunnel de bypass suppose que l'on étende le protocole RSVP-TE en modifiant notamment le message Path . Un nouvel objet est introduit dans ce message pour définir le tunnel de bypass. Il contient les champs suivants : - type de bypass (NHOP ou NNHOP) adresse IP du noeud protégé, si type=NNHOP adresse IP du point PLR en amont du lien protégé (adresse IP locale), si type=NHOP adresse IP du noeud en aval (PLR next hop) du lien protégé, (adresse IP distante), si type=NHOP - liste SRLG du lien protégé s'il s'agit d'un lien ou du lien joignant ledit point
PLR et le noeud en aval dudit point PLR, s'il s'agit d'un noeud.
Bien entendu, l'homme du métier peut étendre le protocole CR-LDP de manière équivalente.

Claims (14)

REVENDICATIONS
1) Méthode de protection d'un chemin à commutation d'étiquettes dans un réseau MPLS comprenant une pluralité de noeuds reliés par des liens IP, ledit chemin commençant à un noeud d'entrée et se terminant à un noeud de sortie dudit réseau en passant par une série déterminée de noeuds et de liens dudit réseau, dits éléments dudit chemin, caractérisée en ce que, lorsque ledit noeud d'entrée requiert la protection d'un élément du chemin, dans une première phase, un noeud dudit chemin, dit point PLR, en amont dudit élément à protéger détermine un chemin de secours, dit tunnel de bypass, rejoignant le chemin en aval dudit élément à protéger en un noeud, dit point PM, et, dans une seconde phase, des ressources du réseau sont réservées sur chacun des liens du tunnel de bypass pour secourir ledit chemin en cas de défaillance dudit élément.
2) Méthode de protection selon la revendication 1, caractérisée en ce que lesdites ressources sur un lien du tunnel de bypass comprennent une bande passante réservée (rBP (L)) relative à ce lien.
3) Méthode de protection selon la revendication 1 ou 2, caractérisée en ce que, pour chaque élément physique dudit réseau, on détermine un groupe (SRLG) de liens dudit réseau atteints par la défaillance dudit élément physique.
4) Méthode de protection selon la revendication 3, caractérisée en ce que pour chaque lien dudit réseau, on détermine la liste, dite liste SRLG, desdits groupes auxquels il appartient.
5) Méthode de protection selon l'une des revendications précédentes, caractérisée en ce que le point PLR recherche, dans une première étape de la première phase, les tunnels de bypass existants dans le réseau susceptibles de protéger ledit élément.
<Desc/Clms Page number 20>
6) Méthode de protection selon les revendications 4 et 5, caractérisée en ce que, si l'élément à protéger est un lien, le point PLR détermine si un tunnel de bypass existant est susceptible de protéger ledit lien en vérifiant que ledit tunnel ne comprend pas ledit lien et que, la liste SRLG associée à chaque lien dudit tunnel existant et la liste SRLG associée au lien à protéger ont une intesection vide.
7) Méthode de protection selon les revendications 4 et 5, caractérisée en ce que, si l'élément à protéger est un noeud, le point PLR détermine si un tunnel de bypass existant est susceptible de protéger le noeud en vérifiant que ledit tunnel ne comprend pas ledit noeud et que la liste SRLG associée à chaque lien dudit tunnel existant et la liste SRLG associée au lien joignant le point PLR et ledit noeud ont une intesection vide.
8) Méthode de protection selon la revendication 6 ou 7, caractérisée en ce que, pour chaque tunnel de bypass existant susceptible de protéger ledit élément, dit tunnel candidat, le point PLR simule, pour chaque lien du tunnel candidat, une augmentation de la bande passante réservée sur ce lien de la valeur de la bande passante du chemin à étiquettes commutées et vérifie si la valeur de la bande passante ainsi obtenue est inférieure à une bande passante maximale (RBP (L)) réservable sur ce lien.
9) Méthode de protection selon la revendication 6 ou 7, caractérisée en ce que pour chaque tunnel de bypass existant susceptible de protéger ledit élément, dit tunnel candidat, le point PLR simule une protection dudit élément par ledit tunnel candidat et détermine, pour chaque lien dudit tunnel candidat, la plus grande bande passante à réserver sur ce lien pour supporter les tunnels de bypass passant par ce lien, y compris le tunnel candidat, en cas de défaillance d'un élément physique quelconque du réseau et que l'on vérifie si ladite plus grande bande passante est inférieure à une bande passante maximale (RBP (L)) réservable sur ce lien.
10) Méthode de protection selon la revendication 8 ou 9, caractérisée en ce que s'il n'existe aucun tunnel candidat ou si la vérification est négative pour au moins un lien de chaque tunnel candidat, le point PLR détermine un nouveau tunnel de bypass.
<Desc/Clms Page number 21>
11) Méthode de protection selon l'une des revendications précédentes, caractérisée en ce que, dans ladite seconde phase, le point PLR transmet un premier message (Path) se propageant de noeud en noeud sur le tunnel de bypass vers le point
PM et qu'un second message (Resv) est retourné le long tunnel de bypass vers le point PLR, et que lors du passage du premier ou du second message, on vérifie pour chaque lien du tunnel de bypass, qu'il est susceptible de protéger ledit élément et que lesdites ressources sont effectivement disponibles sur ce lien, et dans l'affirmative on procède à la réservation desdites ressources.
12) Message de protocole RSVP-TE ou CR-LDP destiné à être transmis lors de la seconde phase de la méthode selon l'une des revendications précédentes, caractérisé en ce qu'il comprend les champs suivants : type du tunnel de bypass, indiquant s'il protège un noeud ou un lien du chemin à commutation d'étiquettes ; adresse IP du noeud protégé, s'il s'agit d'un noeud - adresse IP du point PLR, s'il s'agit d'un lien ; adresse IP du noeud en aval dudit point PLR, s'il s'agit d'un lien ; liste SRLG du lien protégé s'il s'agit d'un lien ou du lien joignant ledit point
PLR et le noeud en aval dudit point PLR, s'il s'agit d'un noeud.
13) Message de protocole OSPF-TE ou ISIS-TE destiné à être transmis par un noeud du réseau MPLS pour la mise en oeuvre de la méthode selon l'une des revendications 1 à 11, ledit message étant relatif à un lien donné du réseau MPLS, caractérisé en ce qu'il comprend les champs suivants : - bande passante réservable à la protection sur ledit lien ; - bande passante sur ledit lien effectivement réservée à la protection ; - liste SRLG dudit lien.
14) Message de protocole OSPF-TE ou ISIS-TE destiné à être transmis par un noeud du réseau MPLS pour la mise en oeuvre de la méthode selon l'une des revendications 1 à 11, ledit message étant relatif à un tunnel de bypass du réseau MPLS, caractérisé en ce qu'il comprend les champs suivants : - adresse IP du point PM dudit tunnel de bypass ;
<Desc/Clms Page number 22>
identification du chemin emprunté par ledit tunnel de bypass ; - type dudit tunnel de bypass indiquant s'il protège un noeud ou un lien du chemin à commutation d'étiquettes ; adresse IP du noeud protégé, s'il s'agit d'un noeud ; adresse IP du point PLR et adresse IP du noeud en aval dudit point PLR, s'il s'agit d'un lien ; bande passante dudit tunnel de bypass.
FR0202437A 2002-02-21 2002-02-21 Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes Withdrawn FR2836314A1 (fr)

Priority Applications (5)

Application Number Priority Date Filing Date Title
FR0202437A FR2836314A1 (fr) 2002-02-21 2002-02-21 Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes
PCT/FR2003/000513 WO2003071745A1 (fr) 2002-02-21 2003-02-17 Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes
EP03718889A EP1476990A1 (fr) 2002-02-21 2003-02-17 Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes
US10/505,484 US20070011284A1 (en) 2002-02-21 2003-02-17 Dynamic distributed method for local protection of a label switching path
AU2003222925A AU2003222925A1 (en) 2002-02-21 2003-02-17 Dynamic distributed method for local protection of a label-switching path

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
FR0202437A FR2836314A1 (fr) 2002-02-21 2002-02-21 Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes

Publications (1)

Publication Number Publication Date
FR2836314A1 true FR2836314A1 (fr) 2003-08-22

Family

ID=27636442

Family Applications (1)

Application Number Title Priority Date Filing Date
FR0202437A Withdrawn FR2836314A1 (fr) 2002-02-21 2002-02-21 Methode dynamique et distribuee de protection locale d'un chemin a commutation d'etiquettes

Country Status (5)

Country Link
US (1) US20070011284A1 (fr)
EP (1) EP1476990A1 (fr)
AU (1) AU2003222925A1 (fr)
FR (1) FR2836314A1 (fr)
WO (1) WO2003071745A1 (fr)

Families Citing this family (62)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7234157B2 (en) * 2002-06-27 2007-06-19 Lenovo Singapore Pte Ltd Remote authentication caching on a trusted client or gateway system
US7792991B2 (en) * 2002-12-17 2010-09-07 Cisco Technology, Inc. Method and apparatus for advertising a link cost in a data communications network
US7707307B2 (en) * 2003-01-09 2010-04-27 Cisco Technology, Inc. Method and apparatus for constructing a backup route in a data communications network
US7869350B1 (en) 2003-01-15 2011-01-11 Cisco Technology, Inc. Method and apparatus for determining a data communication network repair strategy
US7646706B2 (en) * 2003-03-31 2010-01-12 Alcatel-Lucent Usa Inc. Restoration time in mesh networks
US8296407B2 (en) * 2003-03-31 2012-10-23 Alcatel Lucent Calculation, representation, and maintenance of sharing information in mesh networks
US7689693B2 (en) * 2003-03-31 2010-03-30 Alcatel-Lucent Usa Inc. Primary/restoration path calculation in mesh networks based on multiple-cost criteria
US7606237B2 (en) * 2003-03-31 2009-10-20 Alcatel-Lucent Usa Inc. Sharing restoration path bandwidth in mesh networks
US7451340B2 (en) * 2003-03-31 2008-11-11 Lucent Technologies Inc. Connection set-up extension for restoration path establishment in mesh networks
US7643408B2 (en) * 2003-03-31 2010-01-05 Alcatel-Lucent Usa Inc. Restoration time in networks
US8867333B2 (en) * 2003-03-31 2014-10-21 Alcatel Lucent Restoration path calculation considering shared-risk link groups in mesh networks
US7545736B2 (en) * 2003-03-31 2009-06-09 Alcatel-Lucent Usa Inc. Restoration path calculation in mesh networks
US7330440B1 (en) 2003-05-20 2008-02-12 Cisco Technology, Inc. Method and apparatus for constructing a transition route in a data communications network
US7864708B1 (en) 2003-07-15 2011-01-04 Cisco Technology, Inc. Method and apparatus for forwarding a tunneled packet in a data communications network
US7466661B1 (en) 2003-09-22 2008-12-16 Cisco Technology, Inc. Method and apparatus for establishing adjacency for a restarting router during convergence
US7554921B2 (en) * 2003-10-14 2009-06-30 Cisco Technology, Inc. Method and apparatus for generating routing information in a data communication network
US7580360B2 (en) * 2003-10-14 2009-08-25 Cisco Technology, Inc. Method and apparatus for generating routing information in a data communications network
US7428213B2 (en) * 2003-11-21 2008-09-23 Cisco Technology, Inc. Method and apparatus for determining network routing information based on shared risk link group information
US7366099B2 (en) * 2003-12-01 2008-04-29 Cisco Technology, Inc. Method and apparatus for synchronizing a data communications network
US7710882B1 (en) 2004-03-03 2010-05-04 Cisco Technology, Inc. Method and apparatus for computing routing information for a data communications network
JP2005260321A (ja) * 2004-03-09 2005-09-22 Nec Corp ラベルパスネットワークの迂回制御方式
US8111612B2 (en) 2004-04-02 2012-02-07 Alcatel Lucent Link-based recovery with demand granularity in mesh networks
US7500013B2 (en) 2004-04-02 2009-03-03 Alcatel-Lucent Usa Inc. Calculation of link-detour paths in mesh networks
US7848240B2 (en) * 2004-06-01 2010-12-07 Cisco Technology, Inc. Method and apparatus for forwarding data in a data communications network
US7746793B2 (en) * 2004-06-18 2010-06-29 Cisco Technology, Inc. Consistency between MPLS forwarding and control planes
US7577106B1 (en) 2004-07-12 2009-08-18 Cisco Technology, Inc. Method and apparatus for managing a transition for a class of data between first and second topologies in a data communications network
US7630298B2 (en) * 2004-10-27 2009-12-08 Cisco Technology, Inc. Method and apparatus for forwarding data in a data communications network
US7496105B2 (en) * 2004-11-05 2009-02-24 Cisco Technology, Inc. System and method for retrieving computed paths from a path computation element using encrypted objects
US7512063B2 (en) * 2004-12-14 2009-03-31 Cisco Technology, Inc. Border router protection with backup tunnel stitching in a computer network
US7515529B2 (en) * 2004-12-14 2009-04-07 Cisco Technology, Inc. Efficient mechanism for fast recovery in case of border router node failure in a computer network
US8068411B2 (en) * 2004-12-29 2011-11-29 Cisco Technology, Inc. Method and apparatus to compute local repair paths taking into account link resources and attributes
US7406032B2 (en) 2005-01-06 2008-07-29 At&T Corporation Bandwidth management for MPLS fast rerouting
US7411963B2 (en) * 2005-01-19 2008-08-12 Cisco Technology, Inc. Method for dissemination of non-routing information using the IS-IS protocol
US7933197B2 (en) 2005-02-22 2011-04-26 Cisco Technology, Inc. Method and apparatus for constructing a repair path around a non-available component in a data communications network
CN100407725C (zh) * 2005-04-15 2008-07-30 华为技术有限公司 多协议标签交换双向保护切换的实现方法
CN101146115B (zh) * 2005-04-15 2011-08-10 华为技术有限公司 多协议标签交换双向保护切换的实现方法
US7848224B2 (en) 2005-07-05 2010-12-07 Cisco Technology, Inc. Method and apparatus for constructing a repair path for multicast data
US7835312B2 (en) * 2005-07-20 2010-11-16 Cisco Technology, Inc. Method and apparatus for updating label-switched paths
US8072879B2 (en) * 2006-02-03 2011-12-06 Cisco Technology, Inc. Technique for determining whether to reestablish fast rerouted primary tunnels based on backup tunnel path quality feedback
US8208372B2 (en) * 2006-06-02 2012-06-26 Cisco Technology, Inc. Technique for fast activation of a secondary head-end node TE-LSP upon failure of a primary head-end node TE-LSP
US7940776B2 (en) * 2007-06-13 2011-05-10 Cisco Technology, Inc. Fast re-routing in distance vector routing protocol networks
US8040792B2 (en) 2007-08-02 2011-10-18 Foundry Networks, Llc Techniques for determining local repair connections
US8711676B2 (en) 2007-08-02 2014-04-29 Foundry Networks, Llc Techniques for determining optimized local repair paths
US8358576B2 (en) * 2007-10-03 2013-01-22 Foundry Networks, Llc Techniques for determining local repair paths using CSPF
GB0804920D0 (en) * 2008-03-17 2008-04-16 Ericsson Telefon Ab L M Method and apparatus for ethernet re-routing
EP2106068A1 (fr) * 2008-03-28 2009-09-30 British Telecommunications Public Limited Company Mesure de métriques de réseau spécifiques des sources de données
US7937492B1 (en) 2008-09-30 2011-05-03 Juniper Networks, Inc. LSP ping and traceroute for bypass tunnels
US8374502B2 (en) * 2009-02-27 2013-02-12 Futurewei Technologies, Inc. Open shortest path first extensions in support of wavelength switched optical networks
US8462621B2 (en) * 2009-07-27 2013-06-11 At&T Intellectual Property I, L.P. Systems and methods of multicast reconfiguration using cross-layer information
US8542578B1 (en) 2010-08-04 2013-09-24 Cisco Technology, Inc. System and method for providing a link-state path to a node in a network environment
JP5376068B2 (ja) * 2010-11-29 2013-12-25 富士通株式会社 無線通信装置および無線ネットワークにおける迂回経路探索方法
EP2466809B1 (fr) * 2010-12-20 2013-05-01 Alcatel Lucent Procédé et noeud de réseau permettant de configurer un réseau pour le transport optimisé de trafic de paquets
US9356859B2 (en) 2011-08-16 2016-05-31 Brocade Communications Systems, Inc. Techniques for performing a failover from a protected connection to a backup connection
US9083636B2 (en) * 2012-02-13 2015-07-14 Cisco Technology, Inc. System and method for multipoint label distribution protocol node protection using a targeted session in a network environment
US9634924B2 (en) * 2013-03-10 2017-04-25 Cisco Technology, Inc. Server-layer shared link risk group analysis to identify potential client-layer network connectivity loss
US9473392B2 (en) * 2013-05-06 2016-10-18 Verizon Patent And Licensing Inc. Midspan re-optimization of traffic engineered label switched paths
US10020984B1 (en) * 2014-01-10 2018-07-10 Juniper Networks, Inc. RSVP local protection signaling reduction
WO2015149358A1 (fr) 2014-04-04 2015-10-08 Telefonaktiebolaget L M Ericsson (Publ) Appareil et procede pour l'etablissement de chemin de reparation
US9590894B2 (en) * 2014-10-27 2017-03-07 Juniper Networks, Inc. Establishing label switched paths having refresh interval independent fast reroute facility protection
FR3044849A1 (fr) * 2015-12-07 2017-06-09 Orange Procede anti-micro-boucle pendant la convergence de tables de commutation
US10892983B2 (en) * 2018-07-27 2021-01-12 Cisco Technology, Inc. Shared risk link group robustness within and across multi-layer control planes
US12500833B1 (en) * 2023-03-01 2025-12-16 Google Llc Mitigation of congestion loss risk for MPLS local-protection with facility-backup

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6751190B1 (en) * 1999-05-18 2004-06-15 Cisco Technology, Inc. Multihop nested tunnel restoration
US6996065B2 (en) * 2000-07-06 2006-02-07 Lucent Technologies Inc. Dynamic backup routing of network tunnel paths for local restoration in a packet network
KR100725005B1 (ko) * 2000-11-22 2007-06-04 주식회사 케이티 다중 프로토콜 레이블 스위칭 망에서의 고속 재라우팅 방법
US6778492B2 (en) * 2002-01-17 2004-08-17 Cisco Technology, Inc. Load balancing for fast reroute backup tunnels
US7230913B1 (en) * 2002-06-11 2007-06-12 Cisco Technology, Inc. MPLS fast reroute without full mesh traffic engineering

Non-Patent Citations (5)

* Cited by examiner, † Cited by third party
Title
AWDUCHE D., BERGER L., GAN D., LI T., SRINIVANSAN V., SWALLOW G.: "RSVP-TE: Extensions to RSVP for LSP Tunnels", IETF RFC 3209, December 2001 (2001-12-01), pages 1 - 61, XP002222576, Retrieved from the Internet <URL:http://www.cs.utk.edu/~moore/RFC-PDF/rfc3209.pdf> [retrieved on 20021127] *
KODIALAM M ET AL: "Dynamic routing of locally restorable bandwidth guaranteed tunnels using aggregated link usage information", PROCEEDINGS IEEE INFOCOM 2001. THE CONFERENCE ON COMPUTER COMMUNICATIONS. 20TH. ANNUAL JOINT CONFERENCE OF THE IEEE COMPUTER ANDCOMMUNICATIONS SOCIETIES. ANCHORAGE, AK, APRIL 22 - 26, 2001, PROCEEDINGS IEEE INFOCOM. THE CONFERENCE ON COMPUTER COMMUNI, vol. 1 OF 3. CONF. 20, 22 April 2001 (2001-04-22), pages 376 - 385, XP010538718, ISBN: 0-7803-7016-3 *
MANER A ET AL: "On-demand optimization of label switched paths in MPLS networks", COMPUTER COMMUNICATIONS AND NETWORKS, 2000. PROCEEDINGS. NINTH INTERNATIONAL CONFERENCE ON LAS VEGAS, NV, USA 16-18 OCT. 2000, PISCATAWAY, NJ, USA,IEEE, US, 16 October 2000 (2000-10-16), pages 107 - 113, XP010524495, ISBN: 0-7803-6494-5 *
P. PAN, D. GAN, G. SWALLOW, JP. VASSEUR, D. COOPER, A. ATLAS, M. JORK: "Fast Reroute Extensions to RSVP-TE for LSP Tunnels", IETF INTERNET DRAFT, January 2002 (2002-01-01), pages 1 - 33, XP002222575, Retrieved from the Internet <URL:http://www.watersprings.org/pub/id/draft-ietf-mpls-rsvp-lsp-fastreroute-00.txt> [retrieved on 20021126] *
P. SRISURESH, P. JOSEPH: "TE LSAs to extend OSPF for Traffic Engineering", IETF DRAFT, 4 January 2002 (2002-01-04), pages 1 - 41, XP002222577, Retrieved from the Internet <URL:http://www.watersprings.org/pub/id/draft-srisuresh-ospf-te-02.txt> [retrieved on 20021127] *

Also Published As

Publication number Publication date
EP1476990A1 (fr) 2004-11-17
US20070011284A1 (en) 2007-01-11
AU2003222925A1 (en) 2003-09-09
WO2003071745A1 (fr) 2003-08-28

Similar Documents

Publication Publication Date Title
WO2003071745A1 (fr) Methode dynamique et distribuee de protection locale d&#39;un chemin a commutation d&#39;etiquettes
FR2836313A1 (fr) Methode de protection locale de chemins a commutation d&#39;etiquettes avec partage de ressources
EP2263353B1 (fr) Technique pour déterminer un arbre point à multipoint reliant un noeud racine à une pluralité de noeuds feuilles
EP2067317B1 (fr) Procédé de routage dans un réseau de commutation par étiquettes
EP1803258B1 (fr) Procede et dispositif de creation d&#39;un tunnel dans un reseau de telecommunication a permutation d etiquettes
EP2033380B1 (fr) Procede de routage de liens virtuels dans un reseau a commutation de trames a determinisme garanti
EP2345210B1 (fr) Gestion de topologie de routage dans un reseau
FR2931604A1 (fr) Technique de protection dans un reseau de communication en mode connecte d&#39;un arbre primaire point a multipoint.
WO2011086250A1 (fr) Liason virtuelle entre operateur de reseau
EP2070268A1 (fr) Routeur coeur apte a securiser un routeur de sortie d&#39;un systeme autonome
EP1432184B1 (fr) Dispositif de détermination de chemins de communication dans un réseau de communications à commutation d&#39;étiquettes, en présence d&#39;attributs de sélection
WO2003079596A1 (fr) Procede pour determiner une route spectrale pour une connexion donne dans un reseau de telecommunication optique
EP1650910B1 (fr) Contrôle des paramètres d&#39;une connexion Ethernet-GMPLS
EP2332293B1 (fr) Distribution de routes dans un réseau de routeurs
FR3044849A1 (fr) Procede anti-micro-boucle pendant la convergence de tables de commutation
EP2119140B1 (fr) Procede d&#39;acheminement par un routeur d&#39;un paquet de donnees dans un reseau de communication par paquets supporte par un reseau de transport
WO2018205887A1 (fr) Procédé et appareil de collecte de retard
EP2238718B1 (fr) Technique pour protéger un chemin à commutations d&#39;étiquettes en mode connecté lors d&#39;une panne affectant un noeud donné du chemin
EP1771981B1 (fr) Procede de controle de routage dans un reseau de paquets supporte par un reseau de transport
EP2198573B1 (fr) Procédé pour faire communiquer entre eux une pluralité de noeuds d&#39;extrémité à travers un réseau de communication
Oki et al. A disjoint path selection scheme with shared risk link group constraints in GMPLS networks
EP1878172B1 (fr) Controle de la reservation de ressources partagees de chemins de connexion dans un reseau de communication a commutation d&#39;etiquettes de type &#34;non paquet&#34;
EP2235893B1 (fr) Technique pour protéger un chemin à commutation d&#39;étiquettes multipoint à multipoint en mode connecté lors d&#39;une panne affectant un noeud donné du chemin
FR3164865A1 (fr) Procede d&#39;annonce de presence d&#39;equipements de telephonie mobiles
Saidi et al. Targeted distribution of resource allocation for backup LSP computation

Legal Events

Date Code Title Description
ST Notification of lapse

Effective date: 20061031