Cette thèse propose un schéma entièrement distribué de routage résilient pour les réseaux de switches. Dans cette approche une panne est traitée localement ; ainsi les autres nœuds du réseau n’ont pas besoin de prendre des mesures spécifiques. Contrairement aux systèmes classiques de routage IP qui se base uniquement sur la destination, le routage est fait en se basant sur l’arc de l’entrée et la destination. La contrainte qui en résulte est que les deux flux à la même destination entrant dans un nœud par un arc commun doivent fusionner après cet arc. Nous montrons que sous des faibles hypothèses (en supposant que le réseau est symétrique et bi-connexes au sens des liens), il existe un schéma de routage résilient pour toutes les situations de pannes simples de liens. Nous modélisons le problème de dimensionnement par un programme linéaire en nombres entiers qui peut être résolu exactement pour des réseaux de taille modeste. Nous proposons également plusieurs heuristiques pour traiter des instances de grande taille. Notre méthode généralise les méthodes de la littérature, en particulier celles de Xi et al. et de Nelakuditi et al. qui ont proposé des approches similaires. Notre approche permet d’obtenir de meilleurs résultats sur de nombreuses instances de test. Nous avons également étudié l’existence d’un schéma de routage résilient pour situation de panne de nœud dans le réseau basée sur les switches. Nous montrons que dans le cas des pannes de plusieurs liens, la condition de connexité n’est pas suffisante. / This thesis presents a fully distributed resilient routing scheme for switch-based networks. A failure is treated locally, so other nodes in the network do not need to undertakespecial actions. In contrast to conventional IP routing schemes, each node routesthe traffic on the basis of the entering arc and of the destination. The resulting constraintis that two flows to the same destination entering in a node by a common archave to merge after this arc. We show that this is sufficient for dealing with all singlelink failure situations, assuming that the network is symmetric and two-link connected.We model the dimensioning problem with an Integer Linear Program which can besolved exactly for small networks. We also propose several heuristics for larger networks.Our method generalizes the methods of Xi et Chao and Li and of Nelakuditiet al. who have proposed similar schemes in the context of IP. Our methods are moreefficient than previous ones. We have also studied the existence of a resilient routingscheme for single node failure situation in switch-based network. We study also thecase of multi-link failure situations and show that requiring the network to be connectedafter any failure does not guarantee the existence of a resilent routing schemeas described above.

