Brevet FR2784835A1 — publié le 20000421

ROUTAGE DES APPELS SELON LES BANDES PASSANTES DANS UN RESEAU DE TELECOMMUNICATIONS La présente invention concerne les réseaux de télécommunications, et plus particulièrement le routage des appels dans un réseau de télécommunications, notamment dans un réseau privé, dans lequel les appels présentent différentes bandes passantes. Les réseaux privés de télécommunications sont formés de noeuds de communication, reliés entre eux par des arcs ou artères acheminant les 1i0 communications et/ou la signalisation. J. Eldin et K. P. Lathia, Le RNIS appliqué au Centrex et aux réseaux privés virtuels contient une description des réseaux privés physiques et des réseaux privés virtuels. Comme expliqué dans ce document, dans un réseau privé physique, les différents sites ou noeuds sont reliés par des circuits spécialisés, tandis que dans un réseau privé virtuel, chaque noeud est relié au 1 5 commutateur local le plus proche du réseau public, o un logiciel approprié établit les liaisons à la demande. Deux variantes de réseau privé virtuel existent: on peut d'une part prévoir des liaisons semi-permanentes, qui sont établies sans numérotation, dès que l'un des noeuds a besoin du circuit, et qui relient toujours les deux mêmes points. Ce peut être notamment le cas pour des liaisons de signalisation, dans une application sur un réseau numérique à intégration de service. On peut d'autre part prévoir des liaisons commutées, qui ne peuvent être établies que par numérotation. Dans la suite de la description, on considère des réseaux privés physiques ou virtuels, formés de noeuds reliés par des artères, qui peuvent être de tout type: des artères comprenant des liaisons dédiées, ou des artères formées en empruntant le un réseau externe; celui-ci peut être de type quelconque - le réseau public commuté, un réseau public mobile terrestre, un réseau numérique à intégration de service, un autre réseau privé, etc. Dans les réseaux de télécommunications se pose le problème du routage des communications, i. e. du choix d'urnacheminement des artères permettant d'acheminer une communication à travers le réseau, le cas échéant avec des débordements vers un réseau externe. Un tel routage des communications a pour but de permettre l'acheminement d'une communication, tout en cherchant à répartir la charge des communications à travers le réseau, De façon connue en soi, on procède à des calculs de routage en définissant une fonction de coût pour les artères du réseau. Cette fonction permet d'affecter à chaque artère un coût représentatif du risque de blocage de l'artère; on peut choisir une fonction de coût calculée comme le rapport entre les ressources requises et les ressources disponibles sur l'artère: coût:= ressources requises / ressources disponibles. Le meilleur routage est dans ce cas celui qui minimise la somme des coûts des artères composant le routage. On procède habituellement à un calcul de routage au moment de l'établissement d'une communication, de sorte à acheminer la communication. Un problème nouveau auquel l'invention apporte une solution est celui de la fréquence des calculs de routage. En effet, dans la solution de l'art antérieur décrite plus haut, le coût d'un routage sur une artère donnée dépend des ressources requises, et varie donc d'une communication à l'autre. Il est de ce fait nécessaire de répéter un calcul de routage pour chaque nouvelle communication, même si l'on a effectué auparavant un routage entre les mêmes noeuds d'origine et de destination. Ce problème n'apparaît pas dans l'art antérieur, o le routage est considéré comme naturel. Par ailleurs, dans les réseaux privés se pose le problème de la gestion des bandes passantes. En effet, dans la mesure o les réseaux acheminent des types de communications différents - voix, données, ou autres -, différents protocoles proposent, comme une qualité de service, des communications présentant des bandes passantes différentes. C'est par exemple le cas des protocoles X25, Frame relay ou circuit Nx64. Certains de ces protocoles, comme par exemple les protocoles X25 ou Frame Relay autorisent un repli sur des bandes passantes inférieures si la bande passante n'est pas disponible. Un autre problème nouveau auquel l'invention apporte une solution est celui de la gestion des bandes passantes dans le routage des communications. Les solutions de l'art antérieur n'apportent aucune garantie sur la bande passante dans l'établissement d'une communication, etproposent au mieux un repli sur une bande passante plus étroite. L'invention propose un procédé de routage d'une communication, qui permette une gestion efficace des bandes passantes, en permettant de garantir une qualité de service. La solution de l'invention permet aussi de limiter le nombre et la fréquence des calculs de routage. Pour cela, I'invention propose un procédé de routage d'une communication dans un réseau avec une pluralité de noeuds reliés par des artères, comprenant le calcul du coût de différentes routes pour d'acheminer la communication, et le choix d'une route en fonction du coût, dans lequel le coût d'une route est fonction d'une part de la bande passante disponible sur les artères constituant la route, et d'autre part des ressources disponibles sur les dites artères. Dans un mode de mise en ceuvre, le coût d'une route est fonction de la somme des coûts des artères constituant la route, et le coût d'une artère est un vecteur présentant une première composante fonction de la bande passante disponible sur l'artère, et une composante fonction des ressources disponibles sur l'artère. Dans ce cas, la deuxième composante présente avantageusement une i 5 valeur constante au-delà d'une quantité prédéterminée de ressources disponibles. De préférence, la deuxième composante est une fonction présentant un nombre fini de valeurs possibles. Dans un autre mode de mise en ceuvre, la deuxième composante est une fonction décroissante de la quantité de ressources disponibles. Avantageusement, la première composante est une fonction décroissante de la bande passante disponible. De préférence, la première composante est une fonction présentant une valeur nulle si la bande passante est supérieure ou égale à la bande passante requise pour une communication, et une valeur infinie si la bande passante disponible est inférieure à la bande passante requise. Dans un autre mode de mise en oeuvre de l'invention, la première composante est une fonction présentant une valeur nulle si la bande passante est supérieure ou égale à la bande passante requise pour une communication, et une valeur égale à la différence entre la bande passante requise et la bande passante disponible si la bande passante disponible est inférieure à la bande passante requise. De préférence, I'étape de choix s'effectue de sorte à minimiser le coût du routage, pour une relation d'ordre danslaquelle un premier vecteur est inférieur à un second vecteur si la première composante du premier vecteur est inférieure à la première composante du second vecteur, et en cas d'égalité des premières composantes, si la deuxième composante du premier vecteur est inférieure à la deuxième composante du deuxième vecteur. Le vecteur somme d'un premier et d'un deuxième vecteurs est avantageusement défini comme le vecteur dont la première composante est égale à la plus petite des premières composantes des dits premier et second vecteurs, et dont la deuxième composante est égale à la somme des deuxièmes composantes des premier et second vecteurs. Dans un mode de mise en oeuvre, l'étape de calcul des différentes routes s'effectue par application de l'algorithme de Dijkstra. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description qui suit de modes de réalisation de l'invention, donnée à titre d'exemple et en référence aux dessins annexés, dont la figure unique montre un graphe de la composante de charge du vecteur de coût selon un mode de réalisation de l'invention; L'invention propose, dans un réseau de télécommunications, de prendre en compte la bande passante pour la définition du coût et le calcul des routages. Elle permet au réseau de garantir la bande passante requise, si elle est disponible, ou une bande passante plus grande, tout en minimisant le nombre de noeuds et d'artères que comprend le routage. Pour cela, I'invention propose de considérer une fonction de coût Cost présentant une forme vectorielle, i. e. présentant deux composantes indépendantes; ce vecteur de coût présente une composante qui est une fonction de la bande passante libre sur une artère, et une composante fonction de la charge de l'artère. Le vecteur de coût peut donc présenter la forme Cost:= (BandCost; LoadCost) La première composantfe BandCost est la composante fonction de la bande disponible sur l'artère. Elle permet de tenir compte pour le calcul d'un routage dans le réseau privé, non seulement de la charge des artères, mais aussi de la bande disponible sur l'artère. La If inïtion dce liapremière composante est expliquée plus en détail en référence à des exemples dans la suite de la description. La deuxième composante LoadCost est fonction de la charge de l'artère, et est décrite plus en détail dans la suite en référence à la figure. Pour un routage possible d'un appel, le vecteur de coût est défini par itération, en sommant les vecteurs de coût définis sur chacune des artères et chacun des débordements constituant le routage envisagé. On définit donc uniquement le vecteur de coût entre deux noeuds, comme ci- dessus, ainsi que la fonction de somme des deux vecteurs. Cette somme peut se définir comme suit: Costl + Cost2:= (Min[BandCostl; BandCost2]; LoadCostl + LoadCost2) Autrement dit, lorsque l'on effectue la somme des vecteurs de coût sur deux artères, la première composante qui est la composante représentative de la bande passante est égale à la bande passante disponible sur le routage formé des deux artères. C'est donc la valeur inférieure des bandes passantes des deux artères, ce qui dans la formule ci-dessus est représenté par la fonction Min. La deuxième composante d'un vecteur coût est représentative de la charge d'une artère. La deuxième composante de la somme de deux vecteurs coûts est égale à la somme des deuxièmes composantes des vecteurs sommés. Intuitivement, ceci se traduit par le fait qu'indépendamment de la bande passante, le coût pour emprunter un routage formé de deux artères est égal à la somme des coûts de ces deux artères. La définition d'un tel vecteur coût pour une artère, et la définition d'une somme dans l'espace vectoriel correspondant permet d'affecter à chaque routage dans le réseau un coût. L'invention propose une relation d'ordre dans l'espace vectoriel des coûts, de sorte à pouvoir comparer des routages et définir un "meilleur" routage. Celle relation d'ordre est définie de la façon suivante: Cost1 représentative de la charge est la plus faible. Ces définitions permet:ten uhncalcul des différents routages possibles, et une comparaison des différents routages pour en choisir un. La valeur de la première composante peut varier en fonction des protocoles utilisés. On décrit maintenant un mode de réalisation de l'invention, adapté à des protocoles avec repli ou régression, comme par exemple X25. Dans ce cas, la première composante du vecteur de coût dépend du routage calculé; autrement dit, un calcul de routage est effectué entre un noeud d'origine et un noeud de destination, pour une valeur de bande passante requise brequise. La première composante BandCost pour une artère donnée présentant une bande passante disponible bdispo est alors BandCost:= 0 si bdispo 2 brequise et BandCost: brequise - bdispo si bdispo un coût minimal. Si la bande requise n'est pas disponible, on cherche à minimiser le repli, indépendamment du coût. Il est clair encore une fois qu'une modification de la relation d'ordre ou de la définition de la première composante fonction de la charge permet de changer les objectifs recherchés. On décrit maintenant un deuxième mode de réalisation adapté à des protocoles du type N x 64, dans lequel le repli ou régression n'est pas autorisé. Dans ce cas, avec les mêmes notations que ci-dessus, on peut définir la première composante du vecteur coût comme suit: BandCost: 0 si bdispo > brequise et BandCost:= si bdispo de rechercher les routages de coût minimal susceptibles d'acheminer un appel. Dans un troisième mode de réalisation, I'invention propose simplement de considérer que la première composa-nteéest éga[e à l'opposée de la bande passante disponible sur l'artère, i. e. __ BandCost:= - bdispo Dans ce cas, I'invention permet simplement de chercher le routage présentant la bande passante la plus importante, et, à bande passante égale, le coût moindre. Dans tous les cas, on peut utiliser l'algorithme de Dijkstra pour déterminer un routage de l'appel qui minimise le vecteur de coût défini plus haut, en tenant compte de la bande passante requise. L'algorithme de Dijkstra est décrit dans les ouvrages d'algorithmique, et est connu pour trouver dans un graphe valué un plus court chemin entre deux noeuds. Dans l'application de cet algorithme à la présente invention, les noeuds du graphe sont formés des noeuds du réseau. Les trajets entre les noeuds sont formés des artères du réseau privé, ou en cas de débordement possible, des débordements par un réseau externe. La distance est le vecteur de coût défini plus haut, et la relation d'ordre classique dans les réels est remplacée dans l'application de l'algorithme par la relation d'ordre définie elle aussi plus haut. On peut aussi utiliser pour le calcul des routages de l'invention des algorithmes analogues à l'algorithme de Dijkstra, qui permettent aussi de trouver un plus court chemin. On peut citer à titre d'exemple l'algorithme de Bellman ou l'algorithme de Floyd; on notera que l'algorithme de Bellman ne s'applique que pour les graphes sans circuits. L'invention propose encore de rendre plus rapide le calcul de plus court chemin dans l'algorithme de Dijkstra, ou dans un algorithme analogue, en ne parcourant pas les branches de l'arbre qui ne pourront pas conduire à une solution satisfaisante. L'algorithme de Dijkstra procède de la façon suivante: on considère un graphe G de N noeuds, qui est valué, i. e. dont chaque trajet existant entre deux noeuds i et j est affecté d'une valuation ou poids l(i, j). On considère s un noeud de départ du graphe G, d un noeud d'arrivée, et on cherche un chemin minimisant 7t(s, d), la distance de s à d, i. e. la somme des valuations des arcs reliant s à d. On note S le sous-graphe de G formé des noeuds x pour lesquels on connaît le chemin minimal vers s, et S son complémentaire. On note en outre ri l'ensemble des noeuds voisins d'un noeud i donné. Au départ, le sous-graphe S ne contient que le noeud s, et S contient l'ensemble des autres noeuds, affecté des valeurs initiales suivantes: n(s, i) = I(s, i) pour i E As, le noeud parent étant s; t(s, d) =, pour les autres noeuds, qui n'ont pas de noeud parent. Une itération de l'algorithme s'effectue de la façon suivant. Si S est vide, ou s'il ne contient que des noeuds i avec r(s, i) = 0, on a terminé. Sinon, on considère le noeud n de S qui est le plus proche du noeud de départ, i. e. le noeud qui minimise r(s, i), i E S; on prend ce noeud et on l'enlève de S pour le mettre dans S. Ensuite, on considère les voisins de ce noeud n et on calcule t(s, n) + I(n, i), i E rn eti E S; Si cette quantité est inférieure à 7i(s, j), on met à jour re(s, j): 7r(s, j):i(s, n) +I(n, j) et on met aussi à jour le noeud parent de j, qui devient n. On procède à cette opération pour tous les noeuds de Fn, puis on réordonne S. De la sorte, on ajoute progressivement à S l'ensemble des noeuds du graphe, en procédant par longueur croissante des chemins. Si on recherche un chemin vers un noeud d donné, I'algorithme peut être interrompu avant la fin, dès lors que le noeud de destination a été ajouté dans le sous graphe S. L'algorithme se démontre par l'absurde de la façon suivante. On considère n le noeud le plus proche de S, qui doit être ajouté à S. S'il existe un chemin le plus proche, ce chemin part de s et arrive à n, et présente un premier noeud dans S, noté m. On a alors n(s, m) + i(m, n) calculé dans une itération précédente, lors de l'ajout dans S du parent de m. Selon l'invention, lors d'une itération de l'algorithme, lorsque l'on considère les noeuds voisins du noeud n le plus proche du noeud source que l'on vient de retirer de S, le noeud, on peut ne pas considérer les artères pour lesquelles la première composante de coût est infinie. En d'autres termes, il est inutile de parcourir les branches de l'arbre pour lesquelles on sait que le résultat obtenu ne sera pas un routage acceptable du point de vue du protocole. On limite ainsi la durée des calculs pour l'algorithme. L'invention propose aussi de définir la fonction de coût de sorte à minimiser le nombre et la fréquence des calculs de routage. Pour cela l'invention propose qu'au moins une des composantes du vecteur de coût présente des valeurs discrètes - autrement dit, que cette composante présente un nombre fini de valeurs possibles -. La figure montre une allure possible de la deuxième composante LoadCost, qui est fonction de la charge d'une artère du réseau; en ordonnées est portée la composante LoadCost. En abscisses figurent les ressources disponibles - par exemple pour le cas d'un réseau de type RNIS, dans lequel l'artère est formée d'une pluralité d'accès TO ou T2, les ressources disponibles correspondent au nombre de canaux B libres. La figure montre essentiellement que la deuxième composante est une fonction croissante de la charge, ou, de façon strictement équivalente, une fonction décroissante des ressources disponibles sur l'artère. Cette fonction présente une valeur constante en deçà d'une valeur donnée de la charge, ou, de façon équivalente, présente une valeur constante au- delà d'une certaine valeur de ressources disponibles. Dans l'exemple, la charge présente une valeur infinie - i.e. une valeur supérieure à toute autre - si l'artère est coupée. Elle présente une valeur "saturée" si aucun canal n'est disponible; cette valeur "saturée" est choisie de sorte à être supérieure à la somme de tous les coûts possibles d'un routage par des canaux B. Elle présente une première valeur LoadCost3 si un seul canal est disponible, une deuxième valeur LoadCost2 si de 2 à k canaux sont disponibles, k étant un entier, et une valeur LoadCosti = 1 si plus de k canaux sont disponibles, avec LoadCost2 > LoadCostl. Une valeur de k de l'ordre de 10 est appropriée; le choix d'une valeur de k relativement faible permet d'éviter de recalculer les routages, tant que le coût ne varie pas. D'autres valeurs sont possibles, notamment en fonction de la capacité d'une artère et du nombre de canaux occupés par une communication. Le choix des valeurs LoadCosti, du nombre de valeurs LoadCosti, comme le choix des valeurs de charge pour lesquelles la fonction change de valeurs dépend de la nature du réseau, et de la répartition de charge qui est souhaitée. Ces valeurs peuvent être des valeurs absolues - comme dans l'exemple - ou elles peuvent être fonction de la capacité totale de l'artère. On pourrait aussi définir les différentes valeurs LoadCosti de la façon suivante: LoadCosti = (N-1).LoadCosti-l + 1 avec N le nombre de noeuds, et LoadCost1 = 1. Ce choix permet une répartition uniforme des communications sur les différents routages. Le choix selon l'invention d'un coût qui est une fonction des ressources disponibles sur les artères, et non pas comme dans l'art antérieur des ressources requises, permet de limiter considérablement le nombre et la fréquence des calculs de routage. Si l'on considère l'exemple d'une valeur de k valant 10, comme décrit plus haut, on évite tout recalcul de routage tant que les artères du réseau présentent au moins dix canaux libres. On évite donc toute répétition des calculs de routage entre les mêmes noeuds d'origine et de destination tant que le réseau est faiblement chargé. En comparaison, l'art antérieur propose de recalculer un routage pour chaque demande d'établissement de communication. On comprend donc l'intérêt que la fonction définie en référence à la figure présente une valeur constante dès que les ressources disponibles sur l'artère dépassent une valeur donnée. Bien entendu, la présente invention n'est pas limitée aux exemples et modes de réalisation décrits et représentés, mais elle est susceptible de nombreuses variantes accessibles à l'homme de l'art. Elle s'applique à d'autres types de réseaux que les réseaux privés mentionnés dans la description. Il est aussi clair que l'invention n'est pas limitée aux modes de réalisation décrits. On peut choisir des définitions différentes des composantes du vecteur de coût et de la relation d'ordre, en fonction des contraintes du réseau dans lequel l'invention est appliquée. REVENDICATIONS 1. Procédé de routage d'une communication dans un réseau avec une pluralité de noeuds reliés par des artères, comprenant le calcul du coût de différentes routes pour acheminer la communication, et le choix d'une route en fonction du coût, dans lequel le coût d'une route est fonction d'une part de la bande passante disponible sur les artères constituant la route, et d'autre part des ressources disponibles sur les dites artères. 2. Procédé selon la revendication 1, caractérisé en ce que le coût d'une route est fonction de la somme des coûts des artères constituant la route, et en ce que le coût d'une artère est un vecteur présentant une première composante fonction de la bande passante disponible sur l'artère, et une composante fonction des ressources disponibles sur l'artère. 3. Procédé selon la revendication 2, caractérisé en ce que la deuxième composante présente une valeur constante au-delà d'une quantité prédéterminée de ressources disponibles. 4. Procédé selon la revendication 2 ou 3, caractérisé en ce que la deuxième composante est une fonction présentant un nombre fini de valeurs possibles. 5. Procédé selon la revendication 2, 3 ou 4, caractérisé en ce que la deuxième composante est une fonction décroissante de la quantité de ressources disponibles. 6. Procédé selon l'une des revendications 2 à 5, caractérisé en ce que la première composante est une fonction décroissante de la bande passante disponible. 7. Procédé selon l'une des revendications 2 à 6, caractérisé en ce que la première composante est une fonction présentant une valeur nulle si la bande passante est supérieure ou égale à la bande passante requise pour une commuhication, et une valeur saturée si la bande passante disponible est inférieure à la bande passante requise. 8. Procédé selon l'une des revendications 2 à 6, caractérisé en ce que la première composante est une fonction présentant une valeur nulle si la bande passante est supérieure ou égale à la bande passante requise pour une communication, et une valeur égale à la différence entre la bande passante requise et la bande passante disponible si la bande passante disponible est inférieure à la bande passante requise. 9. Procédé selon l'une des revendications 2 à 8, caractérisé en ce que l'étape de choix s'effectue de sorte à minimiser le coût du routage, pour une relation d'ordre dans laquelle un premier vecteur est inférieur à un second vecteur si la première composante du premier vecteur est inférieure à la première composante du second vecteur, et en cas d'égalité des premières composantes, si la deuxième composante du premier vecteur est inférieure à la deuxième composante du deuxième vecteur. 1 0. Procédé selon l'une des revendications 2 à 9, caractérisé en ce que le vecteur somme d'un premier et d'un deuxième vecteurs est défini comme le vecteur dont la première composante est égale à la plus petite des premières composantes des dits premier et second vecteurs, et dont la deuxième composante est égale à la somme des deuxièmes composantes des premier et second vecteurs. 11. Procédé selon l'une des revendications 1 à 10, caractérisé en ce que l'étape de calcul des différentes routes s'effectue par application de l'algorithme de Dijkstra.