Academic literature on the topic 'Protocole de routage épidémique'

Cette thèse s´intéresse à la conception et l´évaluation des protocoles de routage et d´accès au canal pour les réseaux sans fils. La première partie de la thèse focalise principalement sur l´évaluation de protocoles de routage pour les réseaux tolérants aux perturbations quand ces réseaux incluent des relais fixes, appelées boîtes. Dans un premier temps, nous montrons que les instants successifs de rencontre entre une boîte et un noeud mobile qui se déplace selon un modèle de mobilité aléatoire sont bien approximés par un processus de Poisson. Nous donnons une formule explicite approchée pour l´intensité de ce processus qui dépend notamment de la densité de probabilité spatiale du modèle de mobilité considérée ainsi que celle des boîtes. Dans un deuxième temps, nous étudions l´impact d´ajouter des boîtes sur les performances de deux protocoles de routage classiques, le protocole épidémique et le protocole de routage à deux sauts. Nous développons des expressions explicites pour quantifier la distribution et la moyenne du délai de livraison d´un paquet, ainsi que le nombre des copies générées lors de cette transmission. Ensuite, nous proposons cinq stratégies qui s´appuient sur la présence des boîtes pour réaliser le routage des copies. Par ailleurs, nous introduisons une plateforme basée sur un modèle markovien qui permet de calculer et de comparer analytiquement les diverses métriques de performance pour ces cinq stratégies. Dans la deuxième partie de la thèse, nous intéressons à l´algorithme de backoff du standard IEEE 802.11. Nous proposons une extension de cet algorithme dont l´objectif est d´améliorer ses performances dans le cas où le réseau possède un grand nombre d´utilisateurs.

Parmi les architectures orientées contenu, l'architecture NDN (Named-Data Networking) a su agréger la plus importante communauté de chercheurs et est la plus aboutie pour un Internet du futur. Dans le cadre de l'architecture NDN, au cours de ce doctorat, nous nous sommes concentrés sur les mécanismes de routage adaptés à cette nouvelle vision du réseau. En effet, la capacité à acheminer une requête vers la destination est fondamentale pour qu'une architecture réseau soit fonctionnelle et cette problématique avait été très peu étudiée jusqu'alors. Ainsi, dans ce manuscrit, nous proposons le protocole de routage SRSC (SDN-based Routing Scheme for CCN/NDN), qui repose sur l'utilisation du paradigme des réseaux logiciels (Software-Defined Networks\\, SDN). SRSC utilise un contrôleur capable de gérer le plan de contrôle du réseau NDN. En centralisant l'ensemble des informations telles que la topologie du réseau, la localisation des différents contenus et le contenu des mémoires cache des nœuds du réseau, le contrôleur va pouvoir établir la meilleure route pour acheminer les requêtes vers le contenu. SRSC permet également un routage de type anycast, c'est à dire qu'il permet d'acheminer les requêtes vers le nœud le plus proche qui dispose des données, permettant d'optimiser la distribution des requêtes dans le réseau et de répartir la charge parmi tous les nœuds. De plus, SRSC utilise uniquement les messages Interest et Data de l'architecture NDN et tient son originalité du fait qu'il s'affranchit complètement de l'infrastructure TCP/IP existante. Dans un premier temps, SRSC a été évalué via simulation avec le logiciel NS-3 où nous l'avons comparé à la méthode d'inondation des requêtes, appelée flooding, initialement proposée par NDN. SRSC a ensuite été implanté dans NDNx, l'implantation open source de l'architecture NDN, puis déployé sur notre testbed utilisant la technologie Docker. Ce testbed permet de virtualiser des nœuds NDN et d'observer un réel déploiement de cette architecture réseau à large échelle. Nous avons ainsi évalué les performances de notre protocole SRSC sur notre testbed virtualisé et nous l'avons comparé au protocole NLSR, (Named-Data Link State Routing Protocol), le protocole de routage du projet NDN<br>Internet is a mondial content network and its use grows since several years. Content delivery such as P2P or video streaming generates the main part of the Internet traffic and Named Data Networks (NDN) appear as an appropriate architecture to satisfy the user needs. Named-Data Networking is a novel clean-slate architecture for Future Internet. It has been designed to deliver content at large scale and integrates several features such as in-network caching, security, multi-path. However, the lack of scalable routing scheme is one of the main obstacles that slow down a large deployment of NDN at an Internet-scale. As it relies on content names instead of host address, it cannot reuse the traditional routing scheme on the Internet. In this thesis, we propose to use the Software-Defined Networking (SDN) paradigm to decouple data plane and control plane and present SRSC, a new routing scheme for NDN based on SDN paradigm. Our solution is a clean-slate approach, using only NDN messages and the SDN paradigm. We implemented our solution into the NS-3 simulator and perform extensive simulations of our proposal. SRSC show better performances than the flooding scheme used by default in NDN. We also present a new NDN testbed and the implementation of our protocol SRSC, a Controlled-based Routing Scheme for NDN. We implemented SRSC into NDNx, the NDN implementation, and deployed it into a virtual environment through Docker. Our experiments demonstrate the ability of our proposal to forward Interest, while keeping a low computation time for the Controller and low delay to access Content. Moreover, we propose a solution to easily deploy and evaluate NDN network, and we compare SRSC with NLSR, the current routing protocol used in NDNx

