Brevet FR3078466A1 — publié le 20190830

PROCÉDÉ DE CONFIGURATION D'UNE ARCHITECTURE RÉSEAU ET ARCHITECTURE RÉSEAU ASSOCIÉE 1. Domaine technique de l'invention L'invention concerne un procédé de configuration d'une architecture réseau. En particulier, l'invention concerne un procédé de configuration d'une architecture réseau pour une transmission de type multidiffusion (ou muiticast en anglais) par un serveur source d'un flux de données vers des machines clients via un réseau informatique comprenant des machines reliées entre elles, en particulier pour la transmission de données de type flux audiovisuel temps réel (aussi appelé streaming en anglais). 2. Arrière-plan technologique La transmission de flux audiovisuel sur un réseau d'une source vers de multiples destinations est usuellement effectué en multidiffusion ou muiticast en anglais. Le cheminement des flux de la source vers les multiples destinations est déterminé par un arbre déployé sur une topologie. Sur chacune des branches, le flux n'est transporté qu'une fois, ce qui différencie la multidiffusion de diffusions multiples point-à-point ou unicast. La multidiffusion permet ainsi de diminuer la bande passante requise pour la transmission du flux de données. Dans les réseaux de transmission de données audiovisuels, une des principales problématiques est la robustesse, c'est-à-dire la capacité à continuer la transmission des données malgré un problème dans le réseau pour assurer la contrainte temps réel. En particulier, la transmission doit s'effectuer sans pertes et sans délais, afin d'éviter les pertes d'informations ou les microcoupures dans la transmission qui réduisent l'expérience utilisateur à la destination. De nombreuses solutions permettant cette robustesse ont été imaginées. En particulier, le standard de facto est Multicast VPN ou MVPN en réseau IP/MPLS traditionnel. Il s'agit d'une architecture basée sur des services de niveau 2 et 3 construits sur des tunnels résilients (E. C. Rosen and R. Aggarwal, « RFC 6513: Multicast in MPLS/BGP IP VPNs », 2012). Cette solution est basée sur un arbre de diffusion multicast établi par le protocole PIM, basé sur l'IGP. Bien que résiliente, cette solution ne permet 2 pas d'éviter l'impact suite à un reroutage. Ghannami et Shao (A. Ghannami and C. Shao, « Efficient Fast Recovery Mechanism in Software-Defined Networks », 11th International Conference for Internet Technology and Secured Transactions (ICITST -2016), 2016) ont proposé une solution sur 5 des réseaux SDN, dans laquelle des chemins de diffusion sont déployés sur la topologie et rapidement activés en cas de panne grâce aux possibilités offertes par les Fast Failover Group de la technologie OpenFlow. Il ne s'agit néanmoins pas d'arbres de multidiffusion, mais de multiples diffusions point-à-point. Enfin, Xiong et Chen X. Xiong and T. Chen, « MTM: A Reliable Multiple Trees 10 Multicast for Data Center Network », International Conference on Networking, Architecture, and Storage (NAS), 2017) ont proposé une autre approche, dans laquelle les destinations sont séparées en N groupes, portés par N arbres. Chaque destination sélectionne un voisin de secours appartenant à un autre arbre que le sien. En cas de panne d'un arbre, toutes les destinations portées par cet arbre basculent vers le voisin 15 de secours pour récupérer le flux. Les solutions à base d'arbre pour déterminer le cheminement des données sont dépendantes d'un calcul d'arbres. Pour s'assurer de la robustesse d'une telle solution, les arbres sont calculés de façon à être disjoints, de sorte qu'un problème sur un machine d'un des arbres n'impacte pas ou peu le ou les autres arbres. L'objectif est de 20 fournir une diversité de chemin à chaque destination afin que, en cas de panne, la livraison du flux de données soit assuré sans impact. Une telle approche de calcul d'arbre est par exemple présentée par Médard et al. (M. Médard, S. G. Finn, R. A. Barry, and R. G. Gallager, « Redundant Trees for Preplanned Recovery in Arbitrary Vert ex-Redundant or Edge-Redundant Graphs », 25 IEEE/ACM TRANSACTIONS ON NETWORKING, vol. 7, no. 5, /999), dans lequel un algorithme d'ordonnancement des noeuds permet de définir deux arbres totalement disjoints à partir d'une topologie où chaque destination est joignable par 2 chemins totalement disjoints. La recherche de deux arbres totalement disjoints, bien que parfait en théorie 30 pour une robustesse maximale, pose des problèmes car un réseau réel n'a pas forcément la possibilité de contenir ces deux arbres disjoints, auquel cas le calcul de 3 Médard et al. ne fournira aucun résultat. Une autre solution est de calculer des arbres les plus disjoints possibles, permettant d'obtenir d'une part une forte robustesse, et d'autre part d'ajouter certains critères à l'élaboration des arbres au-delà du simple fait qu'ils soient disjoints ou non. 5 Un exemple de calcul d'arbres les plus disjoints possibles est proposé par Bejerano et al., notamment dans deux publications (Y. Bejerano, S. Jana, and P. V. Koppol, « Efficient Construction of Directed Redundant Steiner Trees », in Local Computer Networks (LCN), 2012 IEEE 37th Conference on, 2012, pp. 119127.) et (Y. Bejerano and P. V. Koppol, « Link-Coloring Based Scheme for Multicast and Unicast 10 Protection », in High Performance Switching and Routing (HPSR), 2013 IEEE 14th International Conference on, 2013, pp. 2128). Bejerano et al. ont proposé un algorithme qui permet de calculer deux arbres les plus disjoints possible d'une même source vers les mêmes destinations dans une topologie où chaque destination est joignable par 2 chemins totalement disjoints. 15 Cette solution introduit les notions de n-accessibilité forte et faible. Un graphe est dit faiblement n-accessible pour une source et m destinations si et seulement si il existe au moins n chemins totalement disjoints entre la source et chacune des destinations. Un graphe est dit fortement n-accessible pour une source si et seulement si il 20 existe au moins n chemins totalement disjoints entre la source et chacun des noeuds du graphe. Le fonctionnement de la solution proposée par Bejerano et al. est représenté en référence avec la figure 1. Les étapes de la solution sont les suivantes : 25 - à partir d'un graphe initial faiblement 2-accessible, un sous-graphe faiblement 2- accessible de coût minimal est créé via un algorithme de Suurballe-Tarjan (J. W. Suurballe and R. E. Tarjan, « A Quick Method for Finding Shortest Pairs of Disjoint Paths », in Networks, 1984) permettant de calculer deux chemins strictement à noeuds disjoints entre deux points d'un graphe pondéré (étape 100. C'est une 30 variante de l'algorithme de Suurballe, qui permet de calculer deux chemins à liens disjoints ; 4 - à partir du sous-graphe de coût minimal, l'obtention d'un graphe auxiliaire fortement 2-accessible par sélection de noeuds par Suurballe-Tarjan et création de lien par parcours en profondeur ; - à partir du graphe auxiliaire, l'obtention d'une liste de noeuds par 5 ordonnancement des noeuds de sorte à ce que chaque noeud possède un parent avant et après lui ; - à partir de l'ordonnancement de noeuds, pour chaque noeud les liens vers les parents les plus proches dans l'ordonnancement sont sélectionnés et les liens sont affectés à deux arbres totalement disjoints ; 10 - à partir des deux arbres totalement disjoints, un mappage est effectué sur le graphe initial. Cette solution de Bejerano et al. et les autres solutions existantes présentent un certain nombre d'inconvénients. D'une part, elles nécessitent généralement un graphe fortement 2-accessible. 15 Pour des raisons géographiques et économiques, les topologies des réseaux de transport ne remplissent pas toujours ces contraintes. D'autre part, les solutions existantes ne s'intéressent pas au problème de la contrainte de délai, supposant que les caractéristiques physiques du réseau utilisé remplissent cette contrainte. Or, les applications de transmission de flux audiovisuel 20 nécessitent une transmission continue des données en temps réel, et le délai de transmission doit donc être contraint. Les inventeurs ont donc cherché une solution à ces inconvénients. 3. Objectifs de l'invention 25 L'invention vise à pallier au moins certains des inconvénients des procédés de configuration d'architecture réseau connus. En particulier, l'invention vise à fournir, dans au moins un mode de réalisation de l'invention, un procédé de configuration d'architecture réseau permettant la transmission en multidiffusion d'un flux de données audiovisuel continu, dans un délai 30 contraint, et résilient. L'invention vise aussi à fournir, dans au moins un mode de réalisation, un 5 procédé de configuration d'architecture réseau compatible avec tout type de topologie de l'architecture réseau. 4. Exposé de l'invention Pour ce faire, l'invention concerne un procédé de configuration d'une 5 architecture réseau comprenant un serveur source, une pluralité de machines clientes et une pluralité de machines noeuds, pour une transmission de type multidiffusion par le serveur source d'un flux de données vers les machines clientes via deux arbres de transmission de flux de données disjoints dans lesquels le serveur source forme une racine des arbres, les machines clients forment des feuilles des arbres et les machines 10 noeuds forment des noeuds des arbres, le procédé comprenant les étapes suivantes : - une étape de construction d'un graphe initial à partir de l'architecture réseau, chaque serveur source, machine cliente et machine noeud formant un point du graphe, lesdits points étant reliés par des liens bidirectionnels et pondérés en fonction de la bande passante et du délai 15 de transmission de données entre les points, - une étape de calcul de deux arbres de transmission de flux de données les plus disjoints possible entre le point formé par le serveur source vers tous les points formés par les machines clientes, - une étape de configuration de l'architecture réseau par un contrôleur de 20 réseau en fournissant au serveur source et aux machines noeuds une configuration de routage représentative des deux arbres de transmission de flux de données, caractérisé en ce que l'étape de calcul des deux arbres de transmission de flux de données les plus disjoints possible comprend les sous-étapes suivantes : 25 - une sous-étape de détermination d'un graphe dérivé faiblement 2- accessible à partir du graphe initial, via une sélection de lien contrainte en délai, - une sous-étape de détermination d'un sous-graphe de coût minimal faiblement 2-accessible à partir du graphe dérivé faiblement 2- 30 accessible, via une sélection de lien contrainte en délai, - une sous-étape de détermination d'un graphe auxiliaire fortement 2- 6 accessible à partir du sous-graphe de coût minimal faiblement 2-accessible, - une sous-étape d'ordonnancement des noeuds du graphe auxiliaire fortement 2-accessible de sorte à obtenir une liste de noeuds dans 5 lequel chaque noeud possède un parent avant et après lui, - une sous-étape d'affectation dans deux arbres auxiliaires de liens de chaque noeud vers ses parents les plus proches dans l'ordonnancement, - une sous-étape de suppression dans les arbres auxiliaires des branches dont les feuilles ne correspondent pas à une machine client, 10 - une sous-étape de mappage par retour de trace des arbres auxiliaires dans le graphe initial pour former deux pseudo-arbres définis dans le graphe initial, - une sous-étape de suppression dans les pseudo-arbres des cycles et branches dont les feuilles ne correspondent pas à une machine client 15 pour obtenir les deux arbres de transmission de flux de données les plus disjoints possible. Un procédé de configuration selon l'invention permet donc d'obtenir deux arbres les plus disjoints possible permettant la configuration d'une architecture réseau permettant la transmission en multidiffusion d'un flux de données audiovisuel continu, 20 dans un délai contraint, et résilient, d'une source vers plusieurs machines clientes. Conformément à la définition décrite précédemment, un graphe est dit faiblement 2-accessible pour une source (le serveur source) et m destinations (les machines clientes) si et seulement si il existe au moins 2 chemins totalement disjoints entre la source et chacune des destinations. 25 Un graphe est dit fortement 2-accessible pour une source (le serveur source) si et seulement si il existe au moins 2 chemins totalement disjoints entre la source et chacun des noeuds (les machines noeuds et machines clientes) du graphe. Comme Bejerano et al., l'algorithme permet l'obtention d'arbres le plus disjoints possible permettant la configuration des différents chemins de transmission dans 30 l'architecture réseau depuis le serveur source vers les machines clientes via les machines noeuds. 7 Les modifications apportées permettent de résoudre les inconvénients de Bejerano et al. : notamment, la sous-étape de détermination d'un graphe dérivé faiblement 2-accessible permet de rendre l'algorithme compatible avec toutes les topologies. 5 Ensuite, l'utilisation d'une sélection de lien contrainte en délai lors des différentes sous-étapes permet d'introduire une contrainte en délai dans le procédé de configuration, s'assurant ainsi que les arbres de transmission de flux de données calculés sont bien contraints en délai. Enfin, la sous-étape de suppression dans les arbres auxiliaires des branches dont 10 les feuilles ne correspondent pas à une machine client, la sous-étape de mappage par retour de trace et la sous-étape de suppression dans les pseudo-arbres des cycles et branches dont les feuilles ne correspondent pas à une machine client permettent d'obtenir les arbres sur le graphe initial en compensant les défauts générés par les modifications apportées par l'invention par rapport au procédé selon Bejerano et al. 15 Avantageusement et selon l'invention, la sous-étape de détermination d'un graphe dérivé faiblement 2-accessible à partir du graphe initial comprend, pour chaque machine cliente, le calcul de deux chemins les plus indépendants possible, les moins coûteux en bande passante et contraint en délai entre le serveur source et ladite 20 machine cliente, le calcul des deux chemins étant effectué via un algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale, et comprend la création de noeuds de dérivation ou de liens de dérivation dans le graphe dérivé lorsque les chemins présentent une suite de liens consécutifs communs. Selon cet aspect de l'invention, cette sous-étape de détermination d'un graphe 25 dérivé faiblement 2-accessible permet d'appliquer les sous-étapes suivantes de l'étape de calcul des deux arbres qui nécessitent un graphe faiblement 2-accessible. En particulier, contrairement à l'art antérieur en particulier l'algorithme Bejerano et al., cela permet le calcul des deux arbres sur tout type de graphe initial. L'algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale 30 est une variation de l'algorithme de Suurballe-Tarjan qui permet de trouver deux chemins les plus indépendants possibles, entre deux points d'un graphe pondéré, les 8 moins coûteux suivant la première dimension (ici la bande passante) et sous contrainte d'un seuil pour la seconde dimension (ici le délai). Avantageusement et selon l'invention, la sous-étape de détermination d'un 5 sous-graphe de coût minimal faiblement 2-accessible à partir du graphe dérivé faiblement 2-accessible comprend : a) la création d'une liste des machines clientes dites non traitées, b) pour chaque machine cliente non traitées, le calcul d'une paire de chemins à partir du serveur source via un algorithme de Suurballe-Tarjan contraint en 10 délai, les chemins de la paire étant strictement indépendants, les moins coûteux en bande passante et contraints en délai, c) la sélection de la paire de chemins la moins coûteuse, la modification de la pondération à zéro des liens de la paire de chemins la moins coûteuse, et la suppression de la machine clientes de la liste des machines clientes non traitées, 15 d) la répétition des étapes b) et c) jusqu'à ce que la liste des machines clientes non traitées soit vide. Selon cet aspect de l'invention, cette sous-étape de détermination d'un sous-graphe de coût minimal faiblement 2-accessible à partir du graphe dérivé faiblement 2-accessible permet de construire un sous-graphe de coût minimal, c'est-à-dire un sous- 20 graphe où les liens superflus sont retirés du graphe. L'algorithme de Suurballe-Tarjan contraint en délai est une variation de l'algorithme de Suurballe-Tarjan qui permet de trouver deux chemins strictement indépendants, entre deux points d'un graphe pondéré par deux dimensions, les moins coûteux suivant la première dimension (ici la bande passante) et sous contrainte d'un 25 seuil pour la seconde dimension (ici le délai). Avantageusement et selon l'invention, la sous-étape de détermination d'un graphe auxiliaire fortement 2-accessible à partir du sous-graphe de coût minimal faiblement 2-accessible comprend une recherche via l'algorithme de Suurballe-Tarjan 30 contraint en délai de tous les noeuds du sous-graphe de coût minimal faiblement 2- accessible joignable par deux chemins strictement indépendants depuis le serveur 9 source, le graphe auxiliaire étant composé uniquement desdits noeuds joignables par deux chemins strictement indépendants. Selon cet aspect de l'invention, la sous-étape de détermination d'un graphe auxiliaire fortement 2-accessible à partir du sous-graphe de coût minimal faiblement 2- 5 accessible permet l'obtention d'un graphe auxiliaire fortement 2-accessible qui est composé de tous les noeuds joignables par deux chemins strictement indépendants depuis la source et des liens indirects entre ces noeuds. Avantageusement et selon l'invention, la sous-étape de mappage par retour de 10 trace des arbres auxiliaires dans le graphe initial pour former deux pseudo-arbres définis dans le graphe initial comprend : - pour les liens de chaque arbre auxiliaire non-communs entre les deux arbres auxiliaires, la détermination du chemin le moins coûteux entre les deux extrémités du lien dans le graphe initial privé des noeuds du graphe 15 auxiliaire excepté les extrémités du lien, et l'ajout dudit chemin le moins coûteux dans un pseudo-arbre associé à chaque arbre auxiliaire, - pour les liens communs entre les deux arbres auxiliaires, l'attribution du lien à un ou l'autre pseudo-arbre par un algorithme de Suurballe-Tarjan appliqué entre les deux extrémités du lien de façon à maximiser 20 l'indépendance des pseudo-arbres. Selon cet aspect de l'invention, la sous-étape de mappage par retour de trace des arbres auxiliaires dans le graphe initial pour former deux pseudo-arbres définis dans le graphe initial permet d'utiliser les arbres auxiliaires, obtenus par sous-étape 25 d'ordonnancement des noeuds du graphe auxiliaire fortement 2-accessible et sous- étape d'affectation dans deux arbres auxiliaires de liens de chaque noeud vers ses parents les plus proches dans l'ordonnancement, pour obtenir des arbres définis dans le graphe initial. Cette étape garanti une indépendance maximale, mais peut générer des cycles 30 qui seront supprimé dans la sous-étape suivante de suppression dans les pseudo-arbres des cycles et branches dont les feuilles ne correspondent pas à une machine client pour 10 obtenir les deux arbres de transmission de flux de données les plus disjoints possible. L'invention concerne également un procédé de configuration d'une architecture réseau comprenant une pluralité de serveurs sources, une pluralité de machines clientes 5 et une pluralité de machines noeuds, pour une transmission de type multidiffusion par chaque serveur source d'un flux de données vers les machines clientes via deux arbres de transmission de flux de données disjoints dans lesquels le serveur source forme une racine des arbres, les machines clients forment des feuilles des arbres et les machines noeuds forment des noeuds des arbres, le procédé comprenant les étapes suivantes : 10 - une étape de construction d'un graphe initial à partir de l'architecture réseau, chaque serveur source, machine cliente et machine noeud formant un point du graphe, lesdits points étant reliés par des liens bidirectionnels et pondérés en fonction de la bande passante et du délai de transmission de données entre les points, 15 - une étape de calcul d'une forêt d'arbre de transmission, ladite forêt comprenant, pour chaque serveur source, deux arbres de transmission de flux de données les plus disjoints possible entre le point formé par le serveur source vers tous les points formés par les machines clientes, - une étape de configuration de l'architecture réseau par un contrôleur de 20 réseau en fournissant au serveur source et aux machines noeuds une configuration de routage représentative des deux arbres de transmission de flux de données, caractérisé en ce que l'étape de calcul de la forêt d'arbre de transmission comprend, pour chaque serveur source, une étape de calcul des deux arbres de 25 transmission de flux de données les plus disjoints possible d'un procédé de configuration selon l'invention. Un procédé selon l'invention permet d'étendre le procédé de configuration pour la transmission à partir d'un serveur source à un procédé de configuration d'une architecture comprenant plusieurs serveurs sources. Pour chaque source, deux arbres 30 de transmission de flux de données les plus disjoints possible sont calculés selon l'étape de calcul décrite précédemment et l'ensemble des arbres calculés forme une forêt 11 associant à chaque serveur source deux arbres de transmission de flux. L'invention concerne également une architecture réseau, comprenant un contrôleur de réseau, un serveur source, une pluralité de machines clientes et une 5 pluralité de machines noeuds, pour une transmission de type multidiffusion par le serveur source d'un flux de données vers les machines clientes via deux arbres de transmission de flux de données disjoints dans lesquels le serveur source forme une racine des arbres, les machines clients forment des feuilles des arbres et les machines noeuds forment des noeuds des arbres, caractérisé en ce que le serveur source, la 10 pluralité de machines clientes et la pluralité de machines noeuds sont configurés par le contrôleur de réseau pour réaliser ladite transmission d'un flux de données selon deux arbres calculés selon un procédé selon l'invention. L'invention concerne également un procédé de configuration et une architecture caractérisés en combinaison par tout ou partie des caractéristiques mentionnées ci- 15 dessus ou ci-après. 5. Liste des figures D'autres buts, caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante donnée à titre uniquement non limitatif et qui se réfère aux figures annexées dans lesquelles : 20 - la figure 1, déjà décrite, est un diagramme schématique d'un calcul d'arbres disjoints selon Bejerano et al., - la figure 2 est un diagramme schématique d'une étape de calcul de deux arbres de transmission de flux de données les plus disjoints possible d'un procédé selon un mode de réalisation de l'invention, 25 - la figure 3 est un diagramme schématique d'un algorithme de Suurballe-Tarjan, - la figure 4 est un diagramme schématique d'un algorithme LARAC, - la figure 5 est un diagramme schématique d'une première variation de l'algorithme de Suurballe-Tarjan, dite algorithme de Suurballe-Tarjan contraint en délai, 30 - la figure 6 est un diagramme schématique d'une deuxième variation de l'algorithme de Suurballe-Tarjan, dite algorithme de Suurballe-Tarjan à 12 indépendance maximale, la figure 7 est un diagramme schématique d'une troisième variation de l'algorithme de Suurballe-Trajan, dite algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale, la figure 8 est un diagramme schématique d'une sous-étape de détermination d'un graphe dérivé faiblement 2-accessible à partir du graphe initial d'un procédé selon un mode de réalisation de l'invention, et la figure 8a une variante d'une des phases de cette sous-étape, la figure 9 est un diagramme schématique d'une sous-étape de détermination d'un sous-graphe de coût minimal faiblement 2-accessible à partir du graphe dérivé faiblement 2-accessible d'un procédé selon un mode de réalisation de l'invention, la figure 10 est un diagramme schématique d'une sous-étape de détermination d'un graphe auxiliaire fortement 2-accessible à partir du sous-graphe de coût minimal faiblement 2-accessible d'un procédé selon un mode de réalisation de l'invention, la figure 11 est un diagramme schématique d'une première partie d'une sous-étape d'ordonnancement des noeuds du graphe auxiliaire fortement 2-accessible d'un procédé selon un mode de réalisation de l'invention, la figure 12 est un diagramme schématique d'une deuxième partie d'une sous-étape d'ordonnancement des noeuds du graphe auxiliaire fortement 2-accessible d'un procédé selon un mode de réalisation de l'invention, la figure 13 est un diagramme schématique d'une sous-étape d'affectation dans deux arbres auxiliaires de liens de chaque noeud vers ses parents les plus proches dans l'ordonnancement, la figure 14 est un diagramme schématique d'une sous-étape de suppression dans les arbres auxiliaires des branches dont les feuilles ne correspondent pas à une machine client, la figure 15 est un diagramme schématique d'une sous-étape de mappage par retour de trace des arbres auxiliaires dans le graphe initial pour former deux pseudo-arbres définis dans le graphe initial, 13 - la figure 16 est un diagramme schématique d'une sous-étape de suppression dans les pseudo-arbres des cycles et branches dont les feuilles ne correspondent pas à une machine client - la figure 17 est un diagramme schématique d'une étape de calcul d'une forêt 5 d'arbres de transmission de flux de données d'un procédé selon un mode de réalisation de l'invention. 6. Description détaillée d'un mode de réalisation de l'invention Les réalisations suivantes sont des exemples. Bien que la description se réfère à un ou plusieurs modes de réalisation, ceci ne signifie pas nécessairement que chaque 10 référence concerne le même mode de réalisation, ou que les caractéristiques s'appliquent seulement à un seul mode de réalisation. De simples caractéristiques de différents modes de réalisation peuvent également être combinées pour fournir d'autres réalisations. Le procédé selon l'invention permet la configuration d'une architecture réseau 15 comprenant un serveur source, une pluralité de machines clientes et une pluralité de machines noeuds, pour une transmission de type multidiffusion par le serveur source d'un flux de données vers les machines clientes via deux arbres de transmission de flux de données disjoints dans lesquels le serveur source forme une racine des arbres, les machines clients forment des feuilles des arbres et les machines noeuds forment des 20 noeuds des arbres. De façon connue, un tel procédé de configuration comprend une étape de construction d'un graphe initial à partir de l'architecture réseau, chaque serveur source, machine cliente et machine noeud formant un point du graphe, lesdits points étant reliés par des liens bidirectionnels et pondérés en fonction de la bande passante et du délai de 25 transmission de données entre les points, une étape de calcul de deux arbres de transmission de flux de données les plus disjoints possible entre le point formé par le serveur source vers tous les points formés par les machines clientes, et une étape de configuration de l'architecture réseau par un contrôleur de réseau (ou équivalent) en fournissant au serveur source et aux machines noeuds une configuration de routage 30 représentative des deux arbres de transmission de flux de données. L'architecture ainsi configurée par le contrôleur de réseau permet de mettre en oeuvre la transmission du 14 flux de données entre les différents éléments qui la composent. Le procédé de configuration est particulier en ce que l'étape de calcul des deux arbres de transmission de flux de données les plus disjoints possible est améliorée par rapport aux méthodes connues, en particulier par rapport à la solution de Bejerano et 5 al., déjà décrite. En particulier, la figure 2 représente schématiquement une étape de calcul de deux arbres de transmission de flux de données les plus disjoints possible d'un procédé selon un mode de réalisation de l'invention. L'étape de calcul des deux arbres diffère sur plusieurs sous-étapes qui seront décrites plus loin en référence aux figures 8 à 16. En 10 particulier, l'étape de calcul des deux arbres de transmission de flux de données les plus disjoints possible comprend les sous-étapes suivantes : - une sous-étape de détermination d'un graphe dérivé faiblement 2-accessible à partir du graphe initial, via une sélection de lien contrainte en délai, - une sous-étape de détermination d'un sous-graphe de coût minimal faiblement 2- 15 accessible à partir du graphe dérivé faiblement 2-accessible, via une sélection de lien contrainte en délai, - une sous-étape de détermination d'un graphe auxiliaire fortement 2-accessible à partir du sous-graphe de coût minimal faiblement 2-accessible, - une sous-étape d'ordonnancement des noeuds du graphe auxiliaire fortement 2- 20 accessible de sorte à obtenir une liste de noeuds dans lequel chaque noeud possède un parent avant et après lui, - une sous-étape d'affectation dans deux arbres auxiliaires de liens de chaque noeud vers ses parents les plus proches dans l'ordonnancement, - une sous-étape de mappage par retour de trace des arbres auxiliaires dans le 25 graphe initial pour former deux pseudo-arbres définis dans le graphe initial, - une sous-étape de suppression dans les pseudo-arbres des cycles et branches dont les feuilles ne correspondent pas à une machine client pour obtenir les deux arbres de transmission de flux de données les plus disjoints possible. 30 La description de ces sous-étapes nécessite au préalable une définition des algorithmes de Suurballe-Tarjan et de LARAC, déjà connus et utilisés dans ces sous- 15 étapes, ainsi que trois variations nouvelles de l'algorithme de Suurballe-Tarjan créés spécifiquement pour la mise en oeuvre de ce procédé de configuration et mise en oeuvre dans ces sous-étapes. 5 La figure 3 représente schématiquement un algorithme de Suurballe-Tarjan, connu de l'art antérieur et permettant de calculer deux chemins strictement à noeuds disjoints entre deux points d'un graphe pondéré. Son fonctionnement détaillé est décrit dans la publication J. W. Suurballe and R. E. Tarjan, « A Quick Method for Finding Short est Pairs of Disjoint Paths », in Networks, 1984 déjà citée. 10 La figure 4 représente schématiquement un algorithme LARAC, pour « Lagrangian Relaxation based Aggregated Cost », permettant de calculer un chemin entre deux points d'un graphe pondéré par au moins deux dimensions. Le chemin est le moins coûteux suivant une dimension et sous un seuil défini pour l'autre dimension. Par 15 exemple, en réseau de télécommunication, l'algorithme LARAC permet de trouver le chemin le moins coûteux en bande passante, sous contrainte de délai. Son fonctionnement détaillé est décrit dans la publication A. Juttner, B. Szviatovski, I. Mcs, and Z. Rajk, « Lagrange relaxation based Method for the QoS routing problem », IEEE INFOCOM, vol. 2, pp. 859868, 2001. 20 L'algorithme de LARAC est utilisé dans différentes sous-étapes décrit plus loin. Toutefois, dans d'autres modes de réalisation, il peut être remplacé par d'autres algorithmes de routage contraints, par exemple l'algorithme « Constrained BellmanFord », décrit par Widyono dans R. Widyono, "The design and evaluation of routing algorithms for realtime channels", International Computer Science Institute Berkeley, 25 1994. La figure 5 représente schématiquement une première variation de l'algorithme de Suurballe-Tarjan, dite algorithme de Suurballe-Tarjan contraint en délai. Cet algorithme de Suurballe-Tarjan contraint en délai permet de trouver deux 30 chemins strictement indépendants, entre deux points d'un graphe pondéré par deux dimensions, les moins coûteux suivant la première dimension et sous contrainte d'un 16 seuil pour la seconde dimension (ici le délai). La principale différence avec l'algorithme de Suurballe-Tarjan est l'utilisation d'un algorithme de LARAC ou équivalent pour obtenir deux chemins les moins coûteux et sous contrainte de délai. 5 La figure 6 représente schématiquement une deuxième variation de l'algorithme de Suurballe-Tarjan, dite algorithme de Suurballe-Tarjan à indépendance maximale. Cet algorithme de Suurballe-Tarjan à indépendance maximale permet de trouver deux chemins les plus indépendants possibles, entre deux points d'un graphe pondéré, 10 les moins coûteux possible. La principale différence est la mise en place d'une tolérance permettant d'assurer deux chemins les plus indépendants possibles plutôt que de limiter l'algorithme à la recherche de chemins strictement indépendants. 15 La figure 7 représente schématiquement une troisième variation de l'algorithme de Suurballe-Tarjan, dite algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale. Cet algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale permet de trouver deux chemins strictement indépendants, entre deux points d'un 20 graphe pondéré par deux dimensions, les moins coûteux suivant la première dimension et sous contrainte d'un seuil pour la seconde dimension (ici le délai). Cette troisième variation est une combinaison de la première et de la deuxième variation. 25 La figure 8 représente schématiquement une sous-étape de détermination d'un graphe dérivé faiblement 2-accessible à partir du graphe initial d'un procédé selon un mode de réalisation de l'invention. Le graphe initial est un graphe quelconque connecté bidirectionnel et pondéré par deux dimensions, par exemple la bande passante et le délai. Les sous-étapes 30 suivantes de l'étape de calcul des deux arbres disjoints nécessitent comme entrée un graphe faiblement 2-accessible. LE graphe initial doit être modifié pour remplir ce 17 critère. Cette opération est aussi appelée dérivation du graphe. Pour chaque destination, l'algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale est utilisé pour obtenir deux chemins à partir de la source. Si ces chemins ont des segments communs, c'est-à-dire une suite de liens consécutifs 5 communs, un noeud de dérivation est ajouté pour remplir la propriété de faible 2- accessibilité. Selon un mode de réalisation alternatif, un lien de dérivation est ajouté à la place de noeud de dérivation, comme représenté sur la figure 8a représentant cette phase de création de lien de dérivation, en variante de la phase de création de noeud représentée figure 8. 10 La figure 9 représente schématiquement une sous-étape de détermination d'un sous-graphe de coût minimal faiblement 2-accessible à partir du graphe dérivé faiblement 2-accessible d'un procédé selon un mode de réalisation de l'invention. Cette sous-étape consiste à construire un sous-graphe de coût minimal, c'est-à- 15 dire un sous-graphe où les liens superflus sont retirés du graphe. Pour chaque destination, l'algorithme de Suurballe-Tarjan contraint en délai est utilisé pour obtenir une paire de chemin à partir de la source. La paire la plus légère est sélectionnée et ajoutée au sous-graphe. La pondération dans le graphe dérivé de ces liens est modifiée pour être nulle. La destination correspondant à la paire sélectionnée 20 est marquée comme traitée. Cette opération est répétée jusqu'à ce que toutes les destinations soient traitées. Comme le sous-graphe de coût minimal est un sous-graphe du graphe dérivé faiblement 2-accessible qui ne contient que les liens utiles pour joindre les destinations, il remplit également la propriété de faible 2-accessibilité. 25 La figure 10 représente schématiquement une sous-étape de détermination d'un graphe auxiliaire fortement 2-accessible à partir du sous-graphe de coût minimal faiblement 2-accessible d'un procédé selon un mode de réalisation de l'invention. Cette sous-étape est divisée en deux parties : 30 - L'algorithme de Suurballe Tarjan contraint en délai est utilisé pour déterminer si des chemins strictement indépendants existent entre la source et chaque noeud. 18 Seuls les noeuds pour lesquels des chemins ont été trouvés sont ajoutés au graphe auxiliaire ; - Une fois tous les noeuds du sous-graphe de coût minimal traités, un parcours en profondeur du sous-graphe de coût minimal est effectué pour chacun des noeuds 5 précédemment ajoutés au graphe auxiliaire. Le parcours est interrompu à chaque noeud du graphe auxiliaire trouvé, et un lien est ajouté dans le graphe auxiliaire. En d'autres ternies, le graphe auxiliaire est composé de tous les noeuds joignables par deux chemins strictement indépendants depuis la source et des liens indirects entre ces noeuds. Le graphe auxiliaire obtenu est ainsi fortement 2-accessible. 10 La figure 11 représente schématiquement une première partie d'une sous-étape d'ordonnancement des noeuds du graphe auxiliaire fortement 2-accessible d'un procédé selon un mode de réalisation de l'invention. Cette première partie est la création d'une liste intermédiaire 15 d'ordonnancement La liste est initialisée de la façon suivante : la source est ajoutée à chaque extrémité en tant que singleton. Entre ces deux singletons est insérée une sous-liste ordonnée contenant les voisins sortants directs de la source dans n'importe quel ordre. L'opération suivante est répétée jusqu'à ce que tous les noeuds du graphe soient dans la 20 liste : - Un noeud possédant deux parents dans deux sous-listes distinctes de la liste est sélectionné. Il est ajouté à la liste comme singleton entre les deux sous-listes contenant ses parents ; - Si un tel noeud n'est pas trouvé, un noeud possédant deux parents dans la même 25 sous-liste est sélectionné et ajouté à la fin de cette sous-liste ; - Si un tel noeud n'est pas trouvé, un noeud possédant un parent dans une sous-liste est sélectionné et ajouté à la fin de cette sous-liste ; D'après ces étapes, un noeud remplissant l'une de ces conditions est toujours trouvé. 30 Une fois tous les noeuds dans la liste intermédiaire, cette liste doit être raffinée pour ne plus contenir de sous-listes, dans une deuxième partie. 19 La figure 12 représente schématiquement cette deuxième partie d'une sous-étape d'ordonnancement des noeuds du graphe auxiliaire fortement 2-accessible d'un procédé selon un mode de réalisation de l'invention. 5 Pour chaque sous-liste contenant plus d'un noeud, la position du second parent du dernier noeud possédant au moins un parent hors de la sous-liste par rapport à cette sous-liste est déterminée. Si le parent se trouve avant, le noeud est inséré avant comme singleton. À l'inverse, si le parent est situé après, le noeud est inséré après. Cette deuxième partie se termine lorsque toutes les sous-listes ne contiennent qu'un seul 10 noeud. Cette liste donne un ordonnancement des noeuds tels que chaque noeud possède un parent avant et après lui. La figure 13 représente schématiquement une sous-étape d'affectation dans 15 deux arbres auxiliaires de liens de chaque noeud vers ses parents les plus proches dans l'ordonnancement. Pour chaque noeud excepté la source, d'une part, son plus proche parent le précédant dans l'ordonnancement est identifié et le lien correspondant est ajouté à un premier arbre auxiliaire, appelé « arbre auxiliaire bleu ». D'autre part, son plus proche 20 parent lui succédant dans l'ordonnancement est identité et le lien correspondant ajouté à un deuxième arbre auxiliaire, appelé « arbre auxiliaire rouge ». Cette sous-étape d'affectation s'achève une fois tous les noeuds traités. La figure 14 représente schématiquement une sous-étape de suppression dans 25 les arbres auxiliaires des branches dont les feuilles ne correspondent pas à une machine client. Pour chaque arbre, toutes les feuilles de l'arbre qui ne sont pas des destinations sont supprimées jusqu'à ce que toutes les feuilles soient des destinations (c'est-à-dire correspondent à une machine client). 30 La figure 15 représente schématiquement une sous-étape de mappage par 20 retour de trace des arbres auxiliaires dans le graphe initial pour former deux pseudoarbres définis dans le graphe initial. Cette sous-étape de mappage a pour but d'utiliser les deux arbres auxiliaires pour obtenir des arbres définis dans le graphe initial. 5 Les liens communs entre les deux arbres auxiliaires sont marqués « Communs », et seront traités plus tard. Les autres liens sont traités de la manière suivante : Le noeud entrant du lient est utilisé comme source et le noeud sortant comme destination de l'algorithme LARAC sur le graphe initial. Les liens obtenus sont ajoutés respectivement à deux pseudo-arbres définis dans le graphe initial appelés « pseudo- 10 arbre bleu » et « pseudo-arbre rouge ». Pour tous les liens marqués « Communs », l'objectif est d'utiliser l'algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale et d'affecter chacun des chemins à un arbre, de sorte à ce que les arbres aient le moins de liens communs possible. Pour cela un retour sur trace est effectué : si une affectation rend 15 l'indépendance des arbres impossible, l'algorithme revient sur l'affectation précédente pour explorer une autre combinaison. Si l'indépendance totale n'est pas possible, une contrainte d'indépendance est progressivement relâchée par l'incrémentation d'un compteur de liens communs (noté A). Cette sous-étape garanti une indépendance maximale des pseudo-arbres, mais 20 peut générer des cycles. La figure 16 représente schématiquement une sous-étape de suppression dans les pseudo-arbres des cycles et branches dont les feuilles ne correspondent pas à une machine client. 25 Pour chaque pseudo-arbre, un parcours en profondeur à partir de la source permet de détecter les cycles et de supprimer le lien remontant vers la source. Une fois tous les cycles éliminés, toutes les feuilles de l'arbre qui ne sont pas des destinations sont supprimées jusqu'à ce que toutes les feuilles soient des destinations (c'est-à-dire correspondent à une machine client). 30 Les deux arbres obtenus sont les arbres de transmission de flux de données les plus disjoints possible. 21 Le procédé de configuration peut donc réaliser l'étape de configuration de l'architecture réseau par un contrôleur de réseau en fournissant au serveur source et aux machines noeuds une configuration de routage représentative des deux arbres de transmission de flux de données. 5 La figure 17 représente schématiquement une étape de calcul d'une forêt d'arbres de transmissions de flux de données d'un procédé de configuration selon un mode de réalisation de l'invention. 10 L'étape de calcul des deux arbres de transmission de flux de données les plus disjoints possible telle que décrite précédemment est appelée étape MIDCAST pour Maximally lndependent Delay Constrained Approximation for Steiner Tree en anglais (Approximation contrainte en délai et à indépendance maximale pour arbres de Steiner en français). Elle est mise en oeuvre pour chacune des sources (chaque serveur source), 15 en particuliers pour chacun des noeuds fictifs 0 ajoutés au graphe à chaque source. Un noeud 0 fictif est ajouté au graphe initial. Pour chaque source souhaitée dans le graphe initial, un lien entre la source et le noeud fictif de pondération et délai nuls est ajouté. Le calcul d'arbres disjoints est alors appliqué à ce graphe, utilisant le noeud fictif comme unique source. Deux arbres partiellement disjoints, ayant pour racine le noeud 20 fictif sont obtenus. Pour chacun de ces arbres, les liens vers le noeud fictif sont supprimés. On obtient alors de multiples arbres - autrement appelé une « forêt » - chacun ayant pour racine l'un REVENDICATIONS1. Procédé de configuration d'une architecture réseau comprenant un serveur source, une pluralité de machines clientes et une pluralité de machines noeuds, pour une transmission de type multidiffusion par le serveur source d'un flux de données vers les machines clientes via deux arbres de transmission de flux de données disjoints dans lesquels le serveur source forme une racine des arbres, les machines clients forment des feuilles des arbres et les machines noeuds forment des noeuds des arbres, le procédé comprenant les étapes suivantes : - une étape de construction d'un graphe initial à partir de l'architecture réseau, chaque serveur source, machine cliente et machine noeud formant un point du graphe, lesdits points étant reliés par des liens bidirectionnels et pondérés en fonction de la bande passante et du délai de transmission de données entre les points, - une étape de calcul de deux arbres de transmission de flux de données les plus disjoints possible entre le point formé par le serveur source vers tous les points formés par les machines clientes, - une étape de configuration de l'architecture réseau par un contrôleur de réseau en fournissant au serveur source et aux machines noeuds une configuration de routage représentative des deux arbres de transmission de flux de données, caractérisé en ce que l'étape de calcul des deux arbres de transmission de flux de données les plus disjoints possible comprend les sous-étapes suivantes : - une sous-étape de détermination d'un graphe dérivé faiblement2- accessible à partir du graphe initial, via une sélection de lien contrainte en délai, - une sous-étape de détermination d'un sous-graphe de coût minimal faiblement 2-accessible à partir du graphe dérivé faiblement 2-accessible, via une sélection de lien contrainte en délai, - une sous-étape de détermination d'un graphe auxiliaire fortement 2- accessible à partir du sous-graphe de coût minimal faiblement 2- 23 accessible, - une sous-étape d'ordonnancement des noeuds du graphe auxiliaire fortement 2-accessible de sorte à obtenir une liste de noeuds dans lequel chaque noeud possède un parent avant et après lui, 5 - une sous-étape d'affectation dans deux arbres auxiliaires de liens de chaque noeud vers ses parents les plus proches dans l'ordonnancement, - une sous-étape de suppression dans les arbres auxiliaires des branches dont les feuilles ne correspondent pas à une machine client, - une sous-étape de mappage par retour de trace des arbres auxiliaires 10 dans le graphe initial pour former deux pseudo-arbres définis dans le graphe initial, - une sous-étape de suppression dans les pseudo-arbres des cycles et branches dont les feuilles ne correspondent pas à une machine client pour obtenir les deux arbres de transmission de flux de données les plus 15 disjoints possible. 2. Procédé de configuration selon la revendication 1, caractérisé en ce que la sous- étape de détermination d'un graphe dérivé faiblement 2-accessible à partir du graphe initial comprend, pour chaque machine cliente, le calcul de deux chemins les plus 20 indépendants possible, les moins coûteux en bande passante et contraint en délai entre le serveur source et ladite machine cliente, le calcul des deux chemins étant effectué via un algorithme de Suurballe-Tarjan contraint en délai à indépendance maximale, et comprend la création de noeuds de dérivation ou de liens de dérivation dans le graphe dérivé lorsque les chemins présentent une suite de liens consécutifs communs. 25 3. Procédé de configuration selon l'une des revendications 1 ou 2, caractérisé en ce que la sous-étape de détermination d'un sous-graphe de coût minimal faiblement 2-accessible à partir du graphe dérivé faiblement 2-accessible comprend : a) la création d'une liste des machines clientes dites non traitées, 30 b) pour chaque machine cliente non traitées, le calcul d'une paire de chemins à partir du serveur source via un algorithme de Suurballe-Tarjan contraint en 24 délai, les chemins de la paire étant strictement indépendants, les moins coûteux en bande passante et contraints en délai, c) la sélection de la paire de chemins la moins coûteuse, la modification de la pondération à zéro des liens de la paire de chemins la moins coûteuse, et la 5 suppression de la machine clientes de la liste des machines clientes non traitées, d) la répétition des étapes b) et c) jusqu'à ce que la liste des machines clientes non traitées soit vide. 4. Procédé de configuration selon l'une des revendications 1 à 3, caractérisé en ce 10 que la sous-étape de détermination d'un graphe auxiliaire fortement 2-accessible à partir du sous-graphe de coût minimal faiblement 2-accessible comprend une recherche via l'algorithme de Suurballe-Tarjan contraint en délai de tous les noeuds du sous-graphe de coût minimal faiblement 2-accessible joignable par deux chemins strictement indépendants depuis le serveur source, le graphe auxiliaire étant composé uniquement 15 desdits noeuds joignables par deux chemins strictement indépendants. 5. Procédé de configuration selon l'une des revendications 1 à 4, caractérisé en ce que la sous-étape de mappage par retour de trace des arbres auxiliaires dans le graphe initial pour former deux pseudo-arbres définis dans le graphe initial comprend : 20 - pour les liens de chaque arbre auxiliaire non-communs entre les deux arbres auxiliaires, la détermination du chemin le moins coûteux entre les deux extrémités du lien dans le graphe initial privé des noeuds du graphe auxiliaire excepté les extrémités du lien, et l'ajout dudit chemin le moins coûteux dans un pseudo-arbre associé à chaque arbre auxiliaire, 25 - pour les liens communs entre les deux arbres auxiliaires, l'attribution du lien à un ou l'autre pseudo-arbre par un algorithme de Suurballe-Tarjan appliqué entre les deux extrémités du lien de façon à maximiser l'indépendance des pseudo-arbres. 30 6. Procédé de configuration d'une architecture réseau comprenant une pluralité de serveurs sources, une pluralité de machines clientes et une pluralité de machines 25 noeuds, pour une transmission de type multidiffusion par chaque serveur source d'un flux de données vers les machines clientes via deux arbres de transmission de flux de données disjoints dans lesquels le serveur source forme une racine des arbres, les machines clients forment des feuilles des arbres et les machines noeuds forment des 5 noeuds des arbres, le procédé comprenant les étapes suivantes : - une étape de construction d'un graphe initial à partir de l'architecture réseau, chaque serveur source, machine cliente et machine noeud formant un point du graphe, lesdits points étant reliés par des liens bidirectionnels et pondérés en fonction de la bande passante et du délai 10 de transmission de données entre les points, - une étape de calcul d'une forêt d'arbre de transmission, ladite forêt comprenant, pour chaque serveur source, deux arbres de transmission de flux de données les plus disjoints possible entre le point formé par le serveur source vers tous les points formés par les machines clientes, 15 - une étape de configuration de l'architecture réseau par un contrôleur de réseau en fournissant au serveur source et aux machines noeuds une configuration de routage représentative des deux arbres de transmission de flux de données, caractérisé en ce que l'étape de calcul de la forêt d'arbre de transmission comprend, 20 pour chaque serveur source, une étape de calcul des deux arbres de transmission de flux de données les plus disjoints possible d'un procédé de configuration selon l'une des revendications 1 à 5. 7. Architecture réseau, comprenant un contrôleur de réseau, au moins un serveur 25 source, une pluralité de machines clientes et une pluralité de machines noeuds, pour une transmission de type multidiffusion par le serveur source d'un flux de données vers les machines clientes via deux arbres de transmission de flux de données disjoints dans lesquels le serveur source forme une racine des arbres, les machines clients forment des feuilles des arbres et les machines noeuds forment des noeuds des arbres, caractérisé en 30 ce que le serveur source, la pluralité de machines clientes et la pluralité de machines noeuds sont configurés par le contrôleur de réseau pour réaliser ladite transmission d'un 26 flux de données selon deux arbres calculés selon un procédé selon l'une des revendications 1 à 5, ou selon une forêt calculée selon un procédé selon la revendication 6.