Les interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, de trafic IP, d'achats en ligne, d'exécution de code, etc. Les interactions peuvent être dirigées, pondérées, enrichies d'informations supplémentaires, cependant, dans tous les cas, une interaction signifie que deux entités u et v ont interagi du temps b au temps e : par exemple, deux individus u et v se rencontrent du temps b au temps e, deux machines sur un réseau démarrent une session IP du temps b au temps e, deux personnes u et v se téléphonent du temps b au temps e, etc.Dans cette thèse, nous explorons une nouvelle approche visant à modéliser les interactions directement comme des flots de liens, c'est-à-dire des séquences de quadruplets (b,e,u,v) signifiant que u et v ont interagi du temps b au temps e. Nous posons les fondations du formalisme correspondant. Afin de valider notre travail théorique, nous nous concentrons sur l'analyse de trafic IP. Il est en effet crucial pour nous d'effectuer des aller-retours constants entre théorie et pratique : les cas pratiques doivent nourrir notre réflexion théorique, et, en retour, les outils formels doivent être conçus de façon à être appliqués de la manière la plus générale.Nous appliquons notre formalisme à l'analyse de trafic IP, dans le but de valider la pertinence de notre formalisme for l'analyse de trafic IP, ainsi que comme méthodologie de détection d'événements. Nous élaborons une méthode permettant d'identifier des événements recouvrant plusieurs échelles de temps, et l'appliquons à une trace de trafic issue du jeu de données MAWI. / Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, online purchases, running code, and many others. Interactions may be directed, weighted, enriched with supplementary information, yet the baseline remains: in all cases, an interaction means that two entities u and v interact together from time b to time e: for instance, two individuals u and v meet from time b to time e, two machines on a network start an IP session from time b to time e, two persons u and v phone each other from time b to time e, and so on.In this thesis, we explore a new approach consisting in modelling interactions directly as link streams, i.e. series of quadruplets ( b, e, u, v ) meaning that u and v interacted from time b to time e, and we develop the basis of the corresponding formalism. In order to guide and assess this fundamental work, we focus on the analysis of IP traffic. It is particularly important to us that we make both fundamental and applied progress: application cases should feed our theoretical thoughts, and formal tools are designed to have meaning on application cases in the most general way.We apply our framework to the analysis of IP traffic, with the aim of assessing the relevance of link streams for describing IP traffic as well as finding events inside the traffic. We devise a method to identify events at different scales, and apply it to a trace of traffic from the MAWI dataset.

Dans cette thèse, nous nous sommes intéressés à l'analyse et la conception de réseaux étudiés sont les réseaux de fibres optiques et les réseaux de capteurs. Les problématiques étudiées sont: pour les réseaux de fibres optiques, minimiser le coût de déploiement et assurer la qualité de service; dans les réseaux de capteurs, garantir la sécurité des transmissions et l'énergie consommée par le routage des communications. Pour résoudre ces problèmes nous utilisons des techniques de théorie des graphes, de complexité, de programmation linéaire. Le premier problème consiste à concevoir un plan d'installation de fibres optiques de coût minimal permettant de connecter un ensemble de clients à un noeud de raccordement via un ensemble de coupleurs en respectant les contraintes technologiques imposées par la norme. Nous proposons une modélisation de ce problème ainsi qu'une méthode de résolution. Le deuxième problème est un problème de flot avec contrainte de délai où le délai pour traverser une liaison est proportionnel à la quantité de flot quicircule sur celle-ci. Nous proposons une preuve de NP-complétude dans le cas général, un algorithme d'approximation facteur 2 dans le cas où le graphe support est un chemin et une heuristique évaluée de façon expérimentale qui calcule en un temps raisonnable de bonnes solutions pour des instances de tailles réelles. Enfin, nous proposons deux protocoles concernant les réseaux de capteurs. Le premier, basé sur un algorithme distribué, calcule un ensemble de chemins disjoints entre les terminaux. Le second maximise la durée de vie d'un réseau de capteurs alimentés par batteries. Des résultats s'expérimentations numériques sont présentés. / In this thesis, we study some optimization problem applied to telecommunication networks. We study fiber optical networks and sensor networks. We are interested to analysis and design for these types of networks. The issues studied are: for fiber optic networks, minimize the cost of deployement and ensure quality of service; for sensors network, ensure the safety of transmissions and the energy consumed. To solve these problems we use techniques as graphs theory, complexity, linearprogramming, generalized flows and paths with resource constraints. The first problem is to minimize the cost to deploy a fiber optical network which connect a set of customers to a connection node through a set of splitter and deal about technological constraints imposed by the standard. We propose a model and a method of resolution for this problem. The second problem is a flow problem with delay constraint where time to cross a edge is proportional to the amount of flow that flows thereon. We offer a proof of NP-completeness in the general case, an approximation algorithm factor 2 in the case where the support graph is a path and an estimated experimentally an heuristic that calculates good solutions for instances of real sizes. Finally, we propose two protocols for sensor networks, which resulted in two patents. The first, based on a distributed algorithm, calculates a set of disjoint paths between terminals. The second maximizing the lifetime of sensors powered by batteries. The results of numerical experiments are also presented.

