|
|
1 Overview
1.1 Swarm
The swarm intelligence model is gaining success in the research community as a
meta-heuristic solution using insect societies to solve a variety of combinatorial
optimization problems in wide fields ranging from management science to computer science.
Swarm intelligence is defined as "any attempt to design algorithms or distributed problem
solving devices inspired by collective behavior of social insect colonies and other animal
society". "Swarm" is a decentralized and autonomous multi-agent system, which consists of
myriad of simple and cooperative agents which behave with simple rules and use local
information in a common environment to achieve global goals. The swarm intelligence lies on
the interactions among agents and between agents and the environment.
1.2 Ant Colony Routing
Derived from the forage model of real ant colonies, ant routing algorithms apply swarm
intelligence to solve network routing problems based on the following principles:
- Cooperative behavior: To perform various day-to-day activities such as brooding and
foraging, ants exhibit a cooperative behavior using as main medium of communication a
path built up through an artificial chemical substance called "pheromone".
- Stigmergy communication: When ants forage, they randomly wander the forest or jungle
floor and lay a trail for nest-mates to lead to a source of food. Many individual ants
may discover different routes to the same food but the shortest path that leads to it will
have the strongest concentration of pheromone, a chemical indicator laid down by the ants.
- Autocatalytic behavior: Whenever an ant leaves its nest to search for food, it lays a
trail of pheromone on its path. The number of ants that has traveled on the path
determines the strength of the pheromone trail. The ant, which travels the shortest path,
reinforces the path with more pheromone which aids others to follow. After an initial
randomization the ants finally arrive at the shortest path.
The basic mechanisms used in ant colony routing are:
- Instead of using a single next-hop value, routing tables include multiple entries
corresponding to several next-hop choices for a destination, with each entry associated
with a probability of choosing this hop as the next hop along the shortest path to the
destination.
- These next-hop values are initially equal and will be updated according to how many ant
packets pass by.
- Given a specified source node and destination node, the source node sends out ant packets
based on the entries on its own routing table. Those ants will explore the routes in the
network. They can remember the hops they have passed.
- When an ant packet reaches the destination node, the ant packet will return to the source
node along the same route. Along the way back to the destination node, the ant packet will
change the routing table for every node it passes by.
The rules of updating the routing tables are:
increase the probability of the hop it comes from while decrease the probabilities of
other candidates.
- This process can be compared with the real ant foragers where changing the routing table
corresponds to laying down some virtual pheromone on the way which thus affects the route
of the subsequent ant packets.
- Since the route with higher possibility is always favored, more ants will pick up that
route, and further increase its use and in turn attract more ants. With this positive
feed-back loop, we can expect a best path will be quickly identified.
- Moreover, with the changing of network load, when a new best solution is found, we also
expect that it could be identified and enforced by ant packets too. So ant routing is
more dynamic, robust and scalable.
1.3 Related Work
StarLogo[7]
StarLogo is a programmable modeling environment for exploring the workings of decentralized
systems -- systems that are organized without an organizer, coordinated without a
coordinator. StarLogo provides the ability to program a system that is composed of
thousands of graphic paths and turtles. Turtles are the agents that run in the environment
composed by paths. Both turtles and paths can execute commands and procedures.
Turtles and paths can interact with each other, for example a turtle can move and execute
some commands or procedures to change the states of the paths it pass by. StarLogo provides
a very simple language to describe the behaviors of turtle and paths. It also provides a
run-time environment to run thousands of turtles and paths in parallel. In additionally,
StarLogo also provide a observer command center to setup and influence the system.
All these functionalities are provided with a user-friendly graphic interface. So StarLogo
is well-suited for the simulation of artificial life.
SantaFe-Swarm[8]
The Swarm simulation development kit distributed by Santa Fe Institute is a toolkit for
Java. It provides a library to support swarm primitives and many useful analysis tools to
facilitate the analysis of the simulated systems. The popular Java program and support of
analysis interfaces will be its major advantages. The swarm simulation development kit has
been recently used in the Ecosim project [11] and shown to be an effective tool to simulate
artificial life.
Ant Routing System[12]
The Ant Routing System (ARS) is a java-based library of ant algorithms based on the Ant
Colony Optimization metaheuristic developed by students of the IT University of Copenhagen.
These libraries are used in an event-driven simulator to investigate if ant colony routing
is able to increase throughput while avoiding packet losses in a heavily loaded network.
1.4 Objective
The work done recently on ant colony routing [3] [4] has shown that the ant routing
algorithms are more efficient, robust and scalable than many traditional routing algorithms.
This project builds upon this work extending the forage model to simulate ant colony routing
capabilities such as finding the shortest path between a source and a destination of an IP
network, finding backup paths for a path that has experienced failure,etc...
2 Milestones and Evaluation
The project will follow these steps:
- Investigate the three kits:
- Swarm [11]
- StarLogo [7] and the Ant Routing System [12] to evaluate which of these software
is better suited for IP routing.
- Simulate simple ant routing algorithms using the selected package.
The criteria of success for this project are
- Successfully simulate ant routing in the three kits.
- Evaluate the amount of time to learn each kit and the effort it takes to simulate the
ant routing in each kit.
3 Deliverables
The following deliveries are expected from this project
- working and documented programs for:
- ant colony routing,
- visualization of the ant colony routing process communication and
- tracefile of ant movement to be used for performance evaluation.
- a report on the project.
References
[1] E. Bonabeau, M. Dorigo, G. Theraulaz,
"Swarm Intelligence: from Natural to Artificial Systems",
Santa Fe Institute, Oxford University Press, 1999
[2] D. Evans, "Programming the Swarm".
[3] G. Di Caro, "AntNet: Distributed Stigmergetic Control for Communications Networks",
Journal of Artificial Intelligence Research 9 (1998): 317-365
[4] G. Di Caro, "Two Ant Colony Algorithms for Best-effort Routing in Datagram Networks"
[5] R. Schoonderwoerd, O. Holland, J. Bruten and L. Rothkrantz,
"Ant-based load balancing in telecommunications networks"
[6] T. White, "Routing With Swarm Intelligence", SCE Technical Report, SCE-97-15
[7] StarLogo website, http://www.media.mit.edu/starlogo
[8] Swarm website of Santa Fe Institute, http://www.swarm.org/
[9] D. Coore, "Botanical Computing: A Developmental Approach to Generating Interconnect
Topologies on an Amorphous Computer",
Ph.D. thesis, MIT department of Electrical Engineering and Computer Science, Dec.1998
[10] H. Abelson, et.al., "Amorphous Computing", Communication of the ACM, May 2000
[11] Ecosim Project, http://www.cs.sun.ac.za/~ecosim/
[12] Ant Routing System, http://officehelp.gone.dk/ITCProjeketr/AntRoutingSystem
|
|