Les systèmes avioniques sont soumis à de fortes contraintes de criticité et de temps réel. Pour certifier de telssystèmes, il est nécessaire de calculer une borne supérieure du délai de bout en bout de chaque message transmisdans le réseau. Cette thèse se focalise principalement sur l'étude des systèmes avioniques civils utilisant le réseauAFDX (Avionics Full Duplex Switched Ethernet), qui a été par exemple introduit dans l'architecture de l'AirbusA380.Dans ce contexte, nous nous sommes focalisés sur le calcul des délais de bout en bout des messages circulant dansle réseau. Parmi les méthodes existantes, nous nous sommes intéressés à la méthode des trajectoires proposéedans la littérature. Cette méthode permet de calculer des bornes supérieures du temps de traversée des messagesdans les noeuds d'un réseau AFDX. Notre première contribution a été de démontrer que cette méthode peutcalculer des délais bout en bout optimistes. Cette méthode ne peut donc pas sans modification être utilisée pourvalider les délais de bout en bout des messages transmis dans l'AFDX. Malgré l'identification des problèmes ausein de la méthode des trajectoires, il ne nous apparaît pas simple d'apporter une correction aux problèmes misen évidence. Dans un deuxième temps, nous avons proposé une nouvelle approche pour calculer ces délais quirepose sur la caractérisation pire cas du trafic que peut rencontrer un paquet, sur chaque noeud. / Avionics systems are subject to hard real-time constrainst and criticality. To certify these systems, it is neccessaryto compute the upper bound of the end-to-end delay of each message transmitted in the network. In this thesis,we mainly focus on civils avionics systems that use AFDX (Avionics Full Duplex Switched Ethernet) networkand that has been introduced in the Airbus A380 architecture.In this context, we focus in the computation of the end-to-end delays of messages crossing the network. Amongthe existing methods, we interested in the trajectory approach precedently proposed by researchers. The goal ofthis method is to compute end-to-end delay upper bounds of messages in the nodes of AFDX network. As a firstcontribution, we prove that the end-to-end delays computed by this method can be optimistic. This means thatwithout any modification, it cannot be used to validate transmission end-to-end delays for the AFDX. Despitethe identification of these optimistic problems in the trajectory approach, a solution to remove them seems notto be simple from our point of view. Hence, as a second contribution, we propose a new approach to computethese delays based on the characterization of the worst-case traffic encountered by a packet on each crossednode.

L'objectif de cette thèse est de trouver des techniques de détection et de localisation des anomalies au niveau des liens qui soient à faible coût, précises et rapides. La plupart des techniques de détection et de localisation des anomalies au niveau des liens qui existent dans la littérature calculent les solutions, c-à-d l'ensemble des chemins à monitorer et les emplacements des dispositifs de monitorage, en deux étapes. La première étape sélectionne un ensemble minimal d'emplacements des dispositifs de monitorage qui permet de détecter/localiser toutes les anomalies possibles. La deuxième étape sélectionne un ensemble minimal de chemins de monitorage entre les emplacements sélectionnés de telle sorte que tous les liens du réseau soient couverts/distinguables paire par paire. Toutefois, ces techniques ignorent l'interaction entre les objectifs d'optimisation contradictoires des deux étapes, ce qui entraîne une utilisation sous-optimale des ressources du réseau et des mesures de monitorage biaisées. L'un des objectifs de cette thèse est d'évaluer et de réduire cette interaction. A cette fin, nous proposons des techniques de détection et de localisation d'anomalies au niveau des liens qui sélectionnent les emplacements des moniteurs et les chemins qui doivent être monitorés conjointement en une seule étape. Par ailleurs, nous démontrons que la condition établie pour la localisation des anomalies est suffisante mais pas nécessaire. Une condition nécessaire et suffisante qui minimise le coût de localisation considérablement est établie. Il est démontré que les deux problèmes sont NP-durs. Des algorithmes heuristiques scalables et efficaces sont alors proposés. / The aim of this thesis is to come up with cost-efficient, accurate and fast schemes for link-level network anomaly detection and localization. It has been established that for detecting all potential link-level anomalies, a set of paths that cover all links of the network must be monitored, whereas for localizing all potential link-level anomalies, a set of paths that can distinguish between all links of the network pairwise must be monitored. Either end-node of each path monitored must be equipped with a monitoring device. Most existing link-level anomaly detection and localization schemes are two-step. The first step selects a minimal set of monitor locations that can detect/localize any link-level anomaly. The second step selects a minimal set of monitoring paths between the selected monitor locations such that all links of the network are covered/distinguishable pairwise. However, such stepwise schemes do not consider the interplay between the conflicting optimization objectives of the two steps, which results in suboptimal consumption of the network resources and biased monitoring measurements. One of the objectives of this thesis is to evaluate and reduce this interplay. To this end, one-step anomaly detection and localization schemes that select monitor locations and paths that are to be monitored jointly are proposed. Furthermore, we demonstrate that the already established condition for anomaly localization is sufficient but not necessary. A necessary and sufficient condition that minimizes the localization cost drastically is established. The problems are demonstrated to be NP-Hard. Scalable and near-optimal heuristic algorithms are proposed.