Sur une droite, le transport optimal ne pose pas de difficultés. Récemment, ce constat a été utilisé pour traiter des problèmes plus généraux. En effet, on a remarqué qu'une habile désintégration permet souvent de se ramener à la dimension un, ce qui permet d'utiliser les méthodes afférentes pour obtenir un premier résultat, que l'on fait ensuite évoluer pour gagner en précision.Je montre ici l'efficacité de cette approche, en revenant sur deux problèmes déjà résolus partiellement de cette manière, et en complétant la réponse qui en avait été donnée.Le premier problème concerne le calcul de l'application de Yann Brenier. En effet, Guillaume Carlier, Alfred Galichon et Filippo Santambrogio ont prouvé que celle-ci peut être obtenue grâce à une équation différentielle, pour laquelle une condition initiale est donnée par le réarrangement de Knothe--Rosenblatt (lui-même défini via une succession de transformations unidimensionnelles). Ils n'ont cependant traité que des mesures finales discrètes ; j'étends leur résultat aux cas continus. L'équation de Monge--Ampère, une fois dérivée, donne une EDP pour le potentiel de Kantorovitch; mais pour obtenir une condition initiale, il faut utiliser le théorème des fonctions implicites de Nash--Moser.Le chapitre 1 rappelle quelques résultats essentiels de la théorie du transport optimal, et le chapitre 2 est consacré au théorème de Nash--Moser. J'expose ensuite mes propres résultats dans le chapitre 3, et leur implémentation numérique dans le chapitre 4.Enfin, le dernier chapitre est consacré à l'algorithme IDT, développé par François Pitié, Anil C. Kokaram et Rozenn Dahyot. Celui-ci construit une application de transport suffisamment proche de celle de M. Brenier pour convenir à la plupart des applications. Une interprétation en est proposée en termes de flot de gradients dans l'espace des probabilités, avec pour fonctionnelle la distance de Wasserstein projetée. Je démontre aussi l'équivalence de celle-ci avec la distance usuelle de Wasserstein. / In dimension one, optimal transportation is rather straightforward. The easiness with which a solution can be obtained in that setting has recently been used to tackle more general situations, each time thanks to the same method. First, disintegrate your problem to go back to the unidimensional case, and apply the available 1D methods to get a first result; then, improve it gradually using some evolution process.This dissertation explores that direction more thoroughly. Looking back at two problems only partially solved this way, I show how this viewpoint in fact allows to go even further.The first of these two problems concerns the computation of Yann Brenier's optimal map. Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio found a new way to obtain it, thanks to an differential equation for which an initial condition is given by the Knothe--Rosenblatt rearrangement. (The latter is precisely defined by a series of unidimensional transformations.) However, they only dealt with discrete target measures; I~generalize their approach to a continuous setting. By differentiation, the Monge--Ampère equation readily gives a PDE satisfied by the Kantorovich potential; but to get a proper initial condition, it is necessary to use the Nash--Moser version of the implicit function theorem.The basics of optimal transport are recalled in the first chapter, and the Nash--Moser theory is exposed in chapter 2. My results are presented in chapter 3, and numerical experiments in chapter 4.The last chapter deals with the IDT algorithm, devised by François Pitié, Anil C. Kokaram, and Rozenn Dahyot. It builds a transport map that seems close enough to the optimal map for most applications. A complete mathematical understanding of the procedure is, however, still lacking. An interpretation as a gradient flow in the space of probability measures is proposed, with the sliced Wasserstein distance as the functional. I also prove the equivalence between the sliced and usual Wasserstein distances.

