Dans cette thèse, nous étudions plusieurs modèles de routage efficaces en énergie. Pour chaque modèle, nous présentons une formulation en programmation linéaire mixte permettant de trouver une solution exacte. En outre, comme il s’agit de problèmes NP-Difficiles, nous proposons des heuristiques efficaces pour des réseaux de grande taille. Dans la première partie de cette thèse, nous étudions une solution de routage efficace en énergie dans laquelle nous ajoutons la possibilité d’éliminer des redondances dans les paquets transmis sur le réseau. Nous montrons premièrement que l’ajout de l’élimination des redondances permet d’améliorer l’efficacité énergétique des réseaux en éteignant plus de liens. Ensuite, nous étendons le modèle afin qu’il prenne en compte un certain niveau d’incertitudes dans le volume de trafic et le taux de redondances. La deuxième partie de cette thèse est consacrée aux problèmes qui se posent lors du déploiement de tels protocoles dans les réseaux. Plus particulièrement, nous proposons de minimiser les changements entre deux configurations réseaux consécutives lorsque plusieurs matrices de trafic sont considérées. Le routage des demandes étant alors assuré avec le protocole de routage OSPF (Open Shortest Path First). Ensuite, nous abordons le problème de la limitation du nombre de règles de routage dans les routeurs en utilisant une technologie de type SDN (Software Defined Networks). Enfin, nous présentons en annexe des travaux complémentaires réalisés au cours de cette thèse concernant le routage multicast et le contrôle de congestion TCP. / In this thesis, we study several models of energy-Aware routing. For each model, we present a linear programming formulation to find the exact solution. Moreover, since energy-Aware routing is NP-Hard problem, we also propose efficient heuristic algorithms for large scale networks. In the first part of this thesis, we deal with GreenRE - a new energy-Aware routing model with the support of redundancy elimination. We first present a deterministic model in which we show how to combine energy-Aware routing and redundancy elimination to improve energy efficiency for backbone networks. Then, we extend the model in order to take into account uncertainties in traffic volumes and redundancy rates. The second part of this thesis is devoted to the deployment issues of energy- aware routing in practice. In detail, to avoid service deterioration for end-Users, we limit changes of network configurations in multi-Period traffic matrices in Open Shortest Path First (OSPF) protocol. Next, we address the problem of limited rule space in OpenFlow switches when installing energy-Aware routing configurations. Finally, we present in the appendix other works developed during this thesis: multicast network protocol and TCP congestion control algorithm.