L'évolution de la technologie VLSI permet aux systèmes sur puce (SoCs) d'intégrer de nombreuses fonctions hétérogènes dans une seule puce et demande, en raison de contraintes économiques, une unique mémoire externe partagée (SDRAM). Par conséquent, la conception du système de mémoire principale, et plus particulièrement l'architecture du contrôleur de mémoire, est devenu un facteur très important dans la détermination de la performance globale du système. Le choix d'un contrôleur de mémoire qui répond aux besoins de l'ensemble du système est une question complexe. Cela nécessite l'exploration de l'architecture du contrôleur de mémoire, puis la validation de chaque configuration par simulation. Bien que l'exploration de l'architecture du contrôleur de mémoire soit un facteur clé pour une conception réussite d'un système, l'état de l'art sur les contrôleurs de mémoire ne présente pas des architectures aussi flexibles que nécessaire pour cette tâche. Même si certaines d'entre elles sont configurables, l'exploration est restreinte à des ensembles limités de paramètres tels que la profondeur des tampons, la taille du bus de données, le niveau de la qualité de service et la distribution de la bande passante. Plusieurs classes de trafic coexistent dans les applications réelles, comme le trafic de service au mieux et le trafic de service garanti qui accèdent à la mémoire partagée d'une manière concurrente. En conséquence, la considération de l'interaction entre le système de mémoire et la structur d'interconnexion est devenue vitale dans les SoCs actuels. Beaucoup de réseaux sur puce (NoCs) fournissent des services aux classes de trafic pour répondre aux exigences des applications. Cependant, très peu d'études considèrent l'accès à la SDRAM avec une approche système, et prennent en compte la spécificité de l'accès à la SDRAM dans les systèmes sur puce à base de réseaux intégrés. Cette thèse aborde le sujet de l'accès à la mémoire dynamique SDRAM dans les systèmes sur puce à base de réseaux intégrés. Nous introduisons une architecture de contrôleur de mémoire totalement configurable basée sur des blocs fonctionnels configurables, et proposons un modèle de simulation associé relativement précis temporellement et à haut niveau d'abstraction. Ceci permet l'exploration du sous-système de mémoire grâce à la facilité de configuration de l'architecture du contrôleur de mémoire. En raison de la discontinuité de services entre le réseau sur puce et le contrôleur de mémoire, nous proposons également dans le cadre de cette thèse un protocole de contrôle de flux de bout en bout pour accéder à la mémoire à travers un contrôleur de mémoire multiports. L'idée, simple sur le principe mais novatrice car jamais proposée à notre connaissance, se base sur l'exploitation des informations sur l'état du contrôleur de mémoire dans le réseau intégré. Les résultats expérimentaux montrent qu'en contrôlant l'injection du trafic de service au mieux dans le réseau intégré, notre protocole augmente les performances du trafic de service garanti en termes de bande passante et de latence, tout en préservant la bande passante moyenne du trafic de service au mieux.

