Convergence Results for Ant Routing Algorithms via Stochastic Approximation and Optimization

dc.contributor.authorPurkayastha, Punyaslok
dc.contributor.authorBaras, John S.
dc.description.abstract``Ant algorithms'' have been proposed to solve a variety of problems arising in optimization and distributed control. They form a subset of the larger class of ``Swarm Intelligence'' algorithms. The central idea is that a "swarm" of relatively simple agents can interact through simple mechanisms and collectively solve complex problems. Instances that exemplify the above idea abound in nature. The abilities of ant colonies to collectively accomplish complex tasks have served as sources of inspiration for the design of ``Ant algorithms''. Examples of ``Ant algorithms'' are the set of ``Ant Routing'' algorithms that have been proposed for communication networks. We analyze in this paper Ant Routing Algorithms for packet-switched wireline networks. The algorithm retains most of the salient and attractive features of Ant Routing Algorithms. The scheme is a multiple path probabilistic routing scheme, that is fully adaptive and distributed. Using methods from adaptive algorithms and stochastic approximation, we show that the evolution of the link delay estimates can be closely tracked by a deterministic ODE system. A study of the equilibrium points of the ODE gives us the equilibrium behavior of the routing algorithm, in particular, the equilibrium routing probabilities, and mean delays in the links under equilibrium. We also show that the fixed-point equations that the equilibrium routing probabilities satisfy are actually the necessary and sufficient conditions of an appropriate optimization problem. Simulations supporting the analytical results are provided.en
dc.description.sponsorshipResearch supported by the U.S. Army Research Laboratory under the CTA C & N Consortium Coop. Agreement DAAD19-01-2-0011 and by the U.S. Army Research Office under MURI01 Grant No. DAAD19-01-1-0465.en
dc.format.extent812001 bytes
dc.relation.isAvailableAtInstitute for Systems Researchen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us
dc.subjectant routing algorithmsen
dc.subjectcommunication networksen
dc.subjectstochastic approximationen
dc.titleConvergence Results for Ant Routing Algorithms via Stochastic Approximation and Optimizationen
dc.typeTechnical Reporten


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
792.97 KB
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
1.81 KB
Item-specific license agreed upon to submission