U NIVERSIT E L IBRE DE B RUXELLES FACULT E DES S CIENCES A PPLIQU E ES

Ant Colony Optimization and its Application to Adaptive Routing in Telecommunication Networks

Gianni Di Caro
Dissertation pr sent e en vue de lobtention du grade de e e Docteur en Sciences Appliqu es e
Bruxelles, September 2004

P ROMOTEUR : P ROF. M ARCO D ORIGO IRIDIA, Institut de Recherches Interdisciplinaires et de Dveloppements en Intelligence Articielle e

A NN E E ACAD E MIQUE 2003-2004

Abstract
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 scientic work, mostly in the elds 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 nds its roots in the experimental observation of a specic 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 1990s. From that moment on it has been a ourishing of new combinatorial optimization algorithms designed after the rst algorithms of Dorigos et al., and of related scientic events. In 1999 the ACO metaheuristic was dened 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 dened 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 ACOs 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 denition 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)dened 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 1999s denition, 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 identied in dynamic problems in telecommuni-

cation 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 rstly dened (but maintaining full conceptual and terminological consistency), ACO is here dened 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 ACOs 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 ACOs 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 identication 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 identied 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 trafc in wired IP networks, one is intended for quality-of-service (QoS) trafc in ATM networks, and the fourth is for best-effort trafc 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 efcacy of the ACO approach for network routing problems compared to the characteristics of more classical approaches. Moving further, we also informally dene Ant Colony Routing (ACR), a multi-agent framework explicitly integrating learning components into the ACOs design in order to dene 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.

Contents
List of Figures List of Tables List of Algorithms List of Examples List of Abbreviations 1 Introduction 1.1 Goals and scientic contributions . . . . . . . . . . . . . . . . . 1.1.1 General goals of the thesis . . . . . . . . . . . . . . . . . 1.1.2 Theoretical and practical relevance of the thesis goals . 1.1.3 General scientic contributions . . . . . . . . . . . . . . 1.2 Organization and published sources of the thesis . . . . . . . . 1.3 ACO in a nutshell: a preliminary and informal denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii xiii xv xvii xix 1 4 4 6 8 10 17

I From real ant colonies to the Ant Colony Optimization metaheuristic

2 Ant colonies, the biological roots of Ant Colony Optimization 2.1 Ants colonies can nd shortest paths . . . . . . . . . . . . . . . 2.2 Shortest paths as the result of a synergy of ingredients . . . . . 2.3 Robustness, adaptivity, and self-organization properties . . . . 2.4 Modeling ant colony behaviors using stigmergy: the ant way . 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21
23 24 27 30 31 34 37 39 43 44 46 49 51 52 54 56 61 67 72

Combinatorial optimization, construction methods, and decision processes 3.1 Combinatorial optimization problems . . . . . . . . . . . . . . . . . . . . 3.1.1 Solution components . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Characteristics of problem representations . . . . . . . . . . . . . 3.2 Construction methods for combinatorial optimization . . . . . . . . . . . 3.2.1 Strategies for component inclusion and feasibility issues . . . . . 3.2.2 Appropriate domains of application for construction methods . . 3.3 Construction processes as sequential decision processes . . . . . . . . . . 3.3.1 Optimal control and the state of a construction/decision process 3.3.2 State graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Construction graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 The general framework of Markov decision processes . . . . . . . 3.3.5 Generic non-Markov processes and the notion of phantasma . . .

viii

CONTENTS

3.4

3.5 4

Strategies for solving optimization problems . . . . . . . . . . . . . 3.4.1 General characteristics of optimization strategies . . . . . . 3.4.2 Dynamic programming and the use of state-value functions 3.4.3 Approximate value functions . . . . . . . . . . . . . . . . . . 3.4.4 The policy search approach . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75 76 80 87 88 92 95 97 98 98 99 102 107 108 110 112 112 115 115 122 126 128 128 129 134 137 140 140 147 149 151 153 154 154 156 157 158 160 166

