TY - JOUR

T1 - Analysis on a mobile agent-based algorithm for network routing and management

AU - Sum, John

AU - Shen, Hong

AU - Leung, Chi Sing

AU - Young, G.

N1 - Funding Information:
This work was partially supported by the Competitive Earmarked Grant Research Grant (Project: 9040603), the Research Grants Council, and the Hong Kong Special Administration Region.

PY - 2003/3

Y1 - 2003/3

N2 - Ant routing is a method for network routing in the agent technology. Although its effectiveness and efficiency have been demonstrated and reported in the literature, its properties have not yet been well studied. This paper presents some preliminary analysis on an ant algorithm in regard to its population growing property and jumping behavior. For synchronous networks, three main results are shown. First, the expected number of agents in a node is shown to be no more than (1 + maxi, {|Ωi|})km, where |Ωi| is the number of neighboring hosts of the ith host, k is the number of agents generated per request, and m is the average number of requests. Second, the expected number of jumps of an agent is shown to be no larger than (1 + maxi{|Ωi|}). Third, it is shown that for all p ≤ (1 + maxi{|Ωi|}) km, the probability of the number of agents in a node exceeding p is not greater than fp∞P(x)dx, where P(x) is a normal distribution function with mean and variance given by mean = (1 + maxi{|Ωi|})km, Var. = 2km(1 + maxi{|Ωi|}) + (km)2(1+maxi{|Ωi|})2/(1+2 maxi{|Ωi|}). The first two results are also valid for the case when the network is operated in asynchronous mode. All these results conclude that as long as the value maxi{|Ωi|} is known, the practitioner is able to design the algorithm parameters, such as the number of agents being created for each request, k, and the maximum allowable number of jumps of an agent, in order to meet the network constraint.

AB - Ant routing is a method for network routing in the agent technology. Although its effectiveness and efficiency have been demonstrated and reported in the literature, its properties have not yet been well studied. This paper presents some preliminary analysis on an ant algorithm in regard to its population growing property and jumping behavior. For synchronous networks, three main results are shown. First, the expected number of agents in a node is shown to be no more than (1 + maxi, {|Ωi|})km, where |Ωi| is the number of neighboring hosts of the ith host, k is the number of agents generated per request, and m is the average number of requests. Second, the expected number of jumps of an agent is shown to be no larger than (1 + maxi{|Ωi|}). Third, it is shown that for all p ≤ (1 + maxi{|Ωi|}) km, the probability of the number of agents in a node exceeding p is not greater than fp∞P(x)dx, where P(x) is a normal distribution function with mean and variance given by mean = (1 + maxi{|Ωi|})km, Var. = 2km(1 + maxi{|Ωi|}) + (km)2(1+maxi{|Ωi|})2/(1+2 maxi{|Ωi|}). The first two results are also valid for the case when the network is operated in asynchronous mode. All these results conclude that as long as the value maxi{|Ωi|} is known, the practitioner is able to design the algorithm parameters, such as the number of agents being created for each request, k, and the maximum allowable number of jumps of an agent, in order to meet the network constraint.

KW - Ant algorithm

KW - Mobile agents routing algorithms

KW - Networking routing

UR - http://www.scopus.com/inward/record.url?scp=0038300191&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2003.1189578

DO - 10.1109/TPDS.2003.1189578

M3 - Article

AN - SCOPUS:0038300191

SN - 1045-9219

VL - 14

SP - 193

EP - 200

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 3

ER -