Les réseaux centrés contenus (ICN) sont considérés comme une solution aux nouveaux défis et modes de communication liés à l'émergence de l'Internet des Objets (IoT). Pour confirmer cette hypothèse, la problématique fondamentale du routage sur les réseaux ICN-IoT doit être abordée. Cette thèse traite de ce sujet à travers l'architecture IoT.Premièrement, une méthode sécurisée est introduite pour acheminer des paquets ICN à partir de coordonnées géographiques dans un réseau sans-fil de capteurs à faible puissance. Elle est comparée à une inondation optimisée du réseau inspirée des approches existant dans la littérature. En particulier, leur faisabilité et passage à l'échelle sont évalués via un modèle mathématique. Le modèle est paramétré grâce à des données réalistes issues de simulation, de la littérature, et d'expériences sur des capteurs. Il est montré que le routage géographique permet de diviser la mémoire nécessaire sur les capteurs par deux et de réduire considérablement le coût énergétique du routage, en particulier pour des topologies dynamiques.Ensuite, ICN est utilisé pour contrôler l'admission à une plate-forme de calcul de type Fog afin de garantir le temps de réponse. La stratégie de contrôle d'admission proposée, le LRU-AC, utilise l'algorithme Least-Recently-Used (LRU) pour apprendre en direct la distribution de popularité des requêtes. Son efficacité est démontrée grâce à un modèle fondé sur un réseau de files d'attente. Une implémentation du LRU-AC est proposé, utilisant des filtres de Bloom pour satisfaire aux contraintes des cartes FPGA. Son bien-fondé est prouvé par un modèle mathématique et son efficacité en termes de latence et débit démontrée.Enfin, on présente vICN, un outil pour la gestion et la virtualisation de réseaux ICN-IoT. Il s'agit d'une plate-forme qui unifie la configuration et la gestion des réseaux et des applications en exploitant les progrès des techniques d'isolation et de virtualisation. vICN est flexible, passe à l'échelle, et peut remplir différents buts : expériences à grande échelle reproductibles pour la recherche, démonstrations mélangeant machines émulées et physiques, et déploiements réels des technologies ICN dans les réseaux IP existants. / As the Internet of Things (IoT) has brought upon new communication patterns and challenges, Information-Centric Networking (ICN) has been touted as a potential solution. To confirm that hypothesis, the fundamental issue of routing and forwarding in the ICN-IoT must be addressed. This thesis investigates this topic across the IoT architecture.First, a scheme to securely forward ICN interests packets based on geographic coordinates is proposed for low-power wireless sensor networks (WSN). Its efficiency is compared to an optimized flooding-based scheme similar to current ICN-WSN approaches in terms of deployability and scalability using an analytical model. Realistic data for the model is derived from a mixture of simulation, literature study, and experiments on state-of-the-art sensor boards. Geographic forwarding is shown to halve the memory footprint of the ICN stack on reference deployments and to yield significant energy savings, especially for dynamic topologies. Second, ICN is used to enhance admission control (AC) to fixed-capacity Edge-computing platforms to guarantee request-completion time for latency-constrained applications. The LRU-AC, a request-aware AC strategy based on online learning of the request popularity distribution through a Least-Recently-Used (LRU) filter, is proposed. Using a queueing model, the LRU-AC is shown to decrease the number of requests that must be offloaded to the Cloud. An implementation of the LRU-AC on FPGA hardware is then proposed, using Ageing Bloom Filters (ABF) to provide a compact memory representation. The validity of using ABFs for the LRU-AC is proven through analytical modelling. The implementation provides high throughput and low latency.Finally, the management and virtualization of ICN-IoT networks are considered.vICN (virtualized ICN), a unified intent-based framework for network configuration and management that uses recent progress in resource isolation and virtualization techniques is introduced. It offers a single, flexible and scalable platform to serve different purposes, ranging from reproducible large-scale research experimentation to demonstrations with emulated and/or physical devices and network resources and to real deployments of ICN in existing IP networks.

Dans cette thèse nous nous intéressons à l'étude et à la résolution de problèmes d'optimisation dans le domaine du transport. La première problématique concerne le problème d'élaboration de tournées avec gestion des stocks, et nous considérons dans une seconde partie le problème du voyageur de commerce avec tirant d'eau. Nous avons développé des approches basées sur la recherche à voisinage variable pour résoudre ces problèmes NP-Difficiles, en proposant différentes structures de voisinages et schémas de résolution efficaces. L'évaluation globale des approches proposées sur des instances de la littérature montre leur efficacité. En particulier, nos algorithmes ont amélioré les résultats obtenus par les meilleures approches existantes pour ces deux problèmes. / This thesis deals with the study of optimization problems in the transportation domain. We first address the inventory routing problem and we consider the traveling salesman problem with draft limits in a second part. In both cases we have developed methods based on the variable neighborhood search to solve these NP-hard problems. We have proposed several efficient neighborhood structures and solving frameworks. The global evaluation of the proposed approach on sets of benchmarks available in the litterature shows a remarkable efficency and effectiveness. In particular, our algorithms have improved the results obtained by the current best approaches for these two problems.