The Ant Colony Optimization Metaheuristic (ACO) 4.1 Denition of the ACO metaheuristic . . . . . . . . . . . . . . . . . . . . . 4.1.1 Problem representation and pheromone model exploited by ants 4.1.1.1 State graph and solution feasibility . . . . . . . . . . . . 4.1.1.2 Pheromone graph and solution quality . . . . . . . . . . 4.1.2 Behavior of the ant-like agents . . . . . . . . . . . . . . . . . . . . 4.1.3 Behavior of the metaheuristic at the level of the colony . . . . . . 4.1.3.1 Scheduling of the actions . . . . . . . . . . . . . . . . . . 4.1.3.2 Pheromone management . . . . . . . . . . . . . . . . . . 4.1.3.3 Daemon actions . . . . . . . . . . . . . . . . . . . . . . . 4.2 Ant System: the rst ACO algorithm . . . . . . . . . . . . . . . . . . . . . 4.3 Discussion on general ACOs characteristics . . . . . . . . . . . . . . . . 4.3.1 Optimization by using memory and learning . . . . . . . . . . . . 4.3.2 Strategies for pheromone updating . . . . . . . . . . . . . . . . . . 4.3.3 Shortest paths and implicit/explicit solution evaluation . . . . . 4.4 Revised denitions for the pheromone model and the ant-routing table . 4.4.1 Limits of the original denition . . . . . . . . . . . . . . . . . . . . 4.4.2 New denitions to use more and better pheromone information . 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Application of ACO to combinatorial optimization problems 5.1 ACO algorithms for problems that can be solved in centralized way 5.1.1 Traveling salesman problems . . . . . . . . . . . . . . . . . . 5.1.2 Quadratic assignment problems . . . . . . . . . . . . . . . . 5.1.3 Scheduling problems . . . . . . . . . . . . . . . . . . . . . . . 5.1.4 Vehicle routing problems . . . . . . . . . . . . . . . . . . . . 5.1.5 Sequential ordering problems . . . . . . . . . . . . . . . . . . 5.1.6 Shortest common supersequence problems . . . . . . . . . . 5.1.7 Graph coloring and frequency assignment problems . . . . 5.1.8 Bin packing and multi-knapsack problems . . . . . . . . . . 5.1.9 Constraint satisfaction problems . . . . . . . . . . . . . . . . 5.2 Parallel models and implementations . . . . . . . . . . . . . . . . . 5.3 Related approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

II Application of ACO to problems of adaptive routing in telecommunication networks

6 Routing in telecommunication networks 6.1 Routing: Denition and characteristics . . . . . . . . . . 6.2 Classication of routing algorithms . . . . . . . . . . . . 6.2.1 Control architecture: centralized vs. distributed 6.2.2 Routing tables: static vs. dynamic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

169
171 172 174 175 175

CONTENTS

ix

6.3 6.4

6.5 6.6 7

6.2.3 Optimization criteria: optimal vs. shortest paths . . . . . . . . . . . . . . . 6.2.4 Load distribution: single vs. multiple paths . . . . . . . . . . . . . . . . . . Metrics for performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . Main routing paradigms: Optimal and shortest path routing . . . . . . . . . . . . 6.4.1 Optimal routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Shortest path routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.2.1 Distance-vector algorithms . . . . . . . . . . . . . . . . . . . . . . 6.4.2.2 Link-state algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.3 Collective and individual rationality in optimal and shortest path routing An historical glance at the routing on the Internet . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

177 177 181 182 182 183 184 187 190 192 194 197 200 202 205 208 208 210 210 212 213 214 219 221 221 223 224 226 228 231 232 237 238 239 242 245 254 257 258 259 261 262 263 265 266 267 268 270