Internet est le réseau le plus gigantesque que l'humanité ne se soit pourvu. Il fournit un nombre important de services à plus de deux milliards d'utilisateurs. Cette topologie grandissante et complexe pêche en stabilité, ce qui peut notamment être constaté quand un appel voix est interrompu, quand une page web à besoin d'être rafraîchie, etc. L'initiateur de cette instabilité est l'ensemble des événements constatés dans l'Internet. Ceci nous motive à une Étude profonde de la stabilité d'Internet afin de suggère des solutions à cette problématique. Internet est divisé en deux niveaux de base: le niveau AS (Autonomous System) et le niveau de routage. Cette distinction se répercute dans les protocoles de routage qui contrôlent le trafic Internet à travers deux types de protocoles: extérieur (inter-AS) et intérieur (intra-AS). L'unique protocole de routage extérieur utilité est le mode externe de BGP (External Border Gateway Protocol) tandis qu'il en existe plusieurs de type intérieur. De fait, la stabilisation de l'Internet est corrélée à la stabilité des protocoles de routage. Cela pousse les efforts de traitement de l'instabilité de l'Internet à Étudier le comportement du protocole de routage (BGP). Analyser les résultats des comportements de BGP dans son mode externe (eBGP) souffre d'un temps de convergence important menant notamment à des réponses lentes des évènements de topologie et, à terme, à la perte du trafic. Les études établissent également que le mode interne de BGP (iBGP) souffre de plusieurs types d'anomalies de routage causant la divergence. Afin d'illustrer la stabilité de BGP, nous avons besoin d'un modèle de routage qui formule la procédure de décision et le flot de signalisation. De plus, les améliorations de BGP ne peuvent pas être aisément validées dans l'Internet, rendant ainsi les modèles de BGP indispensables à une validation formelle. De fait, la première étape dans l'étude du routage inter-domaine est de définir un modèle approprié permettant la formulation de ses opérations et de prouver sa correction. Nous avons proposé deux modèles complémentaires: topologique et fonctionnel, avec lesquels nous avons formulé le processus de convergence du routage et démontré la sécurité et la robustesse de nos solutions d'inter/intra-AS. Notre proposition d'inter-AS élimine les déconnections transitoires causées par une faible convergence d'eBGP en suggérant une stratégie de backup lors d'une panne. Notre proposition d'intra-AS (skeleton) donne une alternative aux configurations internes existantes, pour laquelle nous avons montré l'absence d'anomalies.