Dans les réseaux énergétiques, la connaissance des équipements, leurs emplacements et leursfonctions sont les prérequis à l’exploitation de l’infrastucture. En effet, tout opérateur disposed’une carte appelée schéma synoptique indiquant les connexions entre les équipements. À partirde cette carte, sont prises des décisions pour un fonctionnement optimal du réseau.Ce schéma synoptique peut être érronné parce que des opérations de maintenance sur le réseaun’auraient pas été retranscrites ou mal saisies. Et cela peut entrainer des coûts supplémentairesd’exploitation du réseau énergetique.Nous considérons le réseau électrique d’un Datacenter. Ce réseau est composé d’une topologiephysique modélisée par un DAG sans circuit et de mesures électriques sur ces arcs. La particularitéde ce réseau est que les mesures contiennent des erreurs et cette topologie est inconnue c’est-à-direles arcs sont connus mais les extrémités des arcs sont inconnues. Dans le cas où ces mesuressont correctes alors la corrélation des arcs induit la matrice d’adjacence du line-graphe du graphenon-orienté sous-jacent de notre DAG. Un line-graphe est un graphe dans lequel chaque sommet etson voisinage peuvent être partitionnés par une ou deux cliques et que chaque arête est couvertepar une clique. Cependant, avec la présence des erreurs de mesures, nous avons un graphe avecdes arêtes en plus ou en moins qui n’est pas nécessairement un line-graphe. Si ce graphe est unline-graphe alors il n’est pas le line-graphe de notre DAG. Notre problème est de découvrir cettetopologie en se basant sur ces mesures électriques.Nous débutons par une étude bibliographique des corrélations de mesures possibles afin dedéterminer celle qui est pertinente pour notre problème. Ensuite nous proposons deux algorithmespour résoudre ce problème. Le premier algorithme est l’algorithme de couverture et il déterminel’ensemble des cliques qui couvre chaque sommet de notre graphe. Le second algorithme estl’algorithme de correction. Il ajoute ou supprime des arêtes au voisinage d’un sommet non couvertde telle sorte que son voisinage soit partitionné en une ou deux cliques. Enfin, nous évaluons lesperformances de nos algorithmes en vérifiant le nombre d’arêtes corrigées et la capacité à retournerle graphe le plus proche du line-graphe de notre DAG. / In energy network, the knowledge of equipments, their locations and their functions are theimportant information for the distributor service operator. In fact, each operator has a networkplan often named synoptic schema. That schema shows the interconnexion between equipments inthe network. From this schema, some management decisions have taken for ensuring an optimalperformance of a network.Sometimes, a synoptic schema has some mistakes because the maintenance operations, such aschanged the connexion between equipments or replaced equipments, have not been updated orhave been written with errors. And these mistakes increase exploitation cost in the energy network.We consider an electric network of a datacenter. This network consists of physical topologymodelised by a DAG without circuit and measurements are on the edges of a DAG. The mainpoint of the network is that measurements are some mistakes and the topology is unknown i.ewe know edges but the nodes of edges are unknown. When measurements are correct then thecorrelations between pairwise edges provide the adjacency matrix of the linegraph of undirectedgraph of the DAG. A linegraph is a graph in which each node and the neighbor are partitionnedby one or deux cliques. However, with the mistakes in measurements, the obtained graph is nota linegraph because it contains more or less edges. If the obtained graph is a linegraph then it isa linegraph of the other DAG. Our problem is to discovery the topology of the DAG with somemistakes in measurements.We start by the state of art in the measurement correlations in order to choose the good methodfor our problem. Then, we propose two algorithms to resolve our problem. The first algorithmis the cover algorithm and it returns the set of cliques in the graph. The second algorithm is acorrection algorithm which adds or deletes edges in the graph for getting a nearest linegraph ofthe DAG. In the last, we evaluate the performances of the algorithms by checking the number ofedges corrected and the ability to return a nearest linegraph of the DAG.