De nos jours, la complexité de la conception des circuits intégrés et du logiciel croit régulièrement, faisant croître le besoin de la vérification dans chaque étape du cycle de conception. Le prototypage matériel sur une plateforme multi-FPGA présente le meilleur compromis entre le temps de conception d'un circuit et le temps d'exécution d'une application par ce circuit. Pour l'implémenter sur cette plateforme, une opération de partitionnement est effectuée avant de créer des partitions capables de s'intégrer dans chaque FPGAPar conséquent, des signaux coupés à l'interface des partitions doivent passer d'un FPGA à un autre. Cependant, le nombre de traces physiques inter-FPGA est limité ce qui crée des problèmes de routabilité du circuit prototypé. Cette thèse touche surtout la partie post-partitionnement et s'intéresse au problème deroutage inter-FPGA. Ainsi, les principaux travaux de cette thèse sont les suivants :Dans un premier temps, nous nous intéressons au développement d'un générateur debenchmarks qui permet, à l'aide d'une description architecturale simple du benchmark, de générer un circuit modélisé avec le langage de description matérielle VHDL. Le générateur utilise un ensemble de composants ce qui donne aux benchmarks un aspect réel semblable à celui des circuits industriels. Ces circuits de tests nous serviront pour évalue rles performances des techniques développées dans cette thèse. Dans un deuxième temps, nous proposons de développer un outil spécifique qui intervient après le partitionnement pour prendre en compte la contrainte liée à la limitation du nombre d'interconnexion entre les FPGAs. Cet outil est basé sur une approcheitérative visant à réduire le taux de multiplexage (nombre de signaux qui partagent un seul _l physique). Le routage en lui même est assuré par l'algorithme de routage Pathfinder adapté. Cet algorithme servira comme point de départ pour les techniques de routage développées durant cette thèse. Des adaptations adéquates seront faites pour cibler un ré-seau de routage inter-FPGA. Dans une deuxième partie, nous essayons de déterminer la meilleure forme du signal à router (bi-points ou multi-points) ainsi que le graphe de routage utilisé. Pour cela, nous proposons des scénarios de test a_n de sélectionner les critères qui donnent la fréquence de fonctionnement la plus performante. Par la suite, nous présentons une description détaillée des IPs de multiplexage utilisés.Ces IPs sont insérés dans les parties émettrices et réceptrices d'un canal de communication. Ces IPs incluent des composants spécifiques appelés SERDES pour assurer la sérialisation/déserialisation des données à transmettre. L'insertion de ces composants peut créer des problèmes de routabilité intra-FPGA. Ainsi, dans une deuxième partie, nous proposons un algorithme de placement basé sur l'estimation de la congestion afin d'améliorer la routabilité du circuit. / This thesis mainly deals with the post-partitioning task and addresses the problem of inter-FPGA routing. Thus, the main contributions of this thesis are: Firstly, we focus on the development of a benchmark generator which, using a simple architectural description of the benchmark, generates a circuit modelled with the hardware description language VHDL. The generator uses a set of industrial components providing benchmarks with real behaviour similar to that of industrial circuits. These benchmarks are used to evaluate the performance of the techniques developed in this thesis. In a second step , we propose a speci_c tool which acts after the partitioning to handle the constraints related to the limited number of interconnection between FPGAs. This tool is based on an iterative approach and aims to reduce the multiplexing ratio (the number of signals that share the same physical wire). The routing task itself is operated by the Pathfinder routing algorithm which is widely used by academic and industrial researchers . This algorithm is used as a starting point for routing techniques developed in this thesis . In a second part , we try to identify the best shape of the routed signals and the appropriate routing graph. For this reason, we propose scenarios to select criteria that give the best system frequency. Finally, we present a detailed description of the architecture of the multiplexing IPs. These IPs are inserted in the transmitting and receiving FPGAs of a communication channel. These IPs include speci_c components called SERDES for serialization/deserialization of the data. The insertion of these IPs can create problems of intra-FPGA routability. Thus, in a second part, we propose a placement algorithm based on congestion estimation to improve the routability of the circuit.

