Tesis sobre el tema "Routage de paquets distribué"

Les réseaux ad hoc sont des réseaux distribués, auto-organisés ne nécessitant pas d'infrastructure. Les entités formant un tel réseau doivent collaborer afin d'assurer le bon fonctionnement des services réseaux, tel que le routage. Dans un tel environnement, de nombreux algorithmes développés pour le monde filaire ne peuvent être adaptés de façon naïve sans entraîner une congestion importante du réseau qui va réduire son efficacité. Notre travail de thèse se penche sur l'étude de la gestion de services. En effet, sans application, le développement d'une architecture comme les réseaux ad hoc est inutile. La gestion de services consiste à fournir tout les moyens possibles pour faciliter et rendre fiable l'utilisation d'applications distribuées. Nos travaux contribuent à l'étude de deux points précis de la gestion de services. Premièrement, nous fournissons un algorithme permettant de répartir efficacement une information dans le réseau en sélectionnant certains objets du réseau pour être des réplicats de l'information. Cet algorithme peut alors être utilisé pour publier les informations relatives à un service afin de permettre sa recherche. Deuxièmement, nous avons étudié la prédiction de déconnexion entrainée par la mobilité des noeuds. Nous proposons trois solutions basées sur la recherche d'ensemble de chemins disjoints, la recherche de liens critiques et la recherche de noeuds critiques. Les recherches que nous proposons sont entièrement réalisées à partir d'informations locales. Les résultats obtenus fournissent une base au développement d'un gestionnaire de services distribués. De plus, certains de nos algorithmes (comme la recherche d'ensembles de chemins disjoints) peuvent être réutilisés dans d'autres applications, comme le routage QoS multi-chemins.

L'explosion du nombre d'utilisateurs d'Internet et du volume de trafic constitue un défi majeur pour la gestion efficace des réseaux de diffusion de contenu (CDN). Bien que ces réseaux aient amélioré leur temps de réponse en exploitant la mise en cache dans des serveurs cloud proches des utilisateurs, les services non mis en cache continuent de poser des problèmes de gestion de trafic. Pour répondre à cette problématique, les réseaux overlay cloud ont émergé, mais ils introduisent des complexités telles que les violations d'inégalités triangulaires (TIV). Dans ce contexte, l'application du paradigme des réseaux à définition logicielle (SDN) combinée aux techniques d'apprentissage par renforcement profond (DRL) offre une opportunité prometteuse pour s'adapter en temps réel aux fluctuations de l'environnement. Face à l'augmentation constante du nombre de serveurs edge, les solutions distribuées de DRL, notamment les modèles d'apprentissage par renforcement profond multi-agent (MA-DRL), deviennent cruciales. Cependant, ces modèles rencontrent des défis non résolus tels que l'absence de simulateurs réseau réalistes, le surcoût de communication entre agents et la convergence et stabilité.Cette thèse se concentre donc sur l'exploration des méthodes MA-DRL pour le routage de paquets dans les réseaux overlay cloud. Elle propose des solutions pour relever ces défis, notamment le développement de simulateurs de réseau réalistes, l'étude du surcoût de communication et la conception d'une solution MA-DRL adaptée aux réseaux overlay cloud. L'accent est mis sur le compromis entre la performance et la quantité d'information partagée entre les agents, ainsi que sur la convergence et la stabilité durant l'entraînement
The exponential growth of Internet traffic in recent decades has prompted the emergence of Content Delivery Networks (CDNs) as a solution for managing high traffic volumes through data caching in cloud servers located near end-users. However, challenges persist, particularly for non-cacheable services, necessitating the use of cloud overlay networks. Due to a lack of knowledge about the underlay network, cloud overlay networks introduce complexities such as Triangle inequality violations (TIV) and dynamic traffic routing challenges.Leveraging the Software Defined Networks (SDN) paradigm, Deep Reinforcement Learning (DRL) techniques offer the possibility to exploit collected data to better adapt to network changes. Furthermore, the increase of cloud edge servers presents scalability challenges, motivating the exploration of Multi-Agent DRL (MA-DRL) solutions. Despite its suitability for the distributed packet routing problem in cloud overlay networks, MA-DRL faces non-addressed challenges such as the need for realistic network simulators, handling communication overhead, and addressing the multi-objective nature of the routing problem.This Ph.D. thesis delves into the realm of distributed Multi-Agent Deep Reinforcement Learning (MA-DRL) methods, specifically targeting the Distributed Packet Routing problem in cloud overlay networks. Throughout the thesis, we address these challenges by developing realistic network simulators, studying communication overhead in the non-overlay general setting, and proposing a distributed MA-DRL framework tailored to cloud overlay networks, focusing on communication overhead, convergence, and model stability

