An Active Solution to Adaptive Routing

"The effect of good routing is to increase throughput for the same value of average delay per packet under high offered load conditions and to decrease average delay per packet under low and moderate offered load conditions." (D. Bartsekas, R. Gallager, Data Networks)
Adaptive Routing algorithms attemp to change their routing decisions to reflect changes in topology and the current traffic.
Congestion is one of the main factors that prevent current networks from reaching an optimal throughput.
The problem is not so much in the algorithms of flow control, but rather in the net itself, which is not cooperative, so it is clear that Active Networks may provide a powerful tool to address this issue.
Our protocol is not intended to solve the entire problem, rather it just aims to provide a useful service to upper level protocols, through the use of Distributed Artificial Intelligence techniques.

The Project

The algorithm is based on previous studies about cooperative learning and artificial life; in particular the focus is on some aspects of the behaviour of ants in nature. Though very simple insects, ants are able to find optimal paths between the nest and the food source by just reacting to local stimuli; the global effectiveness arises from an environment-based communication (stigmergy) developed through evolution. They release a substance called pheromone as they follow a route and, since they are also influenced by the presence of pheromone in the choice of a new path, the overall effect is that routes that were chosen by a great number of ants will become more and more attractive to subsequent ants, whereas unpromising paths will be discarded. In other words this is reinforcement learning or, in other words, positive feedback.

Basically, if the ants take into account the appropriate parameters when releasing their pheromone, the result is a routing whose metric is congestion, but the approach is quite different from the traditional one:

All of these features make ants particularly suitable to be implemented in an active environment.

Further developments

Future experiments will be focused on the effects of using new metrics for the choice of the best path. Analysis will not be limited to dynamic metrics, but will also cover static ones and in particular we would like to test the performance resulting from a combination of both kinds of metrics.

In a wider range of time we would also like to examine the possibilities deriving by a multipath strategy routing, which entails a somehow more
complex class of issues.

In order to make it easier to carry on with network experiments, it is currently on development a graphical tool, to set up and monitor a network of active nodes, with the possibility of modifying the behavior of the nodes on the fly.

People

Staff

References

G. Di Caro, M. Dorigo, Mobile Agents for Adaptive Routing, Proceedings of the 31st Hawaii International Conference on System, IEEE Computer Society Press, Los Alamitos, CA, 74-83. Also available as Tec.Rep.IRIDIA/97-20, Université Libre de Bruxelles, Belgium, 1998. (gzipped postscript file)

S. N. Willmott, B. Faltings, Active Organisations for Routing, Proceedings of the First International Working Conference on Active Networks, pages 262-273. Editor S. Covaci. Springer Verlag, Lecture Notes in Computer Science Series, number 1653. July 1999. (postcript file)

Publications

G. Di Fatta, S. Gaglio, G. Lo Re, M. Ortolani, Artificial Ants for Active Routing, IAS6, the 6th International Conference on Intelligent Autonomous Systems. Venice, July 2000. (gzipped postscript file)