L'évolution de la technologie VLSI permet aux systèmes sur puce (SoCs) d'intégrer de nombreuses fonctions hétérogènes dans une seule puce et demande, en raison de contraintes économiques, une unique mémoire externe partagée (SDRAM). Par conséquent, la conception du système de mémoire principale, et plus particulièrement l'architecture du contrôleur de mémoire, est devenu un facteur très important dans la détermination de la performance globale du système. Le choix d'un contrôleur de mémoire qui répond aux besoins de l'ensemble du système est une question complexe. Cela nécessite l'exploration de l'architecture du contrôleur de mémoire, puis la validation de chaque configuration par simulation. Bien que l'exploration de l'architecture du contrôleur de mémoire soit un facteur clé pour une conception réussite d'un système, l'état de l'art sur les contrôleurs de mémoire ne présente pas des architectures aussi flexibles que nécessaire pour cette tâche. Même si certaines d'entre elles sont configurables, l'exploration est restreinte à des ensembles limités de paramètres tels que la profondeur des tampons, la taille du bus de données, le niveau de la qualité de service et la distribution de la bande passante. Plusieurs classes de trafic coexistent dans les applications réelles, comme le trafic de service au mieux et le trafic de service garanti qui accèdent à la mémoire partagée d'une manière concurrente. En conséquence, la considération de l'interaction entre le système de mémoire et la structure d'interconnexion est devenue vitale dans les SoCs actuels. Beaucoup de réseaux sur puce (NoCs) fournissent des services aux classes de trafic pour répondre aux exigences des applications. Cependant, très peu d'études considèrent l'accès à la SDRAM avec une approche système, et prennent en compte la spécificité de l'accès à la SDRAM dans les systèmes sur puce à base de réseaux intégrés. Cette thèse aborde le sujet de l'accès à la mémoire dynamique SDRAM dans les systèmes sur puce à base de réseaux intégrés. Nous introduisons une architecture de contrôleur de mémoire totalement configurable basée sur des blocs fonctionnels configurables, et proposons un modèle de simulation associé relativement précis temporellement et à haut niveau d'abstraction. Ceci permet l'exploration du sous-système de mémoire grâce à la facilité de configuration de l'architecture du contrôleur de mémoire. En raison de la discontinuité de services entre le réseau sur puce et le contrôleur de mémoire, nous proposons également dans le cadre de cette thèse un protocole de contrôle de flux de bout en bout pour accéder à la mémoire à travers un contrôleur de mémoire multiports. L'idée, simple sur le principe mais novatrice car jamais proposée à notre connaissance, se base sur l'exploitation des informations sur l'état du contrôleur de mémoire dans le réseau intégré. Les résultats expérimentaux montrent qu'en contrôlant l'injection du trafic de service au mieux dans le réseau intégré, notre protocole augmente les performances du trafic de service garanti en termes de bande passante et de latence, tout en préservant la bande passante moyenne du trafic de service au mieux.