À l'aire du Multimedia Mobile, l'essor des réseaux sans fil est fulgurant et la mobilité est devenue un sujet primordial exacerbé par l'augmentation significative du nombre d'usagers mobiles. Un nœud évoluant dans un réseau mobile de base se comporte de la même manière qu'un aveugle évoluant dans notre univers en en élaborant sa propre représentation à l'aide de son bâton, mécanisme dénommé dans la littérature : mobilité terminale. Pour réduire cet aveuglement, plusieurs méthodes ont été élaborées qui prennent appui sur les services de localisation ou les modèles de mobilité. Un modèle de mobilité est donc destiné à décrire en termes d'environnement, le mode de circulation des nœuds mobiles avec pour défi de trouver des modèles fidèles aux comportements des utilisateurs. Les modèles aléatoires sont biaisés car les appareils mobiles sont portés par des êtres sociaux. Cela nous a amené à inclure des éléments sociaux dans notre modélisation.Nous présentons les modèles de mobilité existants et les classifions. Nous définissons nos modèles, les implémentons et mesurons leur impact sur le test des réseaux. Enfin nous élargissons notre spectre en montrant comment le fait d'octroyer la perception de regroupement social à un protocole de routage réseau, peut en améliorer les performances. / In our area of Mobile Multimedia, the expansion of wireless networks is dazzling and mobility has become a major issue exacerbated by the significant increase in the number of mobile users.A node operating in a basic mobile network behaves the same way a blind person moving in our universe by developing its own representation with his stick, a mechanism known in the literature as terminal mobility. To reduce this blindness, several methods have been developed that are based on location services and mobility models.A mobility model is then intended to describe in terms of environment, the motion criteria of mobile nodes with the challenge to find models faithful to user behavior.Random models are biased because mobile devices are supported by social beings. This led us to include social elements in our models.We present the existing mobility models and classify them.We define our models, implement them and measure their impact on the network testing.Finally we expand our spectrum by showing that granting social grouping perception to a network routing protocol, can improve its performance.