Cette thèse s'inscrit dans le domaine du routage MPLS dynamique pour l'ingénierie de trafic. Nos travaux portent sur l'étude et l'amélioration de ce routage pour optimiser l'utilisation des ressources dans le réseau et réduire les risques de congestion, tout en prenant en compte la réactivité en cas de panne et la stabilité du réseau. Nous introduisons notre travail par la définition d'une architecture regroupant un ensemble de blocs fonctionnels constituant un système de routage MPLS-TE (MPLS-Traffic Engineering). Nous nous sommes ensuite focalisés sur la combinaison des modes distribués et non-coordonnés où les requêtes d'établissement des LSP sont traitées directement sur les routeurs de tête, indépendamment les unes des autres. Cette combinaison offre une meilleure réactivité que les autres combinaisons. En revanche, elle offre de moins bonnes performances en termes d'optimisation de l'utilisation des ressources, et de risques de blocage. Ceci nécessite la recherche d'un compromis entre les performances d'optimisation et la réactivité du système du routage. Afin d'améliorer les performances d'optimisation et réduire les risques de blocage de cette combinaison tout en conservant les propriétés de réactivité, nous proposons deux approches. Une première solution consiste à réordonner dynamiquement l'établissement des LSP que nous mettons en œuvre en utilisant le mécanisme de préemption. Nous étudions enfin une deuxième solution, intermédiaire entre le modèle centralisé coordonné et le modèle distribué non-coordonné, qui consiste à distribuer partiellement le calcul sur certains nœuds du réseau. Ces nœuds calculent de façon coordonnée un sous-ensemble de requêtes
This thesis deals with dynamic MPLS traffic engineering routing. Our work concerns the study and the improvement of this routing in order to optimize network resources usage and to reduce congestion risks, while taking into account the reactivity upon a network failure and the network stability. We have introduced our work by defining an architecture gathering a whole of building blocks which constitute a MPLS-TE (MPLS-Traffic Engineering) routing system. We have focused on the combination of distributed and non-coordinated modes where the LSP establishment requests are handled directly on the head routers, independently the ones of the others. This combination offers a better reactivity. On the other hand, it offers worse performances in terms of network resources usage optimization, and blocking risks (non satisfied requests). This requires to find a tradeoff between the optimization performances and the reactivity of the routing system. In order to improve the optimization performances and to reduce the blocking risks of this combination while preserving the good reactivity, we propose two approaches. A first solution consists in dynamically reordering the LSP establishment. We have used the MPLS-TE pre-emption to implement this solution. Then, we study a second solution, intermediate between the coordinated centralized modes and the non-coordinated distributed modes, which consists in distributing partially the path computation on some network nodes. These nodes compute in a coordinated manner a subset of the requests

L'étude porte sur les architectures de réseau qui puissent supporter un système d'exploitation distribué, avec toutes les contraintes de fonctionnalités; de plus le choix de l'architecture (logique) doit permettre de faire une intégration des services de communication en mixant la transmission des données, de la voix et des images, des textes à travers des fonctions de communication, en conformité avec les normes standards de connexion. La topologie du réseau et du support doivent être choisi pour bien acheminer la transmission en commutation de paquets et de circuits
To realize a distributed operating system with all problems about the functionalities, we must have good network architecture. This architecture (logical) have to permit to do the integrated services of communication mixing the transmissions of data, voice and animated pictures, texts, with communication functions agreed with standard norms connection norms. The choice of network topologies and the medium are very important, they facility the transmission available in pacquet switching and circuit switching

L'intégration d'appareils mobiles ad hoc dans l'Internet pose des problèmes intéressants aussi bien en terme d'optimisation des protocoles de routages utilisés pour fournir la connectivité ad hoc, qu'en terme d'intégration de la mobilité ad hoc dans l'infrastructure IP. Cette thèse passe ces problèmes en revue. Plusieurs solutions développées auparavant sont analysées et évaluées comparativement, ce pendant qu'un certain nombre de nouvelles solutions sont introduites.

Dans ce memoire nous presentons une methode duale parallele originale pour le routage dans les reseaux a commutation de paquets. La premiere partie de ce memoire est consacree a quelques rappels sur le parallelisme: les modeles, les architectures, les languages, la problematique de l'algorithmique parallele, etc. Dans la deuxieme partie, nous rappelons quelques resultats classiques pour les problemes d'optimisation non lineaire sans contraintes et nous presentons les principales methodes iteratives de descente utilisees pour resoudre ces problemes. La troisieme partie est consacree plus particulierement au probleme du routage dans les reseaux a commutation de paquets ainsi qu'a la methode duale de resolution que nous proposons. Dans la quatrieme partie, nous etudions la parallelisation de cette methode en vue d'une implementation sur un multiprocesseur a memoire distribuee, le tnode 16-32. Les resultats experimentaux sont presentes et analyses dans la cinquieme partie

Le but de cette thèse est le développement d'un routeur paramétrable pour C_NET qui est un environnement de programmation de haut niveau pour les machines multiprocesseurs reconfigurables et l'étude de routages minimaux dynamiques et non blocants. La conception du routeur est faite en regard des critères suivants: équite, mise en oeuvre d'un routage minimal dynamique et non blocant, commutation des messages et paramétrisation du routeur. Le premier chapitre présente des généralités sur le routage et détaille différentes techniques de commutation de messages. Le deuxième chapitre identifie et illustre le problème de l'interblocage. Il présente des méthodes générales pour la prévention de l'interblocage dans les graphes de processeurs. Dans le troisième chapitre, on applique aux principales topologies régulières, les méthodes étudiées dans le chapitre deux. Dans chaque cas, nous commençons par une fonction de routage qui peut être blocante (on se limitera aux fonctions de routage statiques minimales et dynamiques minimales). Ensuite, en appliquant chaque méthode, nous dérivons une fonction de routage non blocante. Les fonctions de routages minimales dynamiques et non blocantes développées dans ce chapitre servent à la construction d'une bibliothèque de routage développée pour C_NET. Le chapitre quatre présente la conception et la mise en oeuvre d'un routeur qui satisfait les critères mentionnés précédemment. Il présente également son implantation dans C_NET. Les performances du routeur sont discutées dans le dernier chapitre

