Brevet FR2849560A1 — publié le 20040702

La présente invention concerne un procédé de calcul de chemins contraints pour un réseau de transmission et, en particulier, un procédé pour calculer des 5 chemins contraints pour un réseau de transmission fondé sur le système de protection de hiérarchie numérique synchrone (SDH)/réseau optique synchrone (SONET). Les réseaux de transmission de l'art antérieur reposent principalement sur les normes SDH/SONET. Dans 10 la pratique, une configuration de service de terminal à terminal est réalisée manuellement conformément aux exigences d'utilisateurs. Pour augmenter les possibilités d'exploitation d'un réseau de transmission, on a proposé une technologie de réseau de 15 transmission automatique permettant une configuration de service de terminal à terminal automatique. Le procédé technique le plus proche de la présente invention est l'algorithme de priorité au chemin contraint le plus court (CSPF) utilisé dans le domaine 20 de l'ingénierie du trafic dans le monde entier. Le principe de base de l'algorithme CSPF est le calcul d'un chemin optimisé de terminal à terminal grâce à un algorithme de chemin le plus court en fonction de contraintes. Les principales contraintes concernées 25 sont la largeur de bande, le groupe administratif et les noeuds inhibés, entre autres. L'algorithme CSPF utilise deux bases de données: PATHS et TENT. La base de données PATHS stocke les informations de l'arborescence de chemin le plus court, 30 tandis que la base de données TENT stocke des informations concernant des noeuds provisoires pour lesquels des tentatives ont été effectuées avant de trouver le chemin raccourci. Les informations nodales ne sont ajoutées à la base de données PATHS que lorsque 35 le chemin raccourci jusqu'à un noeud a été trouvé. Plus précisément, l'algorithme CSPF comporte les étapes suivantes. 1) Entrée d'un noeud effectuant le calcul dans PATHS (il ne peut exister aucun chemin plus court 5 jusqu'à lui-même), TENT étant pré-chargé à partir de la base de données de contiguté locale. 2) Lorsque le noeud est entré dans PATHS, examen des liaisons à partir du noeud vers chacun de ses voisins. Si un noeud voisin est déjà dans PATHS, ce 10 nouveau chemin sera plus long et est donc ignoré. Si un noeud voisin est dans TENT et si le nouveau chemin est plus court, l'ancien chemin est remplacé par le nouveau. Si le nouveau chemin a la même longueur que celui qui se trouve dans TENT, le noeud voisin a alors 15 un chemin équivalent. Si un noeud voisin n'est pas dans TENT, les liaisons et les noeuds qui ne satisfont pas aux conditions de contrainte de chemin de commutation repéré (LSP) sont alors supprimés, et les noeuds correspondant respectivement aux liaisons qui satisfont 20 aux conditions de contrainte LSP sont entrés dans TENT. 3) Transfert des noeuds à moindre cot de TENT dans PATHS. 4) Lorsque TENT est vide ou que le noeud à moindre cot présent dans TENT est un noeud de destination, le 25 calcul d'acheminement est alors terminé et le résultat du calcul est fourni en sortie, sinon le traitement revient à l'étape 2). Le principal inconvénient de la technique antérieure ci-dessus réside en ce que, comme elle 30 repose sur une configuration de réseau maillé sans tenir compte du mécanisme de protection inhérent du réseau de transmission, le chemin le plus court satisfaisant aux exigences de protection SDH/SONET ne peut pas être obtenu par la méthode de calcul de chemin 35 selon l'art antérieur. On a par conséquent besoin d'un procédé pour calculer un chemin de service de terminal à terminal contraint optimisé pour un réseau de transmission. Pour qu'un réseau de transmission soit doté d'une capacité 5 de configuration de service automatique, il faut que les dispositifs de réseau optique intelligents soient capables de calculer automatiquement un chemin de service de terminal à terminal optimisé. Toutefois, les réseaux de transmission d'origine ont perfectionné leur 10 capacité de protection; par exemple, ils sont dotés de la capacité de protection de section multiplex fondée sur un protocole de commutation de protection automatique, de sorte qu'il est nécessaire que les dispositifs de réseau optique intelligents soient 15 compatibles avec la capacité de protection d'origine du réseau de transmission. La présente invention a précisément pour but de proposer un procédé de calcul de chemins contraints fondé sur la protection SDH/SONET pour un réseau de 20 transmission. Le procédé permet de calculer automatiquement le chemin le plus court satisfaisant aux normes de protection SDH/SONET en fonction du type de protection du réseau de transmission et, par conséquent, de réduire de manière efficace des temps de 25 calcul répétitif. Pour atteindre ce but et selon la présente invention, un procédé de calcul de chemins contraints pour un réseau de transmission est caractérisé en ce qu'il comprend les étapes qui consistent à: a) collecter des informations d'attributs de la liaison à laquelle chaque noeud est relié et obtenir les informations concernant l'entité de protection à laquelle la liaison appartient; b) acheminer par inondation les informations d'attributs collectées jusqu'aux autres noeuds conformément à un protocole; c) combiner tous les noeuds en fonction des 5 informations des entités de protection auxquelles les liaisons respectives appartiennent et former la structure topologique de chaque entité de protection de l'ensemble du réseau et des informations d'attributs de liaison correspondantes; et d) calculer les chemins contraints pour le réseau de transmission. Conformément à ce procédé, l'étape a) peut également comprendre l'étape qui consiste à obtenir la largeur de bande utilisable de la liaison, la capacité 15 de protection de la liaison, l'adresse de protocole Internet (IP) d'interface locale et l'adresse IP d'interface distante de la liaison. La collecte des informations d'attributs de la liaison à laquelle chaque noeud est relié, au cours de 20 l'étape a), peut aussi comprendre l'étape qui consiste à consulter les informations de configuration d'utilisateurs de dispositifs de réseau optique par l'intermédiaire d'une interface logicielle spécifique. Conformément à une caractéristique particulière de 25 l'invention, le protocole de l'étape b) est le protocole de priorité au chemin ouvert le plus court (OSPF). Dans le procédé de l'invention, l'acheminement par inondation des informations d'attributs collectées 30 jusqu'aux autres noeuds conformément à un protocole au cours de l'étape b) peut être réalisé par l'intermédiaire des paquets d'annonce d'état de liaison (LSA). L'étape d) du procédé de l'invention peut 35 comprendre les étapes qui consistent à: dl) créer PATHS pour stocker les informations concernant l'arborescence de chemin le plus court et TENT pour stocker les informations concernant des noeuds provisoires pour lesquels des tentatives ont été faites avant de trouver le chemin raccourci; d2) mettre le noeud effectuant le calcul dans PATHS, et pré-charger TENT à partir de la base de données de contiguté locale; d3) examiner les liaisons à partir du noeud vers 10 chacun des noeuds voisins de celui-ci, lorsque le noeud est mis dans PATHS; et si un noeud voisin est déjà dans PATHS, ignorer alors ce nouveau chemin, car il est plus long; si un noeud voisin est dans TENT et si le nouveau chemin est 15 plus court, remplacer l'ancien chemin par le nouveau; si le nouveau chemin a la même longueur que celui qui se trouve dans TENT, le noeud voisin a alors un chemin équivalent; si un noeud voisin n'est pas dans TENT, supprimer alors les liaisons et les noeuds qui ne 20 satisfont pas aux conditions de contrainte de chemin de commutation repéré (LSP) et entrer les noeuds correspondant respectivement aux liaisons qui satisfont aux conditions de contrainte LSP dans TENT; d4) transférer les noeuds à moindre cot de TENT 25 dans PATHS; et d5) terminer le calcul d'acheminement lorsque TENT est vide ou que le noeud de destination est déjà dans PATHS. Le procédé de l'invention peut également comprendre 30 les étapes qui consistent à: d6) sélectionner le chemin le plus approprié en fonction d'une politique, s'il existe des chemins à cot égal; d7) attribuer une tranche de temps congruente à 35 tous les noeuds présents sur l'anneau de protection de section multiplex (MSP), si le service passe par un anneau MSP; et d8) s'il est nécessaire de fournir en sortie des chemins de protection simultanément, fournir les 5 chemins de protection sur la base de la topologie de protection de hiérarchie numérique synchrone/réseau optique synchrone (SDH/SONET) conformément aux caractéristiques de l'anneau de protection. L'étape d3 du procédé de l'invention peut également 10 comprendre les étapes qui consistent à: si une protection de type 1:1 est requise, calculer le chemin de protection en fonction de l'anneau de protection MSP ou de la liaison de protection MSP, les noeuds qui peuvent être entrés dans TENT pouvant être 15 ceux de l'anneau de protection MSP ou de la liaison de protection MSP; et lors d'un passage par l'anneau de protection, entrer tous les noeuds qui satisfont aux conditions de contrainte de service et aux exigences en matière de 20 protection sur l'anneau de protection dans TENT. En résumé, l'invention offre les avantages suivants: le chemin contraint le plus court satisfaisant aux conditions de contrainte peut être calculé en fonction du type de protection du réseau de 25 transmission, et, étant donné qu'une topologie de protection est pré-calculée, les temps de calcul répétitif peuvent être réduits et les chemins contraints peuvent être calculés en temps réel. Ce qui précède, ainsi que d'autres buts, 30 caractéristiques et avantages de la présente invention, ressortira plus clairement de la description détaillée suivante d'un mode de mise en oeuvre proposé à titre d'exemple nullement limitatif en référence aux dessins annexés dans lesquels: la figure l est un schéma fonctionnel représentant un algorithme de chemins contraints pour un réseau de transmission, selon la présente invention; et la figure 2 est une représentation schématique 5 d'une procédure d'acheminement par inondation selon la présente invention. Le procédé technique selon la présente invention comprend principalement deux parties, à savoir la distribution et la combinaison d'informations 10 topologiques d'entités protégées, et le calcul de chemins contraints à partir de la topologie de protection SDH/SONET. La distribution des informations topologiques des entités protégées est mise en oeuvre grâce à la 15 procédure d'acheminement par inondation du protocole de priorité au chemin ouvert le plus court (OSPF) qui est un protocole de passerelle interne. En particulier, les informations d'entités protégées, telles que les informations relatives à l'anneau de protection auquel 20 une liaison particulière appartient, sont stockées dans une annonce d'état de liaison (LSA) et acheminées par inondation en tant qu'attributs de la liaison. La procédure d'acheminement par inondation satisfait aux exigences de la demande de commentaires (RFC) 2328. Une 25 fois que le noeud du réseau a obtenu les informations d'attributs de liaisons de l'ensemble du réseau, tous les noeuds sont combinés en fonction des numéros des entités protégées auxquelles chaque liaison appartient respectivement; une topologie des entités protégées de 30 l'ensemble du réseau est établie et des informations d'attributs de liaisons correspondantes sont obtenues. Ici, la topologie est représentée par une liste liée établie à partir des relations d'interconnexion entre les noeuds. Comme cela est représenté sur la figure 1, une procédure complète de calcul de chemins contraints comprend les quatre étapes suivantes. Premièrement, des informations d'attributs de 5 liaisons correspondant directement aux informations nodales sont collectées. Les informations d'attributs d'une liaison comprennent la largeur de bande de la liaison, la capacité de protection de la liaison, l'adresse IP d'interface locale et l'adresse IP 10 d'interface distante. En particulier, le numéro d'entité de protection de l'anneau de protection de section multiplex (MSP) auquel la liaison appartient, c'est-à-dire l'identificateur (ID) du groupe de protection, constitue l'une des informations d'attributs de liaisons les plus importantes qui doivent être collectées. Le traitement spécifique de collecte consiste à consulter les informations de configuration d'utilisateurs des dispositifs de réseau optique par l'intermédiaire d'une interface logicielle 20 spécifique. Deuxièmement, la procédure d'acheminement par inondation est mise en oeuvre strictement en conformité avec le protocole de priorité au chemin ouvert le plus court (OSPF) qui est décrit en détail au chapitre 13 de 25 la demande de commentaires (RFC) 2328 proposée par le groupe de travail Internet (IETF). En résumé, la procédure d'acheminement par inondation est une procédure qui distribue les informations collectées appelées annonce d'état de liaison (LSA) aux autres 30 noeuds. Troisièmement, comme cela est représenté sur la figure 2, tout élément de réseau optique (ONE) du réseau peut obtenir des informations de groupe de protection de toutes les liaisons du réseau grâce à la 35 procédure d'acheminement par inondation. Les informations d'entités protégées, telles que les informations relatives à l'anneau de protection auquel une liaison particulière appartient, sont stockées dans une LSA et acheminées par inondation en tant 5 qu'attributs de la liaison. Par conséquent, une fois l'acheminement par inondation terminé, chacun des noeuds du réseau est en mesure d'obtenir toutes les informations d'attributs des liaisons de l'ensemble du réseau. Puis, tous les noeuds sont combinés en fonction 10 des numéros des entités protégées auxquelles chaque liaison appartient respectivement; une topologie des entités protégées de l'ensemble du réseau est élaborée et les informations d'attributs de liaisons correspondantes sont obtenues. La topologie est 15 représentée par une liste liée fonction des relations de connexion entre les noeuds. Quatrièmement enfin, une fois que la topologie de protection a été combinée, un processus de calcul de chemins contraints peut être mis en oeuvre sur la base 20 de la norme de protection de hiérarchie numérique synchrone (SDH) . Plus précisément, l'algorithme est exécuté de la manière suivante. La base de données PATHS stocke les informations relatives à l'arborescence du chemin le plus court, 25 tandis que la base de données TENT stocke les informations relatives aux noeuds provisoires pour lesquels des tentatives ont été effectuées avant de trouver le chemin raccourci. La base de données TENT est un ensemble trié et son tri est fondé sur une 30 valeur de cot. 1) Entrée d'un noeud effectuant le calcul dans PATHS (il ne peut pas exister de chemin plus court jusqu'à lui) , tandis que TENT est chargée préalablement à partir de la base de données de contiguté locale. 2> Lors de l'entrée du noeud dans PATHS, examen des liaisons à partir du noeud vers chacun des voisins de celui-ci. Si un noeud voisin est déjà dans PATHS, ce nouveau chemin sera plus long et est donc ignoré. Si un 5 noeud voisin est dans TENT et si le nouveau chemin est plus court, l'ancien chemin est remplacé par le nouveau. Si le nouveau chemin a la même longueur que celui qui se trouve dans TENT, le noeud voisin a alors un chemin équivalent. Si un noeud voisin n'est pas dans 10 TENT, les liaisons et les noeuds qui ne satisfont pas aux conditions de contrainte LSP sont supprimés et les noeuds correspondant respectivement aux liaisons qui satisfont aux conditions de contrainte LSP sont entrés dans TENT. Si la protection requise est de type 1:1, il 15 est nécessaire de calculer le chemin de protection à partir de l'anneau de protection MSP ou de la liaison de protection MSP. Dans ce cas, les noeuds qui peuvent entrés dans TENT peuvent être ceux qui se trouvent sur l'anneau de protection MSP ou sur la liaison de 20 protection MSP. En outre, lors du passage par l'anneau de protection, d'autres noeuds satisfaisant aux conditions de contrainte de service et aux exigences en matière de protection sur l'anneau de protection sont entrés dans TENT. 3) Transfert des noeuds à cot moindre de TENT dans PATHS. 4) Lorsque la base de données TENT est vide ou que le noeud de destination est déjà présent dans la base de données PATHS, le calcul d'acheminement est alors 30 terminé. 5> S'il existe des chemins à cot égal, le chemin le plus approprié est alors sélectionné en fonction d'une politique particulière. S'il existe plusieurs chemins à cot égal vers la même destination, un seul 35 chemin approprié doit être sélectionné comme résultat il du calcul. Actuellement, il existe trois politiques de sélection, à savoir, sélection au hasard, priorité au taux de largeur de bande restante maximum et priorité au taux de largeur de bande restante minimum. 6) Si le service passe par un anneau MSP, une tranche de temps congruente doit alors être attribuée à tous les noeuds présents sur l'anneau MSP. Ceci s'explique par le fait qu'en cas de défaillance nodale, une reprise automatique après défaillance ne peut être 10 mise en oeuvre que lorsque les tranches de temps des noeuds de l'anneau MSP sont uniques, de sorte que le chemin calculé doit satisfaire à cette exigence. Toutes les tranches de temps de tous les noeuds de l'anneau depuis le noeud d'entrée jusqu'au noeud de sortie sont 15 examinées et la tranche de temps congruente est sélectionnée. Si aucune tranche de temps de congruente ne peut être sélectionnée, le chemin ne peut pas être utilisé. 7) Lorsque des chemins de protection doivent être 20 fournis en sortie simultanément, les chemins de protection fondés sur la topologie de protection SDH/SONET sont fournis conformément aux caractéristiques des anneaux de protection. Actuellement, la fourniture en sortie d'un chemin de 25 protection vise principalement l'anneau de protection MSP. Lorsque le chemin fonctionnel a été calculé, s'il est nécessaire de connaître davantage d'informations sur le chemin de protection, celui-ci peut être fourni conformément à l'anneau de protection que le chemin 30 fonctionnel emprunte. Au départ, le chemin de protection d'un anneau de protection MSP est constitué par l'autre moitié d'anneau sans couverture par le chemin fonctionnel. Bien que la description précédente ait porté sur 35 une forme de mise en oeuvre particulière de la présente invention, celle-ci n'est bien entendu pas limitée à l'exemple spécifique décrit et illustré ici, et l'homme de l'art comprendra aisément qu'il est possible d'y apporter de nombreuses variantes et modifications sans pour autant sortir du cadre de l'invention. REVENDICATIONS 1. Procédé de calcul de chemins contraints pour un réseau de transmission, caractérisé en ce qu'il comprend les étapes qui consistent à: a) collecter des informations d'attributs concernant la liaison à laquelle chaque noeud est relié et obtenir les informations relatives à l'entité de protection à laquelle la liaison appartient; b) acheminer par inondation les informations d'attributs collectées jusqu'aux autres noeuds conformément à un protocole; c) combiner tous les noeuds en fonction des informations relatives aux entités de protection 15 auxquelles les liaisons respectives appartiennent et former la structure topologique de chaque entité de protection de l'ensemble du réseau et des informations d'attributs de liaisons correspondantes; et d) calculer les chemins contraints pour le réseau 20 de transmission. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape a) comprend également l'étape qui consiste à obtenir la largeur de bande utilisable de la liaison, la capacité de protection de la liaison, 25 l'adresse de protocole Internet (IP) d'interface locale et l'adresse IP d'interface distante de la liaison. 3. Procédé selon la revendication i ou 2, caractérisé en ce que la collecte d'informations d'attributs concernant la liaison à laquelle chaque 30 noeud est relié au cours de l'étape a) comprend également l'étape qui consiste à consulter les informations de configuration d'utilisateurs de dispositifs de réseau optique par l'intermédiaire d'une interface logicielle spécifique. 4. Procédé selon la revendication 1, caractérisé en ce que le protocole utilisé au cours de l'étape b) est le protocole de priorité au chemin ouvert le plus court (OSPF). 5. Procédé selon la revendication 1, caractérisé en ce que l'acheminement par inondation des informations d'attributs collectées jusqu'aux autres noeuds conformément à un protocole au cours de l'étape b) s'effectue par l'intermédiaire des paquets d'annonce 10 d'état de liaison (LSA). 6. Procédé selon la revendication 1, caractérisé en ce que l'étape d) comprend les étapes suivantes qui consistent à: dl) créer une base de données PATHS pour stocker 15 les informations relatives à l'arborescence de chemin le plus court et la base de données TENT pour stocker les informations de noeuds provisoires pour lesquels des tentatives ont été effectuées avant de trouver le chemin raccourci; d2) entrer le noeud effectuant le calcul dans PATHS, et pré-charger TENT à partir de la base de données de contiguté locale; d3) examiner les liaisons à partir du noeud vers chacun des noeuds voisins de celui-ci, lors de l'entrée 25 du noeud dans PATHS; et si un noeud voisin est déjà dans PATHS, ignorer alors ce nouveau chemin car il est plus long; si un noeud voisin est dans TENT et si le nouveau chemin est plus court, remplacer l'ancien chemin par le nouveau; 30 si le nouveau chemin a la même longueur que celui qui se trouve dans TENT, le noeud voisin a alors un chemin équivalent; si un noeud voisin n'est pas dans TENT, supprimer alors les liaisons et les noeuds qui ne satisfont pas aux conditions de contrainte de chemin de 35 commutation repéré (LSP) et entrer les noeuds correspondant respectivement aux liaisons qui satisfont aux conditions de contrainte LSP dans TENT; d4) transférer les noeuds à moindre cot de TENT dans PATHS; et d5) terminer le calcul d'acheminement lorsque TENT est vide ou que le noeud de destination est déjà dans PATHS. 7. Procédé selon la revendication 6, caractérisé en ce qu'il comprend également les étapes qui 10 consistent à: d6) sélectionner le chemin le plus approprié conformément à une politique s'il existe des chemins à cot égal; d7) attribuer une tranche de temps congruente à 15 tous les noeuds présents sur l'anneau de protection de section multiplex (MSP), si le service emprunte un anneau MSP; et d8) s'il est nécessaire de fournir en sortie des chemins de protection simultanément, fournir les 20 chemins de protection conformément à la topologie de protection de hiérarchie numérique synchrone SDH/réseau optique synchrone SONET en fonction des caractéristiques de l'anneau de protection. 8. Procédé selon la revendication 6, caractérisé 25 en ce que l'étape d3) comprend également les étapes qui consistent à' si une protection de type 1:1 est requise, calculer le chemin de protection en fonction de l'anneau de protection MSP ou de la liaison de protection MSP, les 30 noeuds pouvant être entrés dans TENT étant ceux présents sur l'anneau de protection MSP ou sur la liaison de protection MSP; et lors du passage par l'anneau de protection, entrer tous les noeuds qui satisfont aux conditions de contrainte de service et aux exigences en matière de protection de l'anneau de protection dans TENT.