L'évolution de la technologie VLSI permet aux systèmes sur puce (SoCs) d'intégrer de nombreuses fonctions hétérogènes dans une seule puce et demande, en raison de contraintes économiques, une unique mémoire externe partagée (SDRAM). Par conséquent, la conception du système de mémoire principale, et plus particulièrement l'architecture du contrôleur de mémoire, est devenu un facteur très important dans la détermination de la performance globale du système. Le choix d'un contrôleur de mémoire qui répond aux besoins de l'ensemble du système est une question complexe. Cela nécessite l'exploration de l'architecture du contrôleur de mémoire, puis la validation de chaque configuration par simulation. Bien que l'exploration de l'architecture du contrôleur de mémoire soit un facteur clé pour une conception réussite d'un système, l'état de l'art sur les contrôleurs de mémoire ne présente pas des architectures aussi flexibles que nécessaire pour cette tâche. Même si certaines d'entre elles sont configurables, l'exploration est restreinte à des ensembles limités de paramètres tels que la profondeur des tampons, la taille du bus de données, le niveau de la qualité de service et la distribution de la bande passante. Plusieurs classes de trafic coexistent dans les applications réelles, comme le trafic de service au mieux et le trafic de service garanti qui accèdent à la mémoire partagée d'une manière concurrente. En conséquence, la considération de l'interaction entre le système de mémoire et la structure d'interconnexion est devenue vitale dans les SoCs actuels. Beaucoup de réseaux sur puce (NoCs) fournissent des services aux classes de trafic pour répondre aux exigences des applications. Cependant, très peu d'études considèrent l'accès à la SDRAM avec une approche système, et prennent en compte la spécificité de l'accès à la SDRAM dans les systèmes sur puce à base de réseaux intégrés. Cette thèse aborde le sujet de l'accès à la mémoire dynamique SDRAM dans les systèmes sur puce à base de réseaux intégrés. Nous introduisons une architecture de contrôleur de mémoire totalement configurable basée sur des blocs fonctionnels configurables, et proposons un modèle de simulation associé relativement précis temporellement et à haut niveau d'abstraction. Ceci permet l'exploration du sous-système de mémoire grâce à la facilité de configuration de l'architecture du contrôleur de mémoire. En raison de la discontinuité de services entre le réseau sur puce et le contrôleur de mémoire, nous proposons également dans le cadre de cette thèse un protocole de contrôle de flux de bout en bout pour accéder à la mémoire à travers un contrôleur de mémoire multiports. L'idée, simple sur le principe mais novatrice car jamais proposée à notre connaissance, se base sur l'exploitation des informations sur l'état du contrôleur de mémoire dans le réseau intégré. Les résultats expérimentaux montrent qu'en contrôlant l'injection du trafic de service au mieux dans le réseau intégré, notre protocole augmente les performances du trafic de service garanti en termes de bande passante et de latence, tout en préservant la bande passante moyenne du trafic de service au mieux. / The ongoing advancements in VLSI technology allow System-on-Chip (SoC) to integrate many heterogeneous functions into a single chip, but still demand, because of economical constraints, a single and shared main off-chip SDRAM. Consequently, main memory system design, and more specifically the architecture of the memory controller, has become an increasingly important factor in determining the overall system performance. Choosing a memory controller design that meets the needs of the whole system is a complex issue. This requires the exploration of the memory controller architecture, and then the validation of each configuration by simulation. Although the architecture exploration of the memory controller is a key to successful system design, state of the art memory controllers are not as flexible as necessary for this task. Even if some of them present a configurable architecture, the exploration is restricted to limited sets of parameters such as queue depth, data bus size, quality-of-service level, and bandwidth distribution. Several classes of traffic co-exist in real applications, e.g. best effort traffic and guaranteed service traffic, and access the main memory. Therefore, considering the interaction between the memory subsystem and the interconnection system has become vital in today's SoCs. Many on chip networks provide guaranteed services to traffic classes to satisfy the applications requirements. However, very few studies consider the SDRAM access within a system approach, and take into account the specificity of the SDRAM access as a target in NoC-based SoCs. This thesis addresses the topic of dynamic access to SDRAM in NoC-based SoCs. We introduce a totally customizable memory controller architecture based on fully configurable building components and design a high level cycle approximate model for it. This enables the exploration of the memory subsystem thanks to the ease of configuration of the memory controller architecture. Because of the discontinuity of services between the network and the memory controller, we also propose within the framework of this thesis an Extreme End to End flow control protocol to access the memory device through a multi-port memory controller. The simple yet novel idea is to exploit information about the memory controller status in the NoC. Experimental results show that by controlling the best effort traffic injection in the NoC, our protocol increases the performance of the guaranteed service traffic in terms of bandwidth and latency, while maintaining the average bandwidth of the best effort traffic.