Les avancées récentes de la recherche dans le domaine de la virtualisation des réseaux ainsi que l'émergence de nouveaux acteurs, ont beaucoup motivé la recherche et le développement de nouvelles approches et techniques permettant de relever les défis de l'Internet du Futur. Cette thèse a été motivée par ces avancées et par le besoin de concevoir une architecture d'allocation de réseaux virtuels à la demande à partir d'une infrastructure physique partagée. L'objectif de la thèse était, par conséquent, de concevoir et développer des algorithmes d'optimisation et des méthodes d'allocation de ressources virtuelles pour composer et créer des réseaux virtuels selon les besoins des utilisateurs et les conditions du réseau physique partagé. Ce travail suppose l'existence d'un acteur tiers «broker», appelé fournisseur de réseau virtuel, responsable de négocier et d'allouer des ressources virtuelles, offertes comme des services par des fournisseurs d'infrastructures, et de créer et offrir des réseaux virtuels à la demande pour des utilisateurs. L'objectif de la thèse est donc de développer des mécanismes et des algorithmes de découverte (ou «matching»), de correspondance (ou «mapping») et d'instanciation de réseaux virtuels tout en optimisant l'utilisation des ressources du substrat d'une part, et en réduisant, d'autre part, le coût pour les fournisseurs. Dans une première partie, l'analyse et la comparaison de plusieurs algorithmes d'allocation de réseau virtuel proposés dans la littérature ont été menées. Les différentes phases d'allocation de réseaux virtuels comprenant le matching, le mapping et l'instanciation sont définies et explorées en considérant la présence de plusieurs fournisseurs d'infrastructures (multi-domaine). La deuxième partie de cette thèse porte sur la conception, le développement et l'évaluation des algorithmes heuristiques de découverte (matching) permettant la recherche de correspondance entre les besoins spécifiés par les requêtes de réseau virtuel et les propriétés fonctionnelles (ou statiques) des ressources disponibles du substrat physique. Des techniques de regroupement conceptuel sont utilisées pour faciliter et accélérer la découverte et le matching des ressources virtuelles. Des solutions de partitionnement exactes et heuristiques, basées sur des algorithmes de max-flow/min-cut et des techniques de programmation linéaire, sont également proposées et évaluées pour partitionner les requêtes de réseaux virtuels entre plusieurs fournisseurs d'infrastructures tout en réduisant les coûts. La troisième partie de la thèse se focalise sur la conception, le développement et l'évaluation des algorithmes de mapping heuristiques et exacts qui consistent à extraire un graphe de réseau virtuel à partir d'un graphe de substrat physique d'une manière optimale. Un algorithme de mapping heuristique et distribué, basé sur l'approche multi-agents, est développé et évalué permettant d'améliorer le passage à l'échelle et d'assurer une distribution de charge. Un autre algorithme de mapping exact est également modélisé comme étant un programme linéaire afin d'assurer une sélection optimale des ressources tout en réduisant les coûts et maximisant le taux d'acceptation des requêtes. Dans la dernière partie, des algorithmes d'allocation adaptative de réseaux virtuels sont proposés, développés et évalués pour maintenir des réseaux virtuels suite à des changements dynamiques au niveau des services demandés ou bien au niveau des infrastructures physiques. / Recent advances in computer and network virtualisation combined with the emergence of new actors and business models motivated much research and development of new approaches to face the challenges of future Internet architectures. This thesis was motivated by these advances and by the need for efficient algorithms and frameworks to allocate virtual resources and create on demand virtual networks over shared physical infrastructures. The objective of the thesis has consequently been to conceive and develop provisioning algorithms and methods to set up and maintain virtual networks according to user needs and networking conditions. The work assumes the existence of virtual network providers acting as brokers that request virtual resources, on behalf of users, from multiple infrastructure providers. The investigation and research objective is to explore how virtual resources, offered as a service by infrastructure providers, are allocated while optimising the use of substrate resources and reducing the cost for providers. This thesis starts off with the analysis and comparison of several virtual network provisioning approaches and algorithms proposed in the literature. Provisioning phases are defined and explored including resource matching, embedding and binding. The scenario where multiple infrastructure providers are involved in the virtual network provisioning is addressed and a mathematical model of the VN provisioning problem is formulated. The second part of this thesis provides the design, implementation and evaluation of exact and heuristic matching algorithms to search, find and match virtual network requests with available substrate resources. Conceptual clustering techniques are used to facilitate finding and matching of virtual resources in the initial provisioning phases. Exact and heuristic algorithms are also proposed and evaluated to efficiently split virtual network requests over multiple infrastructure providers while reducing the matching cost. The request splitting problem is solved using both max-flow min-cut algorithms and linear programming techniques. The third part of this thesis presents the design, implementation and evaluation of exact and heuristic embedding algorithms to simultaneously assign virtual nodes and links to substrate resources. A distributed embedding algorithm, relying on a multi-agent based approach, is developed for large scale networks. An exact embedding algorithm, formulated as a mixed integer program, is also proposed and evaluated to ensure optimal node and link mapping while reducing cost and increasing the acceptance ratio of requests. Finally, this thesis presents the design and development of adaptive provisioning frameworks and algorithms to maintain virtual networks subject to dynamic changes in services demands and in physical infrastructures. Adaptive matching and embedding algorithms are designed, developed and evaluated to repair resource failures and dynamically optimize substrate networks utilisation.

