Abstract

In this report a routing algorithm Ant Routing System (ARS) is presented. ARS is based on a general-purpose metaheuristic named Ant Colony Optimization, which is a framework for building ant-inspired algorithms.

ARS is applied as the routing algorithm in a simulated package-switched point-to-point network. It is investigated whether ARS is able to obtain an increase in throughput while avoiding package loss in a heavily loaded network, when packages are sent between two distinct routers. To this end, it is investigated how prioritizing different heuristics effect the quality of the routing performed.

It is concluded that ARS behaves differently depending on the relative priority of positive feedback, negative feedback and local heuristics, and that it is possible to adjust the parameters to achieve distribution of traffic over several paths when the network is heavily loaded, resulting in a higher throughput and lower package loss.

Keywords: Ant algorithms, Ant Colony Optimization, ACO, Ant System, routing, metaheuristics, network model, swarm intelligence.

Introduction

The goal of this project is to investigate properties of a certain type of swarm intelligence commonly referred to as ant algorithms. We will study the use of an ant algorithm operating upon a dynamic problem domain, that is, a domain that changes as a function over time.

Specifically, we will discuss and use an ant-inspired graph-based general-purpose algorithm metaheuristic named Ant Colony Optimization as the basis of an implementation of a routing algorithm in a packageswitched point-to-point network (such as the Internet). Ant-inspired algorithms have the capability of finding short paths in graphs, and show an inherent adaptability that could be utilized to solve dynamic problems such as routing in a network.

Motivation

Swarm intelligence is an area of research that over the last decade has experienced a boom in interest. Inspired by the seemingly intelligent behavior of swarms of primitive animals, swarm intelligence has proven to be a promising field of research in many different areas.

A swarm of ants in the search for food shows the remarkable capability of finding shortest paths between a found food source and the anthill. Even though any single ant could be said to possess the capability of finding a short path from the anthill to a nearby food source, the probability of this occurring is very small, since an ant is not a very smart animal. The amazing thing is that when many ants cooperate on finding food, using pheromone trails as a simple indirect form of communication, the swarm of ants seems to be able to find a shortest path effectively. Another feature is their ability to adapt to a changing environment. If an obstacle is placed on the path from the food source back to the anthill, ants are capable of finding the shortest path around the obstacle - and possibly find food sources closer to the anthill.

The emergent intelligence that a swarm of ants seems to possess is enticing from the perspective of computer science, because of the possibility to simulate and potentially exploit this behavior to solve algorithmic problems.

By observing and modeling the processes that occur in natural ants when working in their natural domain, it is possible to use this as inspiration to create a 'colony' of artificial ants, working in an environment represented by a graph and potentially experience a similar emergent intelligence. In fact, researchers in the field of biology have developed good theories on how ants communicate as a group and attempts to adapt these theories to a simulated domain in a computer have verified that it is possible to obtain emergent intelligent behavior from colonies of artificial ants [Bonabeau et al., 1999].

Download

Project:
The report (in pdf) 1310 KB

Appendices (in pdf) 1417 KB

JavaDoc zipped (zipped) 388 KB

Java source code (zipped) 80 KB needs a little tweaking to function under another OS than windows due to hardcoded path delimiters.

Note: First project at ITU (spring 2002) in my second semester of the Internet and Software Technology program.
Relevant links:
Ant Colony Optimization
Ant colony optimization on Scholarpedia
Swarm Intelligence : From Natural to Artificial Systems

Subpages