Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW). Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d'optimiser les transports lorsque le nombre de véhicules est limité et peu élevé. Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème. Notre modélisation prend la forme d'un problème de couverture des clients dont les variables sont des routes. Des contraintes d'exclusion mutuelle expriment la disponibilité des véhicules. Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources. Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu'une approche classique. La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l'un basé sur les arcs, l'autre sur la résolution d'un VRPTW. Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW. Nous donnons les résultats de l'algorithme sur les instances de Solomon. Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes. Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes, pour cette variante du problème. / The multi-trip vehicle routing problem with time windows (MTVRPTW) is a generalization of the vehicle routing problem with time windows (VRPTW). In the MTVRPTW, one vehicle can perform several trips during a planning period. This allows optimizing the transport when the number of vehicles is limited and small.We propose here the first exact method for solving this problem.Our model is designed as a coverage problem for customers where the variables are trips. Mutual exclusion constraints express the availability of vehicles. We use a column generation scheme in which the sub-problem is an elementary shortest path problem with resource constraints (ESPPRC). Our dynamic programming method for ESPPRC takes into account dependencies of several resources through the concept of representative label. It is thus more efficient than a conventional approach. The column generation method is included in a Branch and Price scheme with two types of branching. One is based on arc selection, and the other on solving a VRPTW. We have implemented various accelerating methods which are specific to MTVRPTW. We give the results of our algorithm on Solomon instances.Results from exact methods were available in the literature for the MTVRPTW with time limit on the trips. We proposed a new and more efficient algorithm, based on our methods, to solve this variant of the problem.

