Brevet FR2857531A1 — publié le 20050114

PROCEDE POUR DETERMINER UNE ROUTE SPECTRALE DANS UN RESEAU DE TELECOMMUNICATION OPTIQUE La présente invention concerne un procédé pour déterminer une route spectrale, dans un réseau de télécommunication optique. Elle concerne plus particulièrement les réseaux optiques à multiplexage par division en longueurs d'onde WDM (Wavelength Division Multiplexing) qui utilisent une pluralité de longueurs d'onde pour transmettre simultanément plusieurs flots de données sur une même fibre optique. Les télécommunications connaissent un développement important. De plus en plus d'utilisateurs (particuliers et entreprises) transmettent un nombre croissant de messages dans les réseaux de télécommunication. En outre, ces messages comportent une quantité de plus en plus élevée d'informations, par exemple lors de l'envoi d'images. Pour répondre à cette demande grandissante en débit d'informations, les opérateurs des réseaux de télécommunication utilisent la transmission optique des signaux. Cette transmission utilise la modulation, suivant l'information à transmettre, de signaux optiques, en général produits par des lasers, puis la propagation de ces signaux modulés dans un réseau à conducteurs ou fibres optiques. La transmission optique des signaux comporte plusieurs avantages. En particulier, les atténuations du signal lors de la transmission sont moindres que dans le cas de signaux électriques et les fibres optiques ont une résistance mécanique plus élevée pour un poids plus faible que leurs équivalents électriques. Mais les principaux avantages sont la large bande passante des fibres optiques et la possibilité de faire transiter simultanément plusieurs porteuses de longueurs d'onde distinctes dans une même fibre. Cette dernière technique, dite du multiplexage en longueur d'onde, permet d'atteindre des débits d'information de l'ordre du Gigabits/s et même du Térabitsls. Pour établir une connexion dans un réseau de télécommunication optique, il faut déterminer non seulement une route spatiale constituée d'une suite de segments de route reliant le noeud de départ au noeud 2857531 2 d'arrivée, mais il faut déterminer en outre une route spectrale, puisque chaque segment peut supporter une pluralité de longueurs d'ondes constituant chacune un segment de route spectrale. Choisir une route spectrale consiste à choisir la longueur d'onde, ou les longueurs d'onde, à utiliser successivement sur différents segments, le long de la route spatiale. De manière connue, plusieurs algorithmes permettent d'affecter une longueur d'onde à un segment spatial. De tels algorithmes sont notamment décrits dans le document "wavelength Converters in Dynamically Reconfigurable WDM Networks" (Yates, J. M. , M et M. P. Rumsewicz, IEEE Communications Surveys). Une première solution consiste à utiliser un algorithme d'affectation de la première longueur d'onde disponible ( First-Fit wavelength evaluation en anglais). Une deuxième solution consiste à utiliser un algorithme d'affectation de la longueur d'onde la plus utilisée ( Most-used wavelength evaluation en anglais). La décision est prise en fonction des statistiques de réseau sur l'utilisation des longueurs d'onde. Cette deuxième solution a pour but d'optimiser l'utilisation des longueurs d'onde en remplissant les parties non utilisées des longueurs d'onde les plus utilisées. La mise en oeuvre des solutions mentionnées ci-dessus présente cependant certaines difficultés dans la mesure où elles ne sont pas adaptées pour des réseaux optiques partiellement transparents (i.e. pas de régénération par conversion de longueur d'onde sur certains noeuds du réseau) ; ces solutions supposent en effet que la conversion de longueur d'onde est possible sur chacun des noeuds du réseau (i.e. noeuds du réseau opaques). En outre, l'algorithme d'affectation de la longueur d'onde la plus utilisée impose une mise à jour de la connaissance globale de l'état du réseau, induisant dès lors un surcoût important. La présente invention vise à fournir un procédé pour déterminer une route spectrale dans un réseau de télécommunication optique susceptible d'être mis en oeuvre à bas coût, à la fois sur les réseaux optiques du type 2857531 3 transparent et/ou opaque, et permettant un paramétrage et donc une certaine flexibilité pour les utilisateurs. La présente invention propose à cet effet un procédé pour déterminer une route spectrale, dans un réseau de télécommunication optique, entre un noeud de départ et un noeud d'arrivée appartenant au dit réseau, comportant une étape de détermination, par un procédé de routage classique, d'une route spatiale reliant ledit noeud de départ au dit noeud d'arrivée, ladite route spatiale comportant une suite de segments de route, chaque segment de route reliant directement deux noeuds dudit réseau et pouvant supporter au moins une longueur d'onde ou une bande de longueurs d'onde, ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes: - extraction des longueurs d'onde ou bandes de longueurs d'onde disponibles le long de chacun desdits segments de route de ladite 15 route spatiale, - construction d'un graphe dans lequel: o les sommets sont lesdites longueurs d'onde ou bandes de longeurs d'onde disponibles pour chacun desdits segments de route, o les arcs sont les transitions entre les longueurs d'onde ou bandes de longueurs d'onde disponibles de deux sommets consécutifs, chacun desdits arcs étant affecté d'une distance correspondant à un coût de transition déterminé, détermination du plus court chemin de ce graphe par un algorithme de 25 détermination de plus court chemin. Grâce à l'invention, la détermination de la route spectrale est réalisée à partir d'une pondération par les coûts. Chaque coût peut être fixé de manière flexible par l'utilisateur qui peut ainsi privilégier un choix par rapport à un autre. Le procédé selon l'invention permet de fonctionner à la fois sur les réseaux optiques du type transparent et/ou opaque dans la mesure où un coût infini peut être associé à une transition impossible entre deux longueurs d'onde différentes passant par un noeud transparent. 2857531 4 Notons que le procédé selon l'invention s'applique aux deux types de granularité que sont la granularité associée à la commutation par longueur d'onde ou la granularité associée à la commutation par bande de longueur d'onde. Par soucis de clarté, nous ferons référence dans la suite uniquement au routage de longueurs d'onde. Avantageusement, un coût initial est associé à chacun des sommets du premier segment de route. Ce coût initial permet d'initialiser l'algorithme et correspond au coût de la transition entre le noeud de départ et chacun des sommets du premier 10 segment de route. Selon un mode de réalisation particulièrement avantageux, ledit algorithme de détermination de plus court chemin est un algorithme de Viterbi. Plusieurs types d'algorithme de plus court chemin peuvent être utilisés tels que l'algorithme de Dijkstra. Toutefois, l'algorithme de Dijkstra peut s'avérer relativement complexe et lent lorsque le nombre de noeuds devient élevé. L'utilisation du graphe selon l'invention permet d'utiliser avantageusement l'algorithme de Viterbi plus rapide et utilisé dans le décodage des codes convolutionnels (décodage correcteur d'erreurs) . L'algorithme de Viterbi revient à chercher le chemin qui est le plus favorable, c'est-à-dire le plus court par rapport à la métrique définie. II est basé sur l'argument suivant: le chemin le plus court entre deux noeuds (par exemple entre un noeud de départ i=0 et un noeud d'arrivée i=lmax) passe nécessairement à chaque instant intermédiaire j par un état s. Du fait de la nature additive de la métrique, les deux demi-chemins joignant 0 et j d'une part, j et Imax d'autre part, sont eux-même optimaux; Ainsi, pour établir le chemin optimal entre les instants 0 et Imax, on va estimer, à chaque instant j, les chemins optimaux entre le noeud de départ i=0 et tous les noeuds j. Avantageusement, ledit coût remplit au moins l'une des conditions suivantes: ledit coût de transition est infini lorsque ladite transition n'est pas possible, 2857531 5 - ledit coût de transition inclut le coût d'une nouvelle fibre optique, ledit coût de transition inclut le coût de conversion de longueur d'onde, ledit coût de transition inclut le coût de transit sur un noeud transparent. D'autres caractéristiques et avantages de la présente invention apparaîtront dans la description suivante d'un mode de réalisation de l'invention, donné à titre illustratif et nullement limitatif. Dans les figures suivantes: - La figure 1 représente un graphe pour la mise en oeuvre du procédé 10 selon l'invention, - La figure 2 représente un exemple de mise en oeuvre du procédé selon l'invention. La figure 1 représente un graphe 1 pour la détermination d'une route spectrale dans un réseau de télécommunication optique entre un noeud de 15 départ NI et un noeud d'arrivée N6 appartenant au réseau. A la réception d'une requête d'établissement de connexion, la route spatiale entre le noeud N1 et le noeud N6 est déterminée de façon connue par un algorithme de routage classique tel que l'algorithme de Dijkstra. Rappelons que l'algorithme de Dijkstra consiste à tenir à jour un ensemble E de noeuds dont la distance la plus courte au noeud de départ est déjà connue. Initialement, cet ensemble ne contient que le noeud de départ lui-même. A chaque pas de l'algorithme, un noeud supplémentaire est rajouté dans cet ensemble, jusqu'à ce qu'il contienne le noeud d'arrivée. La route spatiale ainsi déterminée comporte six noeuds NI à N6 connectés entre eux par des liaisons ou segments de routes L1 à L5. Les liaisons LI à L5 vont permettre de construire les sommets S du graphe 1. Chaque liaison Li (i variant de 1 à 5) comporte en effet n; fibres optiques, chacune des n; fibres optiques j (j variant de 1 à n;) pouvant comporter Ri longueurs d'onde. Par soucis de clarté, chaque liaison L1 à L5 a été représentée comme ayant cinq longueurs d'onde disponibles pouvant être réparties sur une ou plusieurs fibres optiques. 2857531 6 Ainsi, chaque sommet S est représenté par un triplet (i, fk, X,) , i désignant le numéro de la liaison, fk désignant la kième (k variant de 1 à ni) fibre de la liaison i et 2 désignant la lème longueur d'onde (I variant de 1 à n;,) de la fibre fk. A titre d'exemple, les sommets (3, f1, Xi) (i.e. troisième liaison, première fibre de la troisième liaison, première longueur d'onde de la première fibre de la troisième liaison) et (4, f1, X2) (i.e. quatrième liaison, première fibre de la quatrième liaison, deuxième longueur d'onde de la première fibre de la quatrième liaison) sont représentés sur la figure 1. A chaque transition entre deux sommets (i, fk, Ii) et 0+1, fk', Ir) est associé un coût de transition C([i,fk,X,]-> [i+1,fk',X,']) prédéterminé. Ainsi, le coût de transition C représenté en figure 1 désigne le coût C([3,fi,X,]-* [4,8,X2]). Les arcs sont les transitions entre les longueurs d'onde disponibles de deux sommets consécutifs et chaque arc est affecté d'un coût de transition. Notons que seules quelques transitions ont été représentées par des flèches pour illustrer le procédé selon l'invention; dans la pratique, une transition existe pour chaque couple de sommets associés respectivement à une liaison et à la liaison suivante. Chaque coût de transition peut par exemple être déterminé par les conditions suivantes: - le coût de transition est infini lorsque ladite transition n'est pas possible (cas d'un noeud transparent et d'une transition entre deux longueurs d'onde différentes), - le coût de transition inclut le coût d'une nouvelle fibre optique (on peut en effet être amené à rajouter une fibre optique pour pouvoir assurer 25 une transition car les fibres déjà installées ne permettent pas supporter l'une des deux longueurs d'onde), - le coût de transition inclut le coût de conversion de longueur d'onde (cas d'une régénération par conversion de longueurs d'onde par un noeud de type opaque), 2857531 7 - le coût de transition inclut le coût de transit sur un noeud transparent (la transition d'une longueur d'onde à une même longueur d'onde peut en effet également induire des coûts supplémentaires). Notons ici que ces coûts sont définis par l'utilisateur qui peut ainsi mettre l'accent sur l'un de ces coûts plus que sur les autres et utiliser le coût comme un paramètre de pondération lui assurant une certaine flexibilité. Une fois le graphe construit, il reste à déterminer le plus court chemin spectral pour passer du noeud de départ NI au noeud d'arrivée N6 en considérant que les distances du graphe sont constituées par les coûts précédemment cités. L'utilisation de l'algorithme de Viterbi se prête particulièrement bien à la détermination de ce chemin le plus court. Cet algorithme connu est décrit dans les documents "Principles of digital communications and coding ", (A. J. Viterbi, J. K. Omura, McGraw-Hill, 1979) et "The Viterbi algorithm" (G. D. Fomey, Proceeding of the IEEE, vol 61, no. 3, pp. 268278, March 1973). Le principe de l'algorithme de Viterbi est le suivant: On part des sommets associés à la liaison L1. On trace tous les arcs possibles à partir de ces sommets vers les sommets de la liaison L2, chaque arc ayant un coût associé. Pour chaque sommet de la liaison L2, on détermine l'arc provenant des sommets de L1 ayant le coût le plus bas. Ce coût est affecté au sommet de L2 correspondant et le triplet (1, fk, 2) correspondant au sommet de L1 associé à ce plus bas coût est mémorisé par le sommet de L2. Ainsi, chaque sommet de L2 comporte un coût minimum et un triplet de L1 associés. Cette opération est répétée pour les arcs correspondant aux transitions des sommets de L2 vers les sommets de L3, en prenant en considération les coûts initiaux des sommets de L2. Ainsi, pour chaque arc, on effectue la somme entre le coût de la transition et le coût du sommet de départ de L2. A nouveau, chaque sommet de L3 comporte un coût minimum et un triplet de L2 associés. 2857531 8 L'opération est répétée jusqu'à la liaison L5 pour laquelle chaque sommet possède donc un coût et un triplet de L4. On détermine alors le sommet de L5 ayant le coût le plus bas. Comme chaque sommet garde en mémoire le triplet de la liaison 5 précédente correspondant au coût minimum, il suffit alors de remonter du sommet de L5 au sommet de LI pour avoir le chemin spectral recherché. La figure 2 représente un exemple 2 de mise en oeuvre du procédé selon l'invention. En d'autres termes, l'exemple 2 fait suite à une demande de connexion entre un noeud NI et un noeud N4 du réseau. Le chemin spatial calculé par l'algorithme de Dijkstra est défini par le chemin N1, N2, N3 et N4. Ainsi, trois segments de route LI à L3 sont définis. Considérons une première fibre f1 et une fibre supplémentaire rajoutée f2. Supposons d'autre part que les noeuds N2 et N3 ne permettent pas la conversion de longueur d'onde et que la capacité de chacune des fibres est limitée à 3 longueurs d'onde 2\4, 12 et 13. L'ensemble des longueurs d'ondes disponibles sur chaque liaison est: - L1 = {X sur fibre 1, 12 sur fibre I} + les trois longueurs d'onde de la fibre supplémentaire. - L2 = {12 sur fibre 1, 13 sur fibre 1} + les trois longueurs d'onde de la fibre supplémentaire. - L3 = {12 sur fibre 1, 13 sur fibre 1} + les trois longueurs d'onde de la 25 fibre supplémentaire. Les coûts des transitions sont les suivants: Coût Fibre Supplémentaire = 100 (représenté par une flèche continue) - Coût Transit = 10 (représenté par une flèche en pointillé). En outre, un coût initial C11 à 015 est associé à chacun des sommets 30 du premier segment de route et correspond au coût de la transition entre le noeud de départ et chacun des sommets du premier segment de route. 2857531 9 L'algorithme de Viterbi détermine alors les éléments suivants: le sommet (2,f1,? 2) de la liaison L2 a un coût minimum de 10+10 et le sommet précédent mémorisé est le sommet (1,f1,?2) de la liaison LI. - le sommet (3,fi,2 2) dispose d'un coût minimum 10+10+10 et le sommet précédent mémorisé est le sommet (2,f1,?,2) de la liaison L2. L'algorithme de Viterbi permet donc de définir le chemin spectral comme suit: - (1,fi,12) : 12 sur la fibre 1 pour la liaison LI. - (2,fi,X2) : 21,2 sur la fibre 1 pour la liaison L2. - (3,fl,2 2) : 12 sur la fibre 1 pour la liaison L3. Bien entendu, l'invention n'est pas limitée au mode de réalisation qui vient d'être décrit. Notamment, l'invention a été décrite dans le cas de sélection de 15 longueurs d'onde mais on peut également envisager un routage par bande de longeurs d'onde. REVENDICATIONS 1. Procédé pour déterminer une route spectrale, dans un réseau de télécommunication optique, entre un noeud de départ (NI) et un noeud d'arrivée (N5) appartenant au dit réseau, comportant une étape de détermination, par un procédé de routage classique, d'une route spatiale reliant ledit noeud de départ (NI) au dit noeud d'arrivée (N5), ladite route spatiale comportant une suite de segments de route (Li), chaque segment de route reliant directement deux noeuds dudit réseau et pouvant supporter au moins une longueur d'onde ou une bande de longueurs d'onde, ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes: extraction des longueurs d'onde ou bandes de longueurs d'onde disponibles le long de chacun desdits segments de route de ladite route spatiale, construction d'un graphe dans lequel: o les sommets ([i, fk, 2 J) sont lesdites longueurs d'onde ou bandes de Iongeurs d'onde disponibles pour chacun desdits segments de route, o les arcs sont les transitions entre les longueurs d'onde ou bandes de longueurs d'onde disponibles de deux sommets consécutifs, chacun desdits arcs étant affecté d'une distance correspondant à un coût de transition déterminé, détermination du plus court chemin de ce graphe par un algorithme de détermination de plus court chemin. 2. Procédé selon la revendication précédente caractérisé en ce qu'un coût initial est associé à chacun des sommets du premier segment de route. 3. Procédé selon l'une des revendications précédentes caractérisé en ce que ledit algorithme de détermination de plus court chemin est un algorithme de Viterbi. 4. Procédé selon l'une des revendications précédentes caractérisé en ce que ledit coût remplit au moins l'une des conditions suivantes: 2857531 11 ledit coût de transition est infini lorsque ladite transition n'est pas possible, ledit coût de transition inclut le coût d'une nouvelle fibre optique, ledit coût de transition inclut le coût de conversion de longueur d'onde, - ledit coût de transition inclut le coût de transit sur un noeud transparent.