NDLI: Convergence results for ant routing algorithms via stochastic approximation

Please wait, while we are loading the content...

Convergence results for ant routing algorithms via stochastic approximation

Content Provider	ACM Digital Library
Author	Purkayastha, Punyaslok Baras, John S.
Copyright Year	2013
Abstract	In this article, we provide convergence results for an Ant-based Routing Algorithm (ARA) 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 earlier by Bean and Costa [2005]. 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.
Starting Page	1
Ending Page	34
Page Count	34
File Format	PDF
ISSN	15564665
e-ISSN	15564703
DOI	10.1145/2451248.2451251
Volume Number	8
Issue Number	1
Journal	ACM Transactions on Autonomous and Adaptive Systems (TAAS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-04-19
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Ant routing algorithms Queuing networks Stochastic approximations and learning algorithms
Content Type	Text
Resource Type	Article
Subject	Control and Systems Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Convergence results for ant routing algorithms viastochastic approximation

Convergence results for ant routing algorithms via stochastic approximation and optimization

Convergence results for ant routing algorithms via stochastic approximation and optimization.

Approximate mean value analysis algorithms for queuing networks: existence, uniqueness, and convergence results

A short convergence proof for a class of ant colony optimization algorithms

Strong diffusion approximations for recursive stochastic algorithms

Stochastic approximation algorithms: Overview and recent trends

General convergence results for constrained and unconstrained stochastic approximations

An alternative proof for convergence of stochastic approximation algorithms

Convergence results for ant routing algorithms via stochastic approximation

Similar Documents

Convergence results for ant routing algorithms viastochastic approximation

Convergence results for ant routing algorithms via stochastic approximation and optimization

Convergence results for ant routing algorithms via stochastic approximation and optimization.

Approximate mean value analysis algorithms for queuing networks: existence, uniqueness, and convergence results

A short convergence proof for a class of ant colony optimization algorithms

Strong diffusion approximations for recursive stochastic algorithms

Stochastic approximation algorithms: Overview and recent trends

General convergence results for constrained and unconstrained stochastic approximations

An alternative proof for convergence of stochastic approximation algorithms

Convergence results for ant routing algorithms via stochastic approximation