Au cours de la dernière décennie, le trafic dans les réseaux a connu une croissance explosive en double environ tous les trente trois mois. Les sources à l'origine de cette croissance proviennent de nombreuses applications à grande vitesse qui impliquent la transmission de données dans des groupes de multicast. Pour réaliser la multicast optique, les routeurs optiques peuvent avoir des répartiteurs de lumière spéciaux pour diviser des signaux lumineux et des convertisseurs de longueur d'onde pour modifier les longueurs d'onde où c'est nécessaire. Cependant, la division réduit l'énergie du signal qui nécessite alors une amplification ou une régénération qui nécessitent du matériel coûteux. Les convertisseurs de longueurs d'onde aussi ne sont pas suffisamment matures pour être largement déployés dans les technologies optiques actuelles. Par conséquent, dans les réseaux tout-optique, les unités de transformation des routeurs sont souvent hétérogènes et les algorithmes de routage doivent en tenir compte tout en parvenant à des solutions de compromis coût-performances qui satisfassent les exigences de bande passante et les contraintes optiques.Dans cette thèse, nous étudions les problème de routage multicast tout-optique (AOMR) dans les réseaux tout-optique hétérogènes. L'hétérogénéité provient principalement de l'absence / présence de séparateurs de lumière et de convertisseurs de longueur d'onde et de la répartition inégale des longueurs d'onde dans les liens du réseau. En général, les problèmes de AOMR sont NP-difficiles. L'objectif de la thèse est d'analyser et de formuler les problèmes sous différentes contraintes optiques, pour rechercher des solutions optimales ou proposer des heuristiques efficaces. Les deux contextes possibles, la demande unique ou multiple de multicast, sont examinés. Toutes les propositions présentées dans la thèse sont validées par des simulations approfondies. Les principales contributions peuvent être résumées comme il suit.1) Nous identifions les structures des routes optimales pour les problèmes de l'AOMR dans les réseaux WDM hétérogènes. Comme indiqué dans la thèse, les solutions optimales ne sont plus basées sur des arbres de lumière classiques, mais sur une structure arborescente plus générale appelée hiérarchie. Certaines formes de hiérarchie pour la multicast WDM sont des parcours optiques, des hiérarchies optiques, des hiérarchies-araignée optiques ou encore des ensembles de ces routes optiques. Les algorithmes exacts et les heuristiques proposés dans la thèse sont principalement basés sur les hiérarchies.2) Dans le cas du problème de multicast avec une seule demande dans des réseaux partiellement équipés de diviseurs de lumière, nous proposons une heuristique efficace dont les résultats font le compromis entre la consommation de longueur d'onde, le coût total, et le délai de bout-en-bout.3) Dans le même cas mais dans des réseaux non équipés de diviseurs de lumière, nous prouvons la NP-difficulté, exprimons les problèmes au moyen d'un programme linéaire (ILP) pour trouver les solutions exactes et proposons plusieurs heuristiques pour calculer de bonnes solutions.4) Pour le cas de demandes multicast multiples, nous nous concentrons sur les modèles de trafic statiques dans des réseaux partiellement équipés de diviseurs mais sans convertisseurs de longueur d'onde. Tout d'abord nous proposons une formulation ILP sur la base de hiérarchies optiques afin de rechercher la solution optimale. Ensuite, utilisant un modèle de graphe en couches, nous développons plusieurs heuristiques adaptatives pour calculer des hiérarchies optiques de solutions approximatives. Ces algorithmes adaptatifs surpassent les techniques de routage existants pour minimiser la probabilité de blocage.Dans l'ensemble, la thèse souligne que les solutions optimales pour les problèmes de l'AOMR considérés correspondent à des hiérarchies, que ce soit pour une seule demande ou des demandes multiples. / Over the past decade, network traffic levels experienced an explosive growth at about double amount in approximately every thirty months. The sources accounting for this growth come from numerous high-speed applications (e.g., video-on-demand, high-definition television) which involve the data transmission in multicast groups. To realize optical multicasting, optical routers should have light splitters to split light signals and wavelength converters to change the wavelengths wherever needed. However, the splitting reduces the energy of the output signal which in turn requires the costly power amplification or regeneration. Wavelength converters are also immature to be deployed widely in current optical technologies. Consequently, in all-optical networks, routers are often heterogeneous in their processing units, which challenges the routing. Therefore, it is crucial to design efficient multicast routing strategies at the backbone optical networks, in order to achieve cost-performance tradeoff solutions while satisfying the ever-increasing bandwidth demands and optical constraints.In this thesis, we investigate the all-optical multicast routing (AOMR) problems in heterogeneous optical networks. The heterogeneity mainly comes from the absence/presence of light splitters and wavelength converters and the uneven distribution of wavelengths in the network links. In general, AOMR problems are often NP-hard. The objective of the thesis is to analyze and formulate the problems, to search for the optimal solutions, and to propose efficient heuristics to solve the problems under different optical constraints. Both possible contexts, i.e., single-multicast request and multiple-multicast requests, are examined. All the reported results in the thesis are supported by extensive and careful simulations. The major contributions can be summarized as follows.1) We identify the optimal route structures for AOMR problems under heterogeneous mesh WDM networks. As shown in the thesis, the optimal solutions are no longer based on conventional light-trees, but a more general tree-like structure called hierarchy. Some forms of hierarchy realized for WDM multicasting are light-trails, light-hierarchies, light-spider hierarchies and a set of these light-structures. The exact and heuristic algorithms proposed in the thesis are mainly based on hierarchy. 2) For single-multicast with sparse-splitting case, we propose an efficient heuristic algorithm to produce a good tradeoff solution among wavelength consumption, channel total cost and end-to-end delay.3) For single-multicast with non-splitting case, we prove the NP-hardness, identify the optimal solution as a set of light-spider hierarchies, formulate the problems by means of Integer Linear Program (ILP) formulations to find the exact solution, and propose several cost-effective heuristic algorithms to compute the approximate solutions. 4) For the case with multiple-multicast requests, we focus on static traffic patterns under sparse-splitting without wavelength conversion case. First, an ILP formulation based on light-hierarchies is proposed to search for the optimal solution. By applying the layered graph model, we then develop several adaptive heuristic algorithms to compute light-hierarchies for approximate solutions. These adaptive algorithms outperform the existing fixed routing ones in minimizing the blocking probability. Overall, the thesis points out that the optimal solutions for heterogeneously constrained AOMR problems correspond to hierarchies, regardless of request multiplicity consideration.