La virtualisation de réseau permet de créer des réseaux logiques, dits virtuels sur un réseau physique partagé dit substrat. Pour ce faire, le problème d’allocation des ressources aux réseaux virtuels doit être résolu efficacement. Appelé VNE (Virtual Network Embedding), ce problème consiste à faire correspondre à chaque nœud virtuel un nœud substrat d’un côté, et de l’autre, à tout lien virtuel un ou plusieurs chemins substrat, de manière à optimiser un objectif tout en satisfaisant un ensemble de contraintes. Les ressources de calcul des nœuds et les ressources de bande passante des liens sont souvent optimisées dans un seul réseau substrat. Dans le contexte multi-domaine où la connaissance de l’information de routage est incomplète, l’optimisation des ressources de nœuds et de liens est difficile et souvent impossible à atteindre. Par ailleurs, pour assurer la continuité de service même après une panne, le VNE doit être réalisé de manière à faire face aux pannes. Dans cette thèse, nous étudions le problème d’allocation de ressources (VNE) sous diverses exigences. Pour offrir la virtualisation dans le contexte de réseau substrat multi-domaines, nous proposons une méthode de mappage conjoint des liens inter-domaines et intra-domaines. Avec une information réduite et limitées annoncées par les domaines, notre méthode est capable de mapper simultanément les liens intra-domaines et les liens inter-domaines afin d’optimiser les ressources. De plus, pour améliorer la robustesse des réseaux virtuels, nous proposons un algorithme d’évitement des pannes qui minimise la probabilité de panne des réseaux virtuels. Des solutions exactes et heuristiques sont proposées et détaillées pour des liens à bande passante infinie ou limitée. En outre, nous combinons l’algorithme d’évitement des pannes avec la protection pour proposer un VNE robuste et résistant aux pannes. Avec cette nouvelle approche, les liens protégeables puis les liens les moins vulnérables sont prioritairement sélectionnés pour le mappage des liens. Pour déterminer les liens protégeables, nous proposons une heuristique qui utilise l’algorithme du maxflow afin de vérifier etdedéterminerlesliensprotégeablesàl’étapedumappagedesliensprimaires. Encasd’insuffisance de ressources pour protéger tous les liens primaires, notre approche sélectionne les liens réduisant la probabilité de panne. / Network virtualization allows to create logical or virtual networks on top of a shared physical or substrate network. The resource allocation problem is an important issue in network virtualization. It corresponds to a well known problem called virtual network embedding (VNE). VNE consists in mapping each virtual node to one substrate node and each virtual link to one or several substrate paths in a way that the objective is optimized and the constraints verified. The objective often corresponds to the optimization of the node computational resources and link bandwidth whereas the constraints generally include geographic location of nodes, CPU, bandwidth, etc. In the multi-domain context where the knowledge of routing information is incomplete, the optimization of node and link resources are difficult and often impossible to achieve. Moreover, to ensure service continuity even upon failure, VNE should cope with failures by selecting the best and resilient mappings. Inthisthesis,westudytheVNEresourceallocationproblemunderdifferentrequirements. To embed a virtual network on multi-domain substrate network, we propose a joint peering and intra domain link mapping method. With reduced and limited information disclosed by the domains, our downsizing algorithm maps the intra domain and peering links in the same stage so that the resource utilization is optimized. To enhance the reliability of virtual networks, we propose a failure avoidance approach that minimizes the failure probability of virtual networks. Exact and heuristic solutions are proposed and detailed for the infinite and limited bandwidth link models. Moreover, we combine the failure avoidance with the failure protection in our novel protection-level-aware survivable VNE in order to improve the reliability. With this last approach, the protectable then the less vulnerable links are first selected for link mapping. To determine the protectable links, we propose a maxflow based heuristic that checks for the existence of backup paths during the primary mapping stage. In case of insufficient backup resources, the failure probability is reduced.