ACO algorithms for adaptive routing 7.1 AntNet: trafc-adaptive multipath routing for best-effort IP networks . . . . 7.1.1 The communication network model . . . . . . . . . . . . . . . . . . . . 7.1.2 Data structures maintained at the nodes . . . . . . . . . . . . . . . . . . 7.1.3 Description of the algorithm . . . . . . . . . . . . . . . . . . . . . . . . 7.1.3.1 Proactive ant generation . . . . . . . . . . . . . . . . . . . . . 7.1.3.2 Storing information during the forward phase . . . . . . . . . 7.1.3.3 Routing decision policy adopted by forward ants . . . . . . . 7.1.3.4 Avoiding loops . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.3.5 Forward ants change into backward ants and retrace the path 7.1.3.6 Updating of routing tables and statistical trafc models . . . 7.1.3.7 Updates of all the sub-paths composing the forward path . . 7.1.3.8 A complete example and pseudo-code description . . . . . . 7.1.4 A critical issue: how to measure the relative goodness of a path? . . . 7.1.4.1 Constant reinforcements . . . . . . . . . . . . . . . . . . . . . 7.1.4.2 Adaptive reinforcements . . . . . . . . . . . . . . . . . . . . . 7.2 AntNet-FA: improving AntNet using faster ants . . . . . . . . . . . . . . . . . 7.3 Ant Colony Routing (ACR): a framework for autonomic network routing . . 7.3.1 The architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1.1 Node managers . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1.2 Active perceptions and effectors . . . . . . . . . . . . . . . . . 7.3.2 Two additional examples of Ant Colony Routing algorithms . . . . . . 7.3.2.1 AntNet+SELA: QoS routing in ATM networks . . . . . . . . . 7.3.2.2 AntHocNet: routing in mobile ad hoc networks . . . . . . . . 7.4 Related work on ant-inspired algorithms for routing . . . . . . . . . . . . . . . 7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Experimental results for ACO routing algorithms 8.1 Experimental settings . . . . . . . . . . . . . . . . . . . . . 8.1.1 Topology and physical properties of the networks 8.1.2 Trafc patterns . . . . . . . . . . . . . . . . . . . . 8.1.3 Performance metrics . . . . . . . . . . . . . . . . . 8.2 Routing algorithms used for comparison . . . . . . . . . 8.2.1 Parameter values . . . . . . . . . . . . . . . . . . . 8.3 Results for AntNet and AntNet-FA . . . . . . . . . . . . . 8.3.1 SimpleNet . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 NSFNET . . . . . . . . . . . . . . . . . . . . . . . . 8.3.3 NTTnet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CONTENTS

8.4 8.5 8.6

8.3.4 6x6Net . . . . . . . . . . . . . . . . . . . . . . . 8.3.5 Larger randomly generated networks . . . . . 8.3.6 Routing overhead . . . . . . . . . . . . . . . . . 8.3.7 Sensitivity of AntNet to the ant launching rate 8.3.8 Efcacy of adaptive path evaluation in AntNet Experimental settings and results for AntHocNet . . . Discussion of the results . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

274 274 276 277 278 278 282 287

III Conclusions
9 Conclusions and future work 9.1 Summary . . . . . . . . . . 9.2 General conclusions . . . . 9.3 Summary of contributions 9.4 Ideas for future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

289
291 291 293 297 301

Appendices A Denition of mentioned combinatorial problems B Modication methods and their relationships with construction methods 305 309

C Observable and partially observable Markov decision processes 313 C.1 Markov decision processes (MDP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 C.2 Partially observable Markov decision processes (POMDP) . . . . . . . . . . . . . . 314 D Monte Carlo statistical methods E Reinforcement learning F Classication of telecommunication networks F.1 Transmission technology . . . . . . . . . . F.2 Switching techniques . . . . . . . . . . . . F.3 Layered architectures . . . . . . . . . . . . F.4 Forwarding mechanisms . . . . . . . . . . F.5 Delivered services . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 319 321 321 322 323 325 327 328