Cette etude a deux objectifs principaux qui sont, d'une part, de montrer que l'amplificateur optique a semi-conducteur (aosc) est, par son aspect multifonctions, un composant de choix pour la fonction de routage dans les systemes de communications optiques et, d'autre part, de mener une reflexion sur les adaptations des reseaux a venir pour que l'optique puisse y jouer pleinement son role. Ce memoire de these comprend trois parties principales : la premiere partie presente differents types de reseaux de communication et les techniques principales de routage de donnees, en particulier optiques. Nous mettons notamment l'accent sur la commutation de paquets par le moyen de commutateurs spatiaux. La deuxieme partie s'attache a l'etude et a la caracterisation des aosc comme amplificateur, porte optique et photodetecteur en ligne. L'etude de la photodetection est etendue a l'utilisation de composants optiques multi-electrodes pour conserver la composante continue du signal optique. Enfin, la troisieme partie de ce memoire decrit de quelle facon a ete menee la realisation d'un commutateur optique 2 vers 2. Les resultats de mesures permettent de montrer que l'utilisation d'aosc, comme composants optiques de base multifonctions, est justifiee pour la fonction de routage de paquets optiques.

Le travail presente dans ce memoire porte sur la conception d'un reseau de telecommunications. Ce probleme designe le choix optimal d'une part des capacites des lignes de transmission composant le reseau et d'autre part du routage des donnees echangees. L'etude est motivee par la necessite de permettre aux entreprises desirant acquerir un reseau de telecommunications, de beneficier de l'installation la moins couteuse possible tout en garantissant une certaine qualite de service. Le modele propose tient compte du caractere discret des valeurs possibles pour les capacites et le niveau de qualite de service est assure par une contrainte limitant la valeur du delai moyen total. Le probleme est formule comme un programme non lineaire en variables mixtes. La technique de resolution proposee essaie d'exploiter au mieux la structure decomposable du probleme. Elle s'appuie sur la methode de decomposition de benders generalisee dont nous proposons une application efficace sur des problemes de taille raisonnable. Une grande partie des efforts d'implementation de l'algorithme de benders porte sur la resolution des sous-problemes resultants de l'application de la methode. Ce sont d'une part des problemes de multiflots a couts convexes qui sont resolus par une methode de decomposition proximale, et d'autre part des problemes de multiflots admissibles pour lesquels plusieurs algorithmes sont proposes et compares

All optical is a promising and challenging technology for future networks. Feasibility and performances were studied in the ROM project. With all optical technology, both transmission and switching are done in optical format. Optical memory is unavailable. The most studied routing for all optical network is the deflection routing which offers a good throughput but suffers from unbounded tail of transport time distribution. Eulerian Routing offers an finite ending guarantee, but has a low throughput. Mixed routing is a combination of deflection routing and eulerian routing, in which a packet enters the network in deflection mode. If this packet takes too much time to reach its destination, it ends the trip in eulerian mode. This thesis follows the works from de ROM project in the ROMéO project and focuses in the routing aspect of an all optical core network. The first part of the work focuses on the performance evaluation of the deflection routing. Performance criteria of interest are the probability of packet to suffer from a deflection and the transport time distribution of a packet. The second part of the work focuses on the mixed routing. We show that mixed routing's throughput significantly drops during a congestion and may be unable to recover from a congestion. We show that adding an access control permits to prevent congestion and to recover from congestion if it occurs
La technologie tout-optique représente une technologie séduisante et prometteuse pour les réseaux du futur. La faisabilité et les performances d'un réseau tout-optique ont été étudiées dans le projet ROM. Avec le tout-optique, la transmission et la commutation des paquets sont effectuées en optique. La mémoire optique n'est pas ou peu disponible. Le routage le plus étudié pour le tout-optique est le routage à déflexion qui offre un bon débit mais dont la queue de la distribution de transport n'est pas bornée. Le routage eulérien offre une garantie de terminaison au transport des paquets, mais un faible débit. Le routage mixte est une combinaison du routage à déflexion et du routage eulérien dans laquelle un paquet débute en mode déflexion, et s'il prend trop de temps pour sortir du réseau, finit son transport en mode eulérien. Cette thèse poursuit les travaux de ROM dans le projet ROMéO en considérant l'aspect routage d'un réseau tout-optique. Le premier aspect étudié porte sur l'évaluation de performance du routage à déflexion, avec comme critère de performance, la probabilité d'un paquet de subir une déflexion et la distribution du temps de transport. Le second aspect étudié porte sur le routage mixte. D'une part, nous proposons des algorithmes pour construire des circuits eulériens en abaissant la garantie de terminaison du routage mixte. D'autre part, nous mettons en évidence la vulnérabilité du routage mixte face à une congestion. Nous montrons que le débit du routage mixte baisse significativement à la suite d'une rafale de trafic et que le débit du réseau peut ne pas remonter, même après la fin de la rafale de trafic. Nous montrons qu'un contrôle d'accès à l'entrée du réseau permet de prévenir la congestion et de sortir le réseau d'une congestion

Il existe de nombreuses méthodes d'optimisation du routage réseau en général. Dans cette thèse nous nous intéressons au développement d'algorithmes distribués permettant une stabilisation, au sens de Nash, des flux réseaux. Nous rappelons tout d'abord brièvement le contexte général d'Internet aujourd'hui et quelques notions de théorie des jeux. Nous présentons un jeu de tarification simple à deux joueurs, que la méthode des joueurs fictifs permet de faire converger. Puis nous présentons un jeu de routage plus complexe, à n joueurs, basé sur le modèle de Wardrop, ainsi qu'un algorithme de comportement distribué qui permet au système de converger vers un équilibre de Wardrop (équilibre social). Ces équilibres sont confondus avec les équilibres de Nash dans le cas limite où un joueur représente une partie infinitésimale du trafic. Nous présentons ensuite un raffinement de notre représentation initiale du problème, qui permet une diminution de sa complexité, en terme de dimension des espaces de stratégies et de temps de calcul. Nous montrons qu'il s'agit d'une bonne heuristique d'approximation de la première méthode trop coûteuse, sa qualité dépend d'un unique paramètre. Enfin, nous concluons par la présentation de résultats de simulation qui montrent que notre méthode distribuée est effectivement capable d'apprendre les meilleurs équilibres du système.