Les prestataires de service réseau doivent faire face à la demande croissante des besoins des utilisateurs, en particulier vers une plus grande flexibilité et toujours plus de capacité. La "softwerisation" et la "cloudification" des composants du réseau offrent une solution prometteuse pour obtenir l'agilité nécessaire afin de répondre dynamiquement à l'exigence au niveau de la consommation des ressources. Cette vision se traduit par le déploiement de la Virtualisation des Fonctions Réseau (NFV) où les Fonctions de Réseau Virtuels (VNFs) peuvent être associées pour créer des services réseau. Cette thèse étudie la problématique de l'allocation de ressources dans un système NFV afin de minimiser son coût sous contraintes sur l'interconnectivité entre les VNF, les ressources du système et les exigences de service. La principale considération est la réduction du coût global du déploiement en ressources informatiques. Nous étudions également d'autres objectifs à satisfaire tels que la migration des fonctions réseau et la gestion de la congestion. Notre premier objectif est d'augmenter notre compréhension de la performance d'un système NFV en étudiant le placement et le routage des fonctions réseau. Nous formalisons le problème dans une approche globale en tenant compte d'un large ensemble de paramètres pertinents. Nous prendrons en compte les cas statiques (Hors Ligne) et dynamiques (En Ligne) du problème. Nous proposons et analysons trois algorithmes heuristiques: deux sont conçus pour traiter de grandes dimensions du scenario "Hors Ligne" et le dernier est conçu pour résoudre le scénario "En Ligne". Les résultats montrent que notre solution surpasse l'état de l'art par rapport à l'indicateur de performance critique. Nous évaluons également l'impact de la migration d'une série de demandes simultanées et proposons une technique de migration simple pour ce système dynamique. A la lumière de ces premiers résultats, nous étendons notre étude afin d'améliorer l'efficacité de notre solution en proposant un modèle plus simple. La seconde partie de notre étude se concentre sur l'optimisation de l'utilisation des ressources d'un système NFV. La principale distinction est que nous pouvons appliquer le modèle à un système dynamique avec de grandes instances. De plus, nous fournissons également une méthode originale pour engendrer de fortes inégalités afin d'améliorer la résolution de la programmation linéaire (LP) dans un espace de dimension supérieur. Les résultats obtenus n'améliorent pas seulement le modèle, mais promettent aussi de pouvoir être utiliser efficacement dans d'autres modèles. Une troisième contribution de notre travail concerne le problème de routage dans NFV. En effet, une évolution importante des besoins des utilisateurs est représentée par la demande d'accès croissante aux ressources réseau, de stockage et de calcul afin de combiner dynamiquement le niveau de consommation de ressources avec leurs besoins de service. Par conséquent, nous nous intéressons au routage efficace d'une demande utilisateur à travers les noeuds qui traitent les fonctions impliquées dans une chaîne de services donnée. Nous proposons une formulation originale de ce problème basée sur la construction d'un réseau étendu. Nous formulons une solution mathématique exacte et proposons plusieurs algorithmes approximatifs tenant compte les principaux paramètres du système. Nous conclurons en soulignant les contributions principales de notre travail et proposons quelques pistes pour des travaux futurs. / Network service providers have to cope with the growing on-demand need from end-users as well as the diversity of usage. The "softwerization" and "loudification" of the network components offer a promising solution to achieve the agility necessary to dynamically match the servcice requirements with the level of resource consumption. Cloud-based solutions promises an economy of scale and simpler management. Virtualizing the many network appliances offers the flexibility to adapt to the varying service demand. This materializes with the deployment of Network Functions Virtualization (NFV) where Virtual Network Functions (VNFs) may be chained together to create network services. This dissertation studies the resource allocation problem in an NFV system for minimizing its cost under constraints on interconnectivity among VNFs, system resources, and service requirements. The main consideration is the reduction of the overall deployment cost while efficiently utilizing the available resources. In addition, a number of other important constraints are considered such as migration and congestion. Our first goal is to increase our understanding of the performance of an NFV system with respect to network functions placement and routing. We formalize the problem in a comprehensive maner taking into account a broad set of relevant parameters. The static (OFFLINE) and dynamic (ONLINE) cases are considered. We propose and analyze three heuristic algorithms: two for handling large dimensions of the OFFLINE problem and one designed to address the ONLINE scenario. The results show that our solution outperforms the state of the art with respect to critical performance index. We also evaluate the impact of migrating a set of running demands, and propose a simple migration technique for the dynamic system. We extend this work by proposing a simpler model to improve the performance of our solution. The second part of our work focuses on minimizing the resource utilization of an NFV system. The main distinctive point is that we can apply the model to a dynamic system with large instances. Moreover, we also provide an interesting method for generating some strong inequalities to improve the Linear Programming (LP) solving in a higher dimensional space. The obtained results are not only making the model easier but also can be used efficiently in other models. A third contribution focuses specifically on the routing problem in NFV. An important evolution of the users’ needs is represented by the dynamic on-demand access to network, vstorage and compute resources. Therefore, routing efficiently a demand across nodes handling the functions involved in a given service chain constitutes the a novel problem that we address in this last section. We provide an original formulation of this problem based on the construction of an expanded network. We derive the exact mathematical formulation and propose several approximate algorithms taking into account the main system’s parameters. We conclude by deriving some interesting insights both about the algorithms and the network performance. We finally conclude with our main findings and highlight many avenues for future work.