Les résultats obtenus dans cette thèse portent sur le dimensionnement de réseaux virtuels de télécommunications. Dans le chapitre 1, nous présentons brièvement la technologie des réseaux étudiés. Le chapitre 2 est consacré à la modélisation des réseaux de télécommunications à l'aide de la théorie des graphes. Les chapitres et traitent du problème du positionnement de chemins virtuels qui consiste à trouver un graphe ayant certaines propriétés tel que son plongement dans un graphe donné soit de congestion minimum. Pour les arbres, nous donnons des algorithmes polynomiaux permettant de trouver une solution optimale lorsque le nombre de sauts est fixé. Dans le chapitre 5 est introduit une extension optique de ce modèle. Le chapitre 6 est consacré au réseaux hiérarchiques en anneaux. Le problème de maximisation du nombre de sommets d'une telle structure ayant un diamètre donné est résolu. Dans le chapitre 7, nous étudions un problème d'optimisation lié à la tarification d'une boucle SDH.

Cette recherche traite du devenir de l’espace urbain et de ses logiques traditionnelles, dans un contexte marqué par les technologies de l’information et de la communication (TIC). Ce sujet est abordé par le prisme des commerces ethniques situés dans trois localités, parisiennes et régionales. Le regard est focalisé sur ces lieux afin de comprendre les facteurs à l’origine de la présence, en leur sein, des TIC accessibles au public. Trois hypothèses sont proposées. Il s’agit d’abord d’expliquer ce phénomène par le message des scénographies commerciales, puis par le besoin qu’éprouvent les migrants de maintenir les liens avec leurs origines culturelles et leur famille, enfin par l’appartenance des commerçants à la communauté des migrants. La méthodologie privilégie les méthodes d’enquête qualitative relevant de l’anthropologie et de la microsociologie. L’analyse des données permet de valider les hypothèses. Elle offre également la possibilité de montrer que dans une société marquée par les technologies de l’information et de la communication l’espace ne disparait pas sous le coup de la domination d’un espace en réseaux. Au contraire, l’analyse permet de souligner d’une part que l’espace urbain, avec ses logiques traditionnelles, persistent tout en s’articulant à une logique en réseaux. D’autre part, elle fait émerger la production de diverses formes spatiales. La plus significative offre à la principale clientèle la possibilité quotidienne de conserver son ancrage aux lieux urbains, tout en étant mobile et virtuellement mobile, de sortir des termes de la fracture numérique. Cette clientèle s’en trouve intégrée à la société en réseaux, dépasse la situation de double présence au pays d’origine et à la famille s’y trouvant et connaît des situations de multiples présences. Enfin, la recherche a permis de montrer que les lieux urbains et particulièrement les commerces ethniques sont des espaces de socialisation des réseaux virtuels en les situant au même niveau que les offres et services marchands, et qu’ils sont des outils dont les migrants et leur famille située à l’étranger savent se saisir pour permettre une évolution de leurs situations quotidienne et projets. / This research deals with the future of the urban space in a context marked by the Technologies of Information and Communication (ICT). This subject is approached by the prism of the ethnic businesses situated in three localities, Parisian and regional. The outlook is focused on these places to understand why ICT are included in those spaces open to the public.Three hypotheses are suggested. First, The ICT are included in the businesses thanks to the commercial message diffused through the setting up of goods. Then, the networking of businesses can be explained by the need which the migrants have to maintain the links with their cultural origins and their family, lastly through the membership of the storekeepers in the community of the migrants.The methodology favors the methods of qualitative investigation coming from the anthropology and the micro-sociology. The empirical data allows a validation of the hypotheses. The analysis of those data underline first that, in the network society, urban places don’t disappear. Among them, the ethnic shops are areas of socialization of the virtual networks by placing them at the same level as the offers of the goods and the trade services. Then, the space produced by those businesses offers to the main clientele the possibility of preserving its anchoring in the urban places while being mobile and virtually mobile. By this last idea, this research shows that the ethnic business and ICT are articulated tools which the migrants and their family situated abroad know how to seize to allow an evolution of their daily situations and projects. This analysis gives possibility to considered migrants out terms of the digital divide, and as integrated into the networks society. This new figure of migrant has overtaken the situation of double presence in their origin country and to their family living there, to actually know situations of multiple presences in this country and to their relatives.