Répondre à des requêtes de routage requiert que les entités du réseau, nommées routeurs, aient une connaissance à jour sur la topologie de celui-ci, cette connaissance est appelée table de routage. Le réseau est modélisé par un graphe dans lequel les noeuds représentent les routeurs, et les arêtes les liens de communication entre ceux ci.Cette thèse s'intéresse au calcul des tables de routage dans un modèle distribué.Dans ce modèle, les calculs sont effectués par un ensemble de processus placés sur les noeuds. Chaque processus a pour objectif de calculer la table de routage du noeud sur lequel il se trouve. Pour effectuer ce calcul les processus doivent communiquer entre eux. Dans des réseaux de grande taille, et dans le cadre d'un calcul distribué, le maintien à jour des tables de routage peut être coûteux en terme de communication. L'un des thèmes principaux abordés et celui de la réduction des coûts de communication lors de ce calcul. L'une des solutions apportées consisteà réduire la taille des tables de routage, permettant ainsi de réduire les coûts de communication. Cette stratégie classique dans le modèle centralisé est connue sous le nom de routage compact. Cette thèse présente notamment un algorithme de routage compact distribué permettant de réduire significativement les coûts de communication dans les réseaux tels que le réseau internet, i.e. le réseau des systèmes autonomes ainsi que dans des réseaux sans-échelle. Ce document contient également une étude expérimentale de différents algorithmes de routage compact distribués.Enfin, les problèmes liés à la dynamique du réseau sont également abordés. Plusprécisément le reste de l'étude porte sur un algorithme auto-stabilisant de calcul d'arbre de plus court chemin, ainsi que sur l'impact de la suppression de noeuds ou d'arêtes sur les tables de routage stockées aux routeurs.