Cette thèse étudie les problèmes d’optimisation bi-objectifs des communications dans les réseaux de capteurs hétérogènes du point de vue de la portée de transmission. Le premier critère considéré est nécessairement l'énergie qu’il s’agit d'économiser pour maximiser la durée de vie du réseau. Le second critère, primordial dans le cas des applications en temps réel, est le délai d'acheminement des données. Pour résoudre le problème d’optimalité de la diffusion, nous proposons une formulation en nombres entiers, un algorithme d’approximation, une méta-heuristique et une heuristique permettant de trouver ou s’approcher de l’optimal pour les objectifs considérés.Pour le cas du routage, nous proposons une approche cross-layer via un programme linéaire en nombre entiers entre les couches MAC et Liaison de données permettant de calculer l'optimal et ainsi d'avoir un point de comparaison pour les futures heuristiques ayant les mêmes objectifs. / This thesis studies the problems of bi-objective optimization of communications in heterogeneous wireless sensor networks from the point of view of the transmission range. The first criterion considered is necessarily the energy consumption that needs to be reduced in order to maximize the network lifetime. The second criterion is the data transmission delay, which is essential for real-time applications.To solve the optimality problem of the broadcast, we propose an integer linear program, an approximation algorithm, a meta-heuristic and a heuristic. All these techniques allow us to find or to approximate the optimal solutions for the considered objectives.For the routing case, we propose a cross-layer approach via an integer linear program between the MAC and Data Link layers. Our method calculates the optimal solution, which represents a point of comparison for future heuristics having the same goals.

La croissance explosive des réseaux sans fil et l’augmentation du nombre de dispositifs sans fil ont soulevé de nombreuses difficultés techniques dans la planification et l’analyse de ces réseaux. Nous utilisons la modélisation continue, utile pour la phase initiale de déploiement et l’analyse à grande échelle des études régionales du réseau. Nous étudions le problème de routage dans les réseaux ad hoc, nous définissons deux principes d’optimisation du réseau: le problème de l’utilisateur et du système. Nous montrons que les conditions d’optimalité d’un problème d’optimisation construit d’une manière appropriée coïncide avec le principe de l’optimisation de l’utilisateur. Pour fonctions de coût différentes, nous résolvons le problème de routage pour les antennes directionnelles et omnidirectionnelles. Nous trouvons également une caractérisation des voies du coût minimum par l’utilisation extensive du Théorème de Green dans le cas d’antennes directionnelles. Dans de nombreux cas, la solution se caractérise par une équation aux dérivés partielles. Nous proposons l’analyse numérique par éléments finis qui donne les limites de la variation de la solution par rapport aux données. Lorsque nous permettons la mobilité des origines et destinations, on trouve la quantité optimale de relais actif. Dans les réseaux MIMO, nous montrons que, même lorsque la chaîne offre un nombre infini de degrés de liberté, la capacité est limitée par le rapport entre la taille du réseau d’antennes, la station de base, la position des mobiles et la longueur d’onde du signal. Nous constatons également l’association optimale mobile pour différentes politiques et distributions des utilisateurs. / The growing number of wireless devices and wireless systems present many challenges on the design and operation of these networks. We focus on massively dense ad hoc networks and cellular systems. We use the continuum modeling approach, useful for the initial phase of deployment and to analyze broad-scale regional studies of the network. We study the routing problem in massively dense ad hoc networks, and similar to the work of Nash, and Wardrop, we define two principles of network optimization: user- and system-optimization. We show that the optimality conditions of an appropriately constructed optimization problem coincides with the user-optimization principle. For different cost functions, we solve the routing problem for directional and omnidirectional antennas. We also find a characterization of the minimum cost paths by extensive use of Green’s theorem in directional antennas. In many cases, the solution is characterized by a partial differential equation. We propose its numerical analysis by finite elements method which gives bounds in the variation of the solution with respect to the data. When we allow mobility of the origin and destination nodes, we find the optimal quantity of active relay nodes. In Network MIMO systems and MIMO broadcast channels, we show that, even when the channel offers an infinite number of degrees of freedom, the capacity is limited by the ratio between the size of the antenna array at the base station and the mobile terminals position and the wavelength of the signal. We also find the optimal mobile association for the user- and system-optimization problem under different policies and distributions of the users.

