Convergence of ant routing algorithms -- Results for a simple parallel network and perspectives
Convergence of ant routing algorithms -- Results for a simple parallel network and perspectives
Files
Publication or External Link
Date
2003
Authors
Yoo, Joon-Hyuk
La, Richard J.
Makowski, Armand M.
Advisor
Citation
DRUM DOI
Abstract
We study the convergence property of a family of distributed routing algorithms based on the ant colony metaphor, namely the uniform and regular ant routing algorithms discussed by Subramanian et al. For a simple two-node network, we show that the probabilistic routing tables converge in distribution (resp. in the a.s. sense) for the uniform (resp. regular) case. To the best of the authors' knowledge, the results given here appear to be the first formal convergence results for ant routing algorithms. Although they hold only for a very limited class of networks, their analysis already provide some useful lessons for extending the results to more complicated networks. We also discuss some of implementation issues that naturally arise from the convergence analysis.