Analysis of the side-effects on latency bounds of combinations of scheduling, redundancy and synchronization mechanisms in time-sensitive networks

Les réseaux temps-réels, comme ceux spécifiés par IEEE Time-Sensitive Networking (TSN) et IETF Deterministic Networking (DetNet), fournissent aux applications critiques un service déterministe avec des bornes de latence garanties.Plusieurs mécanismes comme les ordonnanceurs et les régulateurs de trafic (TSN ATS, asynchronous traffic shaping) ont été développés et leurs effets sur les bornes de latences pire-cas ont été abondamment étudiés dans la littérature en utilisant la théorie du calcul réseau.Toutefois, les réseaux temps-réels doivent désormais aussi offrir une reconfiguration simplifiée avec des chemins alternatifs, un haut niveau de fiabilité et parfois un service de synchronisation du temps.Pour répondre à ces besoins, l'utilisation de topologies à plusieurs chemins a été encouragée pour faciliter la reconfiguration et des mécanismes de redondance et de synchronisation ont été développés pour fournir un haut niveau de fiabilité et une synchronisation du temps.Tandis que chacun de ces mécanismes dispose d'une théorie pour valider son efficacité dans son objectif respectif, la littérature n'a que peu étudié leurs effets secondaires sur les bornes de latences et leurs interactions avec les ordonnanceurs et les régulateurs de trafic.Dans cette thèse, nous utilisons la théorie du calcul réseau pour analyser les combinaisons de mécanismes et leurs effets sur les bornes de latences dans les réseaux temps-réel avec des topologies à plusieurs chemins.Nos principales contributions sur le plan théorique sont :1/ Nous développons un algorithme (FP-TFA) qui calcule des bornes de latence dans les réseaux dans lesquels la variété des chemins crée des dépendances cycliques.Nous proposons et analysons l'approche de déploiement partielle des régulateurs de trafic (soit par flux, soit avec TSN ATS) ainsi qu'un autre algorithme (LCAN) qui casse toutes les dépendances cycliques à coût minimal.2/ Nous analysons les effets des mécanismes de redondance sur les bornes de latence en modélisant leur comportement dans la théorie du calcul réseau.Nous analysons aussi leurs interactions avec les régulateurs de trafic.En particulier, nous observons que TSN ATS peut mener à des latences non bornées lorsqu'il est utilisé avec les mécanismes de redondances.3/ Nous proposons un modèle d'horloge qui décrit, au sein de la théorie du calcul réseau, les imperfections des horloges des réseaux synchronisés ou non.Nous montrons que l'usage de régulateurs de trafic avec des horloges imparfaites occasionne une pénalité dans les bornes de latence.Avec TSN ATS, cette pénalité n'est pas bornée, y compris dans les réseaux synchronisés avec une grande précision.Nous proposons deux méthodes (cascade et ADAM) pour adapter les paramètres des régulateurs et ainsi résoudre ce problème.Nous fournissons également des contributions d'intérêt pratique :a) l'outil modulaire xTFA, qui calcule des bornes de latences en utilisant les résultats de la thèse,b) un module pour simuler l'effet des horloges locales dans le simulateur à évènements discrets ns-3, etc) une application de nos résultats sur une étude de cas industrielle.Time-sensitive networks, as in the context of IEEE Time-Sensitive Networking (TSN) and IETF Deterministic Networking (DetNet), support safety-critical applications by providing deterministic services with guaranteed latency bounds.Several mechanisms, such as schedulers and traffic regulators (TSN ATS, asynchronous traffic shaping), have been developed, and their effects on worst-case latency bounds have been widely studied in the literature by using the network-calculus framework.Time-sensitive networks are also required, however, to offer an easy reconfiguration with alternative paths, a high level of reliability and sometimes a time-synchronization service.To meet these needs, multi-path topologies were developed to enable the reconfiguration, and a set of redundancy and synchronization mechanisms were developed to provide high reliability and time synchronization.Although the mechanisms can rely on their own theory to validate their adequacyto its respective objective, their side effects on the latency bounds and their interactions with the schedulers and traffic regulators have hardly been analyzed in the literature.In this thesis, we use the network-calculus framework to analyze the combinations of mechanisms and their effects on latency bounds in time-sensitive networks with multi-path topologies.Our main contributions at the theoretical level are as follows:1/ We develop an algorithm (FP-TFA) for computing latency bounds in networks with multi-path topologies that lead to cyclic dependencies.We propose and analyze the partial-deployment approach of traffic regulators (either per-flow or TSN ATS) and another algorithm (LCAN) for breaking all cyclic dependencies at minimal cost.2/ We analyze the effect of redundancy mechanisms on latency bounds by capturing their behavior with the network-calculus framework.We analyze their interactions with traffic regulators.We find that, in particular, TSN ATS can yield unbounded latencies when used with redundancy mechanisms.3/ We provide a clock model that captures the clock non-idealities of synchronized and non-synchronized networks within the network-calculus framework.We show that traffic regulators with non-ideal clocks can lead to latency penalties; with TSN ATS this penalty is unbounded even in tightly synchronized networks.We propose two methods (rate-and-burst cascade and ADAM) for adapting the parameters of the traffic regulators and for addressing the above issue.We also provide contributions of practical interest:a) the xTFA modular tool that computes latency bounds by using the results of the thesis,b) a module for simulating the effects of local clocks in the discrete-event simulator ns-3, andc) an application of our results to an industrial use-case