De nos jours, les systèmes distribués doivent répondre de plus en plus à de nouvelles exigences de qualité de service et à l’émergence de nouvelles applications comme le calcul sur la grille ; ce qui généralement se traduit par des impératifs de dynamicité et de mobilité. Si des solutions satisfaisantes existent pour des environnements distribués statiques, elles sont inadaptées dans le cas où le système devient dynamique (mobilité, évolution, modification de composants). En effet, la conception d’algorithmes distribués est traditionnellement fondée sur l’hypothèse d’un réseau dont la topologie est statique. Notre objectif dans cette thèse est de définir et d’étudier un modèle à base d’agents mobiles pour l’implémentation et l’exécution d’algorithmes distribués codés par des calculs locaux.Ce modèle doit tenir en compte des pannes qui peuvent altérer le fonctionnement du système distribué. Il doit aussi améliorer les performances vis-à-vis des modèles classiques (à envoi de messages) / Today, distributed systems must satisfy increasinglynew requirements for quality of service and the emergence ofnew applications such as Grid Computing, whichgenerally results in requirements of dynamicity andmobility. If satisfactory solutions exist forstatic distributed environments, they are inadequate in the casewhere the system becomes dynamic (mobility, evolution,components change). Indeed, the design of distributed algorithms istraditionally based on the assumption of a network whosetopology is static. Our goal, in this thesis, is to defineand study a model based on mobile agents to implementand execute distributed algorithms encoded by local computations.This model must take into account failures that can alter thethe distributed system operation. It should also improveperformance vis-à-vis the classical models (message passing systems)

Récemment, l’informatique distribuée a connu une grande évolution en raison de l’utilisation du paradigme des agents mobiles, doté d’innovantes capacités, au lieu du système client-serveur où les applications sont liées à des nœuds particuliers dans les réseaux. Ayant capturé l’intérêt des chercheurs et de l’industrie, les agents mobiles sont capables de migrer de manière autonome d’un nœud à un autre à travers le réseau, en transférant de leur code et leurs données, ce qui leur permet d’effectuer efficacement des calculs, de recueillir des informations et d’accomplir des tâches. Cependant, en dépit de ses avantages significatifs, ce paradigme souffre encore de certaines limitations qui font obstacle à son expansion, principalement dans le domaine de la sécurité. Selon les efforts actuellement déployés pour évaluer la sécurité des agents mobiles, deux catégories de menaces sont considérées. La première catégorie concerne les attaques menées sur l’agent mobile lors de son voyage à travers des hôtes ou des entités malveillantes, tandis que la seconde catégorie traite les attaques effectuées par un agent mobile illicite afin d’affecter la plate-forme d’hébergement et de consommer ses ressources. Ainsi, il est substantiellement nécessaire de concevoir une infrastructure de sécurité complète pour les systèmes d’agents mobiles, qui comprend la méthodologie, les techniques et la validation. L’objectif de cette thèse est de proposer des approches qui fournissent cette technologie avec des fonctionnalités de sécurité, qui correspondent à sa structure globale sans compromettre ses capacités de mobilité, l’interopérabilité et l’autonomie. Notre première approche est basée sur la sérialisation XML et des primitives cryptographiques, afin d’assurer une mobilité persistante de l’agent ainsi qu’une communication sécurisée avec les plates-formes d’hébergement. Dans la seconde approche, nous avons conçu une alternative à la première approche en utilisant la sérialisation binaire et la cryptographie à base de l’identité. Notre troisième approche introduit l’aspect d’anonymat à l’agent mobile, et lui fournit un mécanisme de traçage pour détecter les intrusions le long de son voyage. La quatrième approche a été développée dans le but de restreindre l’accès aux ressources de la plate-forme de l’agent, en utilisant une politique de contrôle d’accès bien définie à base la cryptographie à seuil. A ce stade, on s’est intéressé à expérimenter l’utilité des agents mobiles avec des fonctionnalités de sécurité, dans la préservation de la sécurité des autres technologies, telles que le Cloud Computing. Ainsi, nous avons proposé une architecture innovante du Cloud, en utilisant des agents mobiles dotés de traces cryptographiques pour la détection d’intrusion et d’un protocole de révocation à base de seuil de confiance pour la prévention. / Recently, the distributed computing has witnessed a great evolution due to the use of mobile agent paradigm, endowed with innovative capabilities, instead of the client-server system where the applications are bound to particular nodes in networks. Having captured the interest of researchers and industry, the mobile agents areable to autonomously migrate from one node to another across the network, transferring their code and data, which allows them to efficiently perform computations, gather information and accomplish tasks. However, despite its significant benefits, this paradigm still suffering from some limitations that obstruct its expansion, primarily in the area of security. According to the current efforts to investigate the security of mobile agents, two categories of threats are considered. The first one concerns the attacks carried out on the mobile agent during its travel or stay by malicious hosts or entities, while the second one deals the attacks performed by a malicious mobile agent in order to affect the hosting platform and consume its resources. Thus, it is substantially needed to conceive a complete security infrastructure for mobile agent systems, which includes methodology, techniques and validation. The aim of this thesis is to propose approaches which provide this technology with security features, that meet with its overall structure without compromising its mobility, interoperbility and autonomy capabilities. Our first approach was based on XML serialization and cryptographic primitives, in order to ensure a persistent mobility of agent as well as a secure communication with hosting platforms. In the second approach, we have conceived an alternative to the first approach using binary serialization and Identity-based cryptography. Our third approach was proposed to introduce anonymity aspect to the mobile agent, and provide him with a tracing mechanism to detect intrusions along its trip. The fourth approach was developed in order to restrict the access to the resources of the agent platform, using a well-defined access control policy based on threshold cryptography. At this stage, we find it interesting to experiment the utility of mobile agents with security features in preserving the security of other technologies such as cloud computing. Thus, we have developed an innovative cloud architecture using mobile agents endowed with cryptographic traces for intrusion detection and a revocation protocol based on trust threshold for prevention.