Des observations récentes montrent que les jeunes étoiles en cours de formation éjectent de la matière à des dizaines de kilomètres par seconde, sous la forme de jets et flots impactant le milieu ambient dont l'effondrement est a l'origine de la formation stellaire. L'impact supersonique entre le jet et le nuage moléculaire parent de l'étoile génère un front de choc sous la forme d'un “bow-shock” se propageant dans le gaz interstellaire, et qui s'accompagne d'un choc en retour qui se propage le long du jet.<br /><br />La structure de ces chocs dépend de leur vitesse ainsi que des propriétés physiques du gaz dans lequel ils se propagent, et notamment de la valeur du champ magnétique local. Les simulations numériques de type magnétohydrodynamique de propagation de tels chocs permettent de contraindre les propriétés physiques et chimiques du gaz dans lequel est générée l'émission moléculaire. Les chocs interstellaires, stationnaires et non stationnaires sont ainsi modélisés, et des grilles de modèles sont construites, pour différentes plages de valeurs des paramètres préchocs qui sont aussi les paramètres d'entrée du code de choc, parmi lesquels la vitesse de choc, la densité préchoc, le champ magnétique, et l'âge des chocs dans le cas des chocs non stationnaires.<br /><br />L'émission de la molécule de dihydrogène est d'abord étudiée. En raison de son importance particulière (due à son importante densité ainsi qu'au rôle crucial joué en tant que refroidisseur du gaz et de partenaire de collision pour les espèces moléculaires), la population de ses niveaux est résolue à l'intérieur du code de choc, ainsi que son transfert de rayonnement. L'onde de choc modifie la composition chimique du gaz, dissociant partiellement ou totalement l'hydrogène moléculaire, qui est le principal agent refroidissant du gaz. Dans les régions où le dihydrogène subsiste, il est excité collisionnellement , générant ainsi de l'émission dans ses transitions rovibrationnelles et purement rotationnelles. Cette émission est en effet observée dans l'infrarouge par les satellites ISO (Infrared Space Observatory) et Spitzer. Les diagrammes d'excitation correspondants sont ensuite utilisés pour comparer les modèles aux observations existantes pour le flot bipolaire L1157, détecté autour d'une jeune protoétoile de Classe 0. Ces comparaisons confirment la nécessité d'un recours aux modèles de chocs non stationnaires pour interpréter les densités de colonne observées pour les niveaux de H2.<br /><br />De telles régions de chocs génèrent des conditions physiques et chimiques elles mêmes à l'origine d'une chimie particulière favorisant la formation de molécules caractéristiques telles que SiO, dont l'émission est alors observée dans les fenêtres infrarouge et submillimétrique (IRAM, CSO, JCMT). Le transfert de rayonnement de la molécule de SiO est simulée à l'aide d'un programme numérique reposant sur l'approximation LVG (Large Velocity Gradient). Ce programme est écrit, testé dans des conditions basiques, comparé à d'autres modèles de référence, puis utilisé en sortie du code de choc pour les modèles des grilles mentionnées plus haut. Les mécanismes d'émission des raies moléculaires sont ainsi étudiés, des digrammes d'intensité intégrée et des profils de raie sont alors produits. Des comparaisons avec les observations de la région L1157 sont effectuées indépendamment des résultats relatifs au dihydrogène, avec un bon accord pour des modèles de choc stationnaires et sous diverses hypothèses de répartition initiale du silicium dans les grains de poussière, et de l'oxygène dans la phase gazeuse. Enfin, l'émission de SiO est aussi étudiée dans le cadre de ces mêmes hypothèses dans les chocs non stationnaires. La comparaison simultanée des observations SiO et H2 est alors réalisée, c'est à dire leur ajustement par un même modèle de choc, avec des résultats encourageants.<br /><br />Pour compléter cette étude, l'émission de CO est aussi envisagée dans les modèles de chocs stationnaires et non stationnaires, et le monoxyde de carbone est ajouté à la liste des molécules dont la production et l'émission peuvent être modélisées par le même choc que H2 et SiO avec un accord satisfaisant, même si cet ajout ne génère pas de contrainte supplémentaire par rapport à ces deux molécules.

La notion de qualité de service (QoS) est un concept important pour transporter sur les réseaux de l'information avec un maximum de fiabilité. Les métriques de la QoS sont le débit, le délai, la gigue et le taux de pertes. Par ailleurs, la multiplicité des applications conduit à une hétérogénéité des données : les flots élastiques requièrent un débit soutenu et les flots non élastiques exigeants en délai. Les algorithmes d'ordonnancement à différenciation proportionnelle permettent de partager équitablement les ressources entre les applications, selon leurs besoins. Toutefois, la proportionnalité ne s'est jusque-là effectuée que selon un seul critère de qualité (débit, délai ou taux de perte). Nous proposons un algorithme d'ordonnancement à différenciation proportionnelle, fondée sur la fonction de puissance mettant en rapport deux critères : le délai et le débit. L'ordonnanceur PSP (Power as a Scheduling Parameter) offre un partage équitable des ressources entre les applications à besoins différents de manière à ce qu'aucune classe ne subisse de phénomène de famine. L'implémentation et les tests de l'ordonnanceur ont été réalisés au moyen de l'outil de simulation ns-2.

L'application des mesures d'importance de type PageRank aux graphes du Web est le sujet de cette thèse, qui est divisée en deux parties. La première introduit une famille particulière de grands graphes, les graphes du Web. Elle commence par définir la notion de Web indexable, puis donne quelques considérations sur les tailles des portions de Web effectivement indexées. Pour finir, elle donne et utilise quelques constatations sur les structures que l'on peut observer sur les graphes induits par ces portions de Web. Ensuite, la seconde partie étudie en profondeur les mesures d'importance à la PageRank. Après un rappel sur la théorie des chaînes de Markov est présentée une classification originale des algorithmes de PageRank, qui part du modèle le plus simple jusqu'à prendre en compte toutes les spécificités liées aux graphes du Web. Enfin, de nouveaux algorithmes sont proposés. L'algorithme BackRank utilise un modèle alternatif de parcours du graphe du Web pour un calcul de PageRank plus rapide. La structure fortement clusterisée des graphes du Web permet quant à elle de décomposer le PageRank sur les sites Web, ce qui est réalisé par les algorithmes FlowRank et BlowRank.

La superposition de topologies virtuelles à la topologie physique d'un réseau est un des principaux mécanismes de l'ingénierie de trafic. Soit un réseau physique d'une certaine topologie et capacité fixées et une matrice de trafic à véhiculer, il s'agit trouver une topologie logique permettant de mapper de manière optimale la matrice de trafic sur le réseau physique. Lors de l'évolution de la matrice de trafic sur des échelles de temps longues, il faudra agir sur le layout. La première contribution concerne la définition de fonctions de coût mieux adaptées à la réalité d'un opérateur, la deuxième contribution concerne la prise en compte du coût de changement du layout. Il s'avère intéressant d'un point de vue opérateur de réduire la complexité du layout, mesurée comme une fonction du nombre de chemins virtuels. Nous avons donc formulé divers problèmes de minimisation de la complexité du layout sous des contraintes de QoS. Il s'agit d'une modélisation réaliste mais qui engendre des modèles difficiles à résoudre. Nous avons développés des heuristiques qui permet de trouver des solutions approchées pour des réseaux de grande taille. Nous avons montré que la complexité des layouts peut être significativement réduite en comparaison avec celle obtenue suite à l'optimisation des fonctions de coût classiques. Le changement du layout implique d'une part un coût d'opération et d'autre part peut engendrer des coupures de service qui affecteront directement le coût d'opération. Nous avons formulé une famille de problèmes prenant en compte le coût de reconfiguration du layout. L'une des heuristiques citées a été adaptée pour analyser ces nouveaux problèmes.

Cette thèse s'inscrit dans le domaine de l'analyse et la modélisation du trafic Internet à l'échelle des flots. Les informations sur les flots (surtout les grands flots) sont très utiles dans différents domaines comme l'ingénierie du trafic, la supervision du réseau et la sécurité. L'extraction en ligne des statistiques sur les flots est une tâche difficile à cause du très haut débit du trafic actuel. Nous nous sommes intéressés dans cette thèse à l'étude de deux classes d'algorithmes traitant en ligne le trafic Internet. Dans la première partie, nous avons conçu un nouvel algorithme basé sur les filtres de Bloom pour l'identification en ligne des grands flots. Le point fort de cet algorithme est l'adaptation automatique aux variations du trafic. Une application intéressante est la détection en ligne des attaques par déni de service. Nous avons donc développé une version de l'algorithme qui intègre les spécificités des attaques. L'expérimentation en ligne montre que cette nouvelle méthode est capable d'identifier quasiment toutes les sources de trafic anormal avec un délai très court. Nous avons aussi étudié la performance de l'algorithme d'identification en ligne des grands flots. En considérant un modèle simplifié, nous avons pu approcher l'erreur générée par cet algorithme sur l'estimation du nombre de grands flots. Cette étude a permis en particulier d'évaluer l'impact des différents paramètres de l'algorithme sur sa performance. Les algorithmes présentés dans la première partie s'appliquent sur la totalité du trafic, ce qui n'est pas toujours possible car dans certains cas, on ne dispose que du trafic échantillonné. La deuxième partie de la thèse est consacrée à l'étude de l'échantillonnage et des algorithmes d'inférence des caractéristiques du trafic d'origine. D'abord, en utilisant un résultat d'approximations poissonniennes, nous avons montré que les deux méthodes d'échantillonnage: déterministe et probabiliste donnent des résultats équivalents du point de vue composition du trafic échantillonné en flots. Ensuite, nous avons conçu un algorithme permettant d'estimer, par un calcul asymptotique, à partir du trafic échantillonné, le nombre de flots dans le trafic réel et la distribution de leur taille sur un intervalle de temps court. Ceci permet de faire l'hypothèse à priori que cette distribution suit une loi de Pareto. Cette hypothèse a été validée sur des traces de trafic de différentes natures.

Dans cette thèse, nous nous intéressons au contrôle d'accès obligatoire dans les systèmes d'exploitation répartis. Nous présentons une approche novatrice fondée sur un modèle de méta-politique pour l'administration décentralisée des noeuds du système réparti. Ces travaux visent la sécurité des grands réseaux partagés, i.e. les clusters, grilles ou ensembles de noeuds coopérant par Internet. L'architecture que nous proposons garantit des propriétés de sécurité globales et une bonne tolérance aux pannes. Ces propriétés, non prises en comptes par les modèles de contrôle d'accès classiques, sont obtenues grâce à notre méta-politique. Nous en présentons une formalisation, puis nous exhibons une technique de vérification garantissant l'absence de flots d'information illégaux au sein des noeuds du réseau. Nous décrivons ensuite comment le modèle peut être étendu pour la détection d'intrusions. Enfin, nous proposons une implantation supportant différents systèmes cibles tels que SELinux et grsecurity.