Le routage par clé et par contenu sont des systèmes de routage ou la destination d'un message suit un parcours entre les nœuds du réseau qui dépend seulement du contenu du message même. On peut les trouver utilisés soit dans des systèmes pair-à-pair connus comme Réseaux Overlay Structurés (Structured Overlay Networks, SON), soit dans les architecture internet de nouvelle génération, les Réseaux Centrés sur les Contenus (Content-Centric Networks, CCN). Le but de cette thèse est double. D'un côté, on explore le sujet de l'interconnexion et de la coopération des réseaux d'overlay, et on propose une architecture capable de permettre à plusieurs réseaux d'overlay hétérogènes, avec différentes topologies et différents mécanismes de routage, d'interagir, grâce à une infrastructure basée sur des nœuds passerelles. On montre, par des moyennes de simulation et déploiement dans un réseaux réel, que la solution est scalable et permet un routage quasi-exhaustif avec un nombre relativement bas des nœuds passerelle bien connectés. De plus, on présente deux exemples d'applications qui pourront bénéficier de cette architecture. Dans une deuxième partie, on rentre plutôt dans les possibilités offertes par le routage basé sur les contenus hors sa "zone de confort": d'abord, on analyse les améliorations qu'un réseau d'overlay structuré peut porter à un système de diffusion vidéo pair-à-pair, en termes de qualité du vidéo et de perte des paquets pendant la transmission. Après, on examine un système entièrement centré sur le routage basé sur les contenus, en développant une solution de diffusion vidéo en temps réel dans un réseau CCN. / Key-based and content-based routing are a class of routing techniques where the destination and routing path for a message depends solely on the content of the message itself. This kind of routing has been implemented in certain peer-to-peer systems, known as Structured Overlay Networks (SON), or in the Next Generation Internet architectures, under the name of Content-Centric Networks (CCN). The scope of this thesis is twofold: on the one side, we explore the topic of the interconnection and cooperation of different structured overlays, and propose architecture capable of allowing several heterogeneous overlay networks, with different topologies and different routing schemes, to interact, thanks to a lightweight infrastructure consisting of co-located nodes. Through the use of simulations and real-world deployment, we show how this solution is scalable and how it facilitates quasi-exhaustive routing, with even a relatively low number of well-connected co-located nodes. To address the problem of scaling network design to millions of nodes, we propose a mathematical model capable of deriving basic performance figures for an interconnected system. Furthermore, we present two application examples that could greatly benefit from such architecture. On the other side, we investigate a little further into the capabilities of content-based routing outside of its "comfort zone": first, we analyze the improvement that a SON could bring to a peer-to-peer real-time video streaming system (P2P-TV), in terms of chunk loss and Quality of Experience. Then, we move the approach to a fully content-based domain, implementing the P2P-TV solution on top of Content-Centric Networks.