D’après Cisco, le trafic mobile de données augmentera d’un facteur 7 entre 2016 et 2021. Pour faire face à l’augmentation du trafic, les opérateurs mobile dimensionnent le réseau, ce qui s’accompagne d’une augmentation de sa consommation d’énergie et de son empreinte Carbonne. En outre, les marges financières des opérateurs baissent. Ainsi, le revenu global généré par le secteur des télécommunications a connu une baisse de 4% entre 2014 et 2015 d’après l’union internationale des télécommunications (UIT). Ces préoccupations ont suscité l’intérêt de la communauté scientifique pour la réduction de la consommation électrique des réseaux. Des études dans la littérature estiment l’énergie consommée par les services sur les équipements réseaux en se focalisant sur la consommation variable. La consommation énergétique d’un équipement réseau est composée d’une composante fixe et d’une composante variable. Dans cette thèse, nous partageons la responsabilité des catégories de service dans la consommation fixe du réseau en utilisant la valeur de Shapley. Dans un premier temps, nous considérons un réseau d’accès mobile et partageons la responsabilité des catégories de service qu’il fournit dans la consommation fixe. Nous définissons 5 catégories de service, à savoir, le «Streaming», le Web, le téléchargement, la voix et les autres services de données. En outre, nous traitons le cas de figure où certaines catégories de service sont obligatoires. Etant donné la complexité algorithmique de la valeur de Shapley, nous en proposons une forme approchée qui permet d’en réduire considérablement le temps de calcul. Ensuite, nous considérons le réseau de bout-en-bout, c’est-à-dire, l’accès mobile, l’accès fixe, la collecte, le coeur IP, le coeur mobile, les registres et les plateformes de service. Pour chaque segment, nous partageons la responsabilité des catégories de service dans la consommation fixe en appliquant notre modèle de partage basé sur la valeur de Shapley. L’analyse des résultats montre que le service «Streaming» consomme le plus d’énergie quel que soit le segment de réseau considéré, à l’exception des registres. Pour finir, nous traitons de la modélisation de l’efficacité énergétique des catégories de service. Dans un premier temps, nous calculons l’efficacité énergétique des catégories de service étant donné une station de base avec et sans «sleep mode». Ensuite, nous calculons l’efficacité énergétique des catégories de service étant donné un réseau d’accès mobile et considérant les cas avec et sans catégories de service obligatoires. Aussi étudions-nous les conditions pour ne pas détériorer l’efficacité énergétique du réseau au cours du temps en fonction des scénarios de dimensionnement / Internet traffic is growing exponentially. According to Cisco, mobile data traffic will increase sevenfold between 2016 and 2021, growing at a compound annual growth rate (CAGR) of 47%. In order to improve or keep up with users quality of experience (QoE), mobile carriers upgrade the network with additional equipment. As a consequence, the network carbon footprint increases over time, alongside with its energy consumption. In addition, mobile carriers margins are decreasing. Global telecommunication revenues declined by 4% between 2014 and 2015 based on the international telecommunication union (ITU) figures. These concerns fostered a great interest in the research community for reducing networks energy consumption. In this regard, many works in the literature investigate the energy consumed by services on network equipment for optimization purposes notably, focusing on the variable component of energy consumption. Energy consumption of a network equipment is composed of a variable and a fixed components. The variable component is consumed to serve traffic. The fixed component is consumed irrespective of traffic. In this thesis, our objective is to share the responsibility of service categories in the fixed energy consumption. To do so, we use the Shapley value. First, we consider a radio access network and share the responsibility of the service categories it delivers in the fixed energy consumption. The services are classified into five categories, namely, Streaming, Web, Download, Voice and other data services. In addition, we consider the case when some service categories are mandatory to be provided, such as Voice due to legal constraints for instance. Because the Shapley value has a huge computational complexity, we introduce closed-form expressions in order to significantly reduce it. Next, we consider the end-to-end network and all its segments, that is, the mobile access, the fixed access, the collect, the mobile core, the registers, the IP core and the service platforms. For each segment, we share the responsibility of the service categories in the fixed energy consumption with the Shapley-based model introduced in the preceding chapter. We find that Streaming is the service that consumes the most whatever the network segment, except for registers, as it represents the vast majority of Internet traffic. Eventually, we focus on the service categories energy efficiency. First, we consider a base station and compute the services energy efficiency for the cases with and without sleep mode. Then, we consider a radio access network and compute the services energy efficiency with and without a mandatory player. Moreover, we discuss the conditions to not deteriorate the network energy efficiency over time following different upgrade scenarios