Les protocoles de routage dans les réseaux peuvent être amenés à changer pour de nombreuses raisons : la détection d'un événement particulier, un changement de topologie planifié ou non, la mobilité des nœuds, l'obsolescence de version, etc. Ces changements ne pouvant être simultanément détectés ou pris en compte par tous les nœuds du réseau, il est nécessaire de considérer le cas où certains nœuds utilisent le protocole de routage initial, tandis que d'autres ont migré vers le nouveau protocole de routage. Les travaux de cette thèse portent sur le problème de boucles de routage susceptibles d'apparaître dans ce contexte, et qui dégradent considérablement les performances du réseau. Nous proposons des solutions d'ordonnancement des nœuds, dans le but de contrôler la migration afin d'éviter ces boucles. Premièrement, nous considérons le contexte des réseaux statiques et des protocoles centralisés avec pour cas particulier le changement de métriques dans le réseau. Nous proposons deux solutions d'évitement des boucles centralisées : SCH-m (amélioration mineure d'un protocole existant), et ACH (nouvelle contribution), basées sur l'identification des boucles de routage dans les composantes connexes que contient l'union des deux protocoles de routage. Nous accélérons la migration du réseau par une opération de fusion étape par étape des différentes transitions produites. Deuxièmement, nous évoluons vers les protocoles distribués en conservant le contexte statique du réseau, et considérons le cas particulier du retrait ou de la panne d'un nœud. Nous proposons également deux solutions : RTH-d (amélioration mineure d'un protocole existant) et DLF (nouvelle contribution traitant les boucles de taille 2) basées sur un échange de messages entre les nœuds tant pour la détection de la panne que pour la notification de la migration. Troisièmement, nous considérons le contexte de mobilité des nœuds, et étudions les performances de DLF-k (version améliorée de DLF qui prend en compte les boucles de taille inférieures ou égales à k, avec k &gt;= 2) sur deux types d'applications : les applications avec un unique nœud mobile qui est la destination, et les applications avec un groupe de nœuds mobiles<br>Routing protocols in networks may change for many reasons: detection of a particular event, planned or unplanned change of topology, mobility of nodes, version obsolescence, etc. As these changes can not be simultaneously detected or taken into account by all nodes of the network, it is necessary to consider the case where some nodes use the initial routing protocol, while others have migrated to the new routing protocol. The work of this thesis deals with the problem of routing loops that may appear in this context, and which considerably degrade the performance of the network. We propose node scheduling solutions to control migration to avoid these loops. First, we consider the context of static networks and centralized protocols with the particular case of changing metrics. We propose two centralized avoidance solutions: SCH-m (minor improvement of an existing heuristic), and ACH (new contribution), based on the identification of the routing loops in the strongly connected components contained in the union of the two routing protocols. We accelerate the migration of the network by a step-by-step merge operation of the different transitions produced. Second, we evolve towards the distributed protocols while preserving the static context of the network, and consider the particular case of the withdrawal or breakdown of a node. We also propose two solutions: RTH-d (minor improvement of an existing heuristic) and DLF (new contribution for loops of size 2) based on message exchange of nodes for both failure detection and for migration notification. Thirdly, we consider the context of nodes mobility, and study the performance of DLF- k (improved version of DLF which takes into account loops of size less than or equal to k, with k &gt;= 2) on two types of applications: applications with a single mobile node that is the destination, and applications with a group of mobile nodes