Pour bien fonctionner, une application répartie nécessite de communiquer<br />et d'échanger des informations entre ces différentes entités. Les agents<br />mobiles apparaissent dans ce contexte comme une solution prometteuse<br />permettant la construction d'applications flexibles, adaptables aux<br />contraintes de l'application et de l'environnement d'exécution. Dans<br />cette thèse, la mobilité est étudiée sous deux angles. D'une part,<br />l'envoi du code sur le serveur permet d'adapter les services distants<br />aux exigences du client ce qui permet la réduction du trafic réseau.<br />D'autre part, une machine surchargée peut déléguer l'exécution de<br />certaines de ces tâches à une autre machine ce qui permet de gagner au<br />niveau du temps d'exécution. Une architecture basée sur la technologie<br />d'agents mobiles est proposée. Elle permet l'équilibrage de charge dans<br />une application répartie. L'architecture proposée est décentralisée et<br />l'équilibrage de charge se fait d'une façon dynamique. Un agent mobile<br />collecteur est utilisé afin de construire une vision globale du système.<br />Pour la réduction du trafic, nous proposons la communication par un<br />agent intelligent hybride. L'agent utilise ainsi deux modes,<br />client/serveur ou migration (échange locale), pour sa communication. Le<br />processus décisionnel de Markov est utilisé pour trouver la politique<br />optimale du déplacement de l'agent. Un travail d'expérimentation sur des<br />problèmes concrets permet de valider les algorithmes proposés.