L'Internet des Objets (IdO) est généralement perçu comme l'extension de l'Internet actuel à notre monde physique. Il interconnecte un grand nombre de capteurs / actionneurs, référencés comme des objets, sur Internet. Face aux importants défis imposés par l'hétérogénéité des dispositifs et l'énorme trafic généré, la pile protocolaire actuelle TCP / IP va atteindre ses limites. Le réseau centré sur l'information (ICN) a récemment reçu beaucoup d'attention comme une nouvelle architecture Internet qui a un grand potentiel pour être adoptée dans un système IdO. Le paradigme ICN forme la future architecture Internet qui s’est contrée sur les données elles-mêmes plutôt que sur leurs emplacements dans le réseau. Il s'agit d'un passage d'un modèle de communication centrée sur l'hôte vers un système centré sur le contenu en se basant sur des noms de contenu uniques et indépendants de la localisation, la mise en cache dans le réseau et le routage basé sur les noms. Grâce à ses avantages pertinents, l'ICN peut être un framework viable pour soutenir l’IdO, interconnectant des milliards d'objets contraints hétérogènes. En effet, ICN permet l'accès facile aux données et réduit à la fois le délai de récupération et la charge des requêtes sur les producteurs de données. Parmi plusieurs architectures ICN, le réseau de données nommées (NDN) est considéré comme l'architecture ICN appropriée pour les systèmes IdO. Néanmoins, de nouveaux problèmes ont apparu et s'opposent aux ambitions visées dans l'utilisation de la philosophie ICN dans les environnements IdO. En fait, nous avons identifié trois défis majeurs. Étant donné que les périphériques IdO sont habituellement limités en termes de ressources avec des limitations sévères de l'énergie, de la mémoire et de la puissance de traitement, les techniques de mise en cache en réseau doivent être optimisées. En outre, les données IdO sont transitoires et sont régulièrement mises à jour par les producteurs, ce qui impose des exigences strictes pour maintenir la cohérence des données mises en cache. Enfin, dans un scénario IdO, les objets sont souvent mobiles et nécessitent des stratégies pour maintenir leurs accessibilités. Dans cette thèse, nous proposons une stratégie de mise en cache optimale qui considère les contraintes des périphériques. Ensuite, nous présentons un nouveau mécanisme de cohérence de cache pour surveiller la validité des contenus mis en cache dans un environnement IdO. En outre, pour améliorer l'efficacité de la mise en cache, nous proposons également une politique de remplacement du cache qui vise à augmenter les performances du système et à maintenir la validité des données. Enfin, nous introduisons un nouveau routage basé sur les noms pour les réseaux NDN / IdO afin de prendre en charge la mobilité des producteurs.Nous simulons et comparons nos propositions à plusieurs propositions pertinentes sous un réseau IdO de trafic réel. Nos contributions présentent de bonnes performances du système en termes de taux de réduction du chemin parcouru par les requêtes, de taux de réduction du nombre des requêtes satisfaites par les serveur, du délai de la réponse et de perte des paquets, de plus, la stratégie de mise en cache offre un faible coût de cache et finalement la validité du contenu est considérablement améliorée grâce au mécanisme de cohérence. / The Internet of Things (IoT) is commonly perceived as the extension of the current Internet to our physical world. It interconnects an unprecedented number of sensors/actuators, referred as things, to the Internet. Facing the important challenges imposed by devices heterogeneity and the tremendous generated traffic, the current Internet protocol suite has reached its limits. The Information-Centric Networking (ICN) has recently received a lot of attention as a potential Internet architecture to be adopted in an IoT ecosystem. The ICN paradigm is shaping the foreseen future Internet architecture by focusing on the data itself rather than its hosting location. It is a shift from a host-centric! communication model to a content-centric one supporting among! others unique and location-independent content names, in-network caching and name-based routing. By leveraging the easy data access, and reducing both the retrieval delay and the load on the data producer, the ICN can be a viable framework to support the IoT, interconnecting billions of heterogeneous constrained objects. Among several ICN architectures, the Named Data Networking (NDN) is considered as a suitable ICN architecture for IoT systems. Nevertheless, new issues have emerged slowing down the ambitions besides using the ICN paradigm in IoT environments. In fact, we have identified three major challenges. Since IoT devices are usually resource-constrained with harsh limitations on energy, memory and processing power, the adopted in-network caching techniques should be optimized. Furthermore, IoT data are transient and frequently updated by the producer which imposes stringent requirements to maintain cached data freshness. Finally, in IoT scenario, devices are ! frequently mobile and IoT applications require keeping data continuity. In this thesis, we propose a caching strategy that considers devices constraints. Then, we introduce a novel cache freshness mechanism to monitor the validity of cached contents in an IoT environment. Furthermore, to improve caching efficiency, we also propose a cache replacement policy that targets to raise the system performances and maintain data freshness. Finally, we introduce a novel name-based routing for NDN/IoT networks to support the producer mobility. We simulate and compare our proposals to several relevant schemes under a real traffic IoT network. Our schemes exhibit good system performances in terms of hop reduction ratio, server hit reduction ratio, response latency and packet loss, yet it provides a low cache cost and significantly improves the content validity.

