Brevet FR3135851A1 — publié le 20231124

La présente invention propose un procédé de routage (600) d’un flux de données dans un réseau déterministe sensible au temps, pour router les paquets d’un flux de données depuis un terminal émetteur vers un terminal récepteur, le réseau comprenant des commutateurs pour la transmission des paquets, les commutateurs étant configurés pour mettre en œuvre une planification de transmission prédéfinie sur des cycles de temps répétés ayant des créneaux de temps de longueur fixe. Le procédé de routage de l’invention utilise la latence d’un chemin comme métrique pour calculer (604) les k chemins les plus courts entre un terminal émetteur et un terminal récepteur, puis pour chaque chemin, détermine pour chaque commutateur situé sur ce chemin, un intervalle de tolérance (406) qui définit pour combien de temps les paquets d’un flux peuvent patienter au niveau du commutateur avant d’être transférés vers le commutateur suivant, sans dépasser la date limite d’arrivée de chaque paquet du flux à destination, afin de réserver des créneaux libres (408). Figure pour l’abrégé : Fig.4 Dispositif et procédé de routage de flux dans les réseaux sensibles au temps Domaine de l’invention La présente invention est dans le domaine des réseaux de télécommunication, et concerne plus particulièrement un procédé de routage de flux multi-QoS dans les réseaux déterministes ou réseaux sensibles au temps (TSN) « Time Sensitive Networking ». Etat de la Technique TSN est un ensemble de normes, définies par le groupe de travail IEEE 802.1, qui étendent le réseau Ethernet afin de répondre aux exigences strictes des communications en temps réel. Ce type de réseaux est destiné à être utilisé principalement dans des réseaux industriels, les réseaux intra-véhiculaires, les réseaux de cœur 5G/6G. En étendant et en adaptant les standards Ethernet existants, le TSN crée une convergence entre la technologie de l'information (IT) et la technologie de l'exploitation industrielle (OT) dans les réseaux industriels. Cela signifie que les données critiques en temps réel et les applications à forte intensité de données peuvent être mises en œuvre sur un câble Ethernet commun sans interférer les unes avec les autres. Les spécifications TSN fournissent des services déterministes, permettant la transmission en temps réel de données dans un cadre prévisible, à l’intérieur d’un espace de temps connu, dans les environnements industriels, telles que les applications de contrôle des machines dans les processus de production, du capteur au nuage (le « cloud » selon l’anglicisme consacré). TSN offre une latence (le temps nécessaire à un paquet de données pour passer de la source à la destination à travers un réseau) et une qualité de service garanties avec la synchronisation temporelle. Les différents documents de la norme TSN offrent une solution de communication en temps réel complète lorsqu'ils sont utilisés ensemble de manière concertée. Chaque spécification standard est autonome et elle peut être utilisée seule. On peut regrouper les spécifications en trois catégories : La synchronisation temporelle correspondant à la norme IEEE 802.1AS, où tous les périphériques qui participent à la communication en temps réel doivent avoir une compréhension commune du temps. La planification ou ordonnancement correspondant à la norme IEEE 802.1Qbv pour la mise en forme du trafic TSN, où tous les périphériques participant à la communication en temps réel respectent les mêmes règles dans le traitement et la transmission des paquets de communication. Le routage ou sélection des chemins de communication, des réservations de chemins et de la tolérance de panne, où tous les périphériques participant à la communication en temps réel respectent les mêmes règles dans la sélection des chemins de communication et dans la réservation de la bande passante et des horaires, en utilisant éventuellement plusieurs chemins simultanés pour obtenir une tolérance de panne. Le mécanisme de contrôle d’un trafic TSN peut alors être considéré sous deux aspects : (1) l’ordonnancement ou planification Qbv (« scheduling » selon l’anglicisme adapté), qui permet de définir quelle trame d’un flux à envoyer et quand l’envoyer ; et (2) le routage correspondant à la sélection pour chaque flux, d'un chemin de la source à la destination. Pour la mise en place de l'ordonnancement, certaines formules ou restrictions répondant aux exigences de temps sont introduites. Elles sont généralement résolues comme des problèmes d’optimisation en appliquant la programmation linéaire en nombres entiers ou « Integer Linear Programming » (ILP) selon l’anglicisme adapté ou comme des problèmes de décision en appliquant la théorie modulaire satisfiable ou « Satisfiability modulo theories » (SMT) selon l’anglicisme adapté. Ainsi, la recherche d’un procédé d'ordonnancement revient à résoudre un problème de complexité « NP-difficile ». De ce fait, il devient trop complexe pour respecter la limite de temps de calcul des réseaux à grande échelle, de chercher à résoudre conjointement les deux aspects que sont l’ordonnancement et le routage. Une solution typique consiste à résoudre d'abord le problème de routage, et ensuite le problème de planification. Dans une approche courante, le routage est calculé selon le chemin le plus court en termes de nombre de sauts. Puis, une fois que les routes sont déterminées, la planification Qbv est calculée sur la base de ces routes. Cette approche n’est pas optimale dans le sens où le calcul des routes ne prend pas en considération les contraintes des flux en termes de latence, ni le fait qu’une planification Qbv soit en court sur les commutateurs constituant le réseau TSN. La planification Qbv propose un mécanisme pour assurer des latences bornées. Il permet aux commutateurs d’un réseau TSN de contrôler le trafic dans des files d’attente de ports de sortie des commutateurs, selon une planification de transmission prédéfinie (l'ordonnanceur temporel IEEE 802.1Qbv), et ainsi de garantir la qualité du trafic prioritaire. L'ordonnanceur temporel IEEE 802.1Qbv est conçu pour séparer la communication sur le réseau Ethernet en cycles de temps répétés de longueur fixe. Au sein de ces cycles, différentes tranches de temps peuvent être configurées et être affectées à une ou plusieurs des huit priorités Ethernet. Les commutateurs (« Switch » en anglais) servent d’intermédiaires entre des terminaux émetteurs (Parleur(s) ou « Talker(s) » en anglais) de flux de données et des terminaux récepteurs (Auditeur(s) ou « Listener(s) » en anglais), en gérant le multiplexage des données, i.e. leur réception, leur traitement et leur retransmission. La illustre de manière schématique et simplifiée un réseau TSN composé d’une pluralité d’équipements sources (T1, T2, T3) et d’un équipement destinataire (L1) connectés à des commutateurs (S1, S2, S3, S4, S5) via des liens Ethernet. Sur cet exemple, il est considéré que trois flux TSN (ST3, ST4, ST5) allant vers la même destination (L1) ont des contraintes de latence par exemple une latence maximale de 200µs pour le flux ST3 (latenceMax3= 200µs), une latence maximale de 10ms pour le flux ST4 (latenceMax4= 10ms) et une latence maximale de 500µs pour le flux ST5 (latenceMax5= 500µs). Selon l’approche courante précitée, ces trois flux vont prendre la même route (i.e. le chemin le plus court, par exemple via les commutateurs S2 et S3), puis l’ordonnanceur décidera un nouveau cycle intégrant trois plages de temps (créneaux de temps ou « time slots » en anglais) pour ces trois flux. Cependant, quand le cycle (calculé sur le port de sortie du commutateur S3 connecté au terminal destinataire L1) ne pourrait pas inclure tous les flux, car devenant complet, comme illustré sur la où le cycle répartit des plages de temps restantes pour les flux ST1 à ST4 et ne peut plus prendre en compte le flux ST5, l’ordonnanceur (i.e. le module de planification) pourrait décider (i.e. produire le résultat ou l’information) de la non-faisabilité de la configuration du système. Ainsi sur cet exemple simplifié, il ressort que par l’approche courante, le fait de considérer uniquement le nombre des sauts (le chemin le plus court) dans le calcul des routes, peut conclure à la sélection d’une même route pour tous les flux, et de ce fait peut entrainer une complexité dans le calcul de la planification Qbv, voire une impossibilité de planifier la transmission de certains flux. De plus, cette approche courante n’est pas adaptée pour les nouveaux scénarios envisagés tel que des lignes de productions reconfigurables dans l’industrie 4.0, ayant un cœur 5G basé sur un réseau TSN. En effet, dans ces types de scénarios, le système est dit ouvert car les flux ne sont pas tous connus à l’avance avant le déploiement du réseau, et le mécanisme de planification Qbv est alors sujet à des reconfigurations pour pouvoir satisfaire les exigences applicatives des flux critiques. Dans ces systèmes, de manière à garantir la précision d’un processus de fabrication et minimiser tout défaut, les appareils tels que les robots, les actionneurs et les capteurs doivent communiquer entre eux rapidement car ils doivent réagir très vite en fonction du système de commande et de contrôle, ou en fonction de certains événements inattendus. Aussi, pour pouvoir répondre à des scénarios envisagés dans l’industrie 4.0 où les lignes de production sont reconfigurables (ce qui implique une dynamique dans le réseau industriel), ou pour répondre au scénario d’intégrer la technologie TSN dans le cœur 5G/6G où les flux ne sont pas connus d’avance, il existe le besoin d’algorithmes qui répondent aux exigences strictes des communications en temps réel. Il existe quelques approches qui abordent en partie ces problématiques. Le standard IEEE 802.1Qcc fournit deux approches principales (celle centralisée et celle distribuée) pour configurer les mécanismes TSN (IEEE, “IEEE Standard for Local and Metropolitan Area Networks - Bridges and Bridged Networks Amendment 31: Stream Reservation Protocol (SRP) Enhancements and Performance Improvements”, IEEE 802.1Qcc-2018. Dans ce standard, il est souligné que l’approche centralisée est la plus favorisée pour assurer la configuration de l’IEEE 802.1Qbv. Cependant, ce standard ne fournit pas les algorithmes qui permettent de décider les routes et générer la configuration des listes de configuration de portes (GCL) (« Gate Configuration List » selon l’anglicisme consacré) à déployer dans le réseau. Dans la littérature, l’approche principale repose généralement sur des outils d’ingénierie : outils de simulation comme « RTaW-Pegase » ou bien des outils d’optimisation mathématiques comme les formulations ILP (« Integer Linear Programming ») ou les solveurs SMT (« Satisfiability modulo Theories »). Or, ces outils d’ingénierie ne permettent pas d’assurer l’aspect de la dynamique attendue par l’ensemble des nouveaux scénarios envisagés dans le futur comme celui des systèmes ouverts dans lesquels l’arrivée des flux n’est pas connue à l’avance. Par exemple, l’article de Nayak, N. G., Duerr, F., & Rothermel, K. (2018), Routing algorithms for IEEE802. 1Qbv networks, ACM SIGBED Review, 15(3), 13-18, propose un algorithme de routage basé sur la technique ILP qui vise à réduire le nombre des flux à ordonnancer dans chaque commutateur. Cependant, l’inconvénient principal de ce type de technique est le temps d’exécution qui ne convient pas pour gérer et configurer un réseau TSN d’une manière dynamique. Les articles de Singh, S. (2017), Routing algorithms for time sensitive networks (Master's thesis), et de Ojewale, M. A., & Yomsi, P. M. (2020), Routing heuristics for load-balanced transmission in TSN-based networks, ACM Sigbed Review, 16(4), 20-25, ont proposé des heuristiques pour le routage qui considèrent comme métrique de calcul des routes, la quantité de trafic à ordonnancer maximale (« Maximum scheduled traffic load MSTL »). Ensuite pour l’ordonnancement des flux, Singh, S. se repose sur la théorie modulaire satisfiable (SMT solver). L’algorithme de routage a pour objectif de minimiser cette métrique pour trouver le chemin pour chacun des flux. L’inconvénient des algorithmes de routage proposés dans la littérature est qu’ils décident des routes seulement sur la base de la quantité du trafic à ordonnancer, sans tenir en compte des contraintes de latence associées à ces flux. Ainsi, avec ce type d’algorithme de routage, les flux ayant des contraintes strictes en termes de latence pourraient malgré tout emprunter des chemins plus longs et de fait leurs contraintes de latence ne seraient pas respectées. Une autre approche connue est décrite dans l’article de Huang, K., Wu, J., Jiang, X., Xiong, D., Huang, K., Yao, H., ... & Liu, Z. (2020), A period-aware routing method for IEEE 802.1 Qbv TSN networks, Electronics, 10(1), 5, qui propose un algorithme de routage qui prend en considération la période des flux. Dans un premier temps, l’algorithme permet d’organiser les flux suivant une métrique de combinabilité des flux (« flux combinability » selon l’anglicisme consacré), qui traduit la capacité des flux à se mettre ensemble sur le même ordonnancement. Dans un second temps, l’algorithme de routage se base sur une métrique de coût calculée selon l’équation suivante : Coût = MSOW + K*hops , où le paramètre ‘MSOW’ est une métrique inventée par les auteurs pour mesurer la combinabilité des flux, le paramètre ‘hops’ représente la longueur du chemin, et le paramètre ‘K’ est un poids défini par l’utilisateur pour pénaliser la longueur du chemin vis-à-vis du paramètre ‘MSOW’. L’inconvénient de cette solution réside dans le choix du paramètre ‘K’ qui selon sa valeur peut impacter les performances de l’algorithme. Par ailleurs, cet algorithme ne prend pas en considération les contraintes des flux en termes de latence. Aussi, il n’existe pas de solution connue d’algorithme de routage pour les réseaux sensibles au temps, qui tienne compte des contraintes de latence des flux tout en respectant les exigences applicatives de ces flux, telle que l’exigence d’arrivée juste à temps (« Just-in-Time » selon l’anglicisme consacré). La présente invention répond à ces différents besoins. Un objet de la présente invention est un procédé et un dispositif pour sa mise en œuvre, permettant de calculer le routage de flux dans les réseaux déterministes. Avantageusement le procédé de l’invention, en plus de considérer la planification Qbv qui est déjà configurée dans les commutateurs faisant partie des chemins, considère les latences des flux de données comme des métriques pour la détermination des chemins de routage. A la différence des méthodes de routage connues, la solution proposée introduit un intervalle de tolérance qui va donner plus de flexibilité à l’ordonnanceur pour déterminer des créneaux de temps à allouer aux flux, quand une planification Qbv est déjà configurée sur les commutateurs. La présente invention peut être mise en œuvre dans les réseaux industriels (domaines de l’usine du future, industrie 4.0 / usines fortement reconfigurables), les réseaux intra-véhiculaires (domaines de véhicules de tout type : automobile, camions, bus, train, bateau…), ou encore dans le cœur du réseau 5G/6G (pour véhiculer des communications temps réels). Pour obtenir les résultats recherchés, il est proposé un procédé de routage d’un flux de données dans un réseau déterministe sensible au temps, pour router les paquets d’un flux de données depuis un terminal émetteur vers un terminal récepteur, le réseau comprenant des commutateurs pour la transmission des paquets, lesdits commutateurs étant configurés pour mettre en œuvre une planification de transmission prédéfinie sur des cycles de temps répétés ayant des créneaux de temps de longueur fixe, le procédé étant mis en œuvre par ordinateur et comprenant des étapes consistant à : - générer en prenant en compte un paramètre de latence de chemin, un ensemble de ‘k’ chemins les plus courts entre le terminal émetteur et le terminal récepteur ; - pour un chemin ‘m’ parmi les ‘k’ chemins : - calculer pour chaque commutateur de ce chemin, un intervalle de tolérance sur la durée du cycle, l’intervalle de tolérance définissant une durée pendant laquelle les paquets dudit flux de données peuvent rester au niveau dudit commutateur avant d’être transmis, sans dépasser une date limite d’arrivée au terminal récepteur ; - déterminer si un créneau de temps peut être réservé sur le cycle prédéfini pour chaque commutateur, et si oui sélectionner ce chemin pour router ledit flux de données ; ou - s’il existe un ou plusieurs commutateurs n’ayant pas de créneau de temps pouvant être réservé, déterminer si un créneau de temps peut être disponible dans l’intervalle de tolérance calculé pour chaque commutateur, et si oui sélectionner ce chemin pour router ledit flux de données, ou si non itérer les étapes précédentes de calcul d’intervalle de tolérance et de détermination de créneau de temps pour un autre chemin ‘m+1’ parmi les ‘k’ chemins. L’invention peut être mise en œuvre selon des modes de réalisation alternatifs ou combinés, où : - l’étape de générer les ‘k’ chemins les plus courts consiste à mettre en œuvre un algorithme de Yen. - le paramètre de latence de chemin est calculé à partir du délai de propagation et le temps de séjour moyen des paquets au niveau d’un commutateur. - l’intervalle de tolérance est calculé sur la base d’une répartition équitable entre tous les commutateurs du chemin. - l’intervalle de tolérance est calculé en fonction de la charge de chaque commutateur du chemin, et consistant à attribuer un intervalle de tolérance plus grand aux commutateurs plus chargés. - le procédé comprend des étapes consistant à retarder l’envoi de paquets pour les commutateurs plus chargés, et à accélérer l’envoi des paquets pour les commutateurs moins chargés. - le procédé comprend une étape consistant à annuler des réservations de créneaux de temps faites sur des commutateurs précédant un commutateur pour lequel il n’existe pas de créneau de temps disponible dans l’intervalle de tolérance. - le procédé comprend une étape préliminaire consistant à synchroniser tous les commutateurs et tous les terminaux connectés au réseau TSN entre eux. L’invention concerne aussi un dispositif de routage de flux de données dans un réseau déterministe sensible au temps, pour router les paquets d’un flux de données depuis un terminal émetteur vers un terminal récepteur, le réseau comprenant des commutateurs pour la transmission des paquets, lesdits commutateurs étant configurés pour mettre en œuvre une planification de transmission prédéfinie sur des cycles de temps répétés ayant des créneaux de temps de longueur fixe,, le dispositif comprenant des moyens pour mettre en œuvre les étapes du procédé de l’invention. Avantageusement, le procédé de la présente invention peut être mis en œuvre dans les deux infrastructures de gestion de réseau présentées dans le standard IEEE 802.1Qcc, à savoir, l’infrastructure centralisée et l’infrastructure distribuée. Dans un mode de réalisation pour l’approche centralisée, le procédé s’exécute au niveau du contrôleur central CNC (« Central Network Controller » en anglais). Dans un mode de réalisation pour l’approche distribuée, chaque commutateur d’un réseau TSN détermine l’allocation de créneaux de temps et il publie cette allocation vers ses voisins. L’invention concerne aussi un produit programme d’ordinateur qui comprend des instructions de code permettant d’effectuer les étapes du procédé de l’invention, lorsque le programme est exécuté sur un ordinateur. Description des figures La est un exemple simplifié pour illustrer la problématique du routage dans un réseau TSN. D’autres caractéristiques et avantages de l’invention apparaîtront à l’aide de la description qui suit et des figures des dessins annexés dans lesquels : La illustre la mesure du délai de propagation entre deux nœuds d’un réseau TSN ; La illustre les échanges entre des nœuds d’un réseau TSN pour synchroniser les horloges ; La illustre l’identification de créneaux de temps disponibles dans un intervalle de tolérance, selon un mode de réalisation de l’invention ; La illustre sur un exemple simplifié, la mise en œuvre du procédé de routage de l’invention dans un réseau TSN ; La et la sont un organigramme des étapes du procédé pour déterminer un chemin de routage selon un mode de réalisation de l’invention ; La illustre un environnement de réseau TSN selon une approche centralisée IEEE 802.1Qcc, permettant de mettre en œuvre le procédé de l’invention ; La illustre un environnement de réseau TSN selon une approche distribuée IEEE 802.1Qcc, permettant de mettre en œuvre le procédé de l’invention. Procédé de routage d’un flux de données dans un réseau déterministe sensible au temps, pour router les paquets d’un flux de données depuis un terminal émetteur vers un terminal récepteur, le réseau comprenant des commutateurs pour la transmission des paquets, lesdits commutateurs étant configurés pour mettre en œuvre une planification de transmission prédéfinie sur des cycles de temps répétés ayant des créneaux de temps de longueur fixe, le procédé étant mis en œuvre par ordinateur et comprenant des étapes consistant à : générer (602, 604) en prenant en compte un paramètre de latence de chemin, un ensemble de ‘k’ chemins les plus courts entre le terminal émetteur et le terminal récepteur ; pour un chemin ‘m’ parmi les ‘k’ chemins : calculer (606) pour chaque commutateur de ce chemin, un intervalle de tolérance sur la durée du cycle, l’intervalle de tolérance définissant une durée pendant laquelle les paquets dudit flux de données peuvent rester au niveau dudit commutateur avant d’être transmis, sans dépasser une date limite d’arrivée au terminal récepteur ; déterminer (608, 610, 622, 624, 626) si un créneau de temps peut être réservé sur le cycle prédéfini pour chaque commutateur, et si oui sélectionner (628) ce chemin pour router ledit flux de données ; ou s’il existe un ou plusieurs commutateurs n’ayant pas de créneau de temps pouvant être réservé, déterminer (612, 614, 616, 618) si un créneau de temps peut être disponible dans l’intervalle de tolérance calculé pour chaque commutateur, et si oui sélectionner (620) ce chemin pour router ledit flux de données, ou si non itérer les étapes précédentes de calcul d’intervalle de tolérance et de détermination de créneau de temps pour un autre chemin ‘m+1’ parmi les ‘k’ chemins. Le procédé selon la revendication 1 dans lequel l’étape de générer les ‘k’ chemins les plus courts consiste à mettre en œuvre un algorithme de Yen. Le procédé selon la revendication 1 ou 2 dans lequel le paramètre de latence de chemin est calculé à partir du délai de propagation et le temps de séjour moyen des paquets au niveau d’un commutateur. Le procédé selon l’une quelconque des revendications 1 à 3 dans lequel l’intervalle de tolérance est calculé sur la base d’une répartition équitable entre tous les commutateurs du chemin. Le procédé selon l’une quelconque des revendications 1 à 3 dans lequel l’intervalle de tolérance est calculé en fonction de la charge de chaque commutateur du chemin, et consistant à attribuer un intervalle de tolérance plus grand aux commutateurs plus chargés. Le procédé selon la revendication 5 comprenant des étapes consistant à retarder l’envoi de paquets pour les commutateurs plus chargés, et à accélérer l’envoi des paquets pour les commutateurs moins chargés. Le procédé selon l’une quelconque des revendications 1 à 6 comprenant une étape consistant à annuler des réservations de créneaux de temps faites sur des commutateurs précédant un commutateur pour lequel il n’existe pas de créneau de temps disponible dans l’intervalle de tolérance. Le procédé selon l’une quelconque des revendications 1 à 7 comprenant une étape préliminaire consistant à synchroniser tous les commutateurs et tous les terminaux connectés au réseau TSN entre eux. Un produit programme d’ordinateur, ledit programme d’ordinateur comprenant des instructions de code permettant d’effectuer les étapes du procédé selon l'une quelconque des revendications 1 à 8, lorsque ledit programme est exécuté sur un ordinateur. Un dispositif de routage de flux de données dans un réseau déterministe sensible au temps, pour router les paquets d’un flux de données depuis un terminal émetteur vers un terminal récepteur, le réseau comprenant des commutateurs pour la transmission des paquets, lesdits commutateurs étant configurés pour mettre en œuvre une planification de transmission prédéfinie sur des cycles de temps répétés ayant des créneaux de temps de longueur fixe, le dispositif comprenant des moyens pour mettre en œuvre les étapes du procédé selon l’une quelconque des revendications 1 à 8. Utilisation du dispositif selon la revendication 10 dans un réseau sensible au temps implémentant une architecture réseau centralisée. Utilisation du dispositif selon la revendication 10 dans un réseau sensible au temps implémentant une architecture réseau distribuée. Utilisation du dispositif selon la revendication 10 dans un réseau déterministe sensible au temps TSN implémentant une architecture réseau centralisée ou distribuée par des moyens définis selon les spécifications de la norme IEEE 802.1 Qcc.