Brevet FR3078466A1 (20190830)

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.\n<CLM>\1\tProcé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\n<CLM>\1\tProcé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.\n<CLM>\1\tProcé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.\n<CLM>\1\tProcé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\n<CLM>\1\tProcé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 à\n<CLM>\1\t7. 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.