La majorité des grands opérateurs utilise la technologie MPLS pour gérer leur réseau via des protocoles de signalisation et de distributions de labels. Or, ces protocoles sont complexes à déployer, à maintenir et la résolution des pannes est souvent très difficile. L'IETF a initié la standardisation d'une architecture de routage par segments (Segment Routing) s'appuyant sur un plan de contrôle simple, léger, facile à gérer et instanciée sur MPLS ou IPv6. Cette architecture repose sur le concept de routage à la source, dans lequel l'en-tête des paquets transporte les indications du chemin à suivre pour atteindre sa destination. Adapté aux cas d'usages simples et offrant nativement une résistance aux pannes, les cas d'usages plus complexes exigent de résoudre des verrous technologiques pour lesquels nous proposons plusieurs solutions. Dans cette thèse effectuée au sein d'Orange Labs, nous nous sommes intéressés à l'instanciation de l'architecture Segment Routing sur le plan de transfert MPLS et plus particulièrement à l'ingénierie de trafic, notamment avec réservation de ressources. Nous avons proposé des solutions aux problèmes liés à la limitation matérielle des routeurs actuels ne permettant pas l'expression de tous les chemins contraints. Ce travail est divisé en deux parties : (i) la proposition d'algorithmes de calcul et d'encodage de chemins de routage par segment afin de contourner les limitations matérielles. (ii) la définition des exigences architecturales et la construction d'une preuve de concept fonctionnelle. Enfin, cette thèse propose de nouvelles pistes d'études afin de consolider les outils d'ingénierie de trafic pour le routage par segment. / Most major operators use MPLS technology to manage their network via signalling and label distribution protocols. However, these protocols are complex to deploy, maintain and troubleshooting is often very difficult. The IETF has initiated the standardization of a segment routing architecture based on a simple control plane, lightweight, easyto-manage and instantiated on MPLS or IPv6. This architecture is based on the concept of source routing, in which the packet header carries the indications of the path to follow to reach its destination. Suitable for simple use cases and natively resistant to failure, more complex use cases require the resolution of technological issues for which we offer several solutions.In this thesis carried out within Orange Labs, we were interested in the instantiation of the Segment Routing architecture on the MPLS transfer plan and more particularly in traffic engineering, particularly with resource reservation. We have proposed solutions to the problems related to the hardware limitation of current routers that do not allow the expression of all constrained paths. This work is divided into two parts : (i) the proposal of algorithms for computing and encoding segment routing paths in order to bypass hardware limitations. (ii) the definition of architectural requirements and the construction of a functional proof of concept. Finally, this thesis proposes new research issues to consolidate traffic engineering tools for segment routing.