La popularité de la grande variété de l'utilisation d'Internet entraîne une croissance significative du trafic de données dans les réseaux de télécommunications. L'efficacité de la transmission de données sera contestée en vertu du principe de la capacité actuelle du réseau et des mécanismes de contrôle de flux de données. En plus d'augmenter l'investissement financier pour étendre la capacité du réseau, améliorer les techniques existantes est plus rationnel et éconmique.Diverses recherches de pointe pour faire face aux besoins en évolution des réseaux ont vu le jour, et l'une d'elles est appelée codage de réseau. Comme une extension naturelle dans la théorie du codage, il permet le mélange de différents flux réseau sur les noeuds intermédiaires, ce qui modifie la façon d'éviter les collisions de flux de données. Il a été appliqué pour obtenir un meilleur débit, fiabilité, sécurité et robustesse dans différents environnements et applications réseau. Cette thèse porte sur l'utilisation du réseau de codage pour le multicast dans les réseaux maillés fixes et systèmes de stockage distribués. Nous avons d'abord des modèles de différentes stratégies de routage multicast dans un cadre d'optimisation, y compris de multicast à base d'arbres et de codage de réseau; nous résolvons les modèles avec des algorithmes efficaces et comparons l'avantage de codage, en termes de gain de débit de taille moyenne graphique généré aléatoirement. Basé sur l'analyse numérique obtenue à partir des expériences précédentes, nous proposons un cadre révisé de routage multicast, appelé codage de réseau stratégique, qui combine transmission muticast standard et fonctions de codage de réseau afin d'obtenir le maximum de bénéfice de codage réseau au moindre coût lorsque ces coûts dépendent à la fois sur le nombre de noeuds à exécuter un codage et le volume de trafic qui est codé. Enfin, nous étudions le problème révisé de transport qui est capable de calculer un système de routage statique entre les serveurs et les clients dans les systèmes de stockage distribués où nous appliquons le codage pour soutenir le stockage de contenu. Nous étendons l'application à un problème d'optimisation général, nommé problème de transport avec des contraintes de degré, qui peut être largement utilisé dans divers domaines industriels, y compris les télécommunications, mais n'a pas été étudié très souvent. Pour ce problème, nous obtenons quelques résultats théoriques préliminaires et nous proposons une approche de décomposition Lagrange raisonnable / The popularity of the great variety of Internet usage brings about a significant growth of the data traffic in telecommunication network. Data transmission efficiency will be challenged under the premise of current network capacity and data flow control mechanisms. In addition to increasing financial investment to expand the network capacity, improving the existing techniques are more rational and economical. Various cutting-edge researches to cope with future network requirement have emerged, and one of them is called network coding. As a natural extension in coding theory, it allows mixing different network flows on the intermediate nodes, which changes the way of avoiding collisions of data flows. It has been applied to achieve better throughput and reliability, security, and robustness in various network environments and applications. This dissertation focuses on the use of network coding for multicast in fixed mesh networks and distributed storage systems. We first model various multicast routing strategies within an optimization framework, including tree-based multicast and network coding; we solve the models with efficient algorithms, and compare the coding advantage, in terms of throughput gain in medium size randomly generated graphs. Based on the numerical analysis obtained from previous experiments, we propose a revised multicast routing framework, called strategic network coding, which combines standard multicast forwarding and network coding features in order to obtain the most benefit from network coding at lowest cost where such costs depend both on the number of nodes performing coding and the volume of traffic that is coded. Finally, we investigate a revised transportation problem which is capable of calculating a static routing scheme between servers and clients in distributed storage systems where we apply coding to support the storage of contents. We extend the application to a general optimization problem, named transportation problem with degree constraints, which can be widely used in different industrial fields, including telecommunication, but has not been studied very often. For this problem, we derive some preliminary theoretical results and propose a reasonable Lagrangian decomposition approach

