Brevet FR2924568A1 — publié le 20090605

PROCÉDÉ ET SYSTÈME DE ROUTAGE DE FLUX DIE DONNÉES DANS UN RÉSEAU IP PAR INONDATION D'UN MESSAGE DE RECHERCHE D'ABONNÉ L'invention concerne un procédé de routage de flux de données dans un réseau IP comportant au préalable une étape de diffusion d'appel dans le réseau par inondation d'un message de recherche d'abonné. Afin de répondre aux besoins exprimés par un usager ou une application pour transmettre des flux de données dans un réseau de communication comprenant des noeuds de routage et des artères, il existe actuellement différentes solutions qui permettent notamment de trouver, pour les flux usagers, le meilleur chemin à emprunter en fonction, notamment : o de la distance, nombre de bonds à parcourir, o du type d'artères à emprunter, en évitant les liens satellites, par exemple. Ces solutions peuvent traiter aussi des problèmes de réservation de ressources (bande passante) nécessaires sur chaque artère du chemin choisi pour acheminer la communication et si besoin, pour préempter une communication de plus faible priorité. Les solutions connues par le Demandeur, utilisent, par exemple : o Les protocoles de routage de type tels que : le protocole de routage dynamique � OSPF � pour Open Shortest Path First, le protocole d'échange de route � BGP � pour Border Gateway Protocol, protocole proactif de routage � OLSR � abréviation anglo-saxonne de � Optimized Link State Routing Protocol �, pour atteindre le destinataire au plus court, o Les protocoles de réservation de ressources, par exemple de type RSVP pour � Resource Reservation Protocol �. En revanche, peu de solutions de l'art antérieur proposent simultanément : o Un routage qui prend en compte la qualité de service QoS demandée par une application et l'état d'occupation des artères, o La préemption de communication de priorité plus faible en cas de saturation des artères. Certaines solutions connues du Demandeur sont construites autour du protocole MPLS correspondant à l'acronyme anglo-saxon � Multi Protocol Label Switching � ou encore par une association des protocoles OLSR, RSVP précités et de marquage de la route par routage politique. Il existe aussi des procédés tel que celui décrit dans la demande de brevet du Demandeur FR 07/02346. Si ces techniques sont efficaces, elles présentent toutefois certains inconvénients. Pour la technique MPLS, cette technologie ne considère que des flux agrégés de même type depuis les sites d'accès, ce qui rend impossible le routage QoS appel par appel et la préemption de ressources communication par communication. Pour les solutions mettant en oeuvre des techniques OLSR, RSVP, si ces solutions apportent globalement le service recherché, avec quelques réserves sur la préemption qui est faite alors que l'appelé n'a pas encore répondu ou qui peut être déclenchée alors qu'une autre route existe, ses inconvénients majeurs se situent au niveau de sa réalisation : o L'agent QSA pour QoS agent héberge son propre protocole de routage et son propre protocole de signalisation, sans tirer parti du protocole de routage mis en oeuvre par les routeurs standards du réseau, o Ce protocole de routage est issu d'un développement spécifique, donc non standard. Dans le cas du procédé exposé dans la demande de brevet FR 07/02346, la solution requiert une implémentation du service de routage décrit dans le RFC 4915 (disponible sur le lien Internet http://www.ietf.org/rfc/rfc4915.txt) par le routeur, ce qui n'est pas le cas pour beaucoup de routeurs du commerce, et une adaptation du protocole RSVP pour s'adapter au routage mufti-topologique. D'autre part, dans les solutions existantes précitées, subsiste le problème du temps de convergence des tables de routage du réseau. Dans certains cas d'applications, par exemple dans un monde tactique, c'est-à-dire pour des réseaux dont la topologie peut être très fluctuante dans le temps, certaines communications pourront échouer pendant cette phase de convergence. De plus, ces solutions utilisent toutes, le protocole standard de réservation RSVP en parallèle de la signalisation d'appel. Dans la plupart des cas, l'appelé reçoit l'appel avant que la session RSVP ne soit complètement établie. Chaque direction déterminée pour transmettre un flux de données étant négociée séparément, les chemins peuvent être différents entre l'aller et le retour, ce qui complexifie les traitements à faire en cas de rupture de l'un de ces chemins. Dans la suite de la description, les abréviations suivantes seront utilisées pour simplifier la description : QSA : désigne une application chargée de trouver le meilleur chemin en fonction d'une qualité de service demandée QoS, cette application vient se superposer au protocole habituellement utilisé par un routeur. Elle est réalisée par un protocole propriétaire basé sur une inondation du réseau WAS. QSP : correspond à une passerelle dont la fonction est de convertir une signalisation d'appel d'une communication en une signalisation de recherche de meilleur chemin dans un réseau comprenant plusieurs noeuds, LOC : fonction de localisation des abonnés, LCC : fonction serveur d'appel ou en anglo-saxon � Local call control �. Mr : Message recherche abonné Mret : Message retour L'objet de la présente invention concerne un procédé pour déterminer le meilleur chemin à emprunter par un flux de données au sein d'un réseau de communication comportant plusieurs noeuds constitués d'un routeur associé à une application, communiquant entre eux par des artères, une passerelle d'entrée et une passerelle de sortie assurant la conversion du protocole multimédia en protocole de routage dans le réseau caractérisé en ce qu'il comporte au moins les étapes suivantes : o localiser l'appelé B au niveau d'un serveur d'appel et identifier la passerelle de sortie à atteindre sur le réseau , o inonder la totalité des noeuds du réseau en diffusant le message de recherche abonné Mr (en l'occurrence ici la passerelle de sortie) émis par la passerelle d'entrée vers lesdits noeuds jusqu'à la passerelle de sortie, o au niveau de chacun des noeuds et sur réception du message de recherche abonné Mr, déterminer pour chaque noeud, le coût de l'artère par laquelle est arrivé le message de recherche abonné, et lancer une temporisation d'attente Ti proportionnelle au coût de l'artère, et réserver la ressource demandée et retransmettre le message de recherche abonné sur les autres artères adjacentes audit noeud excepté l'artère par laquelle le message Mr est arrivé, o sur la réception du premier message de recherche abonné Mr sur la passerelle de sortie, émettre un message de retour Mret et parcourant le chemin inverse à celui par lequel est arrivé le premier message de recherche, c'est-à-dire le chemin optimal P déterminé par le mécanismes de temporisation exécuté au niveau de chacun des noeuds du réseau, L'invention concerne plus largement un système permettant de déterminer le meilleur chemin à emprunter par un flux de données au sein d'un réseau de communication comportant plusieurs noeuds communiquant entre eux par des artères, et constituant un réseau de communication caractérisé en ce qu'il comporte au moins les éléments suivants : o au niveau de chaque routeur du réseau une application QSAi exécutant les étapes du procédé décrit précédemment et ci-après et effectuant, la localisation de la passerelle de sortie, le calcul du coût de routage, le lancement d'une temporisation proportionnelle au coût calculé précédemment, l'établissement de la route entre l'appelant et l'appelé, la réservation et éventuellement la préemption de ressources et la configuration du routeur par imposition du port de sortie pour cette communication. o une desserte d'entrée et une desserte de sortie, reliée chacune à un routeur du réseau, chacune des dessertes comportant une application QSP assurant la conversion du protocole multimédia en protocole de routage dans le réseau et un serveur d'appel et de localisation permettant d'orienter les appels multimédia vers le QSP. D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description qui suit d'un exemple de réalisation donné à titre illustratif, nullement limitatif annexé des figures qui représentent: o La figure 1, un exemple d'architecture générale d'un système selon l'invention, o La figure 2, la phase de recherche d'un abonné, o La figure 3, la phase d'établissement de la communication, et o La figure 4, la communication une fois établie. Afin de mieux faire comprendre le principe mis en oeuvre dans l'invention, la description qui suit est donnée à titre illustratif et nullement limitatif dans le cadre d'un appel multimédia au travers d'un réseau étendu tactique IP plus généralement connu sous l'acronyme anglo-saxon �'WAS IP � pour Wide Area System IP (Internet Protocol). L'invention peut aussi être utilisée dans des systèmes de type WAN (Wide Area Network) désignant des réseaux étendus. Le procédé selon l'invention peut toutefois s'appliquer dans tout réseau supportant le protocole IP (réseau tactique ou réseaux radio haut débit). Elle s'applique notamment pour des services Multimédia qui demandent une réservation de ressources. La figure 1 représente un exemple de structure permettant la mise en oeuvre du procédé selon l'invention, comprenant par exemple une première desserte 1 comprenant des moyens permettant l'établissement d'un appel d'un abonné A cherchant à joindre un abonné B par exemple. Cette desserte comprend un serveur d'appel 10 ou LCC pour Local Control Cali, un serveur de localisation 11 ou LOC, ces deux serveurs ayant pour fonction d'orienter les appels multimédia vers une passerelle 12 appelée plus communément QoS Proxy-QSP qui permet notamment de convertir une signalisation d'appel d'une communication de l'abonné A en signalisation de recherche de meilleur chemin. II est possible d'utiliser tous les protocoles connus par l'Homme du métier sous la désignation H.323, par exemple. Le système comprend une deuxième partie, 2, reliée à la passerelle 12 et chargée de mettre en oeuvre un procédé de routage par inondation explicité plus loin dans la description. Cette deuxième partie comprend un réseau IP 13 composé de plusieurs noeuds 14i reliés et communiquant entre eux par des artères 15ij, ce réseau servant au transport des données. Le réseau 13 supporte par exemple un protocole de routage IPä Sur ce réseau se positionne le procédé de routage par inondation selon l'invention représenté par les applications 16i qui sont associées chacune à un routeur 14i. Le procédé de routage par inondation se positionne ainsi au-dessus du routage WAS IP. Une troisième partie 3 permet la réception de l'appel de l'abonné A et la connexion de l'abonné B (établissement d'une communication entre A et B). Une passerelle 17 est reliée au réseau 13, la passerelle 17 a une fonction similaire à la passerelle 12. Cette passerelle 17 est en liaison avec un serveur d'appel 18 ou LCC pour Local Control Call, un serveur de localisation 19 ou LOC, ces deux serveurs ayant pour fonction d'orienter les appels multimédia. Le système étant symétrique, la passerelle d'entrée 12 pourra aussi jouer le rôle de passerelle de sortie, alors que la passerelle de sortie 17, celle d'entrée. Dans l'exemple donné, la signalisation voix sur IP désignée par l'abréviation VolP va être véhiculée avec la signalisation associée au routage WAS. Au niveau de chacun des routeurs 14i du réseau de transit 13, est ajoutée une application QSAi ayant pour fonction de trouver le meilleur chemin dans le réseau en fonction, notamment de la qualité de service QoS requise par l'application, et de l'état d'occupation des artères et d'activer des commandes de routage politique ou PBR abréviation anglo-saxonne de Policy Based Routing, pour imposer le meilleur chemin trouvé au routeur associé, par rapport à celui qui aurait été obtenu par les protocoles de routage classique. Les routeurs 14i peuvent être des routeurs de type COTS (composants sur étagère commercialisés) et peuvent mettre en oeuvre des protocoles de routage IGP (Interior Gateway Protocol). Au-dessus de ce protocole, l'application QSAi est mise en oeuvre au niveau de chacun des routeurs ou noeuds du réseau, afin de déterminer la localisation d'un point de sortie du WAS, le coût de routage, l'établissement de la route offrant le meilleur coût, la préemption de ressources et d'assurer la configuration du routeur. Le procédé selon l'invention décrit en relation avec les figures 2, 3 et 4 comprend les étapes suivantes : La figure 2 schématise la phase de recherche d'un abonné L'établissement d'un appel multimedia au travers d'un VVAS IP entre les deux dessertes 1 et 2 est effectué suivant le processus ci-dessous : Lorsqu'un appel (Setup) arrive au serveur d'appel 10 de la desserte 1, celui-ci s'adresse au serveur de localisation 11 pour obtenir la localisation de l'appelé B (et le prochain bond à effectuer pour l'atteindre) et identifier la passerelle de sortie à atteindre. Dans le cas d'un service multimedia, la fonction LOC donne les coordonnées : du serveur LCC 18 (serveur sur lequel est inscrit l'appelé B) à atteindre et, si un réseau de type WAS doit être traversé, des deux passerelles d'accès à ce WAS. Sur l'exemple de la figure 2, le serveur LCC à atteindre est le serveur 18 et les passerelles sont les passerelles 12 et 17, respectivement pour que l'appelant A puisse atteindre l'appelé B. Le setup (modifié) est alors prolongé au QSP local (sur la figure le QSPA correspondant à l'abonné A) qui lance la diffusion (par inondation) de la recherche abonné vers les QSAi du réseau WAS ou réseau étendu, 13, en précisant le débit et la priorité de la communication. Les paramètres débit et priorité sont introduits dans le message de recherche abonné à partir des données fournies dans le setup. Le message de setup précise également le type de service demandé (vidéo, audio, ...). Le setup est conservé en attente dans la desserte 1. La recherche abonné ou le message recherche abonné est diffusée ainsi de proche en proche dans tout le réseau 13 WAS. Les différentes applications QSAi qui pilotent chacune les routeurs 14i du réseau 13, recherchent le meilleur chemin et ceci jusqu'à atteindre la passerelle de sortie 17 (et jusqu'aux QSP). Pour cela, sur réception du message de recherche Mr, chaque QSAi calcule le coût de l'artère 15ij par laquelle est arrivé le message. Ce coût prend en compte : • l'état d'occupation des artères empruntées en terme de débit et de nombre de communications, • le nombre de préemptions éventuellement à pratiquer, • le media utilisé pour pénaliser les artères à forte latence, gigue ou taux d'erreur, éventuellement le niveau de sécurisation de l'artère. Ensuite, chaque QSAi lance une temporisation d'attente Ti proportionnelle au coût déterminé pour l'artère 15e, artère par laquelle est arrivé le message, avant de retransmettre le message de recherche d'abonné Mr sur toutes les autres artères adjacentes, exceptée l'artère 15e par laquelle est arrivé le message de recherche d'abonné. Si la QSAi reçoit par une autre artère, un message de recherche déjà traité, elle ne traite plus ce message de recherche. Sur réception du message de recherche, une QSAi va faire une réservation de ressources en fonction du débit inscrit dans le message de recherche abonné. Sur la première réception à la passerelle de sortie 17 du message de recherche abonné, un message de retour Mret émis par la fonction QSP de la desserte de l'appelé B parcourt en sens inverse le chemin optimal P trouvé par le mécanisme des temporisations successives -ci mises en oeuvre au sein des QSAi du réseau. Chacun des noeuds 16i connaît les artères d'entrée 15e du message de recherche abonné premier arrivé. Les réceptions suivantes des messages de recherche provenant d'autres noeuds du réseau sont ignorées par la passerelle 17. A l'issue de cette deuxième phase, le chemin optimal P est déterminé et la phase d'établissement de la communication peut être engagée. La figure 3 représente la phase d'établissement de la communication Une fois l'abonné B trouvé, la transmission du message de A vers B s'effectue de la manière suivante, o Au niveau du QSPA appelant, donc la passerelle 12, sur réception du message retour Mret, l'établissement de la communication (transportant également le message d'appel initial afin que le QSPB appelé 17 pour l'abonné B puisse régénérer l'appel dans sa desserte 3) est émise sur le chemin optimal P trouvé. o Le QSPB appelé 17 récupère le message d'appel et le transmet au serveur d'appel LCC 18 de sa desserte 3. o Au décroché de l'appelé B, une confirmation d'établissement d'appel est véhiculée dans le WAS, confirmation qui est transportée par les différentes applications 16i. o Sur réception de la confirmation d'appel, chaque application QSAi traversée effectue éventuellement une préemption (si des communications moins prioritaires doivent être libérées pour récupérer des ressources pour la communication en cours), puis, pour chaque sens de transmission, chaque application QSAi exécute une commande de routage politique (PBR) pour imposer au routeur local 14i un port de sortie 20k pour un couple (IPQSp, Port RTP/RTCP) donné. Les applications QSA et QSP paramètrent les routeurs 14i, afin que le flux media suive un chemin qui ne correspond pas forcément à celui défini par le protocole de routage du routeur. Une application QSAi va ainsi déterminer les commutations au sein du routeur vers des artères de sortie désignées pour acheminer le trafic correspondant aux adresses IP et ports des deux QSP. o La confirmation d'établissement est traduite en message � Connect � du protocole voix sur IP � VoIP � utilisé par le QSP de l'appelant A. Dans les deux dessertes 1 et 2, à la fin des négociations relatives aux ports logiques et aux CODECs (codeur décodeur ), des commandes DNAT sont émises par les QSP pour que les routeurs d'accès remplacent à la volée les adresses IP des terminaux par celles des QSP pour les flux media (RTP/RTCP). Ainsi, il n'est pas nécessaire d'attendre la négociation des adresses/ports entre terminaux pour établir le chemin dans le réseau de transit. Sur la figure 4 a été représentée le chemin emprunté par les messages, une fois la communication établie. Les commandes DNAT et PBR effectuées sur les routeurs permettent que les flux média ne transitent pas par les serveurs QSP et QSA garantissant ainsi des performances optimales. Le chemin du plan média est indiqué à la figure 4. Physiquement, une application QSAi est installée, par exemple : o soit dans un équipement spécifique connecté au routeur 14i par un lien Ethernet (ou Série), o soit, si les routeurs le permettent (Linux, CISCO), intégrée au routeur en tant qu'application complémentaire. Le procédé selon l'invention offre notamment les avantages suivants : o II gère les ressources de manière symétrique appel par appel, o II effectue les préemptions quand l'appelé a répondu et s'il n'y a vraiment pas d'autre chemin possible. D'autre part, le procédé s'appuie sur n'importe quel routage IGP utilisé dans le réseau de transit. o II ne dépend pas de fonctionnalités de routage non encore industrialisées par les constructeurs de routeurs. o Il est implémenté au-dessus du protocole IP, permettant ainsi de faire varier les coûts des artères au moment des établissements et des libérations des communications sans impacter les noeuds de routage non concernés par la communication en cours. II présente comme avantage de pouvoir être utilisé dans tous les réseaux présentant une forte mobilité topologique et des artères à faible débit, par exemple pour des réseaux tactiques sur IP, des réseaux radio haut débit, etc... REVENDICATIONS 1 û Procédé pour déterminer le meilleur chemin emprunté par un flux de données au sein d'un réseau de communication comportant plusieurs noeuds constitués d'un routeur (14i) associé à une application (16i), communiquant entre eux par des artères (15ij), une passerelle d'entrée (12) et une passerelle de sortie (17) assurant la conversion du protocole multimédia en protocole de routage dans le réseau (13) caractérisé en ce qu'il comporte au moins les étapes suivantes : o localiser l'appelé B au niveau d'un serveur d'appel (10, 11) et identifier la passerelle de sortie à atteindre sur le réseau, o inonder la totalité des noeuds (14i+16i) du réseau (13) en diffusant le message de recherche abonné Mr émis par la passerelle d'entrée (12) vers lesdits noeuds (14i+16i) jusqu'à la passerelle de sortie (17), o au niveau de chacun des noeuds (14i+16i) et sur réception du message de recherche abonné Mr, déterminer pour chaque noeud (14i+16i), le coût de l'artère (15ij) par laquelle est arrivé le message de recherche abonné, et lancer une temporisation d'attente Ti proportionnelle au coût de l'artère, et réserver la ressource demandée, et retransmettre le message de recherche abonné sur les autres artères adjacentes audit noeud excepté l'artère (15e) par laquelle le message Mr est arrivé, o sur la réception du premier message de recherche abonné Mr sur la passerelle de sortie (17), émettre un message de retour Mr et parcourant le chemin inverse à celui par lequel est arrivé le premier message de recherche, c'est-à-dire le chemin optimal P déterminé par le mécanismes de temporisation exécuté au niveau de chacun des noeuds du réseau, 2 ù Procédé selon la revendication 1 caractérisé en ce qu'il comporte au moins les étapes suivantes, si un noeud reçoit par une artère un message de recherche abonné déjà traité, alors, il ignore ledit message. 3 ù Procédé selon la revendication 1 caractérisé en ce que sur réception du message de retour Mret, au niveau de la passerelle d'entrée (12), alors la communication est établie en transmettant à la passerelle de sortie (17) les paramètres d'appel. 4 ù Procédé selon la revendication 2 caractérisé en ce que la confirmation d'établissement de la communication entre l'appelant A et l'appelé B est transmise à travers le réseau (13) et en ce que sur réception de cette confirmation, chacun des noeuds effectue une préemption et pour chaque sens de circulation d'un message exécute une commande de politique de routage pour imposer au routeur un port de sortie. ù Procédé selon l'une des revendications 1 à 4 caractérisé en ce que les données sont des communications multimédia. 6 ù Système permettant de déterminer le meilleur chemin à emprunter par un flux de données au sein d'un réseau de communication comportant plusieurs noeuds (14i+16i) communiquant entre eux par des artères (15ij), et constituant un réseau (13) de communication caractérisé en ce qu'il comporte au moins les éléments suivants : o au niveau de chaque routeur (14i) du réseau (13) une application QSAi exécutant les étapes du procédé selon l'une des revendications 1 à 5 et effectuant, la localisation de la passerelle de sortie (17), le calcul du coût de routage, le lancement d'une temporisation proportionnelle au coût calculé précédemment, l'établissement de la route entre l'appelant et l'appelé, la préemption de ressources et laconfiguration du routeur par imposition du port de sortie pour cette communication. o une desserte d'entrée et une desserte de sortie, reliée chacune à un routeur du réseau (13), chacune des dessertes comportant une application QSP assurant la conversion du protocole multimédia en protocole de routage dans le réseau (13) et un serveur d'appel et de localisation permettant d'orienter les appels multimédia vers le QSP.