La première partie de cette thèse est consacrée à l'étude de la topologie d'Internet, à travers son organisation logique, et à un bref état de l'art des modèles d'Internet. Nous présentons ensuite un nouveau modèle pour la topologie d'Internet. Ce modèle nous servira d'outil pour vérifier des comportements de protocoles de routage unicast et multicast discutés plus loin dans le document. La deuxième partie est consacré à l'étude des protocoles multipoint. Nous nous intéressons dans un premier temps aux techniques de construction d'arbres multipoint, au travers d'un bref état de l'art. Nous proposons ensuite deux protocoles. Le protocole MSDA a pour objet l'optimisation de l'utilisation d'un arbre de multicast donné. Nous avons réalisé des expérimentations sur des topologies obtenues avec notre générateur de topologie afin de mesurer l'amélioration obtenue par MSDA. Nous proposons ensuite un nouveau protocole de construction d'arbre de multicast. Ce protocole s'appelle MCT (pour "Minimum Congestion Tree"). Il permet de construire des arbres optimaux selon tout paramètre de qualité de service donné. Nous avons effectué des simulations sur la topologie du réseau ARPANET (1995) en comparant MCT à d'autres protocoles multipoint classiques. Ces simulations démontrent l'impact positif de MCT pour le multicast. La dernière partie est consacrée à la présentation d'un modèle autosimilaire du trafic d'Internet, et d'un nouveau paramètre de qualité de service : la congestion probabiliste. Ce paramètre permet d'approximer efficacement le taux de pertes. Il est adapté à une description à long terme du trafic, et peut être utilisé dans des protocoles de routage point à point ou multipoint. Nous avons effectué des simulations pour valider notre approche (sur les topologies du réseau UUNET et obtenues à partir de notre modèle d'Internet). Ces simulations démontrent l'utilité de la congestion probabiliste pour les protocoles multipoint<br>The first part of this thesis is dedicated to the study of the Internet topology, and a survey of the Internet models. We present a new model for Internet. This model will allows us to test unicast and multicast routing protocols. The second part is dedicated to multicast protocols. First, we presented a survey of construction technique for multicast trees. We propose two multicast protocols. MSDA protocol optimizes the total delay of multicast messages in a multicast tree. In order to quantify the optimization, we tested MSDA with the topologies obtained with our topology generator. MCT protocol builds the optimal multicast tree according to some predefined quality-of-service parameter. We performed simulations with ARPANET (1995) network topology in order to compare MCT with other classical multicast protocols. These simulations prove the positive impact of MCT for multicast communications. The last part is dedicated to the self-similar model of Internet traffic, and to a new quality-of-service parameter: the probabilistic congestion. This parameter allows the estimation of the rate of packet loss. Probabilistic congestion is adapted to a long-term description of the traffic, and it can be used for unicast routing protocols. We performed a simulation in order to validate our ideas (in the UUNET network and in the generated topologies from our topology model). These simulations prove the usefulness of probabilistic congestion for multicast protocols

La notion de confiance, quoique implicite, est toujours présente dans le fonctionnement des protocoles, en particulier, entre les entités qui participent aux opérations de routage. <br />Dans notre travail, nous nous sommes intéressés à la gestion de la confiance (trust management) comme une solution de sécurité pour le protocole OLSR (Optimized Link State Routing Protocol). Cette approche s'adapte particulièrement à la nature mobile, ad-hoc, distribuée et auto-organisée des réseaux ad-hoc. De plus, la gestion explicite de la confiance permet aux entités de raisonner avec et à propos de la confiance, les rendant ainsi plus robustes pour la prise de décisions concernant les autres entités.<br />Nous commençons par une analyse du fonctionnement du protocole OLSR sous l'optique de la confiance. Ensuite, nous proposons un raisonnement basé sur la confiance pour permettre à chaque noeud d'évaluer le comportement des autres noeuds, de détecter les comportements malveillants, et donc de pouvoir décider de faire confiance ou non. Enfin, nous proposons une solution de prévention et des contremesures pour résoudre le cas d'une incohérence et contrer les comportements malveillants. Ces solutions ne nécessitent que peu de modifications sur le protocole OLSR et peuvent être étendues selon le type d'attaque et les besoins des utilisateurs.

La notion de confiance, quoique implicite, est toujours présente dans le fonctionnement des protocoles, en particulier, entre les entités qui participent aux opérations de routage. Dans notre travail, nous nous sommes intéressés à la gestion de la confiance comme une solution de sécurité pour le protocole OLSR (Optimized Link State Routing Protocol). Cette approche s'adapte particulièrement à la nature mobile, ad-hoc, distribuée et auto-organisée des réseaux ad-hoc. De plus, la gestion explicite de la confiance permet aux entités de raisonner avec et à propos de la confiance, les rendant ainsi plus robustes pour la prise de décisions concernant les autres entités. Nous commençons par une analyse du fonctionnement du protocole OLSR sous l'optique de la confiance. Ensuite, nous proposons un raisonnement basé sur la confiance pour permettre à chaque noeud d'évaluer le comportement des autres noeuds, de détecter les comportements malveillants, et donc de pouvoir décider de faire confiance ou non. Enfin, nous proposons une solution de prévention et des contremesures pour résoudre le cas d'une incohérence et contrer les comportements malveillants. Ces solutions ne nécessitent que peu de modifications sur le protocole OLSR et peuvent être étendues selon le type d'attaque et les besoins des utilisateurs<br>The implicit trust is always present in the operating protocols, in particular, between the entities involved in routing operations. In our work, we are interested by trust management as security solution for OLSR protocol. This approach fits particularly with characteristic of ad-hoc networks. Moreover, the explicit trust management allows entities to reason with and about trust, and to take decisions regarding other entities. First, we analyse the fonctionning of OLSR protocol under the terms of trust. Then, we propose a trust-based reasoning which allow to each node to evaluate the behavior of the other nodes, to detect misbehavior nodes, and then to be able to trust or not the other nodes. Finally, we propose a solutions of prevention and contermeasures to resolve the situations of inconsistency, and counter the malicious nodes. These solutions require only minor modifications on the OLSR and can be extended depending on the attack type and users needs

Les réseaux ad hoc sont constitués d’un ensemble de noeuds mobiles qui échangent des données sans infrastructure de type point d’accès ou artère filaire. Ils sont par définition auto-organisés. Les changements fréquents de topologie des réseaux ad hoc rendent le routage multi-sauts très problématique. Dans cette thèse, nous proposons un protocole de routage à chemins multiples appelé Multipath Optimized Link State Routing (MP-OLSR). C’est une extension d’OLSR à chemins multiples qui peut être considérée comme une méthode de routage hybride. En effet, MP-OLSR combine la caractéristique proactive de la détection de topologie et la caractéristique réactive du calcul de chemins multiples qui est effectué à la demande. Les fonctions auxiliaires comme la récupération de routes ou la détection de boucles sont introduites pour améliorer la performance du réseau. L’utilisation de la longueur des files d’attente des nœuds intermédiaires comme critère de qualité de lien est étudiée et la compatibilité entre routage à chemins multiples et chemin unique est discutée pour faciliter le déploiement du protocole. Les simulations basées sur les logiciels NS2 et Qualnet sont effectuées pour tester le routage MP-OLSR dans des scénarios variés. Une mise en oeuvre a également été réalisée au cours de cette thèse avec une expérimentation sur le campus de Polytech’Nantes. Les résultats de la simulation et de l’expérimentation révèlent que MP-OLSR est particulièrement adapté pour les réseaux mobiles et denses avec des trafics élevés grâce à sa capacité à distribuer le trafic dans des chemins différents et à des fonctions auxiliaires efficaces. Au niveau application, le service vidéo H. 264/SVC est appliqué à des réseaux ad hoc MP-OLSR. En exploitant la hiérarchie naturelle délivrée par le format H. 264/SVC, nous proposons d’utiliser un codage à protection inégale (PFEC) basé sur la Transformation de Radon Finie (FRT) pour améliorer la qualité de la vidéo à la réception. Un outil appelé SVCEval est développé pour simuler la transmission de vidéo SVC sur différents types de réseaux dans le logiciel Qualnet. Cette deuxième étude témoigne de l’intérêt du codage à protection inégale dans un routage à chemins multiples pour améliorer une qualité d’usage sur des réseaux auto-organisés<br>Ad hoc networks consist of a collection of wireless mobile nodes which dynamically exchange data without reliance on any fixed based station or a wired backbone network. They are by definition self-organized. The frequent topological changes make multi-hops routing a crucial issue for these networks. In this PhD thesis, we propose a multipath routing protocol named Multipath Optimized Link State Routing (MP-OLSR). It is a multipath extension of OLSR, and can be regarded as a hybrid routing scheme because it combines the proactive nature of topology sensing and reactive nature of multipath computation. The auxiliary functions as route recovery and loop detection are introduced to improve the performance of the network. The usage of queue length metric for link quality criteria is studied and the compatibility between single path and multipath routing is discussed to facilitate the deployment of the protocol. The simulations based on NS2 and Qualnet are performed in different scenarios. A testbed is also set up in the campus of Polytech’Nantes. The results from the simulator and testbed reveal that MP-OLSR is particularly suitable for mobile, large and dense networks with heavy network load thanks to its ability to distribute the traffic into different paths and effective auxiliary functions. The H. 264/SVC video service is applied to ad hoc networks with MP-OLSR. By exploiting the scalable characteristic of H. 264/SVC, we propose to use Priority Forward Error Correction coding based on Finite Radon Transform (FRT) to improve the received video quality. An evaluation framework called SVCEval is built to simulate the SVC video transmission over different kinds of networks in Qualnet. This second study highlights the interest of multiple path routing to improve quality of experience over self-organized networks

La facilité de déploiement des réseaux ad hoc s'avère utile lorsque la mise en place d'une infrastucture est impossible. L'objectif du routage est de trouver les chemins tout en considérant les contraintes de bande passante et de dynamicité de la topologie. Dans cette thèse, nous nous sommes intéressés à l'adaptation du type de routage selon les conditions de mobilité et de densité du réseau. Nous proposons une méthode d'auto-adaptation du mode de routage en fonction de la mobilité et de la densité. Les métriques de mobilité et de densité, les modes de routages ainsi que les transitions entre les modes ont été définis. Nous avons montré la faisabilité de notre méthode en proposant une extension hiérarchique du protocole plat DSR que nous avons nommée CSR. Nous avons spécifié les procédures CSR et les avons implantée sous ns2. Nous avons mené une étude de performances du CSR en le comparant aux protocoles préconisés par l'IETF pour montrer l'intérêt de l'adaptation du mode de routage.