Internet est constitué de milliers de systèmes autonomes (Autonomous Systems, AS) qui échangent des informations de routage grâce au protocole BGP (Border Gateway Protocol). Chaque AS attend des autres qu'il lui donne des informations de routage correctes, et leur accorde donc une confiance totale. Le détournement de préfixe (prefix hijacking) exploite cette confiance afin d'introduire des routes falsifiées. Les techniques qui détectent cette attaque génèrent un nombre important d'alertes, composé de faux positifs résultant d'opérations de routage courantes. Dans cette dissertation, nous cherchons à trouver la cause principale de ces alertes, de manière indubitable. A cette fin, d'une part, nous réduisons le nombre d'alertes en analysant en profondeur ces réseaux, dont nous dérivons une série de structures qui reflètent les pratiques standard de routage du monde réel, et en considérant le risque associé à ces structures lors une attaque par détournement. D'autre part, nous utilisons des bases de données auxiliaires qui nous permettent de connaître la raison derrière un évènement de routage, qui n'est, en général, connue que du propriétaire du réseau. Précisément, nous regardons les préfixes à origines multiples (Multiple Origin AS, MOAS), et mettons en évidence une classification nous permettant d'éliminer 80% des alertes. Nous présentons un cas réel où un MOAS coïncide avec du spam et des sites d'arnaque en ligne. Nous étudions les préfixes non-disjoints, et présentons un prototype permettant d'éliminer 50% des alertes sub-MOAS.Nous explorons l'espace IP non assigné, cherchons des adresses IP joignables, et localisons une grande quantité de spam et des sites d'arnaques en ligne. / The Internet is composed of tens of thousands Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). Consequently, every AS implicitly trusts every other ASes to provide accurate routing information. Prefix hijacking is an attack against the inter-domain routing infrastructure that abuses mutual trust in order to propagate fallacious routes. The current detection techniques pathologically raise a large number of alerts, mostly composed of false positives resulting from benign routing practices. In this Dissertation, we seek the root cause of routing events beyond reasonable doubts. First, we reduce the global number of alerts by analyzing false positive alerts, from which we extract constructs that reflect real-world standard routing practices. We then consider the security threat associated with these constructs in a prefix hijacking scenario. Second, we use a variety of auxiliary datasets that reflect distinct facets of the networks involved in a suspicious routing event in order to closely approximate the ground-truth, which is traditionally only known by the network owner. Specifically, we investigate Multiple Origin AS (MOAS) prefixes, and introduce a classification that we use to discard up to 80% of false positive. Then we show a real-world case where a MOAS coincided with spam and web scam traffic. We look at prefix overlaps, clarify their global use, and present a prototype that discards around 50% of false positive sub-MOAS alerts. Finally, we explore the IP blackspace, study the routing-level characteristics of those networks, find live IP addresses, and uncover a large amount of spam and scam activities.

Durant ces dernières années, de nombreux travaux de recherches ont été menés dans le domaine des réseaux multi-sauts sans fil à contraintes (MWNs: Multihop Wireless Networks). Grâce à l'évolution de la technologie des systèmes mico-electro-méchaniques (MEMS) et, depuis peu, les nanotechnologies, les MWNs sont une solution de choix pour une variété de problèmes. Le principal avantage de ces réseaux est leur faible coût de production qui permet de développer des applications ayant un unique cycle de vie. Cependant, si le coût de fabrication des nœuds constituant ce type de réseaux est assez faible, ces nœuds sont aussi limités en capacité en termes de: rayon de transmission radio, bande passante, puissance de calcul, mémoire, énergie, etc. Ainsi, les applications qui visent l'utilisation des MWNs doivent être conçues avec une grande précaution, et plus spécialement la conception de la fonction de routage, vu que les communications radio constituent la tâche la plus consommatrice d'énergie.Le but de cette thèse est d'analyser les différents défis et contraintes qui régissent la conception d'applications utilisant les MWNs. Ces contraintes se répartissent tout le long de la pile protocolaire. On trouve au niveau application des contraintes comme: la qualité de service, la tolérance aux pannes, le modèle de livraison de données au niveau application, etc. Au niveau réseau, on peut citer les problèmes de la dynamicité de la topologie réseau, la présence de trous, la mobilité, etc. Nos contributions dans cette thèse sont centrées sur l'optimisation de la fonction de routage en considérant les besoins de l'application et les contraintes du réseau. Premièrement, nous avons proposé un protocole de routage multi-chemin "en ligne" pour les applications orientées QoS utilisant des réseaux de capteurs multimédia. Ce protocole repose sur la construction de multiples chemins durant la transmission des paquets vers leur destination, c'est-à-dire sans découverte et construction des routes préalables. En permettant des transmissions parallèles, ce protocole améliore la transmission de bout-en-bout en maximisant la bande passante du chemin agrégé et en minimisant les délais. Ainsi, il permet de répondre aux exigences des applications orientées QoS.Deuxièmement, nous avons traité le problème du routage dans les réseaux mobiles tolérants aux délais. Nous avons commencé par étudier la connectivité intermittente entre les différents et nous avons extrait un modèle pour les contacts dans le but pouvoir prédire les future contacts entre les nœuds. En se basant sur ce modèle, nous avons proposé un protocole de routage, qui met à profit la position géographique des nœuds, leurs trajectoires, et la prédiction des futurs contacts dans le but d'améliorer les décisions de routage. Le protocole proposé permet la réduction des délais de bout-en-bout tout en utilisant d'une manière efficace les ressources limitées des nœuds que ce soit en termes de mémoire (pour le stockage des messages dans les files d'attentes) ou la puissance de calcul (pour l'exécution de l'algorithme de prédiction).Finalement, nous avons proposé un mécanisme de contrôle de la topologie avec un algorithme de routage des paquets pour les applications orientés évènement et qui utilisent des réseaux de capteurs sans fil statiques. Le contrôle de la topologie est réalisé à travers l'utilisation d'un algorithme distribué pour l'ordonnancement du cycle de service (sleep/awake). Les paramètres de l'algorithme proposé peuvent être réglés et ajustés en fonction de la taille du voisinage actif désiré (le nombre moyen de voisin actifs pour chaque nœud). Le mécanisme proposé assure un compromis entre le délai pour la notification d'un événement et la consommation d'énergie globale dans le réseau. / Great research efforts have been carried out in the field of challenged multihop wireless networks (MWNs). Thanks to the evolution of the Micro-Electro-Mechanical Systems (MEMS) technology and nanotechnologies, multihop wireless networks have been the solution of choice for a plethora of problems. The main advantage of these networks is their low manufacturing cost that permits one-time application lifecycle. However, if nodes are low-costly to produce, they are also less capable in terms of radio range, bandwidth, processing power, memory, energy, etc. Thus, applications need to be carefully designed and especially the routing task because radio communication is the most energy-consuming functionality and energy is the main issue for challenged multihop wireless networks.The aim of this thesis is to analyse the different challenges that govern the design of challenged multihop wireless networks such as applications challenges in terms of quality of service (QoS), fault-tolerance, data delivery model, etc., but also networking challenges in terms of dynamic network topology, topology voids, etc. Our contributions in this thesis focus on the optimization of routing under different application requirements and network constraints. First, we propose an online multipath routing protocol for QoS-based applications using wireless multimedia sensor networks. The proposed protocol relies on the construction of multiple paths while transmitting data packets to their destination, i.e. without prior topology discovery and path establishment. This protocol achieves parallel transmissions and enhances the end-to-end transmission by maximizing path bandwidth and minimizing the delays, and thus meets the requirements of QoS-based applications. Second, we tackle the problem of routing in mobile delay-tolerant networks by studying the intermittent connectivity of nodes and deriving a contact model in order to forecast future nodes' contacts. Based upon this contact model, we propose a routing protocol that makes use of nodes' locations, nodes' trajectories, and inter-node contact prediction in order to perform forwarding decisions. The proposed routing protocol achieves low end-to-end delays while using efficiently constrained nodes' resources in terms of memory (packet queue occupancy) and processing power (forecasting algorithm). Finally, we present a topology control mechanism along a packet forwarding algorithm for event-driven applications using stationary wireless sensor networks. Topology control is achieved by using a distributed duty-cycle scheduling algorithm. Algorithm parameters can be tuned according to the desired node's awake neighbourhood size. The proposed topology control mechanism ensures trade-off between event-reporting delay and energy consumption.

Le développement économique d'une région urbaine est lié à son accessibilité. Le rôle des taxis est reconnu mondialement mais c'est un moyen très coûteux, pas abordable quotidiennement par tous. Pour abaisser les coûts, il faudrait faire partager le service par plusieurs utilisateurs tout en préservant ses qualités essentielles (trajet presque direct, service porte à porte) en accroissant la productivité de ses véhicules devenus "collectifs". Cette idée a été étudiée en 1971, par P.H. Fargier et G. Cohen, considérée toujours comme révolutionnaire et prématurée par un marché strictement réglementé. Avec une révision de la réglementation, cette extension du service des taxis, si on lui donnait l'opportunité de se mettre en place, pourrait permettre aux taxis de prendre leur part du transport public en s'adressant à la majorité de la population et pas seulement à une minorité de privilégiés pouvant assumer le prix d'un transfert individuel.