Show simple item record

dc.contributor.advisorBaras, John
dc.contributor.authorPurkayastha, Punyaslok
dc.contributor.authorBaras, John
dc.date.accessioned2009-10-22T14:40:00Z
dc.date.available2009-10-22T14:40:00Z
dc.date.issued2009-10
dc.identifier.urihttp://hdl.handle.net/1903/9692
dc.description.abstractIn this paper, we provide convergence results for an Ant-Based Routing (ARA) Algorithm for wireline, packet-switched communication networks, that are acyclic. Such algorithms are inspired by the foraging behavior of ants in nature. We consider an ARA algorithm proposed by Bean and Costa. The algorithm has the virtues of being adaptive and distributed, and can provide a multipath routing solution. We consider a scenario where there are multiple incoming data traffic streams that are to be routed to their respective destinations via the network. Ant packets, which are nothing but probe packets, are introduced to estimate the path delays in the network. The node routing tables, which consist of routing probabilities for the outgoing links, are updated based on these delay estimates. In contrast to the available analytical studies in the literature, the link delays in our model are stochastic, time-varying, and dependent on the link traffic. The evolution of the delay estimates and the routing probabilities are described by a set of stochastic iterative equations. In doing so, we take into account the distributed and asynchronous nature of the algorithm operation. Using methods from the theory of stochastic approximations, we show that the evolution of the delay estimates can be closely tracked by a deterministic ODE (Ordinary Differential Equation) system, when the step-size of the delay estimation scheme is small. We study the equilibrium behavior of the ODE system in order to obtain the equilibrium behavior of the routing algorithm. We also explore properties of the equilibrium routing probabilities, and provide illustrative simulation results.en
dc.description.sponsorshipPrepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U. S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon.en
dc.format.extent752834 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen
dc.relation.ispartofseriesTR_2009-17en
dc.subjectcommunication networksen
dc.subjectant routing algorithmsen
dc.subjectstochastic approximations and learning algorithmsen
dc.subjectqueuing networksen
dc.titleConvergence Results for Ant Routing Algorithms via Stochastic Approximationsen
dc.typeTechnical Reporten
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


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record