Cette thèse présente une contribution sur les problèmes de contrôle de réseaux d'irrigations en tenant compte des contraintes de communication grâce à une approche multicouches d’intelligence distribuée. Les analyses détaillées de chaque couche avec les résultats analytiques et les simulations seront décrites dans les différents chapitres. Ils mettent l'accent sur l'intérêt de l'approche multicouches, plus précisément sur son efficacité et sa fiabilité pour la supervision, l'optimisation multi-objectifs et le contrôle coopératif distribué sur des systèmes complexes de transport d'eau.La première couche analysé est le réseau hydraulique composé de canaux d’écoulements à surface libre, de sous-réseaux maillés de tuyaux sous pression et des structures hydrauliques (pompes vannes, ..). En intégrant les équations de Saint-Venant pour décrire l’écoulement physique des fluides en surface libre et la méthode Lattice Boltzmann pour la simulation du fluide, nous obtenons un modèle non linéaire discret pour les canaux à surface libre. Les structures hydrauliques sont généralement traitées comme des limites internes des biefs (tronçons) et modélisées par des relations entre les variables de flux et de pression.Permettant l'échange d'informations entre les éléments du système de contrôle, le réseau de communication sera considéré comme la deuxième couche. La résolution des problèmes d’hétérogénéités des systèmes et des communications (par exemple les retards de diffusion dans le réseau, la perte de paquets, la consommation d'énergie) sera étudié en introduisant une architecture de réseau hybride avec un routage dynamique basé sur les exigences de Qualité de Service (QoS) des applications de contrôle. Pour le routage dynamique dans le réseau, une composition pondérée de certaines métriques standards est proposée afin que le protocole de routage utilisant cette métrique composite converge sans boucle avec une « route » optimum. Grâce à différents scénarios de simulation, plusieurs critères de performance du réseau ont été évalués. La comparaison des résultats de simulation permet de valider l'intérêt de cette approche de composition pour le routage dynamique.Une troisième couche propose un système de contrôle réactif optimal développé pour la régulation du réseau d'irrigation dans un modèle étendue à grande échelle : Distributed Cooperative Model Predictive Control (DCMPC). Cette partie aborde la mise en œuvre de différentes stratégies de contrôle (centralisées, décentralisées et distribuées) et intègre la communication coopérative entre les contrôleurs MPC locaux afin d’améliorer les performances global es du système. La gestion de la divergence dans l'échange d'informations entre les contrôleurs est considérée comme un problème de consensus et résolue en utilisant un protocole de consensus asynchrone. Cette approche du contrôle distribué basée sur le paradigme des systèmes multi-agents, fournit une solution garantissant que tous les contrôleurs aient une vue cohérente de certaines valeurs des données nécessaires pour le calcul de décision. Un cas d’application sur un canal d'irrigation est étudié dans les simulations. La comparaison des résultats de simulations valide les avantages de l'approche du contrôle distribué coopératif par rapport aux autres stratégies de contrôle
This thesis presents control problems of irrigation network with communication constraints and a multi-layer approach to solve these problems in a distributed manner. Detailed discussions of each layer with analytical and simulation results are described throughout several chapters. They emphasize the potential interest of the multi-layer approach, more precisely its efficiency and reliability for supervision, multi-objective optimization and distributed cooperative control of complex water transport systems. Conventionally, the first layer to be considered is the hydraulic network composed of free-surface channels, hydraulic structures and mesh subnetwork of pressurized pipes. By coupling the Saint-Venant equations for describing the physics of free-surface fluid and the Lattice Boltzmann method for the fluid simulation, a discrete-time nonlinear model is obtained for channel reaches. The hydraulic structures are usually treated as internal boundaries of reaches and modeled by algebraic relationships between the flow and pressure variables. To enable the exchange of information among the control system’s components, a communication network is considered in the second layer. Solving challenging problems of heterogeneous devices and communication issues (e.g., network delay, packet loss, energy consumption) is investigated in this thesis by introducing a hybrid network architecture and a dynamic routing design based on Quality of Service (QoS) requirements of control applications. For network routing, a weighted composition of some standard metrics is proposed so that the routing protocol using the composite metric achieves convergence, loop-freeness and path-optimality properties. Through extensive simulation scenarios, different network performance criteria are evaluated. The comparison of simulation results can validate the interest of this composition approach for dynamic routing. Finally, the third layer introduces an optimal reactive control system developed for the regulatory control of large-scale irrigation network under a Distributed Cooperative Model Predictive Control (DCMPC) framework. This part discusses the implementation of different control strategies (e.g., centralized, decentralized, and distributed strategies) and how the cooperative communication among local MPC controllers can be included to improve the performance of the overall system. Managing divergent (or outdated) information exchange among controllers is considered in this thesis as a consensus problem and solved by an asynchronous consensus protocol. This approach based on the multi-agent system paradigm to distributed control requires each controller to agree with its neighbors on some data values needed during action computation. For simulations, a particular benchmark of an irrigation channel is considered. The comparison of simulation results validate the benefits of the distributed cooperative control approach over other control strategies

Nous nous intéressons dans cette thèse à l'organisation des systèmes distribués dynamiquesde grande taille : ensembles de machines capables de communiquer entre elles et pouvant à toutinstant se connecter ou se déconnecter. Nous proposons de partitionner le système en groupesconnexes, appelés clusters. Afin d'organiser des réseaux de grande taille, nous construisons unestructure hiérarchique imbriquée dans laquelle les clusters d'un niveau sont regroupés au seinde clusters du niveau supérieur. Pour mener à bien ce processus, nous mettons en place desmécanismes permettant aux clusters d'être les noeuds d'un nouveau système distribué exécutantl'algorithme de notre choix. Cela nécessite en particulier des mécanismes assurant la cohérence decomportement pour le niveau supérieur au sein de chaque cluster. En permettant aux clusters deconstituer un nouveau système distribué exécutant notre algorithme de clustering, nous construisonsune hiérarchie de clusters par une approche ascendante. Nous démontrons cet algorithme endéfinissant formellement le système distribué des clusters, et en démontrant que chaque exécutionde notre algorithme induit sur ce système une exécution de l'algorithme de niveau supérieur. Celanous permet, en particulier, de démontrer par récurrence que nous calculons bien un clusteringhiérarchique imbriqué. Enfin, nous appliquons cette démarche à la résolution des collisions dansles réseaux de capteurs. Pour éviter ce phénomène, nous proposons de calculer un clusteringadapté du système, qui nous permet de calculer un planning organisant les communications ausein du réseau et garantissant que deux messages ne seront jamais émis simultanément dans laportée de communication de l'un des capteurs
To manage and handle large scale distributed dynamic distributed systems, constitutedby communicating devices that can connect or disconnect at any time, we propose to computeconnected subgraphs of the system, called clusters. We propose to compute a hierarchical structure,in which clusters of a level are grouped into clusters of the higher level. To achieve this goal,we introduce mechanisms that allow clusters to be the nodes of a distinct distributed system,that executes an algorithm. In particular, we need mechanisms to maintain the coherence of thebehavior among the nodes of a cluster regarding the higher level. By allowing clusters to be nodesof a distributed system that executes a clustering algorithm, we compute a nested hierarchicalclustering by a bottom-up approach. We formally define the distributed system of clusters, andprove that any execution of our algorithm induces an execution of the higher level algorithm onthe distributed system of clusters. Then, we prove by induction that our algorithm computes anested hierarchical clustering of the system. Last, we use this approach to solve a problem thatappears in sensor networks : collision. To avoid collisions, we propose to compute a clusteringof the system. This clustering is then used to compute a communication schedule in which twomessages cannot be sent at the same time in the range of a sensor

La résolution du problème des vides dans le routage géographique dédié aux réseaux de capteurs sans fil (RCS), rencontrés lors de la remontée des informations vers les nœuds collecteurs à partir des nœuds du réseau, constitue un verrou technologique qui reste un problème ouvert encore aujourd'hui. Cette thèse, contrairement aux méthodes traditionnelles, propose une nouvelle approche pour la prise en charge de ces vides tout en optimisant l'efficacité énergétique des nœuds déployés dans un RCS faisant ainsi du routage proposé une solution adéquate pour l'acheminement des informations en temps réel. Celui-ci se base sur l'information géographique concernant le nœud courant, les vides voisins et le nœud destinataire du paquet. Notre proposition agit aussi sur des mécanismes assurant la découverte, l'annonce et la maintenance des vides d'un RCS. Le premier protocole proposé, appelé VT-SPEED, est construit sur la base d'une fonction évolutive intégrant un mécanisme d'évitement adaptatif des vides et considérant simultanément la charge des nœuds candidats au routage et leur information géographique de localisation. Afin d'optimiser l'efficacité énergétique de VT-SPEED, notre proposition inclut par ailleurs de nouvelles routines sur la base de fonctions paramétriques pour la prise en compte de l'énergie dans le routage : (a) suppression des paquets retardés sur la base de leur échéance et (b) équilibrage de charge dans le choix des sauts des paquets. Les résultats enregistrés par le protocole résultant, appelé VE-SPEED, montrent que l'approche proposée prend en compte les flux de type temps-réel, possède une grande tolérance aux vides, conserve mieux l'énergie des nœuds de bordure, assure un meilleur équilibrage de charge, et consomme de manière optimisée l'énergie des nœuds capteurs
Resolution of the void-problem in geographical routing in Wireless Sensor Networks (WSN) is an open problem and it can be considered as key issue in disseminating data from sensor nodes to sinks. In this thesis, unlike previously-proposed methods, we address this problem in a different manner by proposing a novel approach to handle both voids and real-time flows with optimizing energy-efficiency of deployed nodes in a WSN. The proposed approach is based on the geographic information of the current node, of the neighbor voids and of the sink. Our proposal relies on the mechanisms that discover voids, announce them and then maintain them. The first proposed protocol, called VT-SPEED, is based on an adaptive void-avoidance mechanism that considers both load of routing candidate nodes and their localization information. To make VT-SPEED energy-aware, we also propose new routines based on parameterized functions that handle routing dissipation energy : (a) dropping out-of-order packets and (b) load-balancing when choosing next hop of packets. The resulting protocol, called VE-SPEED, has satisfactory results which show that the proposed approach satisfies the real-time constraints of data flows, tolerates voids, preserves energy resources of boundary nodes, balances load between nodes and has optimal energy consumption

Le développement des technologies optiques a atteint un niveau de maturité avancé et leur déploiement dans les réseaux métropolitains est devenu désormais réalisable. L’optique fournit une grande capacité de transmission et des revenus attractifs. Le besoin croissant en bande passante, imposé par l’émergence des applications de données, a motivé l’orientation vers le développement de la technologie de commutation de paquets optiques. Cette dernière fournit des gains significatifs en termes de capacité de passage à l’échelle et d’efficacité de gestion des ressources du réseau. Les futurs réseaux demanderont davantage de faisabilité, de remise à l’échelle et de gestion. La convergence des plans de données et de celui de transport est essentielle à la réalisation de ces objectifs. Le protocole GMPLS est un très bon candidat pour une telle convergence. Cette thèse a pour objectif l’étude de la performance de diverses architectures optiques nouvelles. Nous visons essentiellement l’identification et la résolution de quelques problèmes qui caractérisent divers choix de conception d’architecture optique. Parmi ces choix, nous citons la topologie du réseau, le mode de connectivité, le mode de transmission (asynchrone vs synchrone) et le format de paquet optique (taille fixe vs taille variable). Trois volets principaux seront particulièrement adressés: L’évaluation de la performance, l’allocation de ressources et la gestion de la qualité de service dans les réseaux optiques à commutation de paquets. Afin de caractériser la performance des architectures étudiées, nous proposons deux modèles analytiques que nous appliquons respectivement à des architectures optiques multiservices en anneau et maillées qui transportent des paquets de taille fixe. Les modèles proposés capturent l’impact de la matrice de trafic et, dans le cas d’une architecture maillée, de la « table de commutation » des routeurs. En utilisant ces modèles, nous avons déterminé des expressions de plusieurs métriques de performance, dont la valeur moyenne et la variance du délai d’accès, le délai moyen de traversé d’un nœud de cœur et les taux de pertes à l’accès et dans le cœur du réseau. Les modèles développés incorporent également deux mécanismes d’accès (PEM et ERM), un mécanisme de gestion de l’équité entre classes de service (CCM) et un mécanisme de résolution de contention de ressources (DDR) que nous avons proposés. Enfin, les modèles développés peuvent être appliqués plus généralement à divers systèmes synchrones avec un service périodique et une possibilité de blocage de service. Nous avons conçu trois mécanismes d’allocation de ressources : R2A, CENTRAL-SR et G2AR. L’algorithme R2A fournit une solution dynamique et efficace pour l’allocation de ressources dans un réseau asynchrone avec une topologie en anneau. Cependant, les mécanismes CENTRAL-SR et G2AR effectuent la réservation de ressources dans des architectures optiques synchrones respectivement organisées en anneau et en topologie maillée. Quant à lui, l’algorithme G2AR maximise le volume de requêtes de connexion acceptées dans le réseau et fournit des solutions efficaces de calcul de chemin et de reconfiguration après panne. Nous proposons également dans ce travail un mécanisme d’amélioration du remplissage de paquets optiques de taille fixe (mécanisme GPFO) et un mécanisme d’ordonnancement de paquets (RMPS). Le mécanisme GPFO accroît l’efficacité d’utilisation de ressources dans un mode de transmission de paquets optiques de taille fixe. Finalement, RMPS exploite la capacité de mémorisation électronique dans les nœuds d’accès afin de réduire les contentions de ressources dans le cœur du réseau.

La résolution du problème des vides dans le routage géographique dédié aux réseaux de capteurs sans fil (RCS), rencontrés lors de la remontée des informations vers les nœuds collecteurs à partir des nœuds du réseau, constitue un verrou technologique qui reste un problème ouvert encore aujourd'hui. Cette thèse, contrairement aux méthodes traditionnelles, propose une nouvelle approche pour la prise en charge de ces vides tout en optimisant l'efficacité énergétique des nœuds déployés dans un RCS faisant ainsi du routage proposé une solution adéquate pour l'acheminement des informations en temps réel. Celui-ci se base sur l'information géographique concernant le nœud courant, les vides voisins et le nœud destinataire du paquet. Notre proposition agit aussi sur des mécanismes assurant la découverte, l'annonce et la maintenance des vides d'un RCS. Le premier protocole proposé, appelé VT-SPEED, est construit sur la base d'une fonction évolutive intégrant un mécanisme d'évitement adaptatif des vides et considérant simultanément la charge des nœuds candidats au routage et leur information géographique de localisation. Afin d'optimiser l'efficacité énergétique de VT-SPEED, notre proposition inclut par ailleurs de nouvelles routines sur la base de fonctions paramétriques pour la prise en compte de l'énergie dans le routage : (a) suppression des paquets retardés sur la base de leur échéance et (b) équilibrage de charge dans le choix des sauts des paquets. Les résultats enregistrés par le protocole résultant, appelé VE-SPEED, montrent que l'approche proposée prend en compte les flux de type temps-réel, possède une grande tolérance aux vides, conserve mieux l'énergie des nœuds de bordure, assure un meilleur équilibrage de charge, et consomme de manière optimisée l'énergie des nœuds capteurs

Deux situations de comportement égoïste des agents dans les réseaux de communication sont considérées dans le cadre de la théorie des jeux.La première situation concerne les réseaux de communication utilisant un routage décentralisé basé sur des agents autonomes. Nous étudions les propriétés de convergence des dynamiques de meilleures réponses dans un jeu de routage sur des liens parallèles. Le jeu implique un nombre fini d'agents, chacun décidant comment son trafic est routé sur les liens de manière à minimiser son propre coût. Nous proposons l'utilisation du rayon spectral généralisé des matrices Jacobiennes de l'opérateur de meilleure réponse pour démontrer la convergence.La seconde situation apparaît dans les réseaux tolérants aux délais dont l'objectif est de permettre la communication dans des environnements où la connectivité n'est qu'intermittente et où les délais de communication peuvent être très longs. Nous proposons tout d'abord un mécanisme d'incitation basé sur une récompense pour convaincre les noeuds mobiles de relayer les messages, et analysons l'influence de l'information donnée par la source (nombre de copies du message, âge de ces copies) aux relais sur le prix à payer pour transmettre le message. Nous considérons ensuite un modèle dans lequel la source propose une récompense fixe. Les noeuds mobiles peuvent alors décider d'accepter ou non le message, et s'ils l'acceptent, peuvent ensuite à tout moment décider de l'abandonner. Nous modélisons l'interaction entre les noeuds mobiles sous la forme d'un jeu stochastique partiellement observable et analysons les politiques optimales pour les relais
This thesis focuses on the issues related to the selfish behavior of the agents in the communication networks. We are particularly interested in two situations in which these issues arise and we address game-theoretical framework to study them.The first situation relates to communication networks using a distributed routing based on autonomous agents. Compared to a centralized routing, this type of routing offers significant advantages in terms of scalability, ease of deployment or robustness to failures and environmental disturbances. We investigate the convergence properties of the sequential best-response dynamics in a routing game over parallel links. The game involves a finite number of routing agents each of which decides how much flow to route on each of the links with the objective of minimizing its own costs. For some particular cases (e.g., two players), the convergence of the best-response dynamics can be proved by showing that this game has a potential function. For other cases, a potential function has remained elusive. We propose the use of non-linear spectral radius of the Jacobian of the best-response dynamics as an alternative approach to proving its convergence.The second situation occurs in Delay Tolerant Networks (DTNs) that have been the subject of intensive research over the past decade. DTN has an idea to support communication in environments where connectivity is intermittent and where communication delays can be very long. We focus on game-theoretic models for DTNs. First, we propose an incentive mechanism to persuade selfish mobile nodes to participate in relaying messages, and investigate the influence of the information given by the source (number of existing copies of the message, age of these copies) to the relays on the rewards proposed. For static information polices, that is the same type of information given to all the relays, it is shown that the expected reward paid by the source is independent of the policy. However, the source can reduce the reward by dynamically adapting the type of information based on the meeting times with the relays. For the particular cases, we give some structural results of the optimal adaptive policy. Next, we consider the model where the source proposes a fixed reward. The mobile relays can decide to accept or not the packet and then to drop the packet in the future. This game can be modelled as a partially-observable stochastic game. For two relays, we have shown that the optimal policies for the relays relates to the threshold type

Dans les réseaux de distribution de contenu, la Qualité d'Expérience (QoE) est principalement évaluée par un indicateur de performance : la continuité de service. C'est pourquoi la robustesse des réseaux est une problématique majeure pour les opérateurs. La société TDF opère un réseau traditionnel de transport de flux audiovisuels en temps réel à l'aide de protocoles de multidiffusion. Toute panne réseau provoque cependant un temps de convergence non-nul, qui implique des pertes et des impacts sur le contenu. Ceci illustre que la continuité de service est une conséquence directe de la disponibilité de réseau. L'objectif des travaux de cette thèse est de définir une architecture pour inhiber les impacts sur le contenu lors des phases de cicatrisation du réseau. Cette architecture établit des paires d’arbres de multidiffusion redondants disjoints et dynamiques sur le réseau de transport. Les équipements de restitution pouvant exploiter cette redondance de chemins, il est possible de pallier à d'éventuelles pertes de paquet. L'essentiel des travaux porte sur le développement et l'évaluation de différents algorithmes de calcul des arbres de distribution destinés à alimenter le moteur de routage de l’architecture. La spécification des protocoles et processus de mise en œuvre sur le réseau est également abordée. L'implémentation de l'ensemble s'appuie sur une architecture de type Software Defined Networking (SDN), dans laquelle un contrôleur centralisé exploite la connaissance des performances et de la planification en bande passante pour établir et maintenir les paires d’arbres de multidiffusion
In Content Delivery Networks (CDN), Quality of Experience (QoE) provides a major performance indicator that is continuity of service. As a consequence, network robustness has become a major concern for network operators. TDF operates a traditional transport network for real-time video and audio transport through multicast. Any failure on the network causes a recovery time implying loss and an impact in the content viewing. This study's goal is to define an architecture preventing impact on the content during network healing time. This architecture computes and deploys redundant disjoint multicast trees on the transport network. As restitution equipments are able to exploit path diversity, packet loss consequences can be avoided. This work's main part is the development and evaluation of different algorithm for the computation of distribution trees, as part of the routing element of the architecture. Protocol specification and deployment process are also considered. Implementation is based on a Software Defined Networking (SDN) architecture in which a central controller uses its knowledge of the performance and bandwidth allocation to compute and maintain pairs of multicast trees

La Publication/Abonnement (Publish/Subscribe, Pub/Sub) est un paradigme qui permet aux nœuds d'un système distribué de diffuser des informations de manière asynchrone. Cette thèse s'intéresse aux systèmes de Pub/Sub basés sur des sujets (topic-based), en adressant les problèmes de performances et de contention existant dans plusieurs approches reposant sur des arbres. Les solutions proposées utilisent la construction d'arbres couvrants regroupant les abonnés et dont les racines sont les émetteurs. Les arbres associés à différentes sources sont organisés différemment. La première contribution de la thèse propose un protocole de diffusion causal agrégeant des messages et dans lequel aucun temporisateur n'est nécessaire. Le protocole regroupe les messages en un seul message sans utiliser des temporisateurs en tirant parti du délai de livraison supplémentaire imposé à un nœud lorsque les messages sont reçus en dehors de l'ordre causal ainsi que des intersections existantes entre des arbres couvrants. La deuxième contribution est un système de Pub/Sub par sujet, VCube-PS, qui assure l'ordre de traitement causal des messages publiés sur un même sujet et gère efficacement la publication de messages sur des sujets très populaires ("hot topics"). Les résultats des simulations confirment que le protocole d'agrégation causale proposé réduit le trafic réseau ainsi que des latences de livraison, en limitant la contention de messages. Comparé à une approche utilisant un seul arbre par sujet, VCube-PS repartit mieux la charge lors de publications massives sur des "hot topic"
The Publish/Subscribe (Pub/Sub) paradigm enables nodes of a distributed system to disseminate information asynchronously. This thesis investigates how to provide a communication-efficient topic-based Pub/Sub system by addressing the problems of traffic overhead and message contention, present in several tree-based solutions. The proposed contributions build distributed spanning trees on top of a hypercube-like topology, such that the source of each message is the root of its own dynamically built spanning tree. Trees rooted at different nodes are differently organized. Initially, it is proposed a causal broadcast protocol which reduces network traffic by aggregating messages without the use of timers. It exploits the causal relation between messages and path intersections between different trees. Different from existing timer-based approaches, it does not increase delivery latency. The second contribution is a topic-based Pub/Sub system, VCube-PS, which ensures causal delivery order for messages published to the same topic and efficiently supports publication of messages to "hot topics'', i.e., topics with high publication rates. Simulation results confirm that the proposed causal aggregation protocol reduces network traffic as well as delivery latencies since there is less message contention. Compared to an approach that uses one single tree per topic, VCube-PS performs better when there is a high publication rate per topic since it provides load balancing of publication

L'Internet des objets (IoT) a pour objectif de fournir une connectivité à des millions d'appareils utilisés au quotidien. Pour la majorité des applications, les connexions filaires sont peu pratiques et trop coûteuses. Par conséquent, les connexions sans fil sont le seul moyen réalisable de fournir une connectivité aux dispositifs. Une des nombreuses solutions sans fil est la norme IEEE802.15.4, conçue pour les réseaux maillés de faible consommation. Cette norme est largement utilisée pour les bâtiments intelligents, la domotique et les applications industrielles. Un amendement ultérieur, IEEE802.15.4g, définit 3 PHY (FSK, OFDM et O-QPSK). Cela cible les applications SUN (Smart Utility Networks), c’est-à-dire le comptage intelligent, tout en offrant une couverture étendue. Dans cette thèse, nous analysons l'utilisation de cette norme en dehors de l'environnement SUN et sur des applications industrielles. Premièrement, nous menons une série d’expériences avec IEEE802.15.4g-dispositifs afin de mesurer la portée des liens dans des scénarios extérieurs réels. Les résultats montrent que des communications très fiables avec des débits jusqu'à 800 kbps (avec OFDM) peuvent être atteintes en milieu urbain à 540 m entre les nœuds, et que la liaison radio la plus longue utile est obtenue à 779 m (FSK). Deuxièmement, nous comparons les performances de la norme IEEE802.15.4 à celle de la norme IEEE802.15.4g OFDM dans les bâtiments intelligents. A partir d'expériences, nous avons déterminé que l'OFDM IEEE802.15.4g surpasse l'IEEE802.15.4 et doit être considéré comme une solution pour les déploiements ultérieurs. Enfin, nous introduisons le concept du réseau agile: des nœuds pouvant modifier dynamiquement leur PHY en fonction de leurs besoins et de leur situation
The Internet of Things (IoT) aims to provide connectivity to millions of devices used in our day-to-day life. For the vast majority of applications, wired connections are unpractical and too expensive, therefore wireless connections is the only feasible way to provide connectivity to the devices. One of many wireless solutions is the standard IEEE802.15.4, specially designed for low power mesh networks. This standard is widely used for Smart Building, Home Automation and Industrial Applications.A subsequent amendment, the IEEE802.15.4g, defines 3 PHYs (FSK, OFDM and O-QPSK). This targets Smart Utility Networks(SUN) applications, i.e., Smart Metering, while providing extended coverage. In this thesis, we analyse the use of this standard outside the SUN environment and onto Industrial Networking applications.First, we conduct a series of experiments using IEEE802.15.4g compliant devices in order to measure the range coverage on radio links in real use case outdoor scenarios. Results show that highly reliable communications with data rates up to 800 kbps (with OFDM) can be achieved in urban environments at 540 m between nodes, and the longest useful radio link is obtained at 779 m (FSK). Sencond, regarding the robustness and high data rate of OFDM, we compare the performance of the IEEE802.15.4 with the IEEE802.15.4g OFDM in Smart Building scenarios. From experiments, we determine that IEEE802.15.4g OFDM outperforms IEEE802.15.4 and should be considered as a solution for further deployments in combination with a TSCH MAC approach. Finally, we introduce the concept of Network Agility: nodes that can dynamically change their PHY according to their needs and circumstances