The main challenge of this thesis is to cope with the growing complexity of IT systems. In a near future (mainly the next few years) this complexity will prevent new developments and system evolutions. Today the trend is reversing and the managing costs are overtaking the hardware and software costs. Moreover, the manual administration of large systems (distributed applications, sensor networks, and network equipment) is not only slow but error-prone. An emerging research field called autonomic computing tries to bring up self-managed systems. We introduce an approach that enable the description of high level autonomic management policies. These policies allow the system to ensure four fundamental properties for self-management: self-healing, self-self-configuring, self-protecting and self-optimizing. We specify autonomic management Policy Description Diagrams (PDD) and implement them in Toulouse University Network (TUNe). We validated our approach on many systems: electromagnetic simulations distributed on computer grids (grid'5000), wireless sensor networks with SunSPOTs and the computing scheduler DIET. A second part of this thesis presents a mathematical modeling for self-optimizing datacenters. We introduce a minimization problem with a criterion integrating both the electrical consumption of the datacenter networking equipment and the quality of service of the deployed applications. A heuristic takes into account the routing functions used on the network. ; La motivation principale de cette thèse est de faire face à l'accroissement de la complexité des systèmes informatiques, qui, dans un futur proche ( de l'ordre de quelques années) risque fort d'être le principal frein à leur évolution et à leur développement. Aujourd'hui la tendance s'inverse et le coût de gestion humaine dépasse le coût des infrastructures matérielles et logicielles. De plus, l'administration manuelle de grands systèmes (applications distribuées, réseaux de capteurs, équipements réseaux) est non seulement lente mais aussi sujette à de ...
RésuméPlusieurs chercheurs soutiennent qu'il n'existe aucune stratégie, méthode ou technique qui soit appropriée à toutes les situations de développement d'applications informatiques. Ils suggèrent plutǒt que le succès d'un projet requiert que l'approche choisie soit en accord avec le niveau de risque du projet. Bien que plusieurs suggestions aient été faites quant aux sources de risque d'un projet d'informatisation, il n'existe, à ce jour, aucune mesure fiable de risque. La présente étude visait donc à élaborer et à mettre au point un tel instrument. Un questionnaire, servant à mesurer un total de 33 variables, a été distribué aux chefs de projet et à des représentants des utilisateurs de 120 projets répartis dans 75 organisations québécoises. L'évaluation de la fiabilité de chaque échelle a été faite par le biais d'analyses d'alpha de Cronbach, d'analyses de corrélations et d'analyses factorielles. En plus de décrire les résultats de ces analyses, cet article présente l'instrument de mesure.AbstractSeveral researchers claim that in order to decide what methods, techniques, or strategies to use in managing a system development project, it is necessary to take into account the degree of risk inherent in the project. While the information systems literature suggests a number of risk sources, a reliable measure of this concept is not presently available. The purpose of the study reported in this paper was to develop and test such a measure of information system project risk. To accomplish this objective, a questionnaire measuring 33 variables was developed and distributed to the project leaders of 120 projects in 75 organizations in Québec. Cronbach alpha, correlation and factor analyses were performed on the data thus gathered in order to test the reliability of the developed instrument, and to further refine it. In addition to describing the results of these analyses, the article presents the instrument.
The transformation of cities into "smart cities" is one of the goals that governments have been aiming at for the last ten years. This transformation affects several aspects of the city, including eco-citizenship, sustainable governance, and smart mobility. It is on this aspect that our work focuses. Indeed, despite a certain progress in the last few years, people with reduced mobility are often forgotten when it comes to improving urban travel thanks to information and communication technologies. Among these technologies, artificial intelligence is booming and encompasses several fields. Among them, ambient intelligence aims at the design of interconnected services interacting with the real physical environment to provide services to support human activities. It is in this context that our work is placed: the study and construction of an ambient system dedicated to the assistance of people with reduced mobility in an urban environment. However, the design of such a system is constrained by several obstacles. First, we noticed that the vocabulary of the terms coming from these domains was inconstant, and that the whole scientific community is not unanimous on the definition of certain concepts. Our first contribution consists in an ontology, described in OWL, which covers all the elements and concepts necessary for the design of this type of system. Secondly, several current scientific studies underline the lack of a generic architecture model for such systems. As a result, the myriad of solutions proposed in this field suffer from strong limitations in terms of interoperability and reusability of the works. Therefore, our second contribution translates into a generic model facilitating the design of any type of ambient system dedicated to assistance. This model is based on the proposed ontology, while keeping the users at the center of the model. Finally, it has been noticed that ambient systems dedicated to assistance are deployed in an ad-hoc way, either in simulation or in real environment, with an ...
The transformation of cities into "smart cities" is one of the goals that governments have been aiming at for the last ten years. This transformation affects several aspects of the city, including eco-citizenship, sustainable governance, and smart mobility. It is on this aspect that our work focuses. Indeed, despite a certain progress in the last few years, people with reduced mobility are often forgotten when it comes to improving urban travel thanks to information and communication technologies. Among these technologies, artificial intelligence is booming and encompasses several fields. Among them, ambient intelligence aims at the design of interconnected services interacting with the real physical environment to provide services to support human activities. It is in this context that our work is placed: the study and construction of an ambient system dedicated to the assistance of people with reduced mobility in an urban environment. However, the design of such a system is constrained by several obstacles. First, we noticed that the vocabulary of the terms coming from these domains was inconstant, and that the whole scientific community is not unanimous on the definition of certain concepts. Our first contribution consists in an ontology, described in OWL, which covers all the elements and concepts necessary for the design of this type of system. Secondly, several current scientific studies underline the lack of a generic architecture model for such systems. As a result, the myriad of solutions proposed in this field suffer from strong limitations in terms of interoperability and reusability of the works. Therefore, our second contribution translates into a generic model facilitating the design of any type of ambient system dedicated to assistance. This model is based on the proposed ontology, while keeping the users at the center of the model. Finally, it has been noticed that ambient systems dedicated to assistance are deployed in an ad-hoc way, either in simulation or in real environment, with an ...
The transformation of cities into "smart cities" is one of the goals that governments have been aiming at for the last ten years. This transformation affects several aspects of the city, including eco-citizenship, sustainable governance, and smart mobility. It is on this aspect that our work focuses. Indeed, despite a certain progress in the last few years, people with reduced mobility are often forgotten when it comes to improving urban travel thanks to information and communication technologies. Among these technologies, artificial intelligence is booming and encompasses several fields. Among them, ambient intelligence aims at the design of interconnected services interacting with the real physical environment to provide services to support human activities. It is in this context that our work is placed: the study and construction of an ambient system dedicated to the assistance of people with reduced mobility in an urban environment. However, the design of such a system is constrained by several obstacles. First, we noticed that the vocabulary of the terms coming from these domains was inconstant, and that the whole scientific community is not unanimous on the definition of certain concepts. Our first contribution consists in an ontology, described in OWL, which covers all the elements and concepts necessary for the design of this type of system. Secondly, several current scientific studies underline the lack of a generic architecture model for such systems. As a result, the myriad of solutions proposed in this field suffer from strong limitations in terms of interoperability and reusability of the works. Therefore, our second contribution translates into a generic model facilitating the design of any type of ambient system dedicated to assistance. This model is based on the proposed ontology, while keeping the users at the center of the model. Finally, it has been noticed that ambient systems dedicated to assistance are deployed in an ad-hoc way, either in simulation or in real environment, with an ...
International audience ; Network topology –decentralized arrangement of various elements of a computer grid- in which each node relays data for the network, MESH technologies has been recently presented as profoundly disruptive and able to change both our telecom infrastructure, our citizenship practices and our "communicative action" (Habermas, 1981). Recently implemented on mobile devices (Mobile -WiFi- peer-to-peer communication), this technology has been prominently mentioned during global political movements (Arab spring, Occupy movements, etc.) who crystallized, in a certain way, questions related to the Internet citizen's socio-technical and political skills, to the roles of States in the defense of individual liberties, bottom-up telecommunication infrastructures and net neutrality. Disseminated widely within wireless community networks, organizations that attempt to take a grassroots approach to providing a viable alternative to municipal wireless networks for consumers; MESH technology software can be observed in different ways. This article discusses the communication aspects of this technology from a critical point of view, it analyses of the storytelling that surround it and presents an ethnography of a Detroit MESH network and its publics (USA). By observing both the speeches given on this technology and the "manières de faire" (De Certeau, 1989) in local deployment of a software able to create MESH networks, we show how this technology is once a vector for emergence of "democratic rationalization" (Feenberg, 2004) and a set of local "tactics" to a more distributed governance of the Internet, less concentrated around major operators of infrastructure. ; Topología de red (una red en la que cada nodo está conectado a todos los demás nodos de forma que es posible llevar los mensajes de un nodo a otro por distintos caminos), la topología "MESH" (de red malla) esta presentada últimamente como profundamente perturbadora y capaz de cambiar tanto nuestra infraestructura de telecomunicaciones como nuestras prácticas de ciudadanía y nuestra "acción comunicativa" (Habermas, 1981). Implementada en dispositivos móviles, se mencionó esta tecnología durante los recientes movimientos políticos (primaveras árabes, movimientos Occupy y indignados, etc.) porque representó, en ciertos modos, las cuestiones relacionadas con las habilidades socio-técnicas y políticas de los ciudadanos respecto a Internet, con los roles de los Estados en la defensa de las libertades individuales, de las infraestructuras de telecomunicaciones de abajo hacia arriba y de la neutralidad de la red. Diseminada dentro de las redes inalámbricas comunitarias, por grupos de voluntarios o instituciones que construyen redes informáticas libres, gratuitas y alternativas a las redes privadas gestionadas por los proveedores clásicos de Internet, esta tecnología de malla se puede observar de distintas maneras. Este artículo analiza las dimensiones comunicativas de esta tecnología desde un punto de vista crítico y presenta una etnografía de un caso de red MESH en Detroit. Observando tanto los discursos pronunciados sobre esta tecnología como las "manières de faire" (De Certeau, 1989) en la implementación local de un software capaz de crear redes de malla, se demuestra cómo esta tecnología participa a la existencia de una "racionalización democrática" (Feenberg, 2004) y es un conjunto de "tácticas" locales para una gobernanza más distribuida de Internet, menos concentrado por los principales operadores de la infraestructura. ; Principe de structuration d'un réseau numérique où tous les appareils connectés au réseau communiquent entre eux et se distribuent de façon dynamique et intelligente les données pour éviter les points d'engorgement ; la technologie MESH (de l'anglais « mesh », maillage, filet - protocole de routage informatique décentralisé et sans fil) est présentée depuis quelques années comme étant profondément disruptive et en mesure de modifier à la fois nos infrastructures télécoms, nos pratiques citoyennes et notre « agir communicationnel » (Habermas, 1981). Récemment implémentée sur des terminaux mobiles, cette technologie a connu une publicité particulière à la faveur de mouvements politiques mondiaux (printemps arabes, mouvements occupy) qui ont su cristalliser, dans un certain sens, des questionnements relatifs aux compétences sociotechniques et politiques des citoyens internautes, aux rôles des États dans la défense des libertés individuelles, à l'infrastructure matérielle et à la neutralité du Net. Diffusée très largement au sein des réseaux communautaires sans fils, réseaux locaux hors-sol ne reposant pas sur les infrastructures des fournisseurs d'accès ou opérateurs télécom, la technologie MESH peut être envisagée de différentes manières. Cet article se propose d'explorer les aspects communicationnels de cette technologie à partir d'une critique du « storytelling » récent dont on l'affuble et d'une ethnographie de l'implantation d'un logiciel MESH au sein de la ville de Détroit (Etats-Unis). En observant à la fois les discours que l'on porte sur cette technologie de manière globale et les « manières de faire » très locales d'un déploiement d'un logiciel capable de créer des réseaux MESH, nous montrons comment cette technologie est à la fois un vecteur relatif d'émergence de « technologies démocratiques » (Feenberg, 2004) et un ensemble de « tactiques » locales servant une stratégie plus globale qui vise à une gouvernance de l'Internet plus distribuée et moins concentrée autour de grands opérateurs d'infrastructures.
International audience ; Network topology –decentralized arrangement of various elements of a computer grid- in which each node relays data for the network, MESH technologies has been recently presented as profoundly disruptive and able to change both our telecom infrastructure, our citizenship practices and our "communicative action" (Habermas, 1981). Recently implemented on mobile devices (Mobile -WiFi- peer-to-peer communication), this technology has been prominently mentioned during global political movements (Arab spring, Occupy movements, etc.) who crystallized, in a certain way, questions related to the Internet citizen's socio-technical and political skills, to the roles of States in the defense of individual liberties, bottom-up telecommunication infrastructures and net neutrality. Disseminated widely within wireless community networks, organizations that attempt to take a grassroots approach to providing a viable alternative to municipal wireless networks for consumers; MESH technology software can be observed in different ways. This article discusses the communication aspects of this technology from a critical point of view, it analyses of the storytelling that surround it and presents an ethnography of a Detroit MESH network and its publics (USA). By observing both the speeches given on this technology and the "manières de faire" (De Certeau, 1989) in local deployment of a software able to create MESH networks, we show how this technology is once a vector for emergence of "democratic rationalization" (Feenberg, 2004) and a set of local "tactics" to a more distributed governance of the Internet, less concentrated around major operators of infrastructure. ; Topología de red (una red en la que cada nodo está conectado a todos los demás nodos de forma que es posible llevar los mensajes de un nodo a otro por distintos caminos), la topología "MESH" (de red malla) esta presentada últimamente como profundamente perturbadora y capaz de cambiar tanto nuestra infraestructura de telecomunicaciones como nuestras prácticas de ciudadanía y nuestra "acción comunicativa" (Habermas, 1981). Implementada en dispositivos móviles, se mencionó esta tecnología durante los recientes movimientos políticos (primaveras árabes, movimientos Occupy y indignados, etc.) porque representó, en ciertos modos, las cuestiones relacionadas con las habilidades socio-técnicas y políticas de los ciudadanos respecto a Internet, con los roles de los Estados en la defensa de las libertades individuales, de las infraestructuras de telecomunicaciones de abajo hacia arriba y de la neutralidad de la red. Diseminada dentro de las redes inalámbricas comunitarias, por grupos de voluntarios o instituciones que construyen redes informáticas libres, gratuitas y alternativas a las redes privadas gestionadas por los proveedores clásicos de Internet, esta tecnología de malla se puede observar de distintas maneras. Este artículo analiza las dimensiones comunicativas de esta tecnología desde un punto de vista crítico y presenta una etnografía de un caso de red MESH en Detroit. Observando tanto los discursos pronunciados sobre esta tecnología como las "manières de faire" (De Certeau, 1989) en la implementación local de un software capaz de crear redes de malla, se demuestra cómo esta tecnología participa a la existencia de una "racionalización democrática" (Feenberg, 2004) y es un conjunto de "tácticas" locales para una gobernanza más distribuida de Internet, menos concentrado por los principales operadores de la infraestructura. ; Principe de structuration d'un réseau numérique où tous les appareils connectés au réseau communiquent entre eux et se distribuent de façon dynamique et intelligente les données pour éviter les points d'engorgement ; la technologie MESH (de l'anglais « mesh », maillage, filet - protocole de routage informatique décentralisé et sans fil) est présentée depuis quelques années comme étant profondément disruptive et en mesure de modifier à la fois nos infrastructures télécoms, nos pratiques citoyennes et notre « agir communicationnel » (Habermas, 1981). Récemment implémentée sur des terminaux mobiles, cette technologie a connu une publicité particulière à la faveur de mouvements politiques mondiaux (printemps arabes, mouvements occupy) qui ont su cristalliser, dans un certain sens, des questionnements relatifs aux compétences sociotechniques et politiques des citoyens internautes, aux rôles des États dans la défense des libertés individuelles, à l'infrastructure matérielle et à la neutralité du Net. Diffusée très largement au sein des réseaux communautaires sans fils, réseaux locaux hors-sol ne reposant pas sur les infrastructures des fournisseurs d'accès ou opérateurs télécom, la technologie MESH peut être envisagée de différentes manières. Cet article se propose d'explorer les aspects communicationnels de cette technologie à partir d'une critique du « storytelling » récent dont on l'affuble et d'une ethnographie de l'implantation d'un logiciel MESH au sein de la ville de Détroit (Etats-Unis). En observant à la fois les discours que l'on porte sur cette technologie de manière globale et les « manières de faire » très locales d'un déploiement d'un logiciel capable de créer des réseaux MESH, nous montrons comment cette technologie est à la fois un vecteur relatif d'émergence de « technologies démocratiques » (Feenberg, 2004) et un ensemble de « tactiques » locales servant une stratégie plus globale qui vise à une gouvernance de l'Internet plus distribuée et moins concentrée autour de grands opérateurs d'infrastructures.
To preserve their business model, companies have long protected their innovation processes with patents. « Open source hardware » (OSH) is, on the contrary, a collaborative product development process, where design plans and manufacturing "secrets" are accessible to all. The lines between creators and consumers blur more and more, especially when, for example, digital fabrication tools such as 3D printers or laser cutters accessible via Fab Labs or Maker Spaces, enable citizens to create and test products much more easily. Starting from an isolated phenomenon, there are now 1200 Fab Labs in 100 different countries organized in a "Fab City Network", to help cities produce within forty years 50% of the resources they consume.In this context, building a drone to depollute oceans, connected beehives, or a water filter in « Open Source Hardware » (OSH) aims at creating solutions in a more rapid, efficient and inexpensive manner. Furthermore, these innovations are voluntarily kept free by law. They represent a knowledge base, a "digital common good", meaning a reserve of ideas and solutions available on the internet via numerical platforms. According to Elinor Ostrom, who received the Nobel Prize in Economics in 2009, "the challenge of the current generation is to keep the pathways to discovery open" (Hess & Ostrom, 2011). Without attaining the success of open source software initiatives, in practice, these OSH initiatives have continued to spread.But how can a sustainable economic model be developed when co-constructed innovations can be shared by all? Thus, our research questions are the following: 1) How to monetize value created through OSH? 2) How can the business model framework be extended to include value creation and sharing for all stakeholders? 3) In the context of OSH, how does a business model hold together?The OSH phenomenon is not specific to a single sector, company or territory, but is indicative of much more global transformation. To understand the conditions necessary for the survival and growth of OSH, we conducted a qualitative study on the "OSH ecosystem" that allowed us to study the community, firm and territorial ecosystems levels together.Data was collected in three successive phases. First, qualitative interviews were conducted with twenty-three initiatives from the "Open Source Hardware Observatory". These, of course, corresponded to our research criteria, that is the development of complex mechatronic or textile products labeled opened by their surrounding community. Then we conducted a case study on four actors in the automotive sector to study their reaction to OSH developed by innovation communities. The final phase consisted of running an empirical study of the actors in the OSH innovation ecosystem of the city of Barcelona, chosen for its pivotal role in the "Fab Cities" network.Our results show that these initiatives are strongly focused on democratic values aimed at putting technology at the service of humanity. While these values are a powerful vector for federating actors, success is stalled in companies that do not adhere to them. These will primarily focus on the associated risks. Finally, we identified a diversity of possible and configurable revenues to be shaped according to an organization's strategic needs: 1) external financing; 2) a combination of products and services; 3) strategic competence; 4) the model platform, and 5) the distributed enterprise. Together, they enable an OSH initiative to progressively refine its business model, grow in value, and increase its impact. ; Pour préserver leur modèle économique, les entreprises ont longtemps protégé leurs processus d'innovation par des brevets. L'« open source hardware » est, au contraire, un processus collaboratif de développement de produits, où les plans de conception et « secrets » de fabrication sont accessibles à tous. La barrière entre concepteurs et consommateurs s'estompe, grâce aux outils de fabrication digitale, comme les imprimantes 3D ou les découpeuses lasers accessibles via des Fab Labs ou des Maker Spaces permettant aux citoyens de créer et de tester des produits beaucoup plus facilement. Partant d'un phénomène isolé, il existe maintenant 1200 Fab Labs dans 100 différents pays organisés en réseau, « the Fab City Network », dont le but est d'aider les villes à produire 50% des ressources qu'elles consomment d'ici quarante ans.Dans ce contexte, construire un drone pour dépolluer les océans, une ruche connectée, ou un filtre à eau en « Open Source Hardware » (OSH) vise à créer des solutions de manière plus rapide, efficace et à moindre coût. De plus, ces innovations sont gardées volontairement libres de droit. Elles constituent un « bien commun digital », une réserve de connaissances disponible sur Internet via des plateformes numériques. Selon Elinor Ostrom, qui a reçu le prix Nobel d'économie en 2009 « le défi de la génération actuelle est de garder les voies d'accès aux connaissances ouvertes ». Sans atteindre le succès des initiatives en Open Source dans le secteur des logiciels informatiques, ces initiatives n'ont cessé de se propager.Or, comment développer un modèle économique durable avec des innovations qui ont été co-construites et sont partageables par tous ? Nos questions de recherche sont les suivantes : 1) comment rentabiliser la création de valeur produite en OSH ? ; 2) comment étendre cette création de valeur à un ensemble de parties prenantes ? 3) dans le contexte de l'OSH quels sont les facteurs d'adhésions autour de ces modèles économiques ?L'OSH ne s'agit pas d'un phénomène propre à un seul secteur, entreprise ou territoire mais une transformation beaucoup plus globale. Pour chercher à comprendre les conditions nécessaires à la survie et à la montée en puissance de ce phénomène, nous avons mené une étude qualitative multiniveaux qui nous permettait d'étudier les niveaux communautaires, d'entreprise, et d'écosystème territorial, à la fois.La collection de données s'est faite en trois étapes successives. Dans un premier temps, des entretiens qualitatifs ont été menés auprès de vingt-trois initiatives issues de « l'Observatoire de l'Open Source Hardware ». Celles-ci devaient, bien entendu, correspondre à nos critères de recherche, à savoir le développement de produits mécatroniques ou textiles complexes et étiquetés ouverts par leur communauté. Puis, nous avons mené une étude de cas sur quatre acteurs du secteur automobile pour étudier leur réaction face à l'OSH issu de communautés d'innovation. L'étape finale consistait à mener une étude empirique sur les acteurs dans l'écosystème d'innovation d'OSH de la ville de Barcelone, choisie pour son rôle pivot dans le réseau des « Fab Cities ».Nos résultats montrent que ces initiatives sont fortement axées sur des valeurs démocratiques visant à mettre la technologie au service de l'humain. Cet ensemble inhabituel de valeurs constitue un puissant vecteur pour fédérer les acteurs, alors que le succès est mitigé au sein d'entreprises qui n'y adhèrent pas et appréhendent davantage les risques. Enfin, nous avons identifié une diversité de revenus possibles et configurables selon les besoins stratégiques d'une organisation : 1) le financement externe ; 2) la combinaison de produits et de services ; 3) les compétences stratégiques de l'organisation ; 4) le modèle plateforme ; et 5) et l'entreprise distribuée. Ensemble, ils permettent à une initiative en OSH de progressivement affiner son business model, accroître sa valeur, et augmenter sa portée.
The main theme of this thesis is load-balancing in large sparse random graphs. In the computer science context, a load-balancing problem occurs when we have a set of tasks which need to be distributed across multiple resources, and to resolve the load-balancing problem one needs to specify which tasks are going to be handled by which resources. Depending on the context, tasks and resources may have different interpretations. To make things more concrete, we focus in this document on two particular applications: - a multiple-choice hashing system (often refered to as cuckoo hashing in the literature), where the goal is to efficiently assign buckets to items so that the items or any associated data can be stored to be later retrieved quickly. Tasks are here linked to items, and resources to buckets. - a content delivery network (CDN) with a multitude of servers to handle storage and service of the contents. In this context, tasks are requests for a particular content and resources are linked with the servers and the particular contents they store, and resolving the load-balancing problem means assigning servers to requests. The local constraints of which resource is suitable for a particular task as well as the initial amounts of the different available resources and the workload associated with each task can be efficiently represented as a capacitated bipartite graph. Also, in practice and in particular for the two examples mentioned, the systems considered are often of very large size, involving maybe thousands of different tasks and resources, and they tend to be quite random (either by design or due to a lack of coordination capabilities). Therefore, the context of large random graphs is particularly well-suited to the considered evaluations. As the spectrum of solutions to a particular load-balancing problem is vast, it is primordial to understand the performance of the optimal solution to the loadbalancing problem (disregarding its potential complexity) in order to assess the relative efficiency of any given candidate scheme. This optimal load-balancing performance can be derived from the size of maximum capacitated matchings in a large sparse random graph. We analyze this quantity using the cavity method -a powerful tool coming from the study of disordered systems in statistical physics-, showing in the process how to rigorously apply this method to the setups of interest for our work. Coming back to the cuckoo hashing example, we obtain the load thresholds under which cuckoo hashing succeeds with high probability in building a valid hashtable and further show that the same approach can handle other related schemes. In the distributed CDN context, the performance of load-balancing is not the end of the story, as an associated resource-placement problem naturally arises: in such a system, one can choose how to provision resources and how to pool them, i.e., how to replicate contents over the servers. Our study of capacitated matchings already yields the efficiency of static replications of contents under optimal load-balancing, and we further obtain the limits of the optimal replication when the storage capacity of servers increases. Finally, as optimal load-balancing may be too complex for many realistic distributed CDN systems, we address the issues of load-balancing performance and resource-placement optimization under a much simpler -random greedy- load-balancing scheme using mean-field large storage approximations. We also design efficient adaptive replication algorithms for this setup. ; Cette thèse porte principalement sur l'équilibrage de charge dans de grands graphes aléatoires. En informatique, un problème d'équilibrage de charge survient lorsque différentes tâches ont besoin d'accéder à un même ensemble de points de ressources. Il faut alors décider quelles ressources spécifiques seront allouées à quelles tâches. Suivant le contexte, les notions de "tâche" et de "ressource" peuvent avoir différentes interprétations. Afin de prendre des exemples concrets, on se concentrera sur deux applications en particulier: - un système de hachage à choix multiples (plus précisément, le "cuckoo hashing"). L'objectif est ici d'allouer des cellules d'un tableau à des objets, afin de pouvoir ensuite vérifier facilement la présence d'un objet et récupérer les données associées. Les tâches sont liées aux objets à stocker, et les ressources sont les cellules du tableau. - un réseau de distribution de contenu distribué, au sens où les contenus peuvent être stockés sur une multitude de petits serveurs aux capacités individuelles très limitées. Ici, les tâches sont des demandes de téléchargement (ou requêtes) pour un contenu et les ressources sont liées aux serveurs et à la façon dont leurs espaces de stockage sont utilisés. Le problème d'équilibrage de charge consiste à décider quel serveur va servir quelle requête. Les contraintes locales portant sur chaque ressource (en quelle quantité est-elle disponible et pour quelles tâches est-elle convenable?) ainsi que la charge de travail associée avec chaque tâche peuvent être représentées efficacement sur un graphe biparti, avec des contraintes de capacité sur ses sommets et ses arêtes. De plus, en pratique, les systèmes considérés sont souvent de très grande taille (avec parfois des milliers de tâches et de points de ressources différents) et relativement aléatoires (que ce soit par choix ou une conséquence de leur grande taille). Une modélisation à l'aide de grands graphes aléatoires est donc souvent pertinente. L'ensemble des solutions envisageables pour un problème d'équilibrage de charge donné étant vaste, il est primordial de commencer par déterminer des bornes sur les performances que l'on peut espérer. Ainsi, on considérera dans un premier temps une solution optimale du problème (même si elle ne serait pas réalisable avec des contraintes pratiques). Les performances d'une telle solution peuvent être obtenues en étudiant les appariements de taille maximum dans un grand graphe aléatoire, ce que l'on réalisera à l'aide de la méthode de la cavité. Cette méthode vient de l'étude des systèmes désordonnés en physique statistique, et on s'attachera ici à l'appliquer de manière rigoureuse dans le cadre que l'on considère. Dans le contexte du cuckoo hashing, les résultats obtenus permettent de calculer le seuil sur la charge du système (le nombre d'objets à insérer par rapport à la taille du tableau) en-dessous duquel on peut construire une table de hachage correcte avec grande probabilité dans un grand système, et également de traiter de manière similaire de variantes de la méthode de hachage basique qui tentent de diminuer la quantité d'aléa nécessaire au système. Au-delà du problème d'équilibrage de charge, dans le cadre des réseaux de distributions de contenu distribués, un second problème se pose: comment décider quel contenu stocker et en quelle quantité, autrement dit comment répliquer les contenus? On appelle ce second problème un problème d'allocation de ressources. A nouveau, l'étude déjà réalisée permet de quantifier l'efficacité d'une politique de réplication fixée en supposant que la politique d'équilibrage de charge fonctionne de manière optimale. Il reste cependant à optimiser la politique de réplication de contenus utilisée, ce que l'on effectue dans un régime où l'espace de stockage disponible au niveau de chaque serveur est important par rapport à la taille d'un contenu. Finalement, afin de quantifier maintenant les performances minimales atteignables en pratique, on s'intéressera aux mêmes questions lorsque la politique d'équilibrage de charge utilisée est un simple algorithme glouton. Cette étude est réalisée à l'aide d'approximations de champs moyen. On utilisera également les résultats obtenus afin de concevoir des politiques de réplication de contenus adaptatives.