Le but de ce travail est l'étude du problème de gestion de flot de conteneurs et de véhicules dans un réseau multimodal. Nous proposons une formulation du problème sous forme d'un modèle mathématique réaliste qui prend en considération les différents aspects liés au transport et au stockage des conteneurs et dont l'objectif est de minimiser le coût global de transport. Pour la résolution des grandes instances une approche de résolution bi-niveaux est proposée. Dans un premier niveau nous construisons un modèle agrégé plus facile à résoudre pour en extraire les décisions liées aux déplacements des trains et des barges ainsi qu'une borne duale de notre problème de base. Ces informations sont utilisées dans un deuxième niveau pour avoir des solutions de bonne qualité de notre problème par rapport aux solutions données par CPLEX en résolvant directement le modèle de base. Des résultats numériques sur des instances générées aléatoirement sont présentés et ils prouvent l'intérêt de l'approche de résolution proposée dans cette thèse. / The aim of this work is the study of the problem of managing the flow of containers and vehicles in a multimodal network. We propose a formulation of the problem under the form of a realistic mathematical model that takes into account the different aspects related to container transport and storage and whose objective is to minimize the overall cost of transport. For large-scale resolution, a two-level resolution approach is proposed. In a first level we build an aggregated model easier to solve to extract the decisions related to the movements of trains and barges as well as a dual terminal of our basic problem. This information is used in a second level to have good quality solutions of our problem compared to the solutions given by CPLEX by directly solving the basic model. Numerical results on randomly generated instances are presented and prove the value of the proposed resolution approach.

Les résultats obtenus dans cette thèse portent principalement sur l' étude des communications dans les architectures parallèles, distribuées ou réseaux d'interconnexion.<br>Dans le chapitre 1 nous présentons brièvement une rapide classification des machines parallèles. Puis nous décrivons en détails les principaux mécanismes de routage des messages existant à l'heure actuelle dans de telles machines. Nous détaillons en particulier, les nouveaux mécanismes de routage du type "wormhole". Ce chapitre contient également un bref rappel des principales notions de théorie des graphes utilisées pour la modélisation des machines parallèles à mémoire distribuée.<br>Les chapitres 2, 3 et 4 dressent une synthèse des travaux qui nous paraissent les plus significatifs sur quelques principaux problèmes de communications globales (diffusion, échange total et multidistribution) par commutation de circuits, tout au moins lorsque l'on cherche essentiellement à minimiser le nombre d'étapes des protocoles.<br>Dans le chapitre 5 nous résumons en premier lieu nos travaux sur la décomposition hamiltonienne du réseau Butterfly généralisé, puis en second lieu nous donnons notre approche au problème des larges graphes à degré et diamètre fixés.

Cette thèse est dédiée à l'étude du support des réseaux mobiles dans IPv6, la nouvelle génération du protocole qui régit les communications dans l'Internet. Les travaux traditionnels dans ce domaine se préoccupent de fournir une connectivité permanente pour les stations mobiles. En revanche, l'objet de la présente étude est de traiter séparément le cas d'un réseau tout entier qui migre dans la topologie Interne, ce qui pose un certain nombre de nouveaux problèmes. Nous étudions tout d'abord l'Etat de l'Art dans le domaine traditionnel du support de la mobilité des stations mobiles. cette étude nous permet de définir une taxonomie des propositions. En second lieu, nous définissons une nouvelle terminologie dédiée au support des réseaux mobiles, ainsi que leurs caractéristiques et les problèmes spécifiques causé par leur mobilité. Parmi un ensemble d'approches envisagées, nous nous consacrons tout particulièrement à l'usage de Mobile IPv6, le standard de l'IETF pour le support des stations mobiles. Dans un premier temps, nous proposons un certain nombre d'extensions nécessaires à ce protocole. Pour le long terme, nous proposons de réduire le coût des messages de contrôle induit par ce protocole au moyen de deux techniques multipoint. La première, dite traditionnelle, établit un arbre de distribution entre le réseau mobile et ses correspondants. La deuxième enregistre directement la liste des correspondants dans le message de contrôle. La performance de ces extensions multipoint est évaluée par simulation, et nous concluons cette dissertation par une vue d'ensemble d'une nouvelle architecture de gestion de la mobilité rassemblant diverses techniques, dont nos extensions multipoint.