Le déploiement de logiciels répartis dans des environnements à grande échelle et ouverts (tels les systèmes ubiquitaires, les systèmes mobiles et les systèmes P2P) est une problématique actuelle ouverte. Ces environnements sont distribués, hétérogènes et peuvent être de nature instable (dotés d'une topologie dynamique du réseau). Le déploiement dans ces environnements met en jeu un très grand nombre de machines, de liens réseau ainsi qu'un ensemble de contraintes de déploiement. Quelques solutions de déploiement existent aujourd'hui, mais ne sont exploitables que dans le cadre d'architectures figées et fiables. Dans la plupart des solutions, une personne en charge du déploiement doit décrire plus ou moins manuellement la topologie. En outre, la majorité de ces outils ne prennent pas en compte les problèmes dûs à la variabilité de la qualité de service du réseau, aux pannes des hôtes, aux défaillances des liens du réseau ou encore aux changements dynamiques de topologie, qui caractérisent les environnements ouverts. Dans ce mémoire, nous présentons les motivations de la réalisation d'une infrastructure de déploiement logiciel autonomique et les exigences sous-jacentes d'une telle plate-forme. Nous présentons un état de l'art du déploiement logiciel que nous analysons au regard du contexte visé. Ensuite, nous présentons notre contribution pour le déploiement autonomique. Notre proposition s'appuie sur une combinaison de technologies (composants logiciels, agents mobiles adaptables, intergiciel, langage dédié). Nous proposons j-ASD, un intergiciel qui exploite la complémentarité de ces technologies pour réaliser un déploiement logiciel autonomique. Le processus de déploiement contient trois étapes : description des contraintes de déploiement, résolution, et déploiement autonomique. Pour la première étape, nous avons défini un langage dédié (DSL) comme langage de haut niveau pour exprimer des contraintes de déploiement. Pour la deuxième, nous avons conçu une infrastructure répartie pour collecter les propriétés des sites cibles, ce qui permet de résoudre les contraintes de déploiement. Pour la troisième étape, nous proposons un intergiciel à base d'agents mobiles pour la réalisation et la supervision du déploiement autonomique. Enfin, nous donnons les éléments de conception du prototype que nous avons implémenté, ainsi que les résultats de certaines expérimentations pour montrer la validité de notre approche

Le développement rapide de l’informatique mobile a donné lieu à l’apparition et à la popularisation de téléphones mobiles dits intelligents ou smart phones (ex.: iPhone, HTC, etc.) dont le nombre et les performances sans cesse croissantes en font de potentielles plateformes alternatives aux ordinateurs de bureau. Cette avancée technologique a contribué à l’émergence d’une nouvelle catégorie d’acteurs du monde des affaires n’ayant pas de bureau fixe, travaillant directement sur le terrain dans divers endroits (à la maison, en voiture, en avion, chez le client, à l’hôtel, chez le fournisseur, etc.) à l’aide d’équipements mobiles ou nomades, et se déplaçant partout où les affaires l’exigent pour assurer la compétitivité de leurs organisations: ce sont les travailleurs mobiles parmi lesquels on retrouve un grand nombre de décideurs. Étant donné ce monde des affaires de plus en plus compétitif où les gens d’affaires sont de plus en plus mobiles et confrontés à la nécessité de prendre des décisions de plus en plus rapides et efficaces basées sur des analyses pertinentes, l’aide à la prise de décision en mobilité s’avère indispensable. Pour leur apporter une telle aide, la présente thèse de doctorat propose d'aller au-delà du simple accès à distance à une plateforme d’intelligence d’affaire géo-spatiale ou non géo-spatiale (GeoBI/BI) comme le proposent les solutions actuelles. Elle propose de prendre également en considération la localisation et le contexte de travail du décideur/analyste mobile dans l’aide à la décision, et d’enrichir sémantiquement les données d’affaire. Afin de proposer une telle solution de GeoBI mobile sémantiquement augmentée et sensible au contexte mobile du décideur, la présente thèse s’est attelée d’une part à identifier, modéliser et enrichir les informations contextuelles pertinentes pour supporter un raisonnement GeoBI basé sur le contexte, et s’est évertuée d’autre part à proposer une solution d’augmentation sémantique des données d’affaire GeoBI qui permettrait de mettre en exergue les [cor]relations sémantiques pouvant exister entre les données. Un prototype mettant en œuvre une application mobile sensible au contexte et une architecture orientée services web a été développé et testé comme preuve de concept. Les tests ont montré que celui-ci permettait par exemple de soumettre et de visualiser le resultat de requêtes contextuelles du type : « dans un rayon de 5 km autour de ma position actuelle, quelles sont les compagnies partenaires ayant des relations de concurrence avec nos actionnaires et dont le chiffre d’affaire des deux années précédentes dépasse chacune le million ; les relations de partenariat/actionnariat pouvant être transitives, symétriques ou avoir la même sémantique ? » / The rapid development of mobile computing has enabled the emergence and popularization of mobile devices whose increasing number and computing capabilities position them as potential alternative platforms to desktop computers. This technological progress has contributed to the emergence of a new category of business actors having no permanent workplaces, spending very short time in their offices, working directly on the field in various locations (home, car, plane, with the client at the hotel at the supplier, etc.) by using mobile and nomadic devices, and moving to places where business requires them: these are mobile workers including a large number of decision makers. Given this increasingly competitive business world where decision makers are increasingly mobile and are facing the need to take faster and suitable decisions based on relevant analysis, these mobile business people deserve to be supported with appropriate mobile decision support systems (DSS). To give an improved support to these mobile business professionals, this PhD thesis proposes to go further than just allowing a simple remote access to a Geospatial or non-geospatial Business Intelligence (GeoBI/BI) platform as do current solutions. It also proposes to take into account the location and the context of mobile professionals, and to enrich semantically BI data. To propose such a semantically augmented and context-based mobile GeoBI solution, the present thesis has endeavored on the one hand, to identify, model and enrich contextual information that is relevant to support GeoBI context-based reasoning. On the other hand, it has strived to provide a solution that semantically enriches business data in order to help decision makers discover semantic [cor]relations which might exist between the data. A prototype implementing a context-aware mobile application and a services-oriented architecture has been developed and tested as a proof of concept. These tests has shown among other things, that the prototype was able to answer and visualize the result of contextual queries such as: “Within 5 km around my current position, what are partnering companies that are competing with our owners; with the possibility of partnership/ownership relationships to be transitive, symmetric, or have the same semantics?”

Le déploiement de logiciels répartis dans des environnements à grande échelle et ouverts (tels les systèmes ubiquitaires, les systèmes mobiles et les systèmes P2P) est une problématique actuelle ouverte. Ces environnements sont distribués, hétérogènes et peuvent être de nature instable (dotés d’une topologie dynamique du réseau). Le déploiement dans ces environnements met en jeu un très grand nombre de machines, de liens réseau ainsi qu’un ensemble de contraintes de déploiement. Quelques solutions de déploiement existent aujourd’hui, mais ne sont exploitables que dans le cadre d’architectures figées et fiables. Dans la plupart des solutions, une personne en charge du déploiement doit décrire plus ou moins manuellement la topologie. En outre, la majorité de ces outils ne prennent pas en compte les problèmes dûs à la variabilité de la qualité de service du réseau, aux pannes des hôtes, aux défaillances des liens du réseau ou encore aux changements dynamiques de topologie, qui caractérisent les environnements ouverts. Dans ce mémoire, nous présentons les motivations de la réalisation d'une infrastructure de déploiement logiciel autonomique et les exigences sous-jacentes d'une telle plate-forme. Nous présentons un état de l’art du déploiement logiciel que nous analysons au regard du contexte visé. Ensuite, nous présentons notre contribution pour le déploiement autonomique. Notre proposition s'appuie sur une combinaison de technologies (composants logiciels, agents mobiles adaptables, intergiciel, langage dédié). Nous proposons j-ASD, un intergiciel qui exploite la complémentarité de ces technologies pour réaliser un déploiement logiciel autonomique. Le processus de déploiement contient trois étapes : description des contraintes de déploiement, résolution, et déploiement autonomique. Pour la première étape, nous avons défini un langage dédié (DSL) comme langage de haut niveau pour exprimer des contraintes de déploiement. Pour la deuxième, nous avons conçu une infrastructure répartie pour collecter les propriétés des sites cibles, ce qui permet de résoudre les contraintes de déploiement. Pour la troisième étape, nous proposons un intergiciel à base d’agents mobiles pour la réalisation et la supervision du déploiement autonomique. Enfin, nous donnons les éléments de conception du prototype que nous avons implémenté, ainsi que les résultats de certaines expérimentations pour montrer la validité de notre approche / Software deployment in large-scale and open distributed systems (such as ubiquitous systems, mobile systems and P2P systems) is still an open issue. These environments are distributed, heterogeneous and can be naturally unstable (fitted with a dynamic network topology). Deployment in such environments require the management of a large number of hosts, network links and deployment constraints. Existing distributed deployment solutions are usable only within static and reliable topologies of hosts, where a man in charge of the deployment has to describe more or less manually the topology. Moreover, majority of these tools do not take into account network and computer QoS variabilities, hosts crashes, network link failures and network topology changes, which characterize open and mobile environments. In this thesis, we discuss the motivations for an autonomic software deployment and the requirements underlying for such a platform. We carefully study and compare the existing work about software deployment. Then, we propose a middleware framework, designed to reduce the human cost for setting up software deployment and to deal with failure-prone and change-prone environments. We also propose an autonomic deployment process in three steps : deployment constraints description step, constraints resolution step and the autonomic deployment step. For the first step, we defined a high-level constraint-based dedicated language (DSL) as support for expressing deployment constraints. In the second step, we have designed a distributed infrastructure to collect target hosts properties used to solve deployment constraints. For the third step, we propose an agent-based system for establishing and maintaining software deployment. At last, we give an overview of our working prototype with some details on some experimental results

Ce travail appartient au domaine de la simulation numérique sur des plates-formes d'exécution distribuées hétérogènes telles que des grilles de calcul. Ce type de plate-forme se caractérise par des possibles changements de condition d'exécution et par une probabilité importante de défaillance de certains composants. Une application qui s'exécute dans un tel environnement se doit d'être adaptable à son contexte d'exécution et tolérante aux pannes. Face à la complexité croissante de la mise en place de cas de calcul sur des grilles de calcul, nous proposons une plateforme logicielle pour la résolution de cas de calcul numérique dans un environnement distribué hétérogène. Nos travaux apportent une solution qui se base sur un système d'agents mobiles, ce qui permet à une application de s'adapter au changement de son environnement d'exécution. Dans un premier temps, nous utilisons le langage pi calcul d'ordre supérieur pour spécifier une « ferme de travailleurs » capable de participer à la résolution de tout type de cas de calcul. Ensuite, nous énonçons des propriétés qui caractérisent le bon fonctionnement de ce système avec une logique temporelle TCTL. Pour cela, nous souhaitons modéliser notre système à l'aide d'automates temporisés à partir des termes définis par la spécification formelle en pi calcul. Dans ce but, nous définissons une transformation de termes écrits en pi calcul en automates temporisés. Les propriétés sont alors vérifiées avec l'outil UppAal. Pour valider ce travail de modélisation, nous avons réalisé le framework MCA (pour Mobile Computing Architecture). Celui-ci propose un ensemble d'outils facilitant la mise en place de composants sur un environnement distribué hétérogène dans le but d'effectuer la résolution de cas de calcul. La librairie avec laquelle sont développés ces composants, qu'ils soient mobiles ou non, est implantée en Java et se base les technologies Jini et JavaSpaces. Enfin, nous réalisons l'évaluation du framework MCA en procédant à la résolution de trois cas de calcul différents. Chacune de ces expériences, réalisées sur une grappe de 20 noeuds, nous permet de montrer les caractéristiques essentielles de notre framework : une simplicité de programmation, un faible surcoût en temps d'exécution sans l'activation de la tolérance aux pannes et une tolérance aux pannes efficace / This work belongs to the domain of numerical simulation on heterogeneous distributed platforms such as grids. This type of platform is characterized by possible changes in execution conditions and a significant probability of some components failure. An application running in such an environment must be adaptable to its execution context and fault tolerant. Facing the growing complexity of implementing computation cases on grid computing, we propose a software platform which solves numerical computation cases in a distributed heterogeneous environment. Our work provides a solution based on a mobile agent system, which allows an application to adapt to change in its execution environment. At first, we use the higher-order pi calculus language to specify a « farm of workers » able to take part in solving any type of computation case. Then we set the properties that characterize the system's correct execution with a temporal logic TCTL. In order to do this, we perform a temporal modeling system based on terms defined by the formal specification in pi calculus. To achieve this transformation, we define a translation of terms written in pi calculus into timed automata. The properties are verified with the UppAal tool. To validate this modeling work, we develop the MCA (for Mobile Computing Architecture) framework. It offers a set of tools which facilitate the implementation of distributed heterogeneous components in order to solve computation cases. These components, mobile or not, are developed with a library written in Java and which uses Jini and JavaSpaces technologies. Finally, our framework is evaluated through the resolution of three different computation cases. Each of these experiments, performed on a 20 node cluster allow us to highlight our framework's main characteristics : programming simplicity, low overhead in execution time without the fault tolerance activation and efficient fault tolerance

In ant societies, and, more in general, in insect societies, the activities of the individuals, as well as of the society as a whole, are not regulated by any explicit form of centralized control. On the other hand, adaptive and robust behaviors transcending the behavioral repertoire of the single individual can be easily observed at society level. These complex global behaviors are the result of self-organizing dynamics driven by local interactions and communications among a number of relatively simple individuals. The simultaneous presence of these and other fascinating and unique characteristics have made ant societies an attractive and inspiring model for building new algorithms and new multi-agent systems. In the last decade, ant societies have been taken as a reference for an ever growing body of scientific work, mostly in the fields of robotics, operations research, and telecommunications. Among the different works inspired by ant colonies, the Ant Colony Optimization metaheuristic (ACO) is probably the most successful and popular one. The ACO metaheuristic is a multi-agent framework for combinatorial optimization whose main components are: a set of ant-like agents, the use of memory and of stochastic decisions, and strategies of collective and distributed learning. It finds its roots in the experimental observation of a specific foraging behavior of some ant colonies that, under appropriate conditions, are able to select the shortest path among few possible paths connecting their nest to a food site. The pheromone, a volatile chemical substance laid on the ground by the ants while walking and affecting in turn their moving decisions according to its local intensity, is the mediator of this behavior. All the elements playing an essential role in the ant colony foraging behavior were understood, thoroughly reverse-engineered and put to work to solve problems of combinatorial optimization by Marco Dorigo and his co-workers at the beginning of the 1990's. From that moment on it has been a flourishing of new combinatorial optimization algorithms designed after the first algorithms of Dorigo's et al., and of related scientific events. In 1999 the ACO metaheuristic was defined by Dorigo, Di Caro and Gambardella with the purpose of providing a common framework for describing and analyzing all these algorithms inspired by the same ant colony behavior and by the same common process of reverse-engineering of this behavior. Therefore, the ACO metaheuristic was defined a posteriori, as the result of a synthesis effort effectuated on the study of the characteristics of all these ant-inspired algorithms and on the abstraction of their common traits. The ACO's synthesis was also motivated by the usually good performance shown by the algorithms (e.g., for several important combinatorial problems like the quadratic assignment, vehicle routing and job shop scheduling, ACO implementations have outperformed state-of-the-art algorithms). The definition and study of the ACO metaheuristic is one of the two fundamental goals of the thesis. The other one, strictly related to this former one, consists in the design, implementation, and testing of ACO instances for problems of adaptive routing in telecommunication networks. This thesis is an in-depth journey through the ACO metaheuristic, during which we have (re)defined ACO and tried to get a clear understanding of its potentialities, limits, and relationships with other frameworks and with its biological background. The thesis takes into account all the developments that have followed the original 1999's definition, and provides a formal and comprehensive systematization of the subject, as well as an up-to-date and quite comprehensive review of current applications. We have also identified in dynamic problems in telecommunication networks the most appropriate domain of application for the ACO ideas. According to this understanding, in the most applicative part of the thesis we have focused on problems of adaptive routing in networks and we have developed and tested four new algorithms. Adopting an original point of view with respect to the way ACO was firstly defined (but maintaining full conceptual and terminological consistency), ACO is here defined and mainly discussed in the terms of sequential decision processes and Monte Carlo sampling and learning. More precisely, ACO is characterized as a policy search strategy aimed at learning the distributed parameters (called pheromone variables in accordance with the biological metaphor) of the stochastic decision policy which is used by so-called ant agents to generate solutions. Each ant represents in practice an independent sequential decision process aimed at constructing a possibly feasible solution for the optimization problem at hand by using only information local to the decision step. Ants are repeatedly and concurrently generated in order to sample the solution set according to the current policy. The outcomes of the generated solutions are used to partially evaluate the current policy, spot the most promising search areas, and update the policy parameters in order to possibly focus the search in those promising areas while keeping a satisfactory level of overall exploration. This way of looking at ACO has facilitated to disclose the strict relationships between ACO and other well-known frameworks, like dynamic programming, Markov and non-Markov decision processes, and reinforcement learning. In turn, this has favored reasoning on the general properties of ACO in terms of amount of complete state information which is used by the ACO's ants to take optimized decisions and to encode in pheromone variables memory of both the decisions that belonged to the sampled solutions and their quality. The ACO's biological context of inspiration is fully acknowledged in the thesis. We report with extensive discussions on the shortest path behaviors of ant colonies and on the identification and analysis of the few nonlinear dynamics that are at the very core of self-organized behaviors in both the ants and other societal organizations. We discuss these dynamics in the general framework of stigmergic modeling, based on asynchronous environment-mediated communication protocols, and (pheromone) variables priming coordinated responses of a number of ``cheap' and concurrent agents. The second half of the thesis is devoted to the study of the application of ACO to problems of online routing in telecommunication networks. This class of problems has been identified in the thesis as the most appropriate for the application of the multi-agent, distributed, and adaptive nature of the ACO architecture. Four novel ACO algorithms for problems of adaptive routing in telecommunication networks are throughly described. The four algorithms cover a wide spectrum of possible types of network: two of them deliver best-effort traffic in wired IP networks, one is intended for quality-of-service (QoS) traffic in ATM networks, and the fourth is for best-effort traffic in mobile ad hoc networks. The two algorithms for wired IP networks have been extensively tested by simulation studies and compared to state-of-the-art algorithms for a wide set of reference scenarios. The algorithm for mobile ad hoc networks is still under development, but quite extensive results and comparisons with a popular state-of-the-art algorithm are reported. No results are reported for the algorithm for QoS, which has not been fully tested. The observed experimental performance is excellent, especially for the case of wired IP networks: our algorithms always perform comparably or much better than the state-of-the-art competitors. In the thesis we try to understand the rationale behind the brilliant performance obtained and the good level of popularity reached by our algorithms. More in general, we discuss the reasons of the general efficacy of the ACO approach for network routing problems compared to the characteristics of more classical approaches. Moving further, we also informally define Ant Colony Routing (ACR), a multi-agent framework explicitly integrating learning components into the ACO's design in order to define a general and in a sense futuristic architecture for autonomic network control. Most of the material of the thesis comes from a re-elaboration of material co-authored and published in a number of books, journal papers, conference proceedings, and technical reports. The detailed list of references is provided in the Introduction.

In ant societies, and, more in general, in insect societies, the activities of the individuals, as well as of the society as a whole, are not regulated by any explicit form of centralized control. On the other hand, adaptive and robust behaviors transcending the behavioral repertoire of the single individual can be easily observed at society level. These complex global behaviors are the result of self-organizing dynamics driven by local interactions and communications among a number of relatively simple individuals.<p><p>The simultaneous presence of these and other fascinating and unique characteristics have made ant societies an attractive and inspiring model for building new algorithms and new multi-agent systems. In the last decade, ant societies have been taken as a reference for an ever growing body of scientific work, mostly in the fields of robotics, operations research, and telecommunications.<p><p>Among the different works inspired by ant colonies, the Ant Colony Optimization metaheuristic (ACO) is probably the most successful and popular one. The ACO metaheuristic is a multi-agent framework for combinatorial optimization whose main components are: a set of ant-like agents, the use of memory and of stochastic decisions, and strategies of collective and distributed learning.<p><p>It finds its roots in the experimental observation of a specific foraging behavior of some ant colonies that, under appropriate conditions, are able to select the shortest path among few possible paths connecting their nest to a food site. The pheromone, a volatile chemical substance laid on the ground by the ants while walking and affecting in turn their moving decisions according to its local intensity, is the mediator of this behavior.<p><p>All the elements playing an essential role in the ant colony foraging behavior were understood, thoroughly reverse-engineered and put to work to solve problems of combinatorial optimization by Marco Dorigo and his co-workers at the beginning of the 1990's.<p><p>From that moment on it has been a flourishing of new combinatorial optimization algorithms designed after the first algorithms of Dorigo's et al. and of related scientific events.<p><p>In 1999 the ACO metaheuristic was defined by Dorigo, Di Caro and Gambardella with the purpose of providing a common framework for describing and analyzing all these algorithms inspired by the same ant colony behavior and by the same common process of reverse-engineering of this behavior. Therefore, the ACO metaheuristic was defined a posteriori, as the result of a synthesis effort effectuated on the study of the characteristics of all these ant-inspired algorithms and on the abstraction of their common traits.<p><p>The ACO's synthesis was also motivated by the usually good performance shown by the algorithms (e.g. for several important combinatorial problems like the quadratic assignment, vehicle routing and job shop scheduling, ACO implementations have outperformed state-of-the-art algorithms).<p><p>The definition and study of the ACO metaheuristic is one of the two fundamental goals of the thesis. The other one, strictly related to this former one, consists in the design, implementation, and testing of ACO instances for problems of adaptive routing in telecommunication networks.<p><p>This thesis is an in-depth journey through the ACO metaheuristic, during which we have (re)defined ACO and tried to get a clear understanding of its potentialities, limits, and relationships with other frameworks and with its biological background. The thesis takes into account all the developments that have followed the original 1999's definition, and provides a formal and comprehensive systematization of the subject, as well as an up-to-date and quite comprehensive review of current applications. We have also identified in dynamic problems in telecommunication networks the most appropriate domain of application for the ACO ideas. According to this understanding, in the most applicative part of the thesis we have focused on problems of adaptive routing in networks and we have developed and tested four new algorithms.<p><p>Adopting an original point of view with respect to the way ACO was firstly defined (but maintaining full conceptual and terminological consistency), ACO is here defined and mainly discussed in the terms of sequential decision processes and Monte Carlo sampling and learning.<p><p>More precisely, ACO is characterized as a policy search strategy aimed at learning the distributed parameters (called pheromone variables in accordance with the biological metaphor) of the stochastic decision policy which is used by so-called ant agents to generate solutions. Each ant represents in practice an independent sequential decision process aimed at constructing a possibly feasible solution for the optimization problem at hand by using only information local to the decision step.<p>Ants are repeatedly and concurrently generated in order to sample the solution set according to the current policy. The outcomes of the generated solutions are used to partially evaluate the current policy, spot the most promising search areas, and update the policy parameters in order to possibly focus the search in those promising areas while keeping a satisfactory level of overall exploration.<p><p>This way of looking at ACO has facilitated to disclose the strict relationships between ACO and other well-known frameworks, like dynamic programming, Markov and non-Markov decision processes, and reinforcement learning. In turn, this has favored reasoning on the general properties of ACO in terms of amount of complete state information which is used by the ACO's ants to take optimized decisions and to encode in pheromone variables memory of both the decisions that belonged to the sampled solutions and their quality.<p><p>The ACO's biological context of inspiration is fully acknowledged in the thesis. We report with extensive discussions on the shortest path behaviors of ant colonies and on the identification and analysis of the few nonlinear dynamics that are at the very core of self-organized behaviors in both the ants and other societal organizations. We discuss these dynamics in the general framework of stigmergic modeling, based on asynchronous environment-mediated communication protocols, and (pheromone) variables priming coordinated responses of a number of ``cheap' and concurrent agents.<p><p>The second half of the thesis is devoted to the study of the application of ACO to problems of online routing in telecommunication networks. This class of problems has been identified in the thesis as the most appropriate for the application of the multi-agent, distributed, and adaptive nature of the ACO architecture.<p><p>Four novel ACO algorithms for problems of adaptive routing in telecommunication networks are throughly described. The four algorithms cover a wide spectrum of possible types of network: two of them deliver best-effort traffic in wired IP networks, one is intended for quality-of-service (QoS) traffic in ATM networks, and the fourth is for best-effort traffic in mobile ad hoc networks.<p><p>The two algorithms for wired IP networks have been extensively tested by simulation studies and compared to state-of-the-art algorithms for a wide set of reference scenarios. The algorithm for mobile ad hoc networks is still under development, but quite extensive results and comparisons with a popular state-of-the-art algorithm are reported. No results are reported for the algorithm for QoS, which has not been fully tested. The observed experimental performance is excellent, especially for the case of wired IP networks: our algorithms always perform comparably or much better than the state-of-the-art competitors.<p><p>In the thesis we try to understand the rationale behind the brilliant performance obtained and the good level of popularity reached by our algorithms. More in general, we discuss the reasons of the general efficacy of the ACO approach for network routing problems compared to the characteristics of more classical approaches. Moving further, we also informally define Ant Colony Routing (ACR), a multi-agent framework explicitly integrating learning components into the ACO's design in order to define a general and in a sense futuristic architecture for autonomic network control.<p><p>Most of the material of the thesis comes from a re-elaboration of material co-authored and published in a number of books, journal papers, conference proceedings, and technical reports. The detailed list of references is provided in the Introduction.<p><p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Ce document pr esente les travaux que j'ai r ealis es depuis ma th ese de doctorat. Outre la pr esentation de mes contributions, j'ai essay e de pr esenter des survols des domaines dans lesquels mes travaux s'inscrivent et d'indiquer les principales questions qui s'y posent. Mes travaux visent a r epondre aux nouveaux challenges algorithmiques que posent la croissance des r eseaux de telecommunications actuels ainsi que l'augmentation des donnees et du trafi c qui y circulent. Un moyen de faire face a la taille de ces probl emes est de s'aider de la structure particuliere des r eseaux. Pour cela, je m'attache a d e nir de nouvelles caract erisations des propri et es structurelles des graphes pour les calculer et les utiliser effi cacement a des fins algorithmiques. Autant que possible, je propose des algorithmes distribu es qui ne reposent que sur une connaissance locale/partielle des r eseaux. En particulier, j' etudie les jeux de poursuite - traitant de la capture d'une entit e mobile par une equipe d'autres agents - qui off rent un point de vue int eressant sur de nombreuses propri et es de graphes et, notamment, des d ecompositions de graphes. L'approche de ces jeux d'un point de vue agents mobiles permet aussi l' etude de mod eles de calcul distribu e. Le chapitre 1 est d edi e a l' etude de plusieurs variantes des jeux de gendarmes et voleur. Le chapitre 2 traite des decompositions de graphes et de leur relation avec les problemes d'encerclement dans les graphes. Le chapitre 3 se concentre sur les probl emes d'encerclement dans des contextes a la fois centralis e et distribu e. Finalement, le chapitre 4 traite de probl emes de routage dans diff erents contextes, ainsi que de mod eles de calcul distribu e.