Dans cette thèse, nous analysons les réseaux des systèmes temps-réel distribués et plus particulièrement ceux des domaines de l’avionique et de l’automobile. Nous nous sommes focalisés sur deux protocoles : « Avionic Full DupleX Switched Ethernet » (AFDX), « Audio Vidéo Bridging Ethernet » (AVB). Dans ces domaines critiques, le déterminisme du réseau doit être garanti. Il consiste, notamment, en la détermination d’une borne garantie du délai de bout en bout de traversée du réseau pour chaque trame ; et un dimensionnement des files d’attente des trames suffisamment grand pour garantir qu’aucune d’entre elle ne débordera et ainsi, éviter toute perte de trame.Il existe plusieurs méthodes pour l’évaluation des délais et nous avons, principalement, travaillé sur la méthode « Forward end-to-end delay Analysis » (FA). FA avait déjà été définie avec la politique d’ordonnancement « First-In-First-Out » dans le contexte de l’AFDX. Nous sommes repartis de cette approche, nous l’avons reformulé et généralisé à n’importe quel réseau Ethernet commuté. Nous l’avons aussi étendu aux priorités statiques et au protocole AVB et sa politique de service « Credit Based Shaper ». Pour chaque contribution, des démonstrations formelles ont été présentées et une expérimentation incluant une comparaison de FA avec les principales approches d’évaluation sur un exemple industriel. Finalement, nous avons développé et démontré formellement une approche pour le dimensionnement des files d’attente en termes de nombre de trames. Cette approche a été expérimentée également sur une configuration industrielle. / In this thesis, we analyze networks in the context of distributed real-time systems, especially in the fields of avionics, with “Avionics Full DupleX Switched Ethernet” (AFDX), and automobile, with “Audio Video Bridging Ethernet” (AVB). For such applications, network determinism needs to be guaranteed. It involves, in particular, assessing a guaranteed bound on the end-to-end traversal time across the network fr each frame; and dimensioning the buffers in order to avoid any loss of frame because of a buffer overflow.There are several methods for worst-case delay analysis, and we have mainly worked on the “Forward end-to-end Delay Analysis” (FA) method. FA had already been developed for “First-In-First-Out” scheduling policy in the AFDX context, so we generalized it to any Switched Ethernet network. We have also extended it to handle static priorities and the AVB protocol, shaping policy named “Credit Based Shaper” (CBS). Each contribution has been formaly proved and experiments have been led on industrial configurations. For our experimentations, we have compared our results with the results of competing approaches. Finally, we have developed and formally demonstrated an approach for buffer dimensioning in terms of number of frames. This approach has also been tested on an industrial configuration and has produced tight bounds.

Dans cette thèse, nous présentons notre travail sur la gestion des pannes dans les systèmes distribués, avec comme motivation principale le suivi de fautes et de changements brusques dans de grands systèmes informatiques comme la grille et le cloud.Au lieu de construire une connaissance complète a priori du logiciel et des infrastructures matérielles comme dans les méthodes traditionnelles de détection ou de diagnostic, nous proposons d'utiliser des techniques spécifiques pour effectuer une surveillance de bout en bout dans des systèmes de grande envergure, en laissant les détails inaccessibles des composants impliqués dans une boîte noire.Pour la surveillance de pannes d'un système distribué, nous modélisons tout d'abord cette application basée sur des sondes comme une tâche de prédiction statique de collaboration (CP), et démontrons expérimentalement l'efficacité des méthodes de CP en utilisant une méthode de la max margin matrice factorisation. Nous introduisons en outre l’apprentissage actif dans le cadre de CP et exposons son avantage essentiel dans le traitement de données très déséquilibrées, ce qui est particulièrement utile pour identifier la class de classe de défaut de la minorité.Nous étendons ensuite la surveillance statique de défection au cas séquentiel en proposant la méthode de factorisation séquentielle de matrice (SMF). La SMF prend une séquence de matrices partiellement observées en entrée, et produit des prédictions comportant des informations à la fois sur les fenêtres temporelles actuelle et passé. L’apprentissage actif est également utilisé pour la SMF, de sorte que les données très déséquilibrées peuvent être traitées correctement. En plus des méthodes séquentielles, une action de lissage pris sur la séquence d'estimation s'est avérée être une astuce pratique utile pour améliorer la performance de la prédiction séquentielle.Du fait que l'hypothèse de stationnarité utilisée dans le surveillance statique et séquentielle devient irréaliste en présence de changements brusques, nous proposons un framework en ligne semi-Supervisé de détection de changement (SSOCD) qui permette de détecter des changements intentionnels dans les données de séries temporelles. De cette manière, le modèle statique du système peut être recalculé une fois un changement brusque est détecté. Dans SSOCD, un procédé hors ligne non supervisé est proposé pour analyser un échantillon des séries de données. Les points de changement ainsi détectés sont utilisés pour entraîner un modèle en ligne supervisé, qui fournit une décision en ligne concernant la détection de changement à parti de la séquence de données en entrée. Les méthodes de détection de changements de l’état de l’art sont utilisées pour démontrer l'utilité de ce framework.Tous les travaux présentés sont vérifiés sur des ensembles de données du monde réel. Plus précisément, les expériences de surveillance de panne sont effectuées sur un ensemble de données recueillies auprès de l’infrastructure de grille Biomed faisant partie de l’European Grid Initiative et le framework de détection de changement brusque est vérifié sur un ensemble de données concernant le changement de performance d'un site en ligne ayant un fort trafic. / In this dissertation, we present our work on fault management in distributed systems, with motivating application roots in monitoring fault and abrupt change of large computing systems like the grid and the cloud. Instead of building a complete a priori knowledge of the software and hardware infrastructures as in conventional detection or diagnosis methods, we propose to use appropriate techniques to perform end-To-End monitoring for such large scale systems, leaving the inaccessible details of involved components in a black box.For the fault monitoring of a distributed system, we first model this probe-Based application as a static collaborative prediction (CP) task, and experimentally demonstrate the effectiveness of CP methods by using the max margin matrix factorization method. We further introduce active learning to the CP framework and exhibit its critical advantage in dealing with highly imbalanced data, which is specially useful for identifying the minority fault class.Further we extend the static fault monitoring to the sequential case by proposing the sequential matrix factorization (SMF) method. SMF takes a sequence of partially observed matrices as input, and produces predictions with information both from the current and history time windows. Active learning is also employed to SMF, such that the highly imbalanced data can be coped with properly. In addition to the sequential methods, a smoothing action taken on the estimation sequence has shown to be a practically useful trick for enhancing sequential prediction performance.Since the stationary assumption employed in the static and sequential fault monitoring becomes unrealistic in the presence of abrupt changes, we propose a semi-Supervised online change detection (SSOCD) framework to detect intended changes in time series data. In this way, the static model of the system can be recomputed once an abrupt change is detected. In SSOCD, an unsupervised offline method is proposed to analyze a sample data series. The change points thus detected are used to train a supervised online model, which gives online decision about whether there is a change presented in the arriving data sequence. State-Of-The-Art change detection methods are employed to demonstrate the usefulness of the framework.All presented work is verified on real-World datasets. Specifically, the fault monitoring experiments are conducted on a dataset collected from the Biomed grid infrastructure within the European Grid Initiative, and the abrupt change detection framework is verified on a dataset concerning the performance change of an online site with large amount of traffic.

Tout comportement défectueux d’un système temps-réel critique, comme celui utilisé dans le réseau avionique ou le secteur nucléaire, peut mettre en danger des vies. Par conséquent, la vérification et validation de ces systèmes est indispensable avant leurs déploiements. En fait, les autorités de sécurité demandent d’assurer des garanties déterministes. Dans cette thèse, nous nous intéressons à obtenir des garanties temporelles, en particulier nous avons besoin de prouver que le temps de réponse de bout-en-bout de chaque flux présent dans le réseau est borné. Ce sujet a été abordé durant de nombreuses années et plusieurs approches ont été développées. Après une brève comparaison entre les différentes approches existantes, une semble être un bon candidat. Elle s’appelle l’approche par trajectoire; cette méthode utilise les résultats établis par la théorie de l'ordonnancement afin de calculer une limite supérieure. En réalité, la surestimation de la borne calculée peut entrainer la rejection de certification du réseau. Ainsi une première partie du travail consiste à détecter les sources de pessimisme de l’approche adoptée. Dans le cadre d’un ordonnancement FIFO, les termes ajoutant du pessimisme à la borne calculée ont été identifiés. Cependant, comme les autres méthodes, l’approche par trajectoire souffre du problème de passage à l’échelle. En fait, l’approche doit être appliquée sur un réseau composé d’une centaine de commutateur et d’un nombre de flux qui dépasse les milliers. Ainsi, il est important qu’elle soit en mesure d'offrir des résultats dans un délai acceptable. La première étape consiste à identifier, dans le cas d’un ordonnancement FIFO, les termes conduisant à un temps de calcul important. L'analyse montre que la complexité du calcul est due à un processus récursif et itératif. Ensuite, en se basant toujours sur l’approche par trajectoire, nous proposons de calculer une limite supérieure dans un intervalle de temps réduit et sans perte significative de précision. C'est ce qu'on appelle l'approche par trajectoire scalable. Un outil a été développé permettant de comparer les résultats obtenus par l’approche par trajectoire et notre proposition. Après application sur un réseau de taille réduite (composé de 10 commutateurs), les résultats de simulations montrent que la durée totale nécessaire pour calculer les bornes des milles flux a été réduite de plusieurs jours à une dizaine de secondes. / In critical real-time systems, any faulty behavior may endanger lives. Hence, system verification and validation is essential before their deployment. In fact, safety authorities ask to ensure deterministic guarantees. In this thesis, we are interested in offering temporal guarantees; in particular we need to prove that the end-to-end response time of every flow present in the network is bounded. This subject has been addressed for many years and several approaches have been developed. After a brief comparison between the existing approaches, the Trajectory Approach sounded like a good candidate due to the tightness of its offered bound. This method uses results established by the scheduling theory to derive an upper bound. The reasons leading to a pessimistic upper bound are investigated. Moreover, since the method must be applied on large networks, it is important to be able to give results in an acceptable time frame. Hence, a study of the method’s scalability was carried out. Analysis shows that the complexity of the computation is due to a recursive and iterative processes. As the number of flows and switches increase, the total runtime required to compute the upper bound of every flow present in the network understudy grows rapidly. While based on the concept of the Trajectory Approach, we propose to compute an upper bound in a reduced time frame and without significant loss in its precision. It is called the Scalable Trajectory Approach. After applying it to a network, simulation results show that the total runtime was reduced from several days to a dozen seconds.

Les protocoles de contrôle de congestion ont pour but d'autoriser un partage équitable des ressources entre les utilisateurs et d'éviter la congestion dans les réseaux de communications. Dans cette thèse, nous avons commencé par comparer la performance des différents protocoles dans des modèles de réseaux qui intègrent la notion de variation de bande passante produit par l'agrégation/désagrégation des flux ainsi que la présence des mécanismes fournissant de la Qualité du Service.<br /><br />Ainsi, nous avons montré que ce sont les protocoles basés sur l'assistance de routeurs fournissant aux émetteurs un taux d'émission explicite (``Explicit Rate Notification'' - ERN) partagent mieux les ressources du réseaux entre les utilisateurs et évitent mieux la congestion que les protocoles de bout-en-bout (comme les protocoles basés sur TCP). Cependant, l'absence d'inter-opérabilité des protocoles ERN avec les routeurs non-ERN (par exemple, les routeurs DropTail) et les protocoles de congestion de bout-en-bout (comme TCP), empêche leur mise en place dans les réseaux actuels.<br /><br />Pour résoudre les problèmes d'inter-opérabilité des protocoles ERN avec des routeurs non-ERN, nous avons proposé des stratégies et des mécanismes capables de détecter les groupes des routeurs non-ERN entre deux routeurs ERN, d'estimer la bande passante minimale disponible à l'intérieur de ces groupes, et de créer des routeurs virtuels qui remplacent chaque groupe de routeurs non-ERN par un routeur ERN.<br /><br />Nous avons également proposé un système d'équité intra-protocolaire entre les protocoles ERN et les protocoles de bout-en-bout. Avec notre solution, les routeurs ERN dans une première étape estiment les besoins en terme de bande passante des flux ERN et non-ERN puis, dans une deuxième étape, limitent le débit des flux non-ERN en rejetant leurs paquets avec une probabilité qui dépend des résultats de la première étape.<br /><br />Le succès des protocoles ERN est basé sur l'information de rétroalimentation, calculée par les routeurs, et renvoyée par les récepteurs aux émetteurs. Nous avons montré que les protocoles ERN deviennent instables face aux pertes de l'information de rétroalimentation dans des environnements hétérogènes et à bande passante variable. Dans ce cadre là, nous avons proposé une nouvelle architecture qui améliore la robustesse des protocoles ERN, ainsi que la réactivité des émetteurs.<br /><br />Toutes nos propositions, applicables sur d'autres protocoles ERN, ont été expérimentées et validées sur le protocole eXplicit Control Protocol (XCP). Ainsi, nous avons montré que nos solutions surmontent les défis concernant les problèmes d'inter-opérabilité des protocoles ERN dans un grand nombre des scénarios et de topologies.<br /><br />De cette façon, nous avons développé les bases pour bénéficier d'un protocole ERN capable d'être déployé dans des réseaux hétérogènes à grand produit bande passante - délai où le transfert de grande quantité des données est nécessaire, tels que les réseaux de